0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ This question requires some more work on part of the OP---as currently written it seems somewhat vague and open to misinterpretation... $\endgroup$
    – Suvrit
    Commented Aug 11, 2012 at 16:43
  • $\begingroup$ Actually it is pretty clear... I am talking about 2 linear programming problems where the domain of the second equalsthe solution set of the first. $\endgroup$
    – ashade
    Commented Aug 11, 2012 at 17:21

1 Answer 1

3
$\begingroup$

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

$\max c^{T}x $

subject to

$Ax=b$

$x \geq 0$

Suppose the optimal objective value is $p^{*}$. Now suppose you want to solve a second problem

$\max d^{T}x $

subject to

$ Fx=g$

$ x \in U$

This can be formulated as

$\max d^{T}x $

subject to

$Ax=b$

$c^{T}x=p^{*}$

$Fx=g$

$x \ge 0$

Most simplex based LP codes can efficiently reoptimize after adding the additional constraints.

$\endgroup$
1
  • $\begingroup$ Brilliant answer. $\endgroup$
    – ashade
    Commented Aug 11, 2012 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.