In some linear program that is hard to find an initial feasible point, simplex method will fail in its phase one algorithm. But we can find such a feasible point through other method such as genetic algorithm: the problem is such solution may have many "noise" of small numbers for some coordinate. We want to use simplex to finish up such a solution that will eliminate those noise. But simplex method will not use the user provided x0. There is a proposed linear thansformation method to change the original problem so that 0 will be the original x0 and circumvent that restriction of simplex: https://scicomp.stackexchange.com/a/7699/4584. This method need additional work on reformate the problem. Is there more easy solution, such as modify a few lines of the code of simplexphaseone so that x0 will be used directly?


I don't understand how you got to this question because the phase 1 of the simplex algorithm is designed specifically to find a feasible point of the original problem from which phase 2 can start. There is no need to use a genetic algorithm or similar to find a better starting point.

But other than that, your question is very much specific to one particular implementation you appear to be using, but about which you tell us nothing. Clearly, if you implement the simplex method yourself, it is easy to just skip phase 1 and start phase 2 from somewhere. It's your code, you can implement it however you want. But if it's not a code you have written yourself you oftentimes do not have the luxury to just start it with phase 2. In that case, the easiest choice of course is to use it as is, i.e., including phase 1, since phase 1 is guaranteed to give you a starting point. If phase 1 fails, you need to explain to us

  • what implementation you are using
  • how phase 1 fails
  • what the error message means that you get from your code.

It may be that your phase 1 fails because there is no feasible point in your linear program and, consequently, no starting point for phase 2 can be found. Of course, in that case, that's a situation that you won't be able to correct by using a different method to choose a starting point for phase 2.

  • $\begingroup$ Usually theoretically valid theory is not quite true in practice, for a linear program with about 100,000 variables and around same number of constraints, interior-point or active-set method in linprog from Matlab tested not work. Same with open source CLP, GLPK, LP-SOLVE and etc. Linprogramming from Mathematica cannot utilize sparse matrix and will crash out of not enough memory. Phase one in simplex method of Matlab can surpass 1 million iteration without get a feasible solution, which is obviously exist since we can get one from GA-MPC. $\endgroup$ – Frank Jun 24 '13 at 13:34
  • $\begingroup$ ..., which is obviously exist sincewe can get one from GA-MPC and transform the original problem as mentioned in the link. $\endgroup$ – Frank Jun 24 '13 at 14:03
  • $\begingroup$ But then, again, I don't see what you will gain by starting from a different point. The algorithm used in phase-1 is exactly the same as in phase-2 -- it's just run on a different problem. In other words, if your implementation runs out of memory in phase-1, it is likely going to run out of memory during phase-2 as well, regardless from where you start it. $\endgroup$ – Wolfgang Bangerth Jun 24 '13 at 17:30
  • $\begingroup$ @Frank: If you are at an academic institution, and you are solving an LP with 100000 variables, you should be using CPLEX or Gurobi to decide you are resource-constrained computationally. Both solvers are top of the line, an order of magnitude faster than the competition, have the best heuristics, and will select simplex or interior-point methods automatically based on preprocessing the problem. If that doesn't work, then you still have other options besides a genetic algorithm. $\endgroup$ – Geoff Oxberry Jun 25 '13 at 18:10
  • $\begingroup$ Thank you Geoff, aidic.it/cet/12/29/046.pdf have a graph compared cplex and linprog. $\endgroup$ – Frank Jun 28 '13 at 20:33

If a user provides a basic feasible solution to simplex, I don't see why one couldn't start directly with Phase 2 simplex. (In fact, solvers that combine interior-point methods and simplex methods transition from the interior-point method to the simplex method by using a "cross-over" to find a basic feasible solution from the current interior-point iterate.)

That said, Wolfgang is absolutely right: Phase I either finds a basic feasible solution to the problem, or it fails, in which case your linear program is infeasible.

It could be that you mean that Phase I takes too long, in which case I'd recommend using an interior point method. In fact, if you find any feasible solution, you can use it as a starting point to an interior point method, whereas simplex can only use basic feasible solutions. I would not use a genetic algorithm to generate basic feasible solutions without using something like a cross-over procedure. I'm not even sure I would use a genetic algorithm to generate feasible solutions unless I had to; the technology for solving linear programs is so mature, even for problems containing millions to tens of millions of decision variables, that unless your problem were significantly larger than that, it would be difficult to see why you would want to use alternate methods to find feasible solutions because again:

  • the simplex method and interior-point methods each have robust initialization procedures that calculate valid initial points
  • the simplex method requires a basic feasible solution
  • interior-point methods merely require a feasible solution

Instead of modify simplexphaseone, as an alternative solution, we revised a few places of the repair operator of GA-MPC, so that it can finish up the solution by itself and get ride of those "noises". In our test case of TVaR constraint optimization problem, it can get solution as accurate as the linearized solution by linprog , but with running time 60% less than that of linprog.


Your Answer

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

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