Heuristic solution improvement using optimization

Heuristics continue to be an important tool for generating good feasible solutions for both integer programs and for problems that may be ill-structured and/or nonlinear. Such ill-structured problems may in fact not even be... [ view full abstract ]

Heuristics continue to be an important tool for generating good feasible solutions for both integer programs and for problems that may be ill-structured and/or nonlinear. Such ill-structured problems may in fact not even be able to be formulated as formal optimization problems. However, when some variables are fixed at particular values, a “reduced” problem may be solvable using standard approaches. For example, the original problem may be highly nonlinear, nonconvex, and/or of such a size that a formal solution algorithm may not exist or at best takes a large amount of CPU time and resources (and may not guarantee a global optimal solution).
In this paper, we restrict our inquiry to classes of hard integer linear programming problems. “Hard” is defined as a problem that cannot be solved to optimality in 1 hour of CPU time with the use of “off the shelf” optimization codes (GUROBI, CPLEX).
We consider the generalized assignment problem (GAP) initially. The GAP may be described as finding a minimum-cost assignment of tasks (m) to agents(n) such that each task is assigned to exactly one agent and such that each agent’s resource capacity is not violated.
Hard GAP problems often have the property that integer feasible solutions are relatively easy to generate with some ad hoc procedure and/or integer feasible solutions are generated as a by-product in the branch-and-bound search. We capitalize on this property by collecting the feasible solutions generated and keep them in the order of descending objective value. Suppose we have a collection of feasible solutions and select a number (say 4) of those solutions with the smallest objective values. Identify those variables in common equal to 1 in each of the four solutions. Let L be the set containing these variables. If |m| - |L| is sufficiently small, we have a “reduced size” GAP, where |L| variables are locked at the value 1, that can probably be solved to optimality in a short amount of CPU time. The resulting solution may be an improvement on the best known feasible solution or it may not. If it is an improvement, we add this to the list of feasible integer solutions and continue the branch-and-bound procedure. In either case we may add a cut ∑(all xij in L) xij <= |L|-1. If the “reduced size” GAP cannot be solved to optimality within say 5 minutes, the cut is not valid. However, if an improved feasible solution is found, it can be added to the ordered solution list. We then return to the branch and bound search over the original problem. Computational results are included.