A new extended formulation of the generalized assignment problem and some associated valid inequalities

Abstract

We present a new extended formulation of the Generalized Assignment Problem (GAP), that is a disaggregation of the traditional formulation. The disaggregated formulation consists of O( mn2) variables and constraints, where m denotes the number of agents and n the number of jobs. In contrast, the traditional formulation consists of O(mn) variables and constraints. The extended formulation is stronger than the traditional formulation, as its linear programming relaxation provides tighter lower bounds. Furthermore, this new formulation provides additional opportunities to generalize the well-known Cover and (1, k)-Configuration inequalities to make them far more ubiquitous. In fact, we show that the generalizations of both these inequalities when added to the disaggregated formulation provided tighter bounds than when the original Cover and (1, k)-Configuration inequalities are added to the traditional formulation. We introduce two classes of inequalities involving multiple agents that are specific to the disaggregated formulation. One class of inequalities is called the Bar-and-Handle (1, pˆk) Inequality, which under certain restrictive conditions is a facet of the polytope defined by feasible solutions of GAP. The other important class of inequality is the 2-Agent Cardinality Matching Inequality involving two agents. Given the un-capacitated version of GAP in which each agent can process all jobs, we first show this inequality to be a facet of the polytope defined by the un-capacitated GAP. We then show how this inequality can be strengthened easily by lifting it to become a strong inequality for GAP. We also show that when m=2, this inequality, along with trivial facets completely describe the polytope associated with the un-capacitated version of GAP. Finally, through computational testing we demonstrate that by substantially reducing the number of sub-problems visited in the branch-and-bound tree, our extended formulation achieves significant computation gains. © 2019 Elsevier B.V.