Min-max-min robust combinatorial optimization with few recourse solutions - Centre Henri Lebesgue Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Min-max-min robust combinatorial optimization with few recourse solutions

Résumé

In this paper, we consider a variant of adaptive robust combinatorial optimization problems with cost uncertainty where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true cost vectors. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem.
Fichier principal
Vignette du fichier
preprint-version.pdf (544.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02939356 , version 1 (15-09-2020)
hal-02939356 , version 2 (08-10-2020)
hal-02939356 , version 3 (29-06-2021)

Identifiants

  • HAL Id : hal-02939356 , version 1

Citer

Ayşe Nur Arslan, Michael Poss, Marco Silva. Min-max-min robust combinatorial optimization with few recourse solutions. 2020. ⟨hal-02939356v1⟩
254 Consultations
442 Téléchargements

Partager

Gmail Facebook X LinkedIn More