Cover inequalities for robust knapsack sets—Application to the robust bandwidth packing problem
作者： Olivier Klopfenstein , Dritan Nace
DOI: 10.1002/NET.20488
关键词:
摘要: The robust optimization framework proposed by Bertsimas and Sim accounts for data uncertainty in integer linear programs. This article investigates the polyhedral impacts of this model 0-1 knapsack problem. In particular, classical cover cuts are adapted to provide valid inequalities strength is studied theoretically. Then, experiments on bandwidth packing problem illustrate practical interest these solving hard combinatorial problems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012
archives-ouvertes.fr
sci-hub.se 参考文章(17)
Mustafa �. P�nar, A note on robust 0-1 optimization with uncertain cost coefficients A Quarterly Journal of Operations Research. ,vol. 2, pp. 309- 316 ,(2004) , 10.1007/S10288-004-0041-Y
Pietro Belotti, Antonio Capone, Giuliana Carello, Federico Malucelli, Multi-layer MPLS network design: The impact of statistical multiplexing Computer Networks. ,vol. 52, pp. 1291- 1307 ,(2008) , 10.1016/J.COMNET.2008.01.005
V. Gabrel, M. Minoux, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems Operations Research Letters. ,vol. 30, pp. 252- 264 ,(2002) , 10.1016/S0167-6377(02)00124-4
Aharon Ben-Tal, Arkadi Nemirovski, Robust solutions of Linear Programming problems contaminated with uncertain data Mathematical Programming. ,vol. 88, pp. 411- 424 ,(2000) , 10.1007/PL00011380
Zonghao Gu, George L. Nemhauser, Martin W. P. Savelsbergh, Lifted Cover Inequalities for 0-1 Integer Programs: Complexity Informs Journal on Computing. ,vol. 11, pp. 117- 123 ,(1999) , 10.1287/IJOC.11.1.117
Olivier Klopfenstein, Dritan Nace, A robust approach to the chance-constrained knapsack problem Operations Research Letters. ,vol. 36, pp. 628- 632 ,(2008) , 10.1016/J.ORL.2008.03.006
C. E. Ferreira, A. Martin, R. Weismantel, Solving Multiple Knapsack Problems by Cutting Planes Siam Journal on Optimization. ,vol. 6, pp. 858- 877 ,(1996) , 10.1137/S1052623493254455
Alper Atamtürk, Strong Formulations of Robust Mixed 0–1 Programming Mathematical Programming. ,vol. 108, pp. 235- 250 ,(2006) , 10.1007/S10107-006-0709-5
Laurence A. Wolsey, Faces for linear inequalities in 0-1 variables Mathematical Programming. ,vol. 8, pp. 165- 178 ,(1975) , 10.1007/BF01580441
Kyungchul Park, Seokhoon Kang, Sungsoo Park, An Integer Programming Approach to the Bandwidth Packing Problem Management Science. ,vol. 42, pp. 1277- 1291 ,(1996) , 10.1287/MNSC.42.9.1277