Title: Basic Heuristic Semantic Techniques for Structured MIPS

Marcus Poggi (joint work with Eduardo Uchoa, Lorenza Moreno and Marcelo Reis)

Abstract:  

Despite the late developments of MIP solvers, there are still many difficulties in obtaining good solutions, or even feasible solutions, for several classes of problems. This is true specially when the computing time available is limited. Recent research by several authors, including Fischetti and Lodi, consider only the information in the MIP definition.

This work departs from semantic information from the original problem definition to analyze a few basic techniques that are commonly used to tackle large problems with several classes of constraints using state of the art MIP solvers. We try to show when they are likely to work and when pitfalls may happen. 

One first technique is the split/assemble which consists of breaking the problem into pieces, solving them, and then building the global solution. This is usually effective for planning problems over a time horizon, and has its success attached to how strong is the correlation between consecutive periods and how are they managed in the assemble phase.

The aggregate/segregate technique amounts to devise simpler or smaller problems that do not consider all the elements present in the original problem, solve it and use its (optimal) solution as reference for finding good solutions. When feasible solutions cannot be found, the segregated model may generate constraints for the upper level aggregate one. 

Hierarchic decomposition can be seen as a dual to the aggregate/segregate technique. While there is a vertical aspect in using aggregate/segregate, here a horizontal aspect prevails. The idea is to identify groups of decision variables and rank their importance to the objective function (or problem feasibility). At first, a problem considering only the most important group of variables is detached and solved. Following their importance, the next groups of variables are treated in the same way. Constraints can be naturally fed back and, if needed the global problem may be tried. This technique has its resemblance with Benders decomposition, but it differs by not requiring to have strictly independent problems.

Finally, the objective function/constraint sequencing is a technique recommended by commercial solverīs developers. It amounts to use a sequence of objective functions, this leads to reach good solutions much faster (or even reaching better solutions) than by starting up with the original objective function. This is naturally extended to constraints that may be added to the MIP in sequence, reaching a similar effect. 

Examples and computational experiences for all techniques are presented.