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: | Easton Todd, Hickman Randal |
Keywords: | graphs, programming: integer |
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.