Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions

Ayşe N. Arslan (), Michael Poss () and Marco Silva ()
Additional contact information
Ayşe N. Arslan: Université Rennes, Institut National des Sciences Appliquées de Rennes, Centre National de la Recherche Scientifique, Institut de Recherche Mathématique de Rennes, Unité Mixte de Recherche 6625, F-35000 Rennes, France
Michael Poss: Laboratory of Computer Science, Robotics and Microelectronics of Montpellier (LIRMM), UMR CNRS 5506, University of Montpellier, 34095 Montpellier, France
Marco Silva: Centro de Engenharia e Gestão Industrial (CEGI), Instituto de Engenharia de Sistemas e Computadores, Tecnologia e Ciência (INESC TEC), Faculdade de Engenharia da Universidade do Porto, 4200-465 Porto, Portugal

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2212-2228

Abstract: In this paper, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear. 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. Finally, we illustrate how our approach handles nonlinear functions on an all-or-nothing subset problem taken from the literature. Summary of Contribution: Our paper describes a new exact algorithm for solving adaptive robust combinatorial optimization problems when the feasible set of the nominal optimization problems does not contain too many good solutions. Its development relies on a progressive relaxation of the problem augmented with a row-and-column generation technique. Its efficient execution requires a reformulation of this progressive relaxation, coupled with dominance rules and a binary search algorithm. The proposed algorithm is amenable to exploiting the special structures of the problems considered as illustrated with various applications throughout the paper. A practical view is provided by the proposition of a heuristic variant. Our computational experiments show that our proposed exact solution method outperforms the existing methodologies and therefore pushes the computational envelope for the class of problems considered.

Keywords: robust optimization; combinatorial optimization; vertex p -center; scenario generation (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1156 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2212-2228

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().