Open Journal of Mathematical Optimization

Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
Jérémy Omer1; Michael Poss2; Maxime Rougier1
1 Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, France
2 LIRMM, University of Montpellier, CNRS, France
Open Journal of Mathematical Optimization, Volume 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.

Received:
Accepted:
Published online:
DOI: 10.5802/ojmo.33
Mots-clés : robust combinatorial optimization, compact formulations, column generation, cutting plane.
Jérémy Omer 1; Michael Poss 2; Maxime Rougier 1

1 Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, France
2 LIRMM, University of Montpellier, CNRS, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2024__5__A5_0,
     author = {J\'er\'emy Omer and Michael Poss and Maxime Rougier},
     title = {Combinatorial {Robust} {Optimization} with {Decision-Dependent} {Information} {Discovery} and {Polyhedral} {Uncertainty}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {5},
     pages = {1--25},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     year = {2024},
     doi = {10.5802/ojmo.33},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/}
}
TY  - JOUR
AU  - Jérémy Omer
AU  - Michael Poss
AU  - Maxime Rougier
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://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/
DO  - 10.5802/ojmo.33
LA  - en
ID  - OJMO_2024__5__A5_0
ER  - 
%0 Journal Article
%A Jérémy Omer
%A Michael Poss
%A Maxime Rougier
%T Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
%J Open Journal of Mathematical Optimization
%D 2024
%P 1-25
%V 5
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/
%R 10.5802/ojmo.33
%G en
%F OJMO_2024__5__A5_0
Jérémy Omer; Michael Poss; Maxime Rougier. Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty. Open Journal of Mathematical Optimization, Volume 5 (2024), article  no. 5, 25 p. doi : 10.5802/ojmo.33. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/

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

[2] Ayşe N. Arslan; Boris Detienne 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

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

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

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

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

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

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

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

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

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

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

[13] Matthew Colvin; Christos T. Maravelias 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] Iain Dunning; Joey Huchette; Miles Lubin JuMP: A Modeling Language for Mathematical Optimization, SIAM Rev., Volume 59 (2017) no. 2, pp. 295-320 | DOI | Zbl

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

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

[17] Marc Goerigk; Adam Kasperski; Pawel Zielinski 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

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

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

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

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

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

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

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

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

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

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

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

[29] Rosario Paradiso personnal communication, 2023

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

[31] Artur Alves Pessoa; Michael Poss; Ruslan Sadykov; François Vanderbeck 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

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

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

[34] Krzysztof Postek; Dick den Hertog 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

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

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

[37] Filipe Rodrigues; Agostinho Agra; Cristina Requejo; Erick Delage 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

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

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

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

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

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

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

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

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

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

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

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

[49] Bo Zeng; Long Zhao 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

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

Cited by Sources: