5
$\begingroup$

I think this is a very basic question, but I failed to find an algorithm for this...

When I have a set of inequality constraints, $Ax \leq b$ as my feasible region, I can set $b = 0$ and find $n-1$ independent rows to solve for an extreme direction, But when I'm facing equality constraints, I tried the same thing but it didn't work.

So my question is: can anyone guide me or show me an algorithm for finding the extreme direction of a region given equality constraints or a combination of inequality and equality constraints, please?

$\endgroup$
6
$\begingroup$

First observation: any combination of linear equality and inequality constraints can be converted to all $\le $ constraints. If you start with $$\begin{array}{c} Ax\le a\\ Bx\ge b\\ Ex=e \end{array}, $$you can convert it to the equivalent system of inequalities $$ \left[\begin{array}{r} A\\ -B\\ E\\ -E \end{array}\right]x\le\left[\begin{array}{r} a\\ -b\\ e\\ -e \end{array}\right]. $$ Second observation (which requires knowledge of linear programming): if your feasible set is unbounded, you can slap an objective function on it that will improve along the ray (say, maximize the sum of the $x_i$, assuming $x\ge 0$) and get an unbounded linear program. Most LP solvers can find a ray once they have established that an LP is unbounded. If you prefer, you can try to apply the primal simplex method by hand. At some point you will encounter a basis where a variable wants to enter the basis (to improve the objective function) but there is no row in which to pivot. From that basic feasible solution you can easily identify a ray.

Addendum: How to use the all-negative simplex column. Assume a problem in "standard form" (meaning slacks/surpluses have been added) with constraints $Ax=b$. Let $B$ be the basis matrix when the negative column occurs, and for convenience assume the basic columns are the first few, so that $A$ gets partitioned as $[B\ \vert\ N]$ and your tableau corresponds to the system $I x_B + B^{-1}N x_N = B^{-1}b$. Let $k$ be the index of the all negative column and let $h$ be the column. If we freeze all the other nonbasic variables at 0, the system reduces to $x_B + h\cdot x_k = B^{-1}b$, with the right-hand side nonnegative. Since $h$ is all nonnegative, you can set $x_k$ as high as you want and the adjusted basic solution $x_B = B^{-1}b - h\cdot x_k$ will be nonnegative. So the ray originates at the current point $x_B = B^{-1}b, x_N = 0$ and moves in the direction $$\left[\begin{array}{c} -h\\ 1\\ 0 \end{array}\right],$$ where I am assuming that $x_k$ is the first variable after the basic variables and the 0 has dimension equal to the number of nonbasic variables minus 1.

$\endgroup$
3
  • $\begingroup$ Thanks for your reply! The first observation definitely make sense. For the second observation, I think you are referring to the case where in the simplex tableau, a whole column is negative, right? I'm aware this represent unboundness, but how could that tell me which ray is extreme ray? $\endgroup$
    – PetaGlz
    Jun 3 at 20:11
  • $\begingroup$ You are correct about the negative column. The answer to how to use it is too long for a comment, so I'll have to amend my answer. $\endgroup$
    – prubin
    Jun 4 at 22:27
  • $\begingroup$ Fantastic!! Thank a lot! $\endgroup$
    – PetaGlz
    Jun 5 at 15:25

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.