3

I have ~30 non-negative variables and 24 equations and I want to find out the upper and lower bound for each variable. Feasible solutions are guaranteed.

So for each variable, I solve two LP problem, one for min and one for max

$$ \begin{array}{rl} \min & c^T x\\ \textrm{s.t.} & Ax = b\\ &x\geq0 \end{array} $$

where $c=(0, 0, \dots, 0, 1, 0, \dots, 0)^T$ and $(0, 0, \dots, 0, -1, 0, \dots, 0)^T$.

So in total I have 60 LPs with exactly the same constraint, but slightly different objective. I have to do the same thing for each day's data for a few thousand days.

Is there a way to somehow reuse the intermediate results to speed up the calculation? Is it possible to implement using existing Python or R package?

Edit: Just to add that for each day, only the rhs $b$ is different, everything else stays the same.

jf328
  • 482
  • 2
  • 8
  • What changes from day to day? I don't see how anything could be reused for your 60 runs in each day, but I could imagine re-using things from one day to the next. – Wolfgang Bangerth Nov 23 '18 at 23:44
  • 1
    Do you expect the LP to have similar solutions on successive days? If so, you can use the previous day’s solution as a starting basis for the next day. – Brian Borchers Nov 23 '18 at 23:45
  • 2
    That said, if you are using the usual two-phase algorithm for linear optimization, then the output of the first phase gives you a feasible vertex to start phase 2 with. This feasible vertex is feasible for any choice of $c$, and consequently you need to run phase 1 only once for all 60 problems. – Wolfgang Bangerth Nov 23 '18 at 23:45
  • @WolfgangBangerth, only the rhs $b$ changes every day. – jf328 Nov 24 '18 at 17:16
  • @jf328 from your question, it sounds like you are looking for feasible region for each variable, rather than solving the objective function, or were you tryingto say thatthe value required to minimizeandmaximizethe objective function, while talking about upper lower bound? – Güray Hatipoğlu Nov 24 '18 at 21:02
  • @GürayHatipoğlu, yes you are right. I'm looking for the feasible region (I guess it's just an interval) for each variable that $Ax=b, x\geq0$ holds, and I'm casting that as LPs. – jf328 Nov 24 '18 at 22:41

0 Answers0