Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
Operations Research · 1985 · Volume 33 · Issue 3
Abstract
We describe a method for generating cuts for mixed-integer 0/1 programs. These cuts are designed to tighten an integer program prior to applying linear programming based branch and bound algorithms. The method involves two basic ideas: subset selection and coefficient reduction. Coefficient reduction is a process of reducing the coefficients of the 0/1 variables. Subset selection is combined with coefficient reduction by applying the coefficient reduction process to the coefficients of a subset of variables from the constraints in the problem formulation. The paper exploits these two simple ideas to derive a broad class of cuts for integer programs with both 0/1 and continuous variables. It also reports on the use of this methodology in solving a variety of fixed charge problems.
Keywords
625 tightening algorithm for mixed-0/1 programs, 627 LP based branch and bound, 628 cutting planes to reduce duality gap
Enable JavaScript for citation tools and additional paper interactions.