Content area
Full Text
Algorithms and computer-based tools for analyzing infeasible linear and nonlinear programs have been developed in recent years, but few such tools exist for infeasible mixed-integer or integer linear programs. One approach that has proven especially useful for infeasible linear programs is the isolation of an Irreducible Infeasible Set of constraints (HS), a subset of the constraints defining the overall linear program that is itself infeasible, but for which any proper subset is feasible. Isolating an HS from the larger model speeds the diagnosis and repair of the model by focussing the analytic effort. This paper describes and tests algorithms for finding small infeasible sets in infeasible mixed-integer and integer linear programs; where possible these small sets are MSs.
Subject classifications: Optimization
Other key words: Mixed-integer and integer linear programming, infeasibility
IVI ixed-integer and integer linear programs (here collectively referred to as MILPs) are much harder to solve than ordinary linear programs (LPs) because of the inherent combinatorial nature of the solution approaches necessitated by the integer variables. Infeasible MILPs are even more difficult to analyze because they usually require numerous solutions of variations of the original model. In addition, when a branch-and-bound solution procedure finds the original model infeasible, little useful information (such as constraint sensitivity in linear programs) is initially available to guide the analysis of the infeasibility. Some form of automated assistance in analyzing infeasible MILPs is needed, especially as models grow in size in step with increases in computing power.
Few useful tools are currently available. Savelsbergh'171 describes a bound-tightening presolve procedure for MILPs (implemented in the MINTO solver'151) that may detect infeasibility as a side effect of the reformulation. Backtracking the complete set of reformulation operations may then isolate a set of constraints and integer restrictions that cause the infeasibility. However, there is no guarantee that the presolver will detect infeasibility, or that the backtrack of the reformulation operations will provide any useful information. Greenberg also uses related bound-tightening methods for dealing with binary variables in the reduce command of his ANALYZE software.1101
On the other hand, effective methods for assisting in the analysis of infeasible linear and nonlinear programs have been developed in recent years (e.g., [2-7]). These new methods concentrate on isolating an Irreducible Infeasible Subset of...