1 Papers B. and Sim, The Price of Robustness, Operations Research, 2003. B. and Sim, Robust Discrete optimization, Mathematical Programming, 2003. 2 Structure Slide 1 Slide 2 Motivation Data Uncertainty Robust Mixed Integer Programming Robust 0-1 Programming Robust Approximation Algorithms Robust Network Flows Experimental Results Summary and Conclusions 3 Motivation The classical paradigm in optimization is to develop a model that assumes that the input data is precisely known and equal to some nominal values. This approach, however, does not take into account the inuence of data uncertainties on the quality and feasibility of the model. Can we design solution approaches that are immune to data uncertainty, that is they are robust? Ben-Tal and Nemirovski (2000): In real-world applications of Linear Programming (Net Lib library), one cannot ignore the possibility that a small uncertainty in the data can make the usual optimal solution completely meaningless from a practical viewpoint. 1 Slide 3 Slide 4 3.1 Literature Ellipsoidal uncertainty Robust convex optimization Ben-Tal and Nemirovski (1997), El-Ghaoui et. al (1996) Flexible adjustment of conservativism Nonlinear convex models Not extendable to discrete optimization 4 Goal Develop an approach to address data uncertainty for optimization problems that: It allows to control the degree of conservatism of the solution It is computationally tractable both practically and theoretically. 5 Data Uncertainty minimize c x subject to Ax b 0 Slide 5 Slide 6 Slide 7 lxu xi 2 Z i = 1 ::: k WLOG data uncertainty aects only A and c, but not the vector b. (Uncertainty for matrix A): aij j 2 Ji is independent, symmetric and bounded random variable (but with unknown distribution) a~ij j 2 Ji that takes values in aij ; a^ij aij + a^ij ]. (Uncertainty for cost vector c): cj j 2 J0 takes values in cj cj + dj ]. 6 Robust MIP Consider an integer ;i 2 0 jJij], i = 0 1 : : : m. ;i adjusts the robustness of the proposed method against the level of conservativeness of the solution. Speaking intuitively, it is unlikely that all of the aij , j 2 Ji will change. We want to be protected against all cases that up to ;i of the aij 's are allowed to change. Nature will be restricted in its behavior, in that only a subset of the coecients will change in order to adversely aect the solution. 2 Slide 8 Slide 9 Slide 10 We will guarantee that if nature behaves like this then the robust solution will be feasible deterministically. Even if more than ;i change, then the robust solution will be feasible with very high probability. 6.1 Problem minimize subject to (X c x + f 0 j 0 max 0 j 0 j;0 g 0 S X S aij xj xi S j S 2Z S J 8 =1 i Slide 11 j j dj xj 2 (0 S + f j maxj j; g i i i i i lxu j J ) S X j 2 ) ^ j j b aij xj i Slide 12 The robust problem can be reformulated has an equivalent MIP: minimize X c0 x + z0 ;0 + P 2 X p0 0 subject to a x +z ; + p b 8i j j i i 0 ; 2Z 0 + p0j j J j z j ij 2 i 8 2 0 8 6= 0 2 8 2 8 8 Ji dj yj j + p a^ zi ij yj ij pij yj zi yj lj xj yj xj J i j i j Ji j i =1 6.3 Proof (X S S J ij S j X (x� ) = max 2 X j s:t: j ij Ji 2 zij Ji ij i (x� ) = min s:t: X j 2 zi pij ij j ; 1 i 8 2 i j Ji : +; z i i + p a^ jxj 8j 2 J 0 8j 2 J 0 8i: Ji ij pij zi : j S ^a jx jz 0z Dual: k: ) (x� ) = f j maxj j�; g ^a jx j i i i i i 2i i ::: Slide 13 Given a vector x� , we de ne: This equals to: Ji j uj xi i i : : : k: 6.2 Theorem 1 ij 8 Si ij j i i 3 Slide 14 jJij ;i 5 5 10 8.3565 100 24.263 200 33.899 Table 1: Choice of ;i as a function of jJi j so that the probability of constraint violation is less than 1%. 6.4 Size Original Problem has n variables and m constraints P Robust counterpart has 2n + m + l variables, where l = mi�0 jJi j is the number of uncertain coecients, and 2n + m + l constraints. Slide 15 6.5 Probabilistic Guarantee 6.5.1 Theorem 2 Let x be an optimal solution of robust MIP. (a) If A is subject to the model of data uncertainty U: 8 X ! 9 < = X X + Pr ~ 21 :(1 ; ) �b c �b c+1 � n aij xj > bi n j l n n l = jJ j, = ;i2+ and = ; b c bound is tight. (b) As n ! 1 n n l Slide 16 l n i 8 1 <(1 ; ) X + 2 : �b c n n l n l 9 X = n n �b c+1 l l subject to iX 2N i2N : Slide 19 ci xi wi xi b x 2 f0 1gn: 4 Slide 17 Slide 18 7.1 Knapsack Problems X i n 7 Experimental Results maximize 1 ; ;p; 1 0 10 Approx bound Bound 2 −1 10 −2 10 −3 10 −4 10 0 1 2 3 4 5 Γ 6 7 8 9 10 i ; Violation Probability Optimal Value Reduction 0 0.5 5592 0% ; 1 2.8 4:49 10 5585 0.13% 5:71 10;3 36.8 5506 1.54% 5:04 10;9 82.0 5408 3.29% 0 200 5283 5.50% w~i are independently distributed and follow symmetric distributions in wi ; i wi + i ] c is not subject to data uncertainty. 7.1.1 Data jN j = 200, b = 4000, wi randomly chosen from f20 21 : : : 29g. ci randomly chosen from f16 17 : : : 77g. i = 0:1wi. 5 Slide 20 7.1.2 Results Slide 21 8 Robust 0-1 Optimization Slide 22 Nominal combinatorial optimization: minimize c0x subject to x 2 X f0 1g n : Robust Counterpart: Z = minimize subject to c x + f j maxj j�;g 0 S x2 S J S X j 2 dj xj S X WLOG d1 d2 : : : d . n 8.1 Remarks Examples: the shortest path, the minimum spanning tree, the minimum assignment, the traveling salesman, the vehicle routing and matroid intersection problems. Other approaches to robustness are hard. Scenario based uncertainty: minimize max(c1 x c2 x) subject to x 2 X: is NP-hard for the shortest path problem. 0 0 8.2 Approach Primal :Z � = xmin c x + max 2X 0 X j Dual :Z � = xmin c x + min ; + 2X 0 X j 8 j 8 j yj s:t: yj + dj xj yj 0 6 Slide 24 dj xj uj s:t: 0 uj 1 X uj ; j Slide 23 8.3 Algorithm A Slide 25 Solution: yj = max(dj xj ; 0) Z � = x2min ; + X �0 X j (cj xj + max(dj xj ; 0)) Since X f0 1gn, max(dj xj ; 0) = max(dj ; 0) xj Z � = x2min ; + X �0 1 2 For +1 , d d dl ::: dn X j (cj + max(dj ; 0)) xj Slide 26 +1 = 0: dn dl ; + x2 min l l+1 X d dl Z = X n d ; + xmin 2 X j �1 n X j cj xj �1 l ::: n l X j j (d ; d )x = Z n X �1 j �1 (d ; )x = j X j l l j + min +1 d ; + xmin 2 �1 X + cj xj cj xj �1 l + X l l (d ; d )x j j 8.4 Theorem 3 j �1 l j: Algorithm A correctly solves the robust 0-1 optimization problem. It requires at most jJ j + 1 solutions of nominal problems. Thus, If the nominal problem is polynomially time solvable, then the robust 0-1 counterpart is also polynomially solvable. Robust minimum spanning tree, minimum assignment, minimum matching, shortest path and matroid intersection, are polynomially solvable. Slide 27 9 Experimental Results 9.1 Robust Sorting minimize subject to X 2 X i Slide 28 c i xi N 2 xi =k x 2 f0 1g i 7 N n : (;) % change in Z(;) 0% 8822 0.056 % 8827 1.145 % 8923 2.686 % 9059 9.125 % 9627 13.91 % 10049 15.00 % 10146 17.38 % 10355 20.37 % 10619 20.37 % 10619 ; 0 10 20 30 40 50 60 70 80 100 (;) % change in (;) 501.0 0.0 % 493.1 -1.6 % 471.9 -5.8 % 454.3 -9.3 % -20.9 % 396.3 -25.8 % 371.6 -27.0 % 365.7 -29.6 % 352.9 -31.6 % 342.5 -32.1 % 340.1 Z Z (;) = minimize subject to c x + f j maxj j�;g X 0 S xi 2 S J S =k x 2 f0 1g i N n X j 2 dj xj S : 9.1.1 Data Slide 29 jN j = 200 k = 100 cj U 50 200] dj U 20 200] For testing robustness, generate instances such that each cost component independently deviates with probability = 0:2 from the nominal value cj to cj + dj . 9.1.2 Results Slide 30 10 Robust Network Flows Nominal min s:t: X X (i j)2A cij xij f :( )2Ag j xij i j ; X f :( )2Ag j Slide 31 xji =b 0x u X set of feasible solutions ows. Robust X Z = min c0x + f j max A j j;g ( )2 subject to x 2 X: ij ij S S S i j 8 8 2N 8( ) 2 A i i j i S i j dij xij : (cost,capacity) (cij,uij) i j ) ,f (d ij i i’ j’ (0, f) j (0,θ/ dij) (cij,uij) 10.1 Reformulation Slide 32 Z = min Z () 0 X c x+ ( ) = ; + min 0 Z 0 x2 subject to pij pij (i j)2A ; dij xij 8( ) 2 A 8( ) 2 A i j pij i j X: Equivalently c x+ ( ) = ; + min X 0 Z x2 subject to (i j)2A dij max xij ; dij 0 X: 10.2 Network Reformulation Theorem: For xed we can solve the robust problem as a network ow problem 10.3 Complexity Slide 34 0, we have j ( 1 ) ; ( 2 )j jAjj 1 ; 2 j ( ) is a convex function and for all 1 Z Z 2 Z : For any xed ; jAj and every > 0, we can nd a solution x^ 2 X with robust objective value X ^ = c0 x^ + d x ^ Z max f j A j j;g S such that Z S S (i j)2S ij ij Z^ (1 + )Z by solving 2dlog 2 (jAj=)e + 3 network ow problems, where = maxfu (i j ) 2 Ag. 9 Slide 33 ij dij : 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 11 Experimental Results 11.1 Shortest Path 12 Conclusions Robust counterpart of a MIP remains a MIP, of comparable size. Approach permits exibility of adjusting the level of conservatism in terms of probabilistic bound of constraint violation For polynomial solvable 0-1 optimization problems with cost uncertainty, the robust counterpart is polynomial solvable. Robust network ows are solvable as a series of nominal network ow problems. Robust optimization is tractable for stochastic optimization problems without the curse of dimensionality 10 Slide 35 Slide 36 Slide 37 Slide 38 3000 Γ=0 Γ=3 Γ=6 Γ = 10 2500 2000 1500 1000 500 0 3 4 5 6 Distributions of path cost 11 7 8 9