On the finite optimal convergence of logic-based Benders' decomposition in solving 0-1 min-max regret optimization problems with interval costs
From MaRDI portal
Publication:2835657
Abstract: This paper addresses a class of problems under interval data uncertainty composed of min-max regret versions of classical 0-1 optimization problems with interval costs. We refer to them as interval 0-1 min-max regret problems. The state-of-the-art exact algorithms for this class of problems work by solving a corresponding mixed integer linear programming formulation in a Benders' decomposition fashion. Each of the possibly exponentially many Benders' cuts is separated on the fly through the resolution of an instance of the classical 0-1 optimization problem counterpart. Since these separation subproblems may be NP-hard, not all of them can be modeled by means of linear programming, unless P = NP. In these cases, the convergence of the aforementioned algorithms are not guaranteed in a straightforward manner. In fact, to the best of our knowledge, their finite convergence has not been explicitly proved for any interval 0-1 min-max regret problem. In this work, we formally describe these algorithms through the definition of a logic-based Benders' decomposition framework and prove their convergence to an optimal solution in a finite number of iterations. As this framework is applicable to any interval 0-1 min-max regret problem, its finite optimal convergence also holds in the cases where the separation subproblems are NP-hard.
Recommendations
- A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
- The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
- Logic-based Benders decomposition
- Robust min-max regret covering problems
- The robust shortest path problem with interval data via Benders decomposition
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Benders decomposition approach for the robust spanning tree problem with interval data
- A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
- A note on the selection of Benders' cuts
- Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
- An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
- Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
- Combinatorial Benders' cuts for the strip packing problem
- Computing and minimizing the relative regret in combinatorial optimization with interval data
- Discrete optimization with interval data. Minmax regret and fuzzy approach
- Exact and heuristic algorithms for the interval data robust assignment problem
- Generalized Benders decomposition
- Introduction to Stochastic Search and Optimization
- Logic-based Benders decomposition
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- On the complexity of a class of combinatorial optimization problems with uncertainty
- Partitioning procedures for solving mixed-variables programming problems
- Robust discrete optimization and its applications
- The robust set covering problem with interval data
- The robust shortest path problem with interval data via Benders decomposition
- The robust spanning tree problem with interval data
Cited in
(4)- Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
- Logic-based Benders decomposition for large-scale optimization
- Formulation and algorithms for the robust maximal covering location problem
- A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
This page was built for publication: On the finite optimal convergence of logic-based Benders' decomposition in solving 0-1 min-max regret optimization problems with interval costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835657)
