Cutting plane versus compact formulations for uncertain (integer) linear programs

被引:59
作者
Fischetti M. [1 ]
Monaci M. [1 ]
机构
[1] DEI, Università di Padova, Padua
关键词
Cutting planes; Optimization under uncertainty; Uncertain connectivity problems; Uncertain set covering;
D O I
10.1007/s12532-012-0039-y
中图分类号
学科分类号
摘要
Robustness is about reducing the feasible set of a given nominal optimization problem by cutting "risky" solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization à la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magnitude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better performance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness. © 2012 Springer and Mathematical Optimization Society.
引用
收藏
页码:239 / 273
页数:34
相关论文
共 38 条
[1]  
Achterberg, T., (2007) Constraint Integer Programming, , Ph. D. thesis, ZIB, Technische Universität Berlin
[2]  
Balas, E., A class of location, distribution and scheduling problems: modeling and solution methods (1983) Proc. Chinese-US Symposium on System Analysis, , Wiley, New York
[3]  
Ben-Tal, A., Nemirovski, A., Robust solutions to uncertain linear programs (1999) Oper. Res. Lett., 25, pp. 1-13
[4]  
Ben-Tal, A., Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data (2000) Math. Progr., 88, pp. 411-424
[5]  
Ben-Tal, A., Nemirovski, A., Robust optimization-methodology and applications (2002) Math. Progr., 92, pp. 453-480
[6]  
Beraldi, P., Ruszczyński, A., The probabilistic set-covering problem (2002) Oper. Res., 50, pp. 956-967
[7]  
Bertsimas, D., Sim, M., Robust discrete optimization and network flows (2003) Math. Progr., 98, pp. 49-71
[8]  
Bertsimas, D., Sim, M., The price of robustness (2004) Oper. Res., 52, pp. 35-53
[9]  
Caprara, A., Fischetti, M., Toth, P., Algorithms for the set covering problem (2000) Ann. Oper. Res., 98, pp. 353-371
[10]  
Caprara, A., Fischetti, M., Toth, P., Vigo, D., Guida, P.L., Algorithms for railway crew management (1997) Math. Progr., 79, pp. 125-141