2
$\begingroup$

I'm working on a project which involves minimizing a particular objective function with respect to a set of linear constraints (i.e a Linear programming problem).

The twist is that, at every time step, my system receives one additional constraint, and must re-solve the linear program for all the previous constraints plus this new one.

My current solution is to feed all the constraints into a standard LP-solver (in this case, google-ortools) every time step. I treat every time step as a "fresh" problem, unrelated to the previous problems.

This feels inefficient to me. It feels intuitively like I should be able to leverage some information gathered in previous time steps to inform my answer in the current one (since the next time step is essentially exactly the same problem, but with one additional linear constraint).

Could someone either direct me to algorithms for efficiently solving a series of related LP-problems with incrementally increasing numbers of constraints or provide an explanation as to why their relatedness does not help, and the best thing to do is just start a standard LP-solver fresh each time.

$\endgroup$
  • 1
    $\begingroup$ Yes, most (simplex based) LP solvers can exploit this and use an advanced basis for subsequent solves. This can make a lot of difference in practice. $\endgroup$ – Erwin Kalvelagen Sep 15 '17 at 21:29
  • $\begingroup$ @ErwinKalvelagen This is useful to know that simplex based solvers can be exploited in this way. If you have time, could you provide a full answer which elaborates on how such exploitations are implemented in practice? (Or a reference to off-the-shelf solving software which provides such functionality) $\endgroup$ – Craig Innes Sep 19 '17 at 12:50
  • $\begingroup$ Gurobi Example, GAMS/Gurobi Example $\endgroup$ – Erwin Kalvelagen Sep 19 '17 at 15:15

Your Answer

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

Browse other questions tagged or ask your own question.