Software
MINTO  Mixed INTeger Optimizer
MINTO is a software system that solves mixedinteger linear programs by a
branchandbound algorithm with linear programming relaxations. It also
provides automatic constraint classification, preprocessing, primal
heuristics and constraint generation. Moreover, the user can enrich the
basic algorithm by providing a variety of specialized application routines
that can customize MINTO to achieve maximum efficiency for a problem class.
The heart of MINTO is a linear programming based branchandbound algorithm.
It can be implemented on top of any LPsolver that provides capabilities to
solve and modify linear programs and interpret their solutions. The current
version can either be built on top of the CPLEX callable library,
version 2.0 and up, or on top of the Optimization Subroutine Library (OSL),
version 1.2.
To be as effective and efficient as possible when used as a general purpose
mixedinteger optimizer, MINTO attempts to:
* improve the formulation by preprocessing and probing;
* construct feasible solutions;
* generate strong valid inequalities;
* perform variable fixing based on reduced prices;
* control the size of the linear programs by managing active constraints.
To be as flexible and powerful as possible when used to build a special
purpose mixedinteger optimizer, MINTO provides various mechanisms for
incorporating problem specific knowledge.
MINTO Availability
MINTO is available for free. MINTO is maintained by a group of enthusiastic
users and contributors. Go to Minto at CORAL
Relevant publications
A. Atamturk, G.L. Nemhauser, M.W.P. Savelsbergh (2000).
Conflict Graphs in Integer Programming.
European Journal of Operations Research 121, 4055.
Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (1999).
Cover Inequalities for 01 Linear
Programs: Complexity. INFORMS J. on Computing 11,
117123.
J. Linderoth, M.W.P. Savelsbergh (1999).
A Computational Study of Search Strategies for Mixed
Integer Programming.
INFORMS J. on Computing 11, 173187.
Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (1999).
Lifted Flow Covers for Mixed 01 Integer
Programs. Mathematical Programming 85, 439468.
Gu, G.L., Nemhauser, and M.W.P. Savelsbergh (1998).
Cover Inequalities for 01 Linear
Programs: Computation. INFORMS Journal on Computing
10, 427437.
G.L. Nemhauser, M.W.P. Savelsbergh, G.S. Sigismondi (1994). MINTO, a Mixed INTeger Optimizer. Oper. Res. Letters
15, 4758.
M.W.P. Savelsbergh (1994). Preprocessing and Probing
for Mixed Integer Programming Problems. ORSA J. on Computing 6,
445454.
M.W.P. Savelsbergh, G.L. Nemhauser (1998). Functional
description of MINTO, a Mixed INTeger Optimizer (Version 3.0). Report
COC9103D, Georgia Institute of Technology.
M.W.P. Savelsbergh, G.L. Nemhauser (1995). A MINTO
short course. Report COC95xx, Georgia Institute of Technology.
