Cover and Pack Inequalities for (Mixed) Integer Programming |
| |
Authors: | Email author" target="_blank">Alper?AtamtürkEmail author |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720-1777, USA |
| |
Abstract: | We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the
0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to
give a unified presentation of the inequalities based on covers and packs and highlight the connections among them. The focus
of the paper is on recent research on the use of superadditive functions for the analysis of knapsack polyhedra.
We also present some new results on integer knapsacks. In particular, we give an integer version of the cover inequalities
and describe a necessary and sufficient facet condition for them. This condition generalizes the well-known facet condition
of minimality of covers for 0-1 knapsacks.
The author is supported, in part, by NSF Grants 0070127 and 0218265. |
| |
Keywords: | integer programming knapsack polyhedra lifting superadditive functions |
本文献已被 SpringerLink 等数据库收录! |
|