4
$\begingroup$

I'm working on an implementation of the simplex algorithm. I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem. I couldn't really say how much the next problem will be different from the one before.

This should be an illustrating example:

Problem 1:
3 supply points
4 demand points

total supply = 9
total demand = 9

Problem 2:
2 supply points
5 demand points

total supply = 10
total demand = 10

Problem 2 is the problem which follows on problem 1. The costs in between all points are known and linear to the transported good.

In Problem 2 one supply point became a demand point. Thus regarding the simplex there will be a change of my objective function and my restrictions.

Now my question: Could I warmstart problem 2 by using my optimal solution of problem 1? If so, how much could my problem 2 differ from problem 1 so warmstarting would still be possible? For some reason I can't really find literature on this.

Improve this question
$\endgroup$
1
  • $\begingroup$ If your warm-start from P1 can generate a feasible incumbent solution for P2, you will see some improvement in solving time otherwise most of the solvers just check the provided ws and continue their own routines in solving process. $\endgroup$
    – Oguz Toragay
    Apr 18, 2021 at 20:59

3 Answers 3

Reset to default
6
$\begingroup$

Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous solution into a feasible solution for the modified problem (which might not be easy, especially if a source becomes a sink or or if the network structure changes substantially), and would then require the solver to take your proposed solution and reverse-engineer a basis for it (unless you are going to use an interior point method). It's not clear if all that work would pay for itself.

If your problem is sufficiently different from a transportation problem that a starting basis is not obvious, and if you could extract from the previous optimal solution a pretty good (really good?) starting solution for the next problem, then it might be worthwhile.

Improve this answer
$\endgroup$
6
$\begingroup$

I actually have quite a few points. As usual, things are not as clear cut.

  1. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model.
  2. For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related solves (solved with an advanced basis). For NLPs this is similar: interior point for the first problem and active-set algorithms for subsequent solves.
  3. Your problem seems small so likely not much of an issue. Maybe your real problems are larger.
  4. Note that an advanced basis usually means: no presolve. That may be a downside. Solvers typically don't use a basis-preserving presolve algorithm. So you have to choose: using an advanced basis or doing a presolve. Sometimes there are ways to use an advanced basis on the presolved problem (too esoteric for me, so I have no experience with that).
  5. I always try these things out. Much better than guessing. My guesses are about 50% wrong, so I don't really trust them.
  6. For performance you may want to look into more specialized algorithms for transportation problems. Maybe a network algorithm, or something like an auction algorithm.
Improve this answer
$\endgroup$
2
$\begingroup$

Warm starting is used predominantly when solving problems that are only slightly different, and typically when only some coefficients have changed. The idea is that many of the feasible polyhedrons' vertices are shared between the two problems, therefore starting at a vertex that was good at a previous problem will save us pivot operations.

If the problems are more than "slightly different", the chances of putting previous information to good use vanish for this very reason, there is little chance that the warm-starting vertex will be anywhere near the optimum, nor even feasible for that matter.

What's even harder though is that if the two problems have different dimensionality you would need to somehow manually convert the solution of the first problem to the dimensions of the second one.

In some cases this makes sense. For instance, if there is a block of logic that is common between the two problems, say some connectivity constraints, then that information could conceivably carry over well, assuming that you make sure that the variables of the first problem are properly mapped to reflect what's happening in the second one.

To make a long story short, you might be able to derive a meaningful connection if you work on this hard enough, but at potentially minimal tradeoff.

Improve this answer
$\endgroup$

Your Answer

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

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