Combinatorial two-stage minmax regret problems under interval uncertainty
- PDF / 680,767 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 195 Views
Combinatorial two-stage minmax regret problems under interval uncertainty Marc Goerigk1 · Adam Kasperski2
· Paweł Zielinski ´ 2
Accepted: 3 November 2020 © The Author(s) 2020
Abstract In this paper a class of combinatorial optimization problems is discussed. It is assumed that a feasible solution can be constructed in two stages. In the first stage the objective function costs are known while in the second stage they are uncertain and belong to an interval uncertainty set. In order to choose a solution, the minmax regret criterion is used. Some general properties of the problem are established and results for two particular problems, namely the shortest path and the selection problem, are shown. Keywords Robust optimization · Combinatorial optimization · Minmax regret · Two-stage optimization · Complexity
1 Introduction Consider the following deterministic single-stage combinatorial optimization problem: opt P (cc ) = min c T x , x ∈X
(P )
where X ⊆ {0, 1}n is a set of feasible solutions and c ∈ Rn+ is a vector of nonnegative objective function costs. Typically, X is described by a system of linear constraints involving binary variables xi , i ∈ [n] (we will use the notation [n] = {1, . . . , n}), which leads to a 0-1 programming problem. Solution x ∈ X can be interpreted as a characteristic vector of some finite element set E. For example, E can be a set of edges of a graph G = (V , E) and x describes some objects in G such as paths, trees, matchings etc.
B
Adam Kasperski [email protected] Marc Goerigk [email protected] Paweł Zieli´nski [email protected]
1
Network and Data Science Management, University of Siegen, Siegen, Germany
2
Wrocław University of Science and Technology, Wrocław, Poland
123
Annals of Operations Research
In many practical applications the vector of objective function costs c is uncertain and it is only known to belong to an uncertainty set U . There are various methods of defining U which depend on the application and the information available. Among the easiest and most common is the interval uncertainty representation (see, e.g., Kouvelis and Yu 1997), in which ci ∈ [ci , ci ] for each i ∈ [n] and U = i∈[n] [ci , ci ] ⊆ Rn+ . In order to choose a solution, for a specified U , one can apply a robust decision criterion, which takes into account the worst cost realizations. Under the interval uncertainty representation, the minmax regret criterion (also called Savage criterion (Savage 1951)) has attracted a considerable attention in the literature. The regret of a given solution x ∈ X under a cost scenario c ∈ U is the quantity c T x − optP (cc ). It expresses a deviation of solution x from the optimum and can be interpreted as the maximal opportunity loss after x is implemented. In the single-stage minmax regret version of P we seek a solution minimizing the maximum regret, i.e. we study the following problem: min max(cc T x − opt P (cc )).
x ∈X c ∈U
(SStR P )
The SStR P problem has been discussed in a number of papers, for example when P is the
Data Loading...
