Title: Merging valid inequalities over the multiple knapsack polyhedron

Authors: Randal Hickman; Todd Easton

Addresses: Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan, Kansas 66506, USA ' Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan, Kansas 66506, USA

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.

DOI: 10.1504/IJOR.2015.071495

International Journal of Operational Research, 2015 Vol.24 No.2, pp.214 - 227

Received: 11 Oct 2012
Accepted: 28 Jul 2013
Published online: 31 Aug 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article