טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZarivach Igor
SubjectThe Cruncher: A solver for Large-Scale MIP Problems
DepartmentDepartment of Computer Science
Supervisors Professor Emeritus Shlomo Moran
Dr. Yossi Shiloach


Abstract

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. This work presents a heuristic for this problem, which uses 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 deliberately fixing integer variables to their values in the best feasible solution found so far (the incumbent). Unlike previous solvers which use similar strategies, our algorithm may decide in each iteration to apply a time bounded variant of either an exact solver (Branch and Cut) or a heuristic one (the solution polishing algorithm).

The number K of variables whose values are fixed in each iteration is determined by the outcomes of previous iterations. Once K is given, we study two strategies for choosing K fixed variables: One selects these variables uniformly at random from all integer variables. The second is a knowledge based strategy, which uses a partition

of the integer variables based on a modeling suggested by the problem modeler.
For example, in a student assignment problem, we need to assign students to classes. The binary variable Assigni,j models the decision to assign student i to a class j. By fixing the set of variables with a given class index, we fix the assignment to this class, while other students can change their classes. So rather than selecting uniformly at random the variables Assigni,j to fix, we select uniformly at random some indices j, and fix all the variables referring to students in the selected classes. Since many constraints in this problem involve only variables with the same class attribute, this approach is likely to substantially reduce the resulted sub-MIP size.

We tested these methods computationally on practical large MIP problems by using the commercial software CPLEX as a black-box MIP solver. For some instances, like the student assignment problem, both methods performed consistently better than the state of the art commercial heuristic method, the solution polishing algorithm, and the informed strategy performed best. On other instances, our heuristic, and in particular the informed cruncher, were less successful. Possible reasons for these differences are discussed.