Generalized cover facet inequalities for the generalized assignment problem. (English) Zbl 1184.90087
Summary: The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.
Keywords:
generalized assignment problem; Knapsack problem; special ordered set; facet inequalities; generalized coverReferences:
| [1] | DOI: 10.1287/mnsc.40.7.868 · Zbl 0816.90096 · doi:10.1287/mnsc.40.7.868 |
| [2] | DOI: 10.1287/opre.24.4.742 · Zbl 0356.90028 · doi:10.1287/opre.24.4.742 |
| [3] | DOI: 10.1016/S0377-2217(97)00054-4 · Zbl 0951.90008 · doi:10.1016/S0377-2217(97)00054-4 |
| [4] | DOI: 10.1287/opre.31.5.803 · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [5] | DOI: 10.1007/PL00011392 · doi:10.1007/PL00011392 |
| [6] | DOI: 10.1016/S0167-6377(01)00086-4 · Zbl 0981.90050 · doi:10.1016/S0167-6377(01)00086-4 |
| [7] | Garey MR, Computers and intractability: A guide to the theory of NP-completeness (1979) · Zbl 0411.68039 |
| [8] | DOI: 10.1007/BF01585726 · Zbl 0701.90065 · doi:10.1007/BF01585726 |
| [9] | DOI: 10.1007/BF01585725 · Zbl 0694.90071 · doi:10.1007/BF01585725 |
| [10] | DOI: 10.1287/opre.37.4.658 · Zbl 0674.90068 · doi:10.1287/opre.37.4.658 |
| [11] | DOI: 10.1287/mnsc.32.9.1095 · Zbl 0626.90036 · doi:10.1287/mnsc.32.9.1095 |
| [12] | DOI: 10.1287/opre.33.4.803 · Zbl 0569.90056 · doi:10.1287/opre.33.4.803 |
| [13] | Martello S, Knapsack Problems (1990) |
| [14] | DOI: 10.1287/ijoc.15.3.249.16075 · Zbl 1238.90090 · doi:10.1287/ijoc.15.3.249.16075 |
| [15] | DOI: 10.1007/BF01580121 · Zbl 0272.90041 · doi:10.1007/BF01580121 |
| [16] | DOI: 10.1287/opre.23.4.833 · Zbl 0311.90053 · doi:10.1287/opre.23.4.833 |
| [17] | DOI: 10.1287/mnsc.44.12.S271 · Zbl 0989.90536 · doi:10.1287/mnsc.44.12.S271 |
| [18] | DOI: 10.1016/S0167-5060(08)70751-9 · doi:10.1016/S0167-5060(08)70751-9 |
| [19] | DOI: 10.1007/BF01580430 · Zbl 0308.90028 · doi:10.1007/BF01580430 |
| [20] | DOI: 10.1287/mnsc.24.3.345 · Zbl 0378.90066 · doi:10.1287/mnsc.24.3.345 |
| [21] | DOI: 10.1287/opre.45.6.831 · Zbl 0895.90161 · doi:10.1287/opre.45.6.831 |
| [22] | DOI: 10.1007/BF01580441 · Zbl 0314.90063 · doi:10.1007/BF01580441 |
| [23] | DOI: 10.1287/opre.24.2.367 · Zbl 0339.90036 · doi:10.1287/opre.24.2.367 |
| [24] | DOI: 10.1287/moor.2.1.66 · Zbl 0402.90066 · doi:10.1287/moor.2.1.66 |
| [25] | DOI: 10.1007/BF01609032 · Zbl 0428.90042 · doi:10.1007/BF01609032 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
