8
$\begingroup$

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an initial feasible solution for a bounded Simplex solver. How can I efficiently find a corner point from this solution that I can use?

In short, how can I start the Simplex method from a feasible internal point?

$\endgroup$

migrated from stackoverflow.com Jun 11 '13 at 11:59

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ There are algorithms from going from an optimal internal point to an optimal basic solution (used to get an optimal basic solution after an interior point algorithm converges to an optimal non-basic solution). Maybe you could use something like this, but why do you want to provide a feasible initial solution to an LP? Do you have an LP where feasibility is a bottleneck? $\endgroup$ – user327301 Jun 11 '13 at 17:45
  • $\begingroup$ The algorithm I mention that generates the feasible solution in fact only generates that as a by-product. Its main result is the set of constraints for the LP. I just wish to make the most of this feasible solution, instead of ignoring it and using Phase 1. $\endgroup$ – Dylan Jun 12 '13 at 10:12
  • $\begingroup$ Are you sure that it will help? Have you looked at the logs of your solver and seen what percentage of the time is spent on finding a feasible solution vs finding an optimal solution? I'm skeptical that this will help, unless you're providing very good initial solutions to a very large or very dense (i.e., difficult) linear program. $\endgroup$ – user327301 Jun 12 '13 at 16:15
  • $\begingroup$ Regardless of whether it will help, I am curious as to whether it is possible. There is a good chance that the initial feasible solution is near optimal. The LP is very dense - zeroes are unlikely in any part of the tableau. $\endgroup$ – Dylan Jun 12 '13 at 16:35
  • 1
    $\begingroup$ When CPLEX uses interior point algorithms, it performs what the documentation calls crossover to move to a basic solution. I don't know anything about crossover, but that may be a starting point for you to find something. (Now you're making me want to resharpen my LP knowledge!) $\endgroup$ – user327301 Jun 12 '13 at 16:44
6
$\begingroup$

Every book on linear optimization explains the simplex method as a two-stage algorithm: the first for finding a feasible corner as a starting point, and the second for finding the optimum. The first uses a dual problem. Take a look at D. Bertsimas and J. N. Tsitsiklis: "Introduction to linear optimization", for example.

The reason one needs the two-phase approach is that it is typically difficult to find any feasible point -- in high dimensional spaces, the feasible set is very small compared to, say, the unit box. From your question, it sounds as if you have a different way to find at least one feasible point, and in that case it may be possible to generate a vertex of the feasible polyhedron from this point. One idea would be to use the following approach: each inequality constraint represents a half space separated by a hyperplane. Given a feasible point $x^\ast$, find the $n+1$ hyperplanes that are closest to $x^\ast$ and take their intersection. Intuitively, this vertex should be feasible, though I will admit that one would need to think about this a bit more.

$\endgroup$
  • 1
    $\begingroup$ Unfortunately all of the two-stage algorithms for the simplex method I have found describe "Phase 1", where artificial variables are used to find a basic feasible solution from a basic non-feasible solution. However what I want is to find a basic feasible solution from a nonbasic feasible solution. Am I missing something about "Phase 1" that can be applied to nonbasic solutions? $\endgroup$ – Dylan Jun 12 '13 at 10:33
  • $\begingroup$ I don't understand why you need that. All you need for phase 2 is any vertex (a basic feasible solution). Why would you care where phase 1 starts as long as you know where it ends? $\endgroup$ – Wolfgang Bangerth Jun 12 '13 at 15:52
  • $\begingroup$ But Phase 1 requires a basic (non-feasible) solution. If I can somehow start Phase 2 with a non-basic feasible solution, it should solve a lot quicker than starting Phase 1 from the origin. $\endgroup$ – Dylan Jun 12 '13 at 16:00
  • $\begingroup$ But phase 2 -- the actual simplex method -- walks from vertex to vertex of the polyhedron that is the feasible set. It needs to start with a vertex, i.e. a basic feasible point. There is no way around it. Phase 1 is intended to provide you exactly such a starting point. I imagine that you could indeed accelerate the algorithm if you had a way to generate a vertex of the feasible set from any other feasible point, and I imagine that that wouldn't even be very difficult (just project onto the closest $n+1$ constraints). The problem in general is to find any feasible point at all. $\endgroup$ – Wolfgang Bangerth Jun 12 '13 at 16:26
  • $\begingroup$ If it isn't very difficult, could you please detail it? As far as I can see, as you project on to each constraint in turn, you may dissatisfy previous constraints. So how do you project onto all constraints at once? This is the problem I am asking to solve. Not the general case of finding a feasible point. $\endgroup$ – Dylan Jun 12 '13 at 16:33
4
$\begingroup$

Unfortunately Wolfgang Bangerth's solution isn't guaranteed to work:

enter image description here

Here's what you can do instead: Pick a direction, and move along it until you hit a hyperplane. Pick a direction along the hyperplane and move along it until you hit another. Pick a direction along the intersection of the two hyperplanes... After $i$ steps, you will have $i$ active constraints, and you will pick a direction along the $(n-i)$-dimensional null space. After $n$ steps, you will arrive at a vertex (assuming the feasible set is bounded).

$\endgroup$
4
$\begingroup$

There are actually many different approaches to phase I in the simplex method. In particular, there are phase I algorithms that use primal simplex simplex iterations and other phase I algorithms that use dual simplex iterations. Here's a very general approach that could easily be adapted to make use of a known feasible solution. This version uses the dual simplex method in phase I and the primal simplex method in phase II, but there's a variant that uses primal simplex iterations in phase I and dual simplex iterations in phase II that I'll mention at the end. The approach that I'm going to describe here is discussed in many textbooks on linear programming. For example, see Robert Vanderbei's text.

Assume that we're solving

$ \max cx $

subject to

$ Ax=b $

$l \leq x \leq u$

where $A$ of size $m$ by $n$. For simplicity, assume that the rows of $A$ are linearly independent (this can be accomplished by a rank revealing factorization.)

  1. Pick an initial basis. This is a collection of $m$ variables so that the corresponding columns of $A$ form a non-singular matrix $B$. The remaining nonbasic variables can be set to either their upper or lower bounds (or zero if a variable has no bounds at all.)

An easy way to do this from your initial solution is to select as basic variables those variables that are furthest from their bounds in the known feasible solution and then verify that $B$ is non-singular. You may have to modify the basis to make $B$ non-singular. The point here is that there are many possible bases, but this one has as basic variables that variables that seem to be right from your feasible solution.

Solve the equations $Ax=b$ to obtain the values of the basic variables.

  1. The basic solution that you obtain is likely to be primal infeasible in the sense that some of the primal variables are outside of their bounds. It is also likely to be dual infeasible in the sense that some of the reduced costs of the non-basic variables have the wrong signs (e.g. nonbasic variables at lower bounds with positive reduced costs or nonbasic variables at upper bounds with negative reduced costs.)

We will overcome this problem by changing the objective function to one that is dual feasible. For each nonbasic variable at its lower bound, subtract a large positive quantity $M$ from the objective function coefficient. For each nonbasic variable at its upper bound, add a large positive quantity $M$ to the coefficient. This ensures that the dictionary is dual feasible.

The point of this modification of the objective function is to try to work towards primal feasibility but also to move towards optimality with respect to the original objective function. You want $M$ to be large enough that you have dual feasibility, but you want to keep as much influence as you can from the original objective function.

  1. Perform dual simplex methods to obtain a basic solution which is both primal feasible (all basic variables within boudns) and dual feasible (all reduced costs have the desired sign.) This solution is optimal for the phase I problem.

  2. Replace the modified phase I objective function with the original objective function. Now you'll have a basic solution that is primal feasible (changing the objective function doesn't affect this) but dual infeasible. Perform primal simplex iterations to get back to optimality.

An obvious alternative to this approach would be to modify the right hand side b at the start of phase I, use primal simplex iterations in phase I to get to optimality, then put the original right hand side back for phase II and use dual simplex iterations in phase II.

$\endgroup$
-3
$\begingroup$

I was searching for the solution for similar question: for a very large sparse linear program, only simplex method tested work, but only when the default 0 solution is feasible. Seems the phase one algorithm (like in linprog of Matlab) is bad. And the phase one source code is so complex to substitute it by other algorithm like genetic algorithm, so a work around method is to make linear transformation of the original problem, so that in the new varibles the provided initial feasible solution is 0, and this 0 will be used by phase one without using its own method to find a different starting point.

In testing this method, by step through linprog.m, simplex.m, simplexpresolve.m, and simplexphaseone.m, in cases where only inequality constraints are used, it is confirmed that the default 0 will be used for the original variables, where the slack variables will take the differences. So the linear transformation can sneak x0 into simplex which intentionally prevent user provided x0.You can then see the message of "The default starting point is feasible, skipping Phase 1." On the other hand, usually GA can find solution close to linear program to 0.01 percent by using double or triple times, so it may not merit the efforts of the linear transformation of those constraints, objective and bounds, especially when the constraints are artificially created.

$\endgroup$
  • $\begingroup$ Hi Frank and welcome to Scicomp! The question you pose is perfectly valid, but since it doesn't really address the original OP's question, it really doesn't belong as an 'answer'. You should really delete it and repost it in more detail as a separate question. $\endgroup$ – Paul Jun 18 '13 at 20:16
  • $\begingroup$ Never mind: this method is amount to make simplex use a supplied initial x0 after translate the x0 to 0, simplex method originally ignore any x0 provided. $\endgroup$ – Frank Jun 18 '13 at 21:45

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.