most recent 30 from http://mathoverflow.net 2013-05-22T07:08:26Z http://mathoverflow.net/feeds/question/104500 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104500/cascading-minimization-problems ashade 2012-08-11T16:41:25Z 2012-08-11T17:35:29Z

<p>Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. Therefore, I have a cascaded optmization problem. Is there anyway to combine them in a single optimization problem?</p>

http://mathoverflow.net/questions/104500/cascading-minimization-problems/104502#104502 Brian Borchers 2012-08-11T17:35:29Z 2012-08-11T17:35:29Z

<p>You can solve the first LP, obtain the optimal value, and then add a constraint that the first objective has that optimal value. Then you can add your second set of constraints to the original set of constraints and solve that LP. e.g. if your original LP is </p> <p>$\max c^{T}x $</p> <p>subject to </p> <p>$Ax=b$</p> <p>$x \geq 0$</p> <p>Suppose the optimal objective value is $p^{*}$. Now suppose you want to solve a second problem</p> <p>$\max d^{T}x $</p> <p>subject to</p> <p>$ Fx=g$</p> <p>$ x \in U$</p> <p>This can be formulated as </p> <p>$\max d^{T}x $</p> <p>subject to </p> <p>$Ax=b$</p> <p>$c^{T}x=p^{*}$</p> <p>$Fx=g$</p> <p>$x \ge 0$</p> <p>Most simplex based LP codes can efficiently reoptimize after adding the additional constraints. </p>