The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $H$-polytope) and is defined as the intersection of a finite number of halfspaces.

The simplex method for the linear program optimizes over a polytope

$$ \begin{array}{ll} \min_{x\in \mathbb R^n} &c^Tx\\ \mathrm{s.t.} & Ax \leq b \end{array} $$

and initializes by finding an extreme point, e.g $\bar x$ where $A\bar x \leq b$, and $A_I\bar x = b_I$ for a set of row indices $I$ of length $n$, and $A_I$ is invertible.

Suppose that such an $A_I$ exists. Are there any systematic or commonly accepted ways of finding an extreme feasible point? Even if it's a crappy way, are there any ways that are used in practice? I found many references on how to proceed once the feasible point is found, but not how to pick it to begin with.

Thank you!

  • $\begingroup$ I updated the title to include the definition, but a linear polytope is just the set of vectors $x$ satisfying the constraint $Ax \leq b$. $\endgroup$ – Y. S. Mar 2 at 17:47
  • $\begingroup$ I would call that an $\mathcal H$-polytope, since it's defined by the intersection of half-spaces. This is standard terminology. $\endgroup$ – Rodrigo de Azevedo Mar 2 at 18:40
  • $\begingroup$ Ok, I added a clarification in the question description. $\endgroup$ – Y. S. Mar 2 at 21:19

A common approach is to introduce slack variables $s$, i.e., $Ax + s = b$. Define $s = s^+ - s^-$ with $s^+ \geq 0$ and $s^- \geq 0.$ And consider for objective function $\min_{s,x} 1^Ts^-$. In other words, solve

\begin{array}{ll} \min_{s, x} & 1^T s^-\\ \mathrm{s.t.} & Ax + s= b\\ & s = s^+ - s^-\\ & s^+, s^- \geq 0\\ \end{array}

Then, $s = b$ with $x = 0$ is a solution for that particular problem. Now, if the optimal value is $0$, then $s^- = 0$, hence the corresponding $x$ verifies $Ax \leq b$, and therefore is a solution to your original problem. If the optimal value is not $0$, then your original problem is not feasible.

  • $\begingroup$ So the idea is, this LP I CAN solve, because there exists an intuitive initialization, and the solution gives me an initialization for the LP I am actually trying to solve? Actually that makes a lot of sense; thank you! $\endgroup$ – Y. S. Mar 2 at 17:40
  • 1
    $\begingroup$ That is correct! $\endgroup$ – Pebeto Mar 2 at 18:16

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.