$title Robust linear programming as an SOCP (ROBUSTLP,SEQ=416)$onText Consider a linear optimization problem of the form min_x c^Tx s.t. a_i^Tx <= b_i, i=1,..,m. In practice, the coefficient vectors a_i may not be known perfectly, as they are subject to noise. Assume that we only know that a_i in E_i, where E_i are given ellipsoids. In robust optimization, we seek to minimize the original objective, but we insist that each constraint be satisfied, irrespective of the choice of the corresponding vector a_i in E_i. We obtain the second-order cone optimization problem min_x c^Tx s.t. a'_i^Tx + ||R_i^Tx|| <= b_i, i=1,..,m, where E_i = { a'_i + R_iu | ||u|| <= 1}. In the above, we observe that the feasible set is smaller than the original one, due to the terms involving the l_2-norms. The figure above illustrates the kind of feasible set one obtains in a particular instance of the above problem, with spherical uncertainties (that is, all the ellipsoids are spheres, R_i = rho I for some rho >0). We observe that the robust feasible set is indeed contained in the original polyhedron. In this particular example we allow coefficients A(i,*) to vary in an ellipsoid. The robust LP is reformulated as a SOCP. Contributed by Michael Ferris, University of Wisconsin, Madison Lobo, M S, Vandenberghe, L, Boyd, S, and Lebret, H, Applications of Second Order Cone Programming. Linear Algebra and its Applications, Special Issue on Linear Algebra in Control, Signals and Image Processing. 284 (November, 1998). Keywords: linear programming, quadratic constraint programming, robust optimization, second order cone programming $offText$if not set mu \$set mu 1.0e-2 Set i / 1*7 / j / 1*4 /; Parameter b(i), c(j), A(i,j); b(i) = 1; c(j) = -1; option seed = 0; A(i,j) = uniform(0,1); Variable obj, x(j); Equation defobj, cons(i); defobj.. obj =e= sum(j, c(j)*x(j)); cons(i).. sum(j, A(i,j)*x(j)) =l= b(i); Model lpmod / defobj, cons /; solve lpmod using lp min obj; Parameter results(*,*); results('lp',j) = x.l(j); results('lp','obj') = obj.l; Scalar mu / %mu% /; Positive Variable lambda(j), gamma(j); Equation lpcons(i), defdual(j); * A(i,*) \in A(i,*) + [-mu(i) 1, mu(i) 1] (infty norm ball) * constraint is mu(i) * norm(x)_1 + Ax <= b (just use one mu here) * just implement one norm (dual of inf norm) using lambda and gamma lpcons(i).. mu*sum(j, lambda(j) + gamma(j)) + sum(j, A(i,j)*x(j)) =l= b(i); defdual(j).. lambda(j) - gamma(j) =e= x(j); Model lproblp / defobj, lpcons, defdual /; solve lproblp using lp min obj; results('roblp',j) = x.l(j); results('roblp','obj') = obj.l; Alias (j,k); Parameter P(i,j,k); P(i,j,j) = %mu%; Variable y(i), v(i,k); Equation defrhs(i), defv(i,k), socpcons(i); defrhs(i).. y(i) =e= b(i) - sum(j, A(i,j)*x(j)); defv(i,k).. v(i,k) =e= sum(j, P(i,j,k)*x(j)); Equation socpqcpcons(i); socpqcpcons(i).. sqr(y(i)) =g= sum(k, sqr(v(i,k))); Model roblpqcp / defobj, socpqcpcons, defrhs, defv /; y.lo(i) = 0; option qcp = cplexd; solve roblpqcp using qcp min obj; results('qcp',j) = x.l(j); results('qcp','obj') = obj.l; display results;