In this paper we will proof that rather tight upper bounds can be given for the number of non-unique assignments that are achieved after solving the linear programming relaxation of some types of mixed integer linear assignment problems. Since in these cases the number of splitted assignments is small a heuristic can be used to reach a practically good and feasible assignment. Moreover the type of proof can be exploited for related problems to investigate whether a linear programming relaxation will yield mainly integer assignments.
Key words: mixed integer linear programming, assignment problems, location allocation problems, distribution problems.

Name | Memorandum COSOR |
---|

Volume | 8220 |
---|

ISSN (Print) | 0926-4493 |
---|