Starting at a Given Basic Feasible Solution in the Simplex Method

Question

I have a Simplex problem $ A y \ge b $, where some of the elements of $b$ are positive and some are negative, and thus setting $y = 0$ does not give a basic feasible solution (BFS). By previous work, however, I happen to know a specific BFS. How do I then set up the table to start at this BFS instead of the standard $y=0$?

Please note: I don't want to use phase one of the simplex method because I want to use a specific BFS that I already know, and phase one finds me a BFS.

I assume that I have to do some row operations, but I can't work out what ones I would need to do. (Also, my specific case is reasonably large so I don't want to have to do it by hand but want some method that I can implement!)

(Sorry for the poor tagging - I'm not allowed to use better tags until I have a higher reputation! Also, I realise that there is a similar question posted elsewhere, but that focuses on a different point: I am interested in how to set up the table initially, which is not the focus of the other post.)

Thanks in advance! :)

Answer 1

If your problem is in standard form (that is, with constraints $Ax = b$, $x \geq 0$), and you know a BFS, then you should know which columns of the standard form $A$ matrix to select to form a basis, from which you can set up your initial tableau by calculating reduced costs, etc.

Unless you have to implement the simplex algorithm yourself, I would use a library. In modeling languages, you can supply an initial guess; presumably, if this were a basic feasible solution for a linear program, it would be immediately usable. If it were not, there should be procedures for using that information to find one (e.g., Phase I simplex, crossover procedures for converting interior-point method iterate to a BFS, or just using an interior-point algorithm instead of simplex).

If you have to implement simplex yourself, convert the problem to standard form. The algorithms in Bertsimas and Tsitsiklis' book are easy to follow (but probably not efficient, since it's a textbook on linear programming theory); a library would be faster, and probably would save you time.

Answer 2

Can you simply modify your problem from

$$Ay\geq b$$

to

$$Ax \geq b−Ay_0,$$

where the new unknown is $x=(y−y_0)$ and $y_0$ is your known specific BFS? Then you can use $x=0$ to start, and recover the solution of the initial problem by means of $y = x+y_0$.

Answer 3

Replace "Phase I" by a simple algorithm which takes indices from a known BFS (one by one) and converts corresponding columns to $[0..X_i..0]^T$ in the matrix with constraints (and target functional) by the Gauss-Jordan elimination. This will create identity matrix with RHS (free) values = values of BFS.

It's a good idea also to eliminate possible excessive constraints at this stage (fully zeroed rows) and to catch degeneracies ($X=0$ where $X$ is a basis variable).