Software
MINTO - Mixed INTeger Optimizer
MINTO is a software system that solves mixed-integer linear programs by a
branch-and-bound 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 branch-and-bound algorithm.
It can be implemented on top of any LP-solver 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
mixed-integer 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 mixed-integer 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, 40-55.
Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (1999).
Cover Inequalities for 0-1 Linear
Programs: Complexity. INFORMS J. on Computing 11,
117-123.
J. Linderoth, M.W.P. Savelsbergh (1999).
A Computational Study of Search Strategies for Mixed
Integer Programming.
INFORMS J. on Computing 11, 173-187.
Z. Gu, G.L. Nemhauser, and M.W.P. Savelsbergh (1999).
Lifted Flow Covers for Mixed 0-1 Integer
Programs. Mathematical Programming 85, 439-468.
Gu, G.L., Nemhauser, and M.W.P. Savelsbergh (1998).
Cover Inequalities for 0-1 Linear
Programs: Computation. INFORMS Journal on Computing
10, 427-437.
G.L. Nemhauser, M.W.P. Savelsbergh, G.S. Sigismondi (1994). MINTO, a Mixed INTeger Optimizer. Oper. Res. Letters
15, 47-58.
M.W.P. Savelsbergh (1994). Preprocessing and Probing
for Mixed Integer Programming Problems. ORSA J. on Computing 6,
445-454.
M.W.P. Savelsbergh, G.L. Nemhauser (1998). Functional
description of MINTO, a Mixed INTeger Optimizer (Version 3.0). Report
COC-91-03D, Georgia Institute of Technology.
M.W.P. Savelsbergh, G.L. Nemhauser (1995). A MINTO
short course. Report COC-95-xx, Georgia Institute of Technology.
|
