On the finite optimal convergence of logic-based Benders' decomposition in solving 0-1 min-max regret optimization problems with interval costs

DOI10.1007/978-3-319-45587-7_1zbMATH Open1419.90090arXiv2001.00943OpenAlexW2514449360MaRDI QIDQ2835657FDOQ2835657

Authors: Lucas Assunção, Andréa Cynthia Santos, Thiago F. Noronha, Rafael Andrade Edit this on Wikidata

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Minimax problems in mathematical programming (90C47)

Cites Work

• Title not available (Why is that?)
• Introduction to Stochastic Search and Optimization
• Partitioning procedures for solving mixed-variables programming problems
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• Robust discrete optimization and its applications
• Logic-based Benders decomposition
• Generalized Benders decomposition
• A note on the selection of Benders' cuts
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• The robust shortest path problem with interval data via Benders decomposition
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data
• A Benders decomposition approach for the robust spanning tree problem with interval data
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• The robust set covering problem with interval data
• Exact and heuristic algorithms for the interval data robust assignment problem
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• Combinatorial Benders' cuts for the strip packing problem

Cited In (4)

• Formulation and algorithms for the robust maximal covering location problem
• Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• Logic-based Benders decomposition for large-scale optimization

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)