Saddle point approximation approaches for two-stage robust optimization problems
- PDF / 424,352 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 169 Views
Saddle point approximation approaches for two-stage robust optimization problems Ning Zhang1 · Chang Fang2 Received: 1 March 2019 / Accepted: 30 September 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract This paper aims to present improvable and computable approximation approaches for solving the two-stage robust optimization problem, which arises from various applications such as optimal energy management and production planning. Based on sampling finite number scenarios of uncertainty, we can obtain a lower bound approximation and show that the corresponding solution is at least ε-level feasible. Moreover, piecewise linear decision rules (PLDRs) are also introduced to improve the upper bound that obtained by the widely-used linear decision rule. Furthermore, we show that both the lower bound and upper bound approximation problems can be reformulated into solvable saddle point problems and consequently be solved by the mirror descent method. Keywords Two-stage robust optimization · Randomized approach · Piecewise linear decision rule · Saddle point problem · Mirror descent algorithm
1 Introduction In the real world, many decisions have to be made before all the information are known. Especially in intelligent manufacturing, many decisions have to consider the risk of uncertainty. For example, inventory control in intelligent manufacturing system must depend on forecast demands, which must consider many factors such as market outlook, transportation costs, seasonality, and so forth [33]. Another example is aggregate production planning in
This author is supported by the National Natural Science Foundation of China (No. 71801005), the Natural Science Foundation of Anhui Province (Nos. 1808085QG227, 1608085MG152), and the Social Sciences Foundation of Anhui Province (No. AHSKQ2016D28).
B
Chang Fang [email protected] Ning Zhang [email protected]
1
School of Computer Science and Technology, Dongguan University of Technology, Dongguan 523808, Guangdong, China
2
School of Economics and Management, Anhui Normal University, 189 Jiuhua South Road, Wuhu City 241002, Anhui, China
123
Journal of Global Optimization
the automotive production system, which is challenged by fierce competition, high product variety, short life cycles, and unreliable demand forecasts [7]. The network flow structure is one of the most important strategic layer problems in intelligent systems [34,41], which is the second stage decision problem in the following problems: supply chain planning [5,7], optimal energy management [24], unit commitment problems [2,36], vehicle routing problems [1], and location transportation problems [4,19]. This motivates us to study two-stage robust optimization problems. In this paper, we consider a general formulation of the two-stage robust optimization (RO) in the following form: (1.1) min x∈X c T x + maxξ ∈U Q(x, ξ ) , where
Q(x, ξ ) := min q T y| T (ξ )x + W y ≤ h(ξ ) . y∈Y
(1.2)
Here, X ⊆ n and Y ⊆ m are two non-empty convex sets, x is the first s
Data Loading...
