Constraint Classification for Mixed Integer Programming Formulations.

摘要

There are various ways to tighten the linear programming relaxation of an integer program. Preprocessing techniques try to reduce the size of coefficients in the constraint matrix and to reduce the size of bounds on the variables. Constraint generation techniques try to generate strong valid inequalities. Reformulation techniques should make the best possible use of the problem structure. General reformulation techniques try to identify problem structure based on an analysis of the constraint matrix. Problem specific reformulation techniques are based on an a priori investigation of the polyhedron associated with the set of feasible solutions. The note defines a classification scheme that is used in the system MINTO. Its purpose is to identify important classes to be used in preprocessing, constraint generation, branching, etc. It is proposed as a general scheme to be evaluated, modified and then, hopefully, adopted, by the mixed integer programming community.