There are two algorithmic issues in optimization that are often overlooked because of the natural tendency to focus on on algorithms for finding an optimal solution to a feasible optimization problem. The first issue is to determine whether or not an optimization problem is feasible and if possible find a feasible solution. When a problem is found to be infeasible, the most common cause is an error in the problem formulation. Analysis of the infeasible problem can sometimes help to pinpoint specific constraints that make the problem infeasible. Much of John Chinneck's research has focused on these two issues. This book is a research monograph that summarizes recent progress in the area.
The first part of the book deals with the feasibility problem. A chapter on the feasibility problem for linear programming covers many well established topics including the two-phase simplex method, the big-M method, and crash starts. A second chapter discusses heuristics for mixed integer linear programming problems, including pivot-and-complement, the OCTANE heuristic, and the feasibility pump. A chapter on feasibility problems for nonlinear programming problems includes sections on hit-and-run methods, heuristics for selecting an initial point and multistart methods.
The second part of the book deals with the analysis of infeasible problems. This part begins with a chapter on isolating the cause of the infeasibility of an optimization problem. The concept of an irreducible infeasible subset (IIS) of the constraints is particularly important. Chinneck describes several methods for finding an IIS in a linear programming problem as well as extensions to mixed integer linear programming problems and nonlinear programming problems. Methods for adjusting constraints to achieve feasibility are also discussed.
The third part of the book is a somewhat disorganized collection of topics including other types of model analysis and applications of the methods of model analysis to various applications. Although this material serves to illustrate the ideas presented earlier in the book, specific connections to earlier chapters are somewhat vague. This material should perhaps have been merged into the first two parts of the book.
This book is really the first monograph to summarize the growing body of research on the analysis of feasibility and infeasibility of optimization problems. With up to date coverage and very thorough bibliography, it will be of definite interest to researchers working in this area. The book may also be of interest to those readers who are more interested in modeling and applications but want to learn something about techniques for analyzing the feasibility of optimization models.
Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.
Part I: Analyzing Infeasibility.- Isolating an Infeasibility.- Methods Specific to Linear Programming.- Methods Specific to Mixed Integer Programming.- Methods Specific to Nonlinear Programming.- Finding the Maximum Feasible Subset of Linear Constraints.- Finding the Best Fix for an Infeasible System.- Part II: Reaching Feasibility Quickly.- Linear Programming.- Mixed Integer Programming.- Nonlinear Programming.- Part III: Applications.- Analyzing Unboundedness in Linear Programs.- Analyzing the Viability of Network Models.- Analyzing Multiple-Objective Linear Programs.- Data Classification and Training Neural Networks.- Applications In Statistics.- Radiation Treatment Planning.- Backtracking in Constraint Programming.- Protein Folding.- Automatic Test Assembly.- General NP-Hard Problems.