Almost Robust Discrete Optimization

Opher Baron, Oded Berman, Mohammad M. Fazel-Zarandi and Vahid Roshanaei

European Journal of Operational Research, 2019, vol. 276, issue 2, 451-465

Abstract: The main goal of this paper is to present a simple and tractable methodology for incorporating data uncertainty into optimization models in the presence of binary variables. We introduce the Almost Robust Discrete Optimization (ARDO). ARDO extends the Integrated Chance-Constrained approach, developed for linear programs, to include binary integer variables. Both models trade off the objective function value with robustness and find optimal solutions that are almost robust (feasible under most realizations). These models are attractive due to their simplicity, ability to capture dependency among uncertain parameters, and that they incorporate the decision maker’s attitude towards risk by controlling the degree of conservatism of the optimal solution. To solve the ARDO model efficiently, we decompose it into a deterministic master problem and a single subproblem that checks the master problem solution under different realizations and generates cuts if needed. In contrast to other robust optimization models that are less tractable with binary decision variables, we demonstrate that with these cuts, the ARDO remains tractable. Computational experiments for the capacitated single-source facility location problem where demands in each node are uncertain demonstrate the effectiveness of our approach.

Keywords: Combinatorial optimization; Decision making under uncertainty; Robust/stochastic discrete optimization; Decomposition; Almost robust optimization; Binary variables (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719300785
Full text for ScienceDirect subscribers only

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:eee:ejores:v:276:y:2019:i:2:p:451-465

DOI: 10.1016/j.ejor.2019.01.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().