Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming

R. Kipp Martin and Linus Schrage
Additional contact information
R. Kipp Martin: University of Chicago, Chicago, Illinois
Linus Schrage: University of Chicago, Chicago, Illinois

Operations Research, 1985, vol. 33, issue 3, 505-526

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 (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.3.505 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:3:p:505-526

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().