Stronger Inequalities for 0, 1 Integer Programming Using Knapsack Functions

Ferydoon Kianfar
Additional contact information
Ferydoon Kianfar: Arya-Mehr University of Technology, Tehran, Iran

Operations Research, 1971, vol. 19, issue 6, 1374-1392

Abstract: In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0,1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.6.1374 (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:19:y:1971:i:6:p:1374-1392

Access Statistics for this article

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