Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
Omer, Jérémy1 ; Poss, Michael2 ; Rougier, Maxime1
1Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, France
2LIRMM, University of Montpellier, CNRS, France
Open Journal of Mathematical Optimization, Tome 5 (2024), article no. 5, 25 p.

Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called Decision-Dependent Information Discovery (DDID). In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still uncertain. Given a compact linear programming formulation for the nominal problem, we provide a mixed-integer linear programming (MILP) formulation for DDID. The MILP is compact if the number of constraints describing the uncertainty polytope other than lower and upper bounds is constant. The proof of this result involves the generalization to any polyhedral uncertainty set of a classical result, showing that solving a robust combinatorial optimization problem with cost uncertainty amounts to solving several times the nominal counterpart. We extend this formulation to more general nominal problems through column generation and constraint generation algorithms. We illustrate our reformulations and algorithms numerically on the selection problem, the orienteering problem, and the spanning tree problem.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/ojmo.33
Keywords: robust combinatorial optimization, compact formulations, column generation, cutting plane.

Omer, Jérémy  1   ; Poss, Michael  2   ; Rougier, Maxime  1

1 Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, France
2 LIRMM, University of Montpellier, CNRS, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{OJMO_2024__5__A5_0,
     author = {Omer, J\'er\'emy and Poss, Michael and Rougier, Maxime},
     title = {Combinatorial {Robust} {Optimization} with {Decision-Dependent} {Information} {Discovery} and {Polyhedral} {Uncertainty}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {5},
     pages = {1--25},
     year = {2024},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     doi = {10.5802/ojmo.33},
     mrnumber = {4795171},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ojmo.33/}
}
TY  - JOUR
AU  - Omer, Jérémy
AU  - Poss, Michael
AU  - Rougier, Maxime
TI  - Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
JO  - Open Journal of Mathematical Optimization
PY  - 2024
SP  - 1
EP  - 25
VL  - 5
PB  - Université de Montpellier
UR  - https://www.numdam.org/articles/10.5802/ojmo.33/
DO  - 10.5802/ojmo.33
LA  - en
ID  - OJMO_2024__5__A5_0
ER  - 
%0 Journal Article
%A Omer, Jérémy
%A Poss, Michael
%A Rougier, Maxime
%T Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
%J Open Journal of Mathematical Optimization
%] 5
%D 2024
%P 1-25
%V 5
%I Université de Montpellier
%U https://www.numdam.org/articles/10.5802/ojmo.33/
%R 10.5802/ojmo.33
%G en
%F OJMO_2024__5__A5_0
Omer, Jérémy; Poss, Michael; Rougier, Maxime. Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty. Open Journal of Mathematical Optimization, Tome 5 (2024), article  no. 5, 25 p.. doi: 10.5802/ojmo.33

[1] Agra, Agostinho; Santos, Marcio Costa; Nace, Dritan; Poss, Michael A Dynamic Programming Approach for a Class of Robust Optimization Problems, SIAM J. Optim., Volume 26 (2016) no. 3, pp. 1799-1823 | DOI | Zbl | MR

[2] Arslan, Ayşe N.; Detienne, Boris Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems, INFORMS J. Comput., Volume 34 (2022) no. 2, pp. 857-871 | DOI | Zbl | MR

[3] Arslan, Ayşe N.; Poss, Michael Uncertainty reduction in robust optimization, Oper. Res. Lett., Volume 55 (2024), 107131 | DOI | MR

[4] Arslan, Ayşe N.; Poss, Michael; Silva, Marco Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions, INFORMS J. Comput., Volume 34 (2022) no. 4, pp. 2212-2228 | DOI | Zbl | MR

[5] Ayoub, Josette; Poss, Michael Decomposition for adjustable robust linear optimization subject to uncertainty polytope, Comput. Manag. Sci., Volume 13 (2016) no. 2, pp. 219-239 | DOI | Zbl | MR

[6] Ben-Tal, Aharon; Goryashko, A. P.; Guslitzer, E.; Nemirovski, Arkadi Adjustable robust solutions of uncertain linear programs, Math. Program., Volume 99 (2004) no. 2, pp. 351-376 | DOI | Zbl | MR

[7] Ben-Tal, Aharon; Nemirovski, Arkadi Robust convex optimization, Math. Oper. Res., Volume 23 (1998) no. 4, pp. 769-805 | DOI | MR

[8] Bertsimas, Dimitris; Dunning, Iain Multistage Robust Mixed-Integer Optimization with Adaptive Partitions, Oper. Res., Volume 64 (2016) no. 4, pp. 980-998 | DOI | Zbl | MR

[9] Bertsimas, Dimitris; Sim, Melvyn Robust discrete optimization and network flows, Math. Program., Volume 98 (2003) no. 1-3, pp. 49-71 | DOI | Zbl | MR

[10] Bertsimas, Dimitris; Sim, Melvyn The Price of Robustness, Oper. Res., Volume 52 (2004) no. 1, pp. 35-53 | DOI | Zbl | MR

[11] Bertsimas, Dimitris; Thiele, Aurélie A robust optimization approach to inventory theory, Oper. Res., Volume 54 (2006) no. 1, pp. 150-168 | DOI | Zbl | MR

[12] Bezanson, Jeff; Edelman, Alan; Karpinski, Stefan; Shah, Viral B. Julia: A fresh approach to numerical computing, SIAM Rev., Volume 59 (2017) no. 1, pp. 65-98 | DOI | Zbl | MR

[13] Colvin, Matthew; Maravelias, Christos T. A stochastic programming approach for clinical trial planning in new drug development, Comput. Chem. Eng., Volume 32 (2008) no. 11, pp. 2626-2642 | DOI

[14] Dunning, Iain; Huchette, Joey; Lubin, Miles JuMP: A Modeling Language for Mathematical Optimization, SIAM Rev., Volume 59 (2017) no. 2, pp. 295-320 | DOI | Zbl | MR

[15] Focke, Jacob; Megow, Nicole; Meißner, Julie Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments, ACM J. Exp. Algorithm., Volume 25 (2020), 1.14, 20 pages | DOI | Zbl | MR

[16] Goerigk, Marc; Hartisch, Michael An Introduction to Robust Combinatorial Optimization, International Series in Operations Research & Management Science, 361, Springer, 2024 (Forthcoming. https://link.springer.com/book/9783031612602) | DOI | MR

[17] Goerigk, Marc; Kasperski, Adam; Zielinski, Pawel Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, J. Comb. Optim., Volume 43 (2022) no. 3, pp. 497-527 | DOI | Zbl | MR

[18] Goerigk, Marc; Lendl, Stefan Robust Combinatorial Optimization with Locally Budgeted Uncertainty, Open J. Math. Optim., Volume 2 (2021), 3, 18 pages | Numdam | DOI | Zbl | MR

[19] Goerigk, Marc; Lendl, Stefan; Wulf, Lasse Two-Stage robust optimization problems with two-stage uncertainty, Eur. J. Oper. Res., Volume 302 (2022) no. 1, pp. 62-78 | DOI | Zbl | MR

[20] Gounaris, Chrysanthos E.; Wiesemann, Wolfram; Floudas, Christodoulos A. The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty, Oper. Res., Volume 61 (2013) no. 3, pp. 677-693 | DOI | Zbl | MR

[21] Hanasusanto, Grani A.; Kuhn, Daniel; Wiesemann, Wolfram K-adaptability in two-stage robust binary programming, Oper. Res., Volume 63 (2015) no. 4, pp. 877-891 | DOI | Zbl | MR

[22] Jonsbråten, Tore W. Optimization models for petroleum field exploitation, 1998

[23] Jonsbråten, Tore W.; Wets, Roger J. B.; Woodruff, David L. A class of stochastic programs withdecision dependent random elements, Ann. Oper. Res., Volume 82 (1998), pp. 83-106 | Zbl | DOI | MR

[24] Kämmerling, Nicolas; Kurtz, Jannis Oracle-based algorithms for binary two-stage robust optimization, Comput. Optim. Appl., Volume 77 (2020) no. 2, pp. 539-569 | DOI | Zbl | MR

[25] Kouvelis, Panos; Yu, Gang Robust discrete optimization: past successes and future challenges, Robust discrete optimization and its applications, Springer, 1997, pp. 333-356 | DOI | MR

[26] Ley, Eva; Marx, Rebecca; Merkert, Maximilian; Niemann, Tim; Stiller, Sebastian Robust Optimization Under Controllable Uncertainty (2023) (available at Optimization Online)

[27] Magnanti, Thomas L.; Wolsey, Laurence A. Optimal trees, Network models (Handbooks in Operations Research and Management Science), Volume 7, North-Holland, 1995, pp. 503-615 | DOI | Zbl

[28] Nohadani, Omid; Sharma, Kartikey Optimization under decision-dependent uncertainty, SIAM J. Optim., Volume 28 (2018) no. 2, pp. 1773-1795 | DOI | Zbl | MR

[29] Paradiso, Rosario personnal communication, 2023

[30] Paradiso, Rosario; Georghiou, Angelos; Dabia, Said; Tönissen, Denise Exact and Approximate Schemes for Robust Optimization Problems with Decision Dependent Information Discovery (2022) | arXiv

[31] Pessoa, Artur Alves; Poss, Michael; Sadykov, Ruslan; Vanderbeck, François Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty, Oper. Res., Volume 69 (2021) no. 3, pp. 739-754 | DOI | Zbl | MR

[32] Poss, Michael Robust combinatorial optimization with variable budgeted uncertainty, 4OR, Volume 11 (2013) no. 1, pp. 75-92 | DOI | Zbl | MR

[33] Poss, Michael Robust combinatorial optimization with knapsack uncertainty, Discrete Optim., Volume 27 (2018), pp. 88-102 | DOI | Zbl | MR

[34] Postek, Krzysztof; Hertog, Dick den Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set, INFORMS J. Comput., Volume 28 (2016) no. 3, pp. 553-574 | DOI | Zbl | MR

[35] Pulleyblank, William R. Faces Of Matching Polyhedra, 1973 http://hdl.handle.net/10012/10971

[36] Queyranne, Maurice; Schulz, Andreas S. Polyhedral approaches to machine scheduling, Citeseer, 1994

[37] Rodrigues, Filipe; Agra, Agostinho; Requejo, Cristina; Delage, Erick Lagrangian Duality for Robust Problems with Decomposable Functions: The Case of a Robust Inventory Problem, INFORMS J. Comput., Volume 33 (2021) no. 2, pp. 685-705 | DOI | Zbl | MR

[38] Schrijver, A. Combinatorial optimization: polyhedra and efficiency, 24, Springer, 2003

[39] Solak, Senay; Clarke, John-Paul B.; Johnson, Ellis L.; Barnes, Earl R. Optimization of R&D project portfolios under endogenous uncertainty, Eur. J. Oper. Res., Volume 207 (2010) no. 1, pp. 420-433 | DOI | Zbl | MR

[40] Spacey, Simon A.; Wiesemann, Wolfram; Kuhn, Daniel; Luk, Wayne Robust software partitioning with multiple instantiation, INFORMS J. Comput., Volume 24 (2012) no. 3, pp. 500-515 | DOI | Zbl | MR

[41] Subramanyam, Anirudh; Gounaris, Chrysanthos E.; Wiesemann, Wolfram K-adaptability in two-stage mixed-integer robust optimization, Math. Program. Comput., Volume 12 (2020) no. 2, pp. 193-224 | DOI | Zbl | MR

[42] Taccari, Leonardo Integer programming formulations for the elementary shortest path problem, Eur. J. Oper. Res., Volume 252 (2016) no. 1, pp. 122-130 | DOI | Zbl | MR

[43] Tadayon, Bita; Smith, J. Cole Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems, J. Sched., Volume 18 (2015) no. 6, pp. 575-592 | DOI | Zbl | MR

[44] Vayanos, Phebe; Georghiou, Angelos; Yu, Han Robust optimization with decision-dependent information discovery (2020) | arXiv

[45] Vayanos, Phebe; Georghiou, Angelos; Yu, Han Robust optimization with decision-dependent information discovery (2022) | arXiv

[46] Wolsey, Laurence A. Integer programming, John Wiley & Sons, 2020 | DOI

[47] Yaman, Hande Short Paper - A Note on Robust Combinatorial Optimization with Generalized Interval Uncertainty, Open J. Math. Optim., Volume 4 (2023), 4, 7 pages | DOI | Zbl | MR

[48] Yanikoglu, Ihsan; Gorissen, Bram L.; Hertog, Dick den A survey of adjustable robust optimization, Eur. J. Oper. Res., Volume 277 (2019) no. 3, pp. 799-813 | DOI | Zbl | MR

[49] Zeng, Bo; Zhao, Long Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., Volume 41 (2013) no. 5, pp. 457-461 | DOI | Zbl | MR

[50] Zhen, Jianzhe; den Hertog, Dick; Sim, Melvyn Adjustable robust optimization via Fourier–Motzkin elimination, Oper. Res., Volume 66 (2018) no. 4, pp. 1086-1100 | DOI | Zbl | MR

Cité par Sources :