Technical Report MSC-2017-29

TR#:MSC-2017-29
Class:MSC
Title: The Cruncher: A solver for large-scale MIP problems
Authors: Igor Zarivach
Supervisors: Shlomo Moran and Yossi Shiloach
PDFCurrently accessibly only within the Technion network
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 Assign(i,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 Assign(i,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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2017/MSC/MSC-2017-29), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion
admin