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

Description

We present a new extended formulation of the Generalized Assignment Problem (GAP), based on a disaggregation of the traditional formulation. The proposed disaggregated formulation comprises O(mn2)O(mn^2)O(mn2) variables and constraints, where mmm denotes the number of agents and nnn the number of jobs, compared to the O(mn)O(mn)O(mn) variables and constraints in the traditional formulation. The extended formulation is stronger, as its linear programming relaxation yields tighter lower bounds than the traditional approach. Furthermore, it facilitates the extension of well-known inequalities—such as the Cover and (1,k)(1, k)(1,k)-Configuration inequalities—making them more broadly applicable. We show that these generalized inequalities, when applied to the disaggregated formulation, produce tighter bounds than when the original inequalities are applied to the traditional formulation. In addition, we introduce two new classes of inequalities specific to the disaggregated formulation. The first is the Bar-and-Handle (1,p^k)(1, \hat{p}k)(1,p^​k) inequality, which under certain conditions defines a facet of the GAP polytope. The second is the 2-Agent Cardinality Matching Inequality, which involves interactions between two agents. We demonstrate that, in the uncapacitated version of GAP—where each agent can process all jobs—this inequality defines a facet of the associated polytope. Moreover, through a lifting procedure, it can be strengthened to yield a more powerful inequality applicable to the capacitated case. When m=2m = 2m=2, we further show that this inequality, together with trivial facets, fully characterizes the polytope of the uncapacitated GAP. Finally, computational experiments indicate that the extended formulation significantly improves solution efficiency by reducing the number of subproblems explored in the branch-and-bound tree, thereby achieving substantial computational gains.

Publication Date

1-1-2019

DOI

10.1016/j.dam.2019.08.015

Publisher

Elsevier B.V.

Keywords

Generalized assignment, Integer polytope, Integer programming, Valid inequalities

This document is currently not available here.

Share

COinS