An inexact column-and-constraint generation method to solve two-stage robust optimization problems

DOI10.1016/J.ORL.2022.12.002MaRDI QIDQ6161289zbMATH OpenOpenAlexFDO

Authors Man Yiu Tsang, Karmel S. Shehadeh, Frank E. Curtis

Publication date 27 June 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.03291

zbMATH Keywords

column-and-constraint generationdecomposition algorithmsrobust optimizationtwo-stage stochastic optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Robustness in mathematical programming (90C17) Minimax problems in mathematical programming (90C47)

Abstract: We propose a new inexact column-and-constraint generation (i-C&CG) method to solve two-stage robust optimization problems. The method allows solutions to the master problems to be inexact, which is desirable when solving large-scale and/or challenging problems. It is equipped with a backtracking routine that controls the trade-off between bound improvement and inexactness. Importantly, this routine allows us to derive theoretical finite convergence guarantees for our i-C&CG method. Numerical experiments demonstrate computational advantages of our i-C&CG method over state-of-the-art column-and-constraint generation methods.

Recommendations

• Two-stage robust optimization problems with two-stage uncertainty
• A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization
• Solving robust two-stage combinatorial optimization problems under convex uncertainty
• Saddle point approximation approaches for two-stage robust optimization problems
• A Lagrangian dual method for two-stage robust optimization with binary uncertainties
• A primal-dual lifting scheme for two-stage robust optimization
• Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
• Two-stage robust mixed integer programming problem with objective uncertainty

Cites work

• A robust optimization approach to energy and reserve dispatch in electricity markets
• A two-stage robust model for a reliable p-center facility location problem
• Decomposition for adjustable robust linear optimization subject to uncertainty polytope
• Optimal allocation of surgery blocks to operating rooms under uncertainty
• Recent advances in robust optimization: an overview
• Solving two-stage robust optimization problems using a column-and-constraint generation method
• The Price of Robustness
• Two-stage robust optimization approach to elective surgery and downstream capacity planning

Cited in

(10)

• Exact and matheuristic algorithms for robust lot-sizing and scheduling problems with uncertain capacity
• Flow-shop and job-shop robust scheduling problems with budgeted uncertainty
• Two-stage robust optimization approach for enhanced community resilience under tornado hazards
• Equity-driven facility location: a two-stage robust optimization approach
• An extended C\&CG algorithm for solving two-stage robust optimization of economic and feasible scheduling
• Faster solutions to the interdiction defense problem using suboptimal solutions
• Bundle-enhanced column-and-constraint generation method for solving two-stage robust optimization problems
• An environmentally friendly elective patient scheduling under the predict-then-optimize framework
• Operating room planning problem under uncertainty: a regret minimization model
• A fast approximate column-and-constraint generation method for two-stage robust mixed-integer programs

This page was built for publication: An inexact column-and-constraint generation method to solve two-stage robust optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161289)