Solving Hard Generalized Assignment Problems with Solution Value Contingent Cuts

We define hard generalized assignment problems (GAP) to be those that take more than 1 hour of CPU time to prove optimality. The GAP may be described as finding a minimum-cost assignment of tasks to agents such that each task... [ view full abstract ]

We define hard generalized assignment problems (GAP) to be those that take more than 1 hour of CPU time to prove optimality. The GAP may be described as finding a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent’s resource capacity is not violated. Tremendous strides have been made in the capability of “off the shelf” software, such as GUROBI and CPLEX, to solve general integer linear programs (ILP). However, some classes of ILPs remain difficult to solve to optimality in a reasonable amount of time. Certain instances of the GAP exhibit this behavior. In this paper we explore various approaches to improving the efficacy of “off the shelf” optimizers in solving hard generalized assignment problems. We introduce some novel cuts (and methods for deriving said cuts) that are applied with an “off the shelf” solver through the use of CALLBACK functions. Computational results are presented.