4
$\begingroup$

I have multiple linear programming problems of the form:

$$ Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0 $$

Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a more efficient solution than solving each problem from scratch?

Currently I'm using scipy's linprog but the performance is too slow given the amount of problems (thousands). I was wondering if there's a way to make this feasible with some smart preprocessing.
I've tried searching using terms such as "repeated linear programming", "repeated simplex" etc., but to no avail.

$\endgroup$
1
  • $\begingroup$ For future reference, I've asked this question on math overflow where it was proposed to search for warm-start LP solvers and use the dual simplex algorithm. $\endgroup$ – andersource Aug 18 '20 at 4:25

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.