A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

DOI10.1016/J.COR.2016.12.010zbMath1391.90504arXiv1609.09179OpenAlexW2526392488WikidataQ56523986 ScholiaQ56523986MaRDI QIDQ1652219

Thiago F. Noronha, Andréa Cynthia Santos, Lucas Assunção, Rafael Andrade

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

robust optimizationmatheuristicsBenders' decomposition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

The robust (minmax regret) assembly line worker assignment and balancing problem ⋮ Robust min-max regret covering problems ⋮ Minmax regret maximal covering location problems with edge demands ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ Logic-Based Benders Decomposition for Large-Scale Optimization ⋮ A dynamic reformulation heuristic for generalized interdiction problems

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
• The robust set covering problem with interval data
• Pinpointing the complexity of the interval min-max regret knapsack problem
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• The computational complexity of the relative robust shortest path problem with interval data
• Exact and heuristic algorithms for the interval data robust assignment problem
• Reduction approaches for robust shortest path problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Restricted robust uniform matroid maximization under interval uncertainty
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Partitioning procedures for solving mixed-variables programming problems
• Robust discrete optimization and its applications
• Algorithms for railway crew management
• Logic-based Benders decomposition
• Local branching
• A branch and bound algorithm for the robust shortest path problem with interval data.
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• Interval data minmax regret network optimization problems
• An exact algorithm for the robust shortest path problem with interval data
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• A Benders decomposition approach for the robust spanning tree problem with interval data
• The robust shortest path problem with interval data via Benders decomposition
• The shortest route problem with constraints
• Generalized Benders decomposition
• A note on the selection of Benders' cuts
• A survey of resource constrained shortest path problems: Exact solution approaches
• On the Finite Optimal Convergence of Logic-Based Benders’ Decomposition in Solving 0–1 Min-Max Regret Optimization Problems with Interval Costs
• The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• Shortest chain subject to side constraints
• An algorithm for the resource constrained shortest path problem
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Approximation Schemes for the Restricted Shortest Path Problem
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• Introduction to Stochastic Search and Optimization
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• Algorithms for the set covering problem
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data

This page was built for publication: A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs