Abstract
In this paper we will prove 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.
| Original language | English |
|---|---|
| Pages (from-to) | 47-52 |
| Number of pages | 6 |
| Journal | Operations Research Letters |
| Volume | 2 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1983 |