10
$\begingroup$

I have the following LP:

/* Objective function */
min: 1 w + 2 x + 0.5 y + z;

/* Variable bounds */
w + x <= T1;
w + y = U1;
x + z = U2;
T1 = 50;
U1 = 70;
U2 = 25;

In this case U1 + U2 > T1 and the optimal solution is y = 70 and z = 25. I want to enforce the condition that w and x variables be assigned values before assigning values to y and z. If U1 + U2 < T1, then I want only w and x to have values and y = z = 0. Is there a way to enforce such a constraint in an LP or an MILP?

$\endgroup$
  • $\begingroup$ not sure why the downvote: it's a reasonable, albeit narrow question in LPs $\endgroup$ – Suresh Venkat Nov 1 '10 at 7:42
11
$\begingroup$

Here are answers to your two questions. The details will depend upon which solver you are using:

  • Ensuring that $w$ and $x$ are assigned values before $y$ and $z$ can often be done programmatically by expressing the variable ordering used by the solver. That is, specifying which variables the solver tries to find values for first. This is possible, for example, in the choco solver (which is a constraint satisfaction problem (CSP) solver not one for LP or MILP), though I'm sure other solvers offer this possibility too.

  • The GNU Linear Programming Kit actually has an if-then-else construct for expressing conditionals. Look for "conditional" in the manual. You could wrap the clauses you are interested in in such a statement: if U1 + U2 < T2 then y = 0 and z = 0 else true. (Note that I haven't actually tried this, so the syntax may be wrong.)

  • An alternative answer to the second question takes advantage of the fact that $U1$, $U2$ and $T1$ are constants. Simply, have two variants of the LP problem, one for when $U1 + U2 < T1$ and one for when $U1 + U2 \ge T1$.

$\endgroup$
  • $\begingroup$ Thanks for the options. I will go with option 3 for now. $\endgroup$ – Bala Nov 2 '10 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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