1

I'm attempting to write a MPS to custom format converter for a generalized simplex algorithm and I am running into a couple of difficulties.

According to this tutorial on the Big-M method for finding a basic feasible solution the following is necessary for an alternative approach, an all slack solution.

In my examples so far, I have looked at problems that, when put into standard LP form, conveniently have an all slack starting solution. An all slack solution is only a possibility when all of the constraints in the problem have <= inequalities.

Granted this url identifies itself as a business course so the level of rigor may not be great. In any case the language it uses is that it is necessary. First off, I am wondering if this is true.

However it will be even more useful for me if it is sufficient. I don't need it to be necessary. Is it known whether sufficiency is true for this condition?

Meadowlark Bradsher
  • 150
  • 1
    Use your intuition: adding one slack variable to each $\le$ constraint implies that your initial basis will be the identity matrix. Hence, if all your constraints are of this type you will always have a BFS. But it is not necessary, as the trivial example $\max{x_1+x_2}$ s.t. $x_1 \le 3, x_2 \le 5$ shows. – baudolino Apr 25 '14 at 02:21
  • Hence if I am using a non-standard form (introducing negative RHS) I can easily convert $x\geq b$ and $x=b$ into one or more $x'\leq b'$ and side step the trouble of Big-M. Thank you! – Meadowlark Bradsher Apr 25 '14 at 02:37
  • Most of the modern simplex implementations use the Two-phase approach, where Phase 1 solves a smaller LP to create an initial bfs which is then passed to Phase II. You could check out that paradigm as well. – baudolino Apr 25 '14 at 15:06

0 Answers0