Cover inequalities for robust knapsack sets – application to the robust bandwidth packing problem. (English) Zbl 1241.90113
Summary: 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 robust model for the \(0\)-\(1\) knapsack problem. In particular, classical cover cuts are adapted to provide valid inequalities for the robust knapsack problem. The strength of the proposed inequalities is studied theoretically. Then, experiments on the robust bandwidth packing problem illustrate the practical interest of these inequalities for solving hard robust combinatorial problems.
MSC:
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
robust optimization; knapsack set; polyhedral analysis; knapsack cover inequalities; routing; bandwidth packing problemReferences:
| [1] | Atamtürk, Strong formulations of robust mixed 0-1 programming, Math Program 108 pp 235– (2006) · Zbl 1136.93331 · doi:10.1007/s10107-006-0709-5 |
| [2] | Balas, Facets of the knapsack polytope, Math Program 8 pp 146– (1975) · Zbl 0316.90046 · doi:10.1007/BF01580440 |
| [3] | Bellman, Dynamic programming (1957) |
| [4] | Belotti, Multi-layer MPLS network design: The impact of statistical multiplexing, Comput Networks 52 pp 1291– (2008) · Zbl 1138.68011 · doi:10.1016/j.comnet.2008.01.005 |
| [5] | Ben-Tal, Robust solutions of linear programming problems contamined with uncertain data, Math Program A 88 pp 411– (2000) · doi:10.1007/PL00011380 |
| [6] | Bertsimas, Robust discrete optimization and network flows, Math Program B 98 pp 49– (2003) · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4 |
| [7] | Bertsimas, The price of robustness, Oper Res 52-1 pp 35– (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [8] | Crowder, Solving large-scale zero-one linear programming problems, Oper Res 31 pp 803– (1983) · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [9] | Ferreira, Solving multiple knapsack problems by cutting planes, SIAM J Optim 6 pp 858– (1996) · Zbl 0856.90082 · doi:10.1137/S1052623493254455 |
| [10] | Gabrel, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Oper Res Lett 30 pp 252– (2002) · Zbl 1049.90074 · doi:10.1016/S0167-6377(02)00124-4 |
| [11] | Gu, Lifted cover inequalities for 0-1 integer programs: computation, INFORMS J Comput 10 pp 427– (1998) · doi:10.1287/ijoc.10.4.427 |
| [12] | Gu, Lifted cover inequalities for 0-1 integer programs: complexity, INFORMS J Comput 11-1 pp 117– (1999) · Zbl 1092.90527 · doi:10.1287/ijoc.11.1.117 |
| [13] | Kellerer, Knapsack Problems (2004) · doi:10.1007/978-3-540-24777-7 |
| [14] | Klopfenstein, A robust approach to the chance-constrained knapsack problem, Oper Res Lett 36 pp 628– (2008) · Zbl 1210.90126 · doi:10.1016/j.orl.2008.03.006 |
| [15] | Klopfenstein, Tractable algorithms for chance-constrained combinatorial problems, RAIRO-Oper Res 43 pp 157– (2009) · Zbl 1173.90478 · doi:10.1051/ro/2009010 |
| [16] | Koster, Multicommodity single path routing with submodular bandwidth consumption, Proc Int Network Optim Conf (INOC) (2009) |
| [17] | Martello, Knapsack problems: Algorithms and computer implementations (1990) · Zbl 0708.68002 |
| [18] | Nemhauser, Integer and combinatorial optimization (1999) |
| [19] | Ouorou, A model for robust capacity planning for telecommunications networks under demand uncertainty, Proc Workshop on Des Reliable Commun Networks (DRCN) (2007) · doi:10.1109/DRCN.2007.4762287 |
| [20] | Park, An integer programming approach to the bandwidth packing problem, Manage Sci 42 pp 1277– (1996) · Zbl 0880.90043 · doi:10.1287/mnsc.42.9.1277 |
| [21] | Pinar, A note on robust 0-1 optimization with uncertain cost coefficients, 4OR, Quarterly J Belg Fr Ital Oper Res Soc 2 pp 309– (2004) · Zbl 1112.90050 · doi:10.1007/s10288-004-0041-y |
| [22] | Prékopa, Stochastic Programming, Vol. 10 of Handbooks in OR&MS pp 267– (2003) · doi:10.1016/S0927-0507(03)10005-9 |
| [23] | Wolsey, Faces for linear inequality in 0-1 variables, Math Program 8 pp 165– (1975) · Zbl 0314.90063 · doi:10.1007/BF01580441 |
| [24] | Zemel, Easily computable facets of the knapsack problem, Math Oper Res 14 pp 760– (1989) · Zbl 0689.90057 · doi:10.1287/moor.14.4.760 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
