The Taub Faculty of Computer Science Events and Talks

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of a paramount importance for practical applications. Unfortunately, in most practical large scale problems, a general-purpose MIP solver may prove not effective even after a clever tuning. In the present paper we investigate the use of a generic MIP solver as a black box tool to produce a sequence of reasonably good feasible solutions quickly. The procedure is based on solving a series of sub-problems obtained by fixing integer variables to their values in the best feasible solution found so far, the incumbent. The number of fixed variables k is controlled by a simple framework. We investigate a random choice of the set of fixed variables versus a knowledge based strategy for choosing that set, based on a modeling suggested by the problem modeler. The former strategy selects the k-element subset of integer variables uniformly, while the latter uses the model metadata, supplied as a set of attributes describing the variable roles in the model. By fixing all the variables which have the same value in the chosen attribute, we preserve the hopefully good structure of the incumbent. The new solution strategy is designed to improve the heuristic behaviour of the MIP solver at hand. The result is a completely general-purpose solver producing high-quality MIP solutions at early stages of the computation. The method is tested computationally on two practical large MIP problems by using the commercial software CPLEX as the black-box MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method performs consistently better than the state of the art heuristic method, the CPLEX polishing.