Merging valid inequalities over the multiple knapsack polyhedron

Randal Hickman and Todd Easton

International Journal of Operational Research, 2015, vol. 24, issue 2, 214-227

Abstract: This paper provides the theoretical foundations for generating a new class of valid inequalities for integer programming problems through inequality merging. The inequality merging technique combines two low dimensional inequalities of a multiple knapsack problem, potentially yielding a valid inequality of higher dimension. The paper describes theoretical conditions for validity of the merged inequality and shows that the validity of a merged cover inequality may be verified in quadratic time. Conditions under which a valid merged inequality is facet defining are also presented. The technique is demonstrated through a multiple knapsack example. The example also demonstrates that inequality merging yields a new class of valid inequalities that are fundamentally different from other known techniques.

Keywords: integer programming; inequality merging; valid inequalities; multiple knapsack; polyhedral theory. (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=71495 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijores:v:24:y:2015:i:2:p:214-227

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().