Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems

Ayşe N. Arslan () and Boris Detienne ()
Additional contact information
Ayşe N. Arslan: Univiersité 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
Boris Detienne: Univiersité Bordeaux, Centre National de la Recherche Scientifique, Institut de Mathématiques de Bordeaux–Unité Mixte de Recherche 5251, Inria Bordeaux Sud-Ouest, F-33400 Talence, France

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 857-871

Abstract: In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty, where recourse decisions are restricted to be mixed-binary. For these problems, we present a deterministic equivalent formulation through the convexification of the recourse-feasible region. We then explore this formulation under the lens of a relaxation, showing that the specific relaxation we propose can be solved by using the branch-and-price algorithm. We present conditions under which this relaxation is exact and describe alternative exact solution methods when this is not the case. Despite the two-stage nature of the problem, we provide NP-completeness results based on our reformulations. Finally, we present various applications in which the methodology we propose can be applied. We compare our exact methodology to those approximate methods recently proposed in the literature under the name K − adaptability. Our computational results show that our methodology is able to produce better solutions in less computational time compared with the K − adaptability approach, as well as to solve bigger instances than those previously managed in the literature. Summary of Contribution: Our manuscript describes an exact solution approach for a class of robust binary optimization problems with mixed-binary recourse and objective uncertainty. Its development reposes first on a reformulation of the problem, then a carefully constructed relaxation of this reformulation. Our solution approach is designed to exploit the two-stage and binary structure of the problem for effective resolution. In its execution, it relies on the branch-and-price algorithm and its efficient implementation. With our computational experiments, we show that our proposed exact solution method outperforms the existing approximate methodologies and, therefore, pushes the computational envelope for the class of problems considered.

Keywords: two-stage robust optimization; column generation; exact solution methods; mathematical programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1061 (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:2:p:857-871

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 ().