5
$\begingroup$

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! :)

$\endgroup$
  • $\begingroup$ Can you simply modify your problem from $Ay\geq b$ to $A x \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. Anyway, as @Geoff Oxberry said, a library should allow you to use an intitial guess (using a library can also help you to save a lot of time) $\endgroup$ – sebas Mar 3 '14 at 1:13
  • $\begingroup$ Cleaned up thread to remove discussion re: question revisions so that the focus is on the technical content of the question. (Thank you, everyone who contributed!) $\endgroup$ – Geoff Oxberry Mar 3 '14 at 23:03
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I was thinking about this after the other day, and I realised that actually correct, since the simplex algorithm maintains $y \ge 0$ (ie each component $y_i \ge 0$), but we don't necessarily have, for the optimum, $y \ge 0$. As such, we lose possible solutions. $\endgroup$ – Sam T Nov 10 '14 at 16:44

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.