Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty

DOI10.1016/J.EJOR.2017.12.018zbMATH Open1403.90585arXiv1701.06317OpenAlexW2582217285MaRDI QIDQ723948FDOQ723948

Lisa Thom, Andrea Raith, Marie Schmidt, Anita Schöbel

Publication date: 25 July 2018

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

Abstract: In this paper we develop two approaches to find minmax robust efficient solutions for multi-objective combinatorial optimization problems with cardinality-constrained uncertainty. First, we extend an algorithm of Bertsimas and Sim (2003) for the single-objective problem to multi-objective optimization. We propose also an enhancement to accelerate the algorithm, even for the single-objective case, and we develop a faster version for special multi-objective instances. Second, we introduce a deterministic multi-objective problem with sum and bottleneck functions, which provides a superset of the robust efficient solutions. Based on this, we develop a label setting algorithm to solve the multi-objective uncertain shortest path problem. We compare both approaches on instances of the multi-objective uncertain shortest path problem originating from hazardous material transportation.

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

zbMATH Keywords

combinatorial optimizationmultiple objective programmingrobust optimizationshortest path problemmulti-objective robust optimization

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Combinatorial optimization (90C27) Sensitivity, stability, parametric optimization (90C31) Minimax problems in mathematical programming (90C47)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• GitHub
• The Price of Robustness
• Robust discrete optimization and network flows
• The relationship between multi-objective robustness concepts and set-valued optimization
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• An application of deterministic and robust optimization in the wood cutting industry
• On robust multiobjective optimization
• Robust multiobjective optimization \& applications in portfolio optimization
• Minmax robustness for multi-objective optimization problems
• Robust multiple objective game theory
• On a multicriteria shortest path problem
• Bi-objective robust optimisation
• Robustness for uncertain multi-objective optimization: a survey and analysis of different concepts
• An aggregate label setting policy for the multi-objective shortest path problem
• Generalized multiple objective bottleneck problems
• Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function
• A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty
• Decision uncertainty in multiobjective optimization
• Optimality and duality for robust multiobjective optimization problems

Cited In (13)

• Algorithms for the minmax regret path problem with interval data
• Facing robustness as a multi-objective problem: a bi-objective shortest path problem in smart regions
• Dominance for multi-objective robust optimization concepts
• Pareto solutions in multicriteria optimization under uncertainty
• The price of multiobjective robustness: analyzing solution sets to uncertain multiobjective problems
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
• Robust optimality conditions for multiobjective programming problems under data uncertainty and its applications
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• Extensions of labeling algorithms for multi‐objective uncertain shortest path problems
• Multiobjective optimization under uncertainty: a multiobjective robust (relative) regret approach
• Robust Optimality and Duality in Multiobjective Optimization Problems under Data Uncertainty
• Min-ordering and max-ordering scalarization methods for multi-objective robust optimization

Uses Software

• GitHub

Recommendations

• Title not available (Why is that?) 👍 👎
• Minmax robustness for multi-objective optimization problems 👍 👎
• Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty 👍 👎
• Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions 👍 👎
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets 👍 👎
• Min-max-min robust combinatorial optimization 👍 👎
• A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty 👍 👎
• Robust combinatorial optimization under convex and discrete cost uncertainty 👍 👎
• Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios 👍 👎
• Mixed uncertainty sets for robust combinatorial optimization 👍 👎

This page was built for publication: Multi-objective minmax robust combinatorial optimization with cardinality-constrained uncertainty

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