Discrete OptimizationBi-objective robust optimisation
Introduction
Many real-world optimisation problems are modelled as bi- or multi-objective optimisation problems (MOP) acknowledging that many decisions are based on multiple conflicting objectives (Ehrgott, 2005). On the other hand, real-world optimisation problems often depend on uncertain parameters, such as weather conditions, uncertain processing times, or delays in public transportation systems. To deal with this uncertainty, different approaches such as stochastic optimisation (Birge & Louveaux, 1997) and robust optimisation (Ben-Tal, Ghaoui, & Nemirovski, 2009) have been developed.
As much attention has been given to both MOPs and robust optimisation, a natural next step is the combination of the two concepts. In this paper we analyse such a combination for bi-objective optimisation problems with one uncertain objective: where is the feasible set, the first objective is z1 and the second uncertain objective is z2(x, ξ) which depends on an uncertain parameter ξ, see Section 4. Such problems arise in many application areas, e.g., in the aircraft route guidance problem or when shipping hazardous materials; see Section 8 for details.
Section snippets
Related work
The need to combine robust and multi-objective optimisation has been recognised in the literature and has led to the development of different concepts of efficiency under uncertainty. This issue has been described recently in the survey by Ide and Schöbel (2016). Also see the overview given by Goberna, Jeyakumar, Li, and Vicente-Prez (2015). We review the relevant parts.
There are two rather straightforward ways for defining robust efficient (RE) solutions for multi-objective optimisation. The
Background
In Section 4 we define a robust solution to an uncertain optimisation problem such as (1), i.e., we combine robust and multi-objective optimisation. Before doing so, we discuss basic concepts of both fields in Sections 3.1 and 3.2.
Problem definition
We consider an uncertain bi-objective optimisation problem where a solution x has to be chosen from a given set of feasible solutions. Every is assigned an objective value and a second objective value which is uncertain, since the parameter ξ is not known. We assume that for some uncertainty set which is a subset of some vector space.
In this paper we make the following assumptions:
- •
is continuous,
- •
is continuous for every fixed and for every
Extension to PRO RE solutions and related multi-objective problems
Iancu and Trichakis (2014) deal with single-objective robust optimisation problems and use the concept of efficiency to refine the definition of (single-objective) strict robustness. Their idea is as follows. The ‘traditional’ set of strictly RE solutions contains all solutions which minimise the objective value in the worst case; however, some of these solutions would not be considered reasonable in any practical setting. Consider a solution x which is not better than another solution y
An algorithm for bi-objective combinatorial optimisation problems with finite uncertainty set
We can use the insights gained in Observations 1 and 2 to compute the sets of flimsily, highly, strictly, and ε-representative lightly PRO RE solutions in two steps.
- 1.
Solve a deterministic MOP w.r.t. ζ and obtain a complete set of efficient solutions,
- 2.
Filter among the efficient solutions found in Step 1 for flimsily/highly/strictly/ε-representative lightly PRO RE solutions.
The applicability and efficiency of this approach depends on the algorithms available for the two steps. For the first step,
Bi-objective optimisation problems with polyhedral uncertainty sets
In this section we turn our attention to the second type of uncertainty set, namely to the case in which is a polytope, i.e., Note that the assumption of a polyhedral uncertainty set is not unrealistic. As a special case it includes interval-based uncertainty which is (apart from finite uncertainty sets) probably the most considered case in uncertain single-objective optimisation (e.g. Bertsimas, Sim, 2004, Ben-Tal, Nemirovski, 2000).
Applications and experimental results
We present two real-world applications which are modelled as bi-objective robust optimisation problems with one uncertain objective.
Conclusions
We compare four different robustness concepts for bi-objective optimisation with one uncertain objective function and propose an algorithm for the most common case of finite or polyhedral uncertainty sets. From our experience with two real-world applications we conclude that robust efficient solutions to such problems can be computed in a reasonable time, and that different types of robust solutions can be identified. Comparing the four concepts, representative light robustness turns out to be
Acknowledgment
This research has been partially supported by the European Union Seventh Framework Programme (FP7-PEOPLE-2009-IRSES) under grant agreement no 246647 and by the New Zealand Government (grant 649378 v2) as part of the OptALI project. Furthermore, Andrea Raith has been partially supported by the Marsden Fund under grant number UOA1008, Marie Schmidt by grant SCHO 1140/3-2 of DFG, and Kenneth Kuhn by NASA grant NNA14AB47C.
References (44)
- et al.
Minmax robustness for multi-objective optimization problems
European Journal of Operational Research
(2014) - et al.
Hazardous materials transportation
- et al.
Robust aspects of solutions in deterministic multiple objective linear programming
European Journal of Operational Research
(2013) - et al.
Robust solutions to multi-objective linear programs with uncertain data
European Journal of Operational Research
(2015) - et al.
On the cardinality of the Pareto set in bicriteria shortest path problems
Annals of Operations Research
(2006) Convex programming with set-inclusive constraints and applications to inexact linear programming
Operations Research
(1973)- Bar-Gera, H. last visited june 2013. transportation network test problems. Online....
- et al.
Robustness analysis in multi-objective optimization using a degree of robustness concept
IEEE congress on evolutionary computation. CEC 2006.
(2006) Mixed route strategies for the risk-averse shipment of hazardous materials
Networks and Spatial Economics
(2006)- et al.
Robust Optimization
(2009)
Robust convex optimization
Mathematics of Operations Research
Robust solutions of linear programming problems contaminated with uncertain data
Mathematical Programming A
The price of robustness
Operations Research
Introduction to Stochastic Programming
Linear multiple objective problems with interval coefficients
Management Science
Creating robust solutions by means of evolutionary algorithms
Including robustness in multi-criteria optimization for intensity-modulated proton therapy
Physics in Medicine and Biology
Introducing robustness in multi-objective optimization
Evolutionary Computation
Searching for robust pareto-optimal solutions in multi-objective optimization
A robust multiobjective optimization problem with application to internet routing
Tech. Rep. R2012-11-DKW, Clemson University
Multicriteria optimization
Multiobjective combinatorial optimization – theory, methodology, and applications
Cited by (48)
Bi-objective scenario-guided swarm intelligent algorithms based on reinforcement learning for robust unrelated parallel machines scheduling with setup times
2023, Swarm and Evolutionary ComputationA pareto-based multi-objective network design approach for mitigating the risk of hazardous materials transportation
2022, Process Safety and Environmental ProtectionMultiobjective optimization under uncertainty: A multiobjective robust (relative) regret approach
2022, European Journal of Operational ResearchMulti-scenario multi-objective robust optimization under deep uncertainty: A posteriori approach
2021, Environmental Modelling and SoftwareAnalysis of different risk models for the hazardous materials vehicle routing problem in urban areas
2021, Cleaner Environmental Systems