M.Sc Student | Zarivach Igor |
---|---|

Subject | The Cruncher: A solver for Large-Scale MIP Problems |

Department | Department of Computer Science |

Supervisors | Professor Emeritus Shlomo Moran |

Dr. Yossi Shiloach |

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 *Assign _{i,j}* models the decision to
assign student

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.