Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2024-09-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205177430310912 |
|---|---|
| author | Omer, Jérémy Poss, Michael Rougier, Maxime |
| author_facet | Omer, Jérémy Poss, Michael Rougier, Maxime |
| author_sort | Omer, Jérémy |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-cf7c5ee482f544aaba5eb285a04e0147 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-cf7c5ee482f544aaba5eb285a04e01472025-02-07T14:01:17ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602024-09-01512510.5802/ojmo.3310.5802/ojmo.33Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral UncertaintyOmer, Jérémy0Poss, Michael1Rougier, Maxime2Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, FranceLIRMM, University of Montpellier, CNRS, FranceUniv Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, 35000 Rennes, FranceGiven 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/robust combinatorial optimizationcompact formulationscolumn generationcutting plane. |
| spellingShingle | Omer, Jérémy Poss, Michael Rougier, Maxime Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty Open Journal of Mathematical Optimization robust combinatorial optimization compact formulations column generation cutting plane. |
| title | Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty |
| title_full | Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty |
| title_fullStr | Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty |
| title_full_unstemmed | Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty |
| title_short | Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty |
| title_sort | combinatorial robust optimization with decision dependent information discovery and polyhedral uncertainty |
| topic | robust combinatorial optimization compact formulations column generation cutting plane. |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.33/ |
| work_keys_str_mv | AT omerjeremy combinatorialrobustoptimizationwithdecisiondependentinformationdiscoveryandpolyhedraluncertainty AT possmichael combinatorialrobustoptimizationwithdecisiondependentinformationdiscoveryandpolyhedraluncertainty AT rougiermaxime combinatorialrobustoptimizationwithdecisiondependentinformationdiscoveryandpolyhedraluncertainty |