Merging valid inequalities over the multiple knapsack polyhedron

Merging valid inequalities over the multiple knapsack polyhedron

0.00 Avg rating0 Votes
Article ID: iaor201527380
Volume: 24
Issue: 2
Start Page Number: 214
End Page Number: 227
Publication Date: Aug 2015
Journal: International Journal of Operational Research
Authors: ,
Keywords: graphs, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.