Improving logic-based Benders’ algorithms for solving min-max regret problems

• Autorzy: Assunção Lucas , Santos Andréa Cynthia , Noronha Thiago F. , Andrade Rafael

Identyfikatory

DOI

10.37190/ord210202

• Języki publikacji: EN

Abstrakty

EN

This paper addresses a class of problems under interval data uncertainty, composed of min-max regret generalisations of classical 0-1 optimisation problems with interval costs. These problems are called robust-hard when their classical counterparts are already NP-hard. The state-of-the-art exact algorithms for interval 0-1 min-max regret problems in general work by solving a corresponding mixed- -integer linear programming formulation in a Benders’ decomposition fashion. Each of the possibly exponentially many Benders’ cuts is separated on the fly by the resolution of an instance of the classical 0-1 optimisation problem counterpart. Since these separation subproblems may be NP-hard, not all of them can be easily modelled using linear programming (LP), unless P equals NP. In this work, we formally describe these algorithms through a logic-based Benders’ decomposition framework and assess the impact of three warm-start procedures. These procedures work by providing promising initial cuts and primal bounds through the resolution of a linearly relaxed model and an LP-based heuristic. Extensive computational experiments in solving two challenging robust-hard problems indicate that these procedures can highly improve the quality of the bounds obtained by the Benders’ framework within a limited execution time. Moreover, the simplicity and effectiveness of these speed-up procedures make them an easily reproducible option when dealing with interval 0-1 min-max regret problems in general, especially the more challenging subclass of robust-hard problems.

Słowa kluczowe

EN

robust optimisation; min-max regret problem; Benders’ decomposition; warm-start procedure

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2021
• Tom: Vol. 31, No. 2
• Strony: 23--57
• Opis fizyczny: Bibliogr. 38 poz., tab.

Twórcy

autor

Assunção Lucas

• Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Avenida Antônio Carlos, 6627, CEP 31270-901, Belo Horizonte, MG, Brazil

autor

Santos Andréa Cynthia

• Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, 25 Rue Philippe Lebon, 76600 Le Havre, France

autor

Noronha Thiago F.

• Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Avenida Antônio Carlos, 6627, CEP 31270-901, Belo Horizonte, MG, Brazil

autor

Andrade Rafael

• Departamento de Estatística e Matemática Aplicada, Universidade Federal do Ceará, Campus do Pici – Bloco 910, CEP 60455-900, Fortaleza, CE, Brazil

Bibliografia

• [1] AISSI H., BAZGAN C., VANDERPOOTEN D., Approximation of min-max and min-max regret versions of some combinatorial optimization problems, Eur. J. Oper. Res., 2007, 179 (2), 281–290.
• [2] AISSI H., BAZGAN C., VANDERPOOTEN D., Min-max and min-max regret versions of combinatorial optimization problems: A survey, Eur. J. Oper. Res., 2009, 197 (2), 427–438.
• [3] ASSUNÇÃO L., NORONHA T.F., SANTOS A., ANDRADE R., A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, Comp. Oper. Res., 2017, 81, 51 – 66.
• [4] ASSUNÇÃO L., SANTOS A.C., NORONHA T.F., ANDRADE R., On the finite optimal convergence of logic--based Benders’ decomposition in solving 0-1 min-max regret optimization problems with interval costs, [In:] R. Cerulli, S. Fujishige, R.A. Mahjoub (Eds.), Combinatorial Optimization, ISCO 2016, Lecture Notes in Computer Science, Springer, 2016, 9849, 1–12.
• [5] AVERBAKH I., LEBEDEV V., On the complexity of minmax regret linear programming, Eur. J. Oper. Res., 2005, 160 (1), 227–231.
• [6] BEASLEY J.E., OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc., 1990, 41(11), 1069–1072.
• [7] BENDERS J.F., Partitioning procedures for solving mixed-variables programming problems, Num. Math., 1962, 4 (1), 238–252.
• [8] BONDY J.A., MURTY U.S.R., Graph Theory with Applications, Elsevier, New York 1976.
• [9] CAPRARA A., TOTH P., FISCHETTI M., Algorithms for the set covering problem, Ann. Oper. Res., 2000, 98 (1), 353–371.
• [10] COCO A.A., JÚNIOR J.C.A., NORONHA T.F., SANTOS A.C., An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem, J. Global Opt., 2014, 60 (2), 265–287.
• [11] COCO A.A., SANTOS A.C., NORONHA T.F., Scenario-based heuristics with path-relinking for the robust set covering problem, Proc. XI Metaheuristics International Conference, Agadir, Marocco, 2015, 1–8.
• [12] CODATO G., FISCHETTI M., Combinatorial Benders’ cuts for mixed-integer linear programming, Oper. Res., 2006, 54 (4), 756–766.
• [13] CONDE E., Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios, Comp. Oper. Res., 2019, 103, 97–108.
• [14] CREMA A., Min-max-min robust (relative) regret combinatorial optimization, Math. Meth. Oper. Res., 2020, 92 (2), 249–283.
• [15] FEIZOLLAHI M.J., AVERBAKH I., The robust (minmax regret) quadratic assignment problem with interval flows, INFORMS J. Comp., 2014, 26 (2), 321–335.
• [16] FISCHETTI M., LODI A., Local branching, Math. Progr., 2003, 98 (1–3), 23–47.
• [17] FISCHETTI M., SALVAGNIN D., ZANETTE A., A note on the selection of Benders’ cuts, Math. Progr., 2010, 124 (1–2), 175–182.
• [18] GAREY M.R., JOHNSON D.S., Computers and Intractability. A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York 1979.
• [19] HOOKER J., OTTOSSON G., Logic-based Benders decomposition, Math. Progr., 2003, 96 (1), 33–60.
• [20] KARAŞAN O.E., PINAR M.Ç., YAMAN H., The robust shortest path problem with interval data, Technical Report, Bilkent University, Ankara 2001.
• [21] KASPERSKI A., KOBYLAŃSKI P., KULEJ M., ZIELIŃSKI P., Minimizing maximal regret in discrete optimization problems with interval data, [In:] Issues in Soft Computing. Decisions and Operations Research, O. Hryniewicz, J. Kacprzyk, D. Kuchta (Eds.), Akademicka Oficyna Wydawnicza EXIT, Warszawa 2005.
• [22] KASPERSKI A., ZIELIŃSKI P., An approximation algorithm for interval data minmax regret combinatorial optimization problems, Inf. Proc. Lett., 2006, 97 (5), 177–180.
• [23] KASPERSKI A., ZIELIŃSKI P., Soft robust solutions to possibilistic optimization problems, Fuzzy Sets Syst., 2020, DOI: 10.1016/j.fss.2020.12.016.
• [24] KASPERSKI A., Discrete Optimization with Interval Data. Minmax Regret and Fuzzy Approach (Studies in Fuzziness and Soft Computing), Springer, Berlin 2008.
• [25] KOUVELIS P., YU G., Robust Discrete Optimization and Its Applications, Kluwer, Boston 1997.
• [26] MCDANIEL D., DEVINE M., A modified Benders’ partitioning algorithm for mixed integer programming, Manage. Sci., 1977, 24 (3), 312–319.
• [27] GOERIGK M., KASPERSKI A., ZIELINSKI P., Combinatorial two-stage minmax regret problems under interval uncertainty, Ann. Oper. Res., 2020, 1–28.
• [28] MONTEMANNI R., BARTA J., GAMBARDELLA L.M., Heuristic and preprocessing techniques for the robust traveling salesman problem with interval data, Technical Report, Dalle Molle Institute for Artificial Intelligence, 2006.
• [29] MONTEMANNI R.,BARTA J., GAMBARDELLA L.M., The robust traveling salesman problem with interval data, Trans. Sci., 2007, 41 (3), 366–381.
• [30] MONTEMANNI R., GAMBARDELLA L.M., A branch and bound algorithm for the robust spanning tree problem with interval data, Eur. J. Oper. Res., 2005, 161 (3), 771–779.
• [31] MONTEMANNI R., GAMBARDELLA L.M., The robust shortest path problem with interval data via Benders decomposition, 4OR, 2005, 3 (4), 315–328.
• [32] MONTEMANNI R., A Benders decomposition approach for the robust spanning tree problem with interval data, Eur. J. Oper. Res., 2006, 174 (3), 1479–1490.
• [33] PEREIRA J., AVERBAKH I., Exact and heuristic algorithms for the interval data robust assignment problem, Comp. Oper. Res., 2011, 38 (8), 1153–1163.
• [34] PEREIRA J., AVERBAKH I., The robust set covering problem with interval data, Ann. Oper. Res., 2013, 207 (1), 217–235.
• [35] SPALL J.C., Introduction to Stochastic Search and Optimization. Estimation, Simulation and Control, Wiley, New York 2003.
• [36] SUGIYAMA K., TAGAWA S., TODA M., Methods for visual understanding of hierarchical system structures, IEEE Trans. Syst., Man Cyber., 1981, 11 (2), 109–125.
• [37] YU G., On the max-min 0-1 knapsack problem with robust optimization applications, Oper. Res., 1996, 44 (2), 407–415.
• [38] ZHU X., WILHELM W.E., A three-stage approach for the resource-constrained shortest path as a subproblem in column generation, Comp. Oper. Res., 2012, 39 (2), 164–178.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).