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.
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.