Min-max and min-max regret versions of combinatorial optimization problems: A survey

DOI10.1016/j.ejor.2008.09.012zbMath1159.90472OpenAlexW2028589351MaRDI QIDQ1014933

Hassene Aissi, Daniel Vanderpooten, Cristina Bazgan

Publication date: 30 April 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.09.012

zbMATH Keywords

complexityrobustnesscombinatorial optimizationapproximationmin-maxmin-max regret

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Facility layout problem with QAP formulation under scenario-based uncertainty ⋮ An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems ⋮ Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem ⋮ ROPI—a robust optimization programming interface for C++ ⋮ Choquet-based optimisation in multiobjective shortest path and spanning tree problems ⋮ Min‐Max quickest path problems ⋮ On the complexity of min-max-min robustness with two alternatives and budgeted uncertainty ⋮ Lawler's minmax cost problem under uncertainty ⋮ A robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ Exact solutions for the two-machine robust flow shop with budgeted uncertainty ⋮ Adjustable robust optimization with objective uncertainty ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions ⋮ Complexity results for common due date scheduling problems with interval data and minmax regret criterion ⋮ Approximating single- and multi-objective nonlinear sum and product knapsack problems ⋮ Data-driven robust optimization using deep neural networks ⋮ Robust permutation flow shop total weighted completion time problem: solution and application to the oil and gas industry ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective ⋮ Mathematical optimization models for reallocating and sharing health equipment in pandemic situations ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ Combinatorial optimization problems with balanced regret ⋮ Global solution of constrained min-max problems with inflationary differential evolution ⋮ Modeling the Emergency Service Network of Police Special Forces Units for High-Risk Law Enforcement Operations ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ Minimizing recovery cost of network optimization problems ⋮ Robust capacitated Steiner trees and networks with uniform demands ⋮ On the complexity of robust multi-stage problems with discrete recourse ⋮ Randomized strategies for robust combinatorial optimization with approximate separation ⋮ Min-max relative regret for scheduling to minimize maximum lateness ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ $$\beta $$ -Robustness Approach for Fuzzy Multi-objective Problems ⋮ Multi-material topology optimization for maximizing structural stability under thermo-mechanical loading ⋮ A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines ⋮ Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ An algebraic framework for multi-objective and robust variants of path problems ⋮ Robustness in Multi-criteria Decision Aiding ⋮ Extensions of labeling algorithms for multi‐objective uncertain shortest path problems ⋮ Clear Preferences Under Partial Distribution Information ⋮ Bulk-robust combinatorial optimization ⋮ Unnamed Item ⋮ The lexicographic α-robust knapsack problem ⋮ Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty ⋮ On the Finite Optimal Convergence of Logic-Based Benders’ Decomposition in Solving 0–1 Min-Max Regret Optimization Problems with Interval Costs ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities ⋮ JUST-IN-TIME SCHEDULING UNDER SCENARIO-BASED UNCERTAINTY ⋮ Representative scenario construction and preprocessing for robust combinatorial optimization problems ⋮ Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ Random walks on graphs with interval weights and precise marginals ⋮ Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Robust approach to restricted items selection problem ⋮ Robustness-based approach for fuzzy multi-objective problems ⋮ Minmax regret for sink location on dynamic flow paths with general capacities ⋮ Minmax robustness for multi-objective optimization problems ⋮ A largest empty hypersphere metaheuristic for robust optimisation with implementation uncertainty ⋮ Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios ⋮ Flexible here-and-now decisions for two-stage multi-objective optimization: method and application to energy system design selection ⋮ Algorithms and uncertainty sets for data-driven robust shortest path problems ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Heterogeneous beliefs, regret, and uncertainty: the role of speculation in energy price dynamics ⋮ An integrated approach for planning a long-term care network with uncertainty, strategic policy and equity considerations ⋮ Heuristic algorithms for the minmax regret flow-shop problem with interval processing times ⋮ The bipartite quadratic assignment problem and extensions ⋮ Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty ⋮ On the recoverable robust traveling salesman problem ⋮ On exact solutions for the minmax regret spanning tree problem ⋮ A minimum expected regret model for the shortest path problem with solution-dependent probability distributions ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Minmax regret combinatorial optimization problems with investments ⋮ Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty ⋮ The robust (minmax regret) assembly line worker assignment and balancing problem ⋮ Robust flows with losses and improvability in evacuation planning ⋮ A parameterized view to the robust recoverable base problem of matroids under structural uncertainty ⋮ The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective ⋮ A bicriteria approach to robust optimization ⋮ Robust min-max regret covering problems ⋮ Robust combinatorial optimization with locally budgeted uncertainty ⋮ Robust combinatorial optimization with knapsack uncertainty ⋮ Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty ⋮ The robust set covering problem with interval data ⋮ Coevolutionary makespan optimisation through different ranking methods for the fuzzy flexible job shop ⋮ Complexity and in-approximability of a selection problem in robust optimization ⋮ Computing knapsack solutions with cardinality robustness ⋮ Lexicographic \(\alpha \)-robustness: an alternative to min-max criteria ⋮ On recoverable and two-stage robust selection problems with budgeted uncertainty ⋮ Ranking robustness and its application to evacuation planning ⋮ Minimizing maximum cost for a single machine under uncertainty of processing times ⋮ A double oracle approach to minmax regret optimization problems with interval data ⋮ Approximating combinatorial optimization problems with the ordered weighted averaging criterion ⋮ On the approximability of robust spanning tree problems ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty ⋮ Mixed uncertainty sets for robust combinatorial optimization ⋮ Variable-sized uncertainty and inverse problems in robust optimization ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ A model predictive control approach to the periodic implementation of the solutions of the optimal dynamic resource allocation problem ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty ⋮ Algorithms for the minmax regret path problem with interval data ⋮ Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets ⋮ Exact and heuristic algorithms for the interval data robust assignment problem ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ Pinpointing the complexity of the interval min-max regret knapsack problem ⋮ Algorithms and complexity analysis for robust single-machine scheduling problems ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ Scenario based robust line balancing: Computational complexity ⋮ Min max min robust (relative) regret combinatorial optimization ⋮ Complexity of strict robust integer minimum cost flow problems: an overview and further results ⋮ Robust combinatorial optimization under budgeted-ellipsoidal uncertainty ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem ⋮ Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ Robust balanced optimization ⋮ Minimizing the weighted sum of completion times under processing time uncertainty ⋮ Formulation and algorithms for the robust maximal covering location problem ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ Compromise solutions for robust combinatorial optimization with variable-sized uncertainty ⋮ A single-machine scheduling problem with uncertainty in processing times and outsourcing costs ⋮ Complexity results and exact algorithms for robust knapsack problems ⋮ Superiority-inferiority modeling coupled minimax-regret analysis for energy management systems ⋮ A biobjective approach to recoverable robustness based on location planning ⋮ Robust unit commitment with \(n-1\) security criteria ⋮ Exact algorithms for OWA-optimization in multiobjective spanning tree problems ⋮ A note on upper bounds to the robust knapsack problem with discrete scenarios ⋮ Generating hard instances for robust combinatorial optimization ⋮ Oracle-based algorithms for binary two-stage robust optimization ⋮ Approximability of the robust representatives selection problem ⋮ A 2-approximation for minmax regret problems via a mid-point scenario optimal solution ⋮ Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty ⋮ Maximum excess dominance: identifying impractical solutions in linear problems with interval coefficients ⋮ Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ Pessimistic, optimistic, and minimax regret approaches for linear programs under uncertainty ⋮ Preference elicitation and robust winner determination for single- and multi-winner social choice ⋮ Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times ⋮ On scenario aggregation to approximate robust combinatorial optimization problems ⋮ Competitive difference analysis of the cash management problem with uncertain demands ⋮ The trouble with the second quantifier ⋮ Approximate cutting plane approaches for exact solutions to robust optimization problems ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems ⋮ An adaptive robust optimization model for parallel machine scheduling ⋮ Decision space robustness for multi-objective integer linear programming ⋮ Robust pricing for airlines with partial information

Cites Work

• Unnamed Item
• Unnamed Item
• A branch and bound algorithm for the robust spanning tree problem with interval data
• Complexity of the min-max and min-max regret assignment problems
• About the applicability of MCDA to some robustness problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Complexity of single machine scheduling problems under scenario-based uncertainty
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• Minimax regret solution to linear programming problems with an interval objective function
• On the robust shortest path problem.
• Minmax regret linear resource allocation problems.
• Robust discrete optimization and network flows
• A branch and bound algorithm for the robust shortest path problem with interval data.
• On the complexity of the robust spanning tree problem with interval data
• Minmax regret solutions for minimax optimization problems with uncertainty
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• Interval data minmax regret network optimization problems
• A heuristic to minimax absolute regret for linear programs with interval objective function coefficients
• An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
• An exact algorithm for the robust shortest path problem with interval data
• On the complexity of minmax regret linear programming
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion
• Robust optimization of contaminant sensor placement for community water systems
• 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 minmax regret permutation flow-shop problem with two jobs
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data
• The robust minimum spanning tree problem: compact and convex uncertainty
• Approximating Multiobjective Knapsack Problems
• Energy crop supply in France: a min-max regret approach
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• The Price of Robustness
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Combinatorial Problems: Reductibility and Approximation
• α-Reliable p-minimax regret: A new model for strategic facility location modeling
• Minimax regret p-center location on a network with demand uncertainty
• Minmax-regret robust 1-median location on a tree
• Robust solutions and methods in decision-aid
• Minmax Regret Median Location on a Network Under Uncertainty
• Robust Optimization of Large-Scale Systems
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• Multicriteria Optimization
• Algorithms and Computation
• Algorithms and Computation
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data