1
$\begingroup$

When a linear program is formulated like this:

$\begin{align} \text{minimise}\quad &c^Tx\\ \text{subject to}\quad &Ax \ge b \end{align}$

With $c\in \mathbb{R}^{|x|}$, $A \in \mathbb{R}^{n \times |x|}$ (where $n$ is the number of constraints) and $b \in \mathbb{R}$, we can say that the feasible region is the intersection of the half spaces associated with all of the linear inequality constraints.

However, sometimes I see linear programs formulated like this:

$\begin{align} \text{minimise}\quad &c^Tx\\ \text{subject to}\quad &Ax = b \end{align}$

How can we use this formulation to define a feasible region? If $b \in \mathbb{R}$, then the constraints define a set of lines, instead of half spaces. Do we now take $b \subseteq \mathbb{R}$ instead of some single element? Or, is the implication that we can write $x = y \Leftrightarrow x \ge y \land x \le y$, so the lines $Ax = b$ each define the boundary of a half space? If so, then how do we determine on which side of the boundary the feasible region lies?

$\endgroup$
  • 2
    $\begingroup$ The feasible set is the line itself in that case. $\endgroup$ – Sean Roberson Oct 4 '19 at 5:44
  • $\begingroup$ That is what I would have thought, but I see these two ways of formulating LP problems being used interchangeably.. $\endgroup$ – guskenny83 Oct 4 '19 at 5:45
  • 1
    $\begingroup$ There is no way the two formulations are always equivalent. $\endgroup$ – Sean Roberson Oct 4 '19 at 5:47
  • 1
    $\begingroup$ Or maybe, you choose the half spaces that give a finite bounded area? But there may be more than one such areas formed. Interesting question. $\endgroup$ – Balakrishnan Rajan Oct 4 '19 at 5:48
  • 1
    $\begingroup$ Well, the second one has just double the constraints, no? $Ax\ge b$ and $-Ax\ge -b$. $\endgroup$ – Gae. S. Oct 4 '19 at 5:52
1
$\begingroup$

If you like the first form better, you can write condition $Ax=b$ as $$\begin{bmatrix}A\\ -A\end{bmatrix}x\ge \begin{bmatrix}b\\ -b\end{bmatrix}$$

and work just like you would in the first instance with $2n$ constraints instead of $n$.

$\endgroup$
  • $\begingroup$ Okay, so we are just splitting each equality constraint into two inequality constraints then? And instead of one inequality describing a single half space, the feasible region is the intersection of two half spaces reflected about the origin? $\endgroup$ – guskenny83 Oct 4 '19 at 6:00
  • $\begingroup$ I'd say reflected about their boundaries. $\endgroup$ – Gae. S. Oct 4 '19 at 6:54
1
$\begingroup$

First, a common convention in LP theory is to work with positive vectors (each component is positive).

Gae. S. showed that you can go from an equality constraint to an inequality from a practical point of view by making a change of variable. However, there is a theorem in convex optimization (LP are convex problems) based on subgradient telling you that every optimal solution of the problem lies on the boundary of the feasible region for LP problems. Hence the two problems are equivalent in the sense they will always lead to the same solutions, even if one has a way larger feasible region.

$\endgroup$
  • $\begingroup$ When you say "every solution", do you mean "every optimal solution"? or just every feasible solution, period? $\endgroup$ – guskenny83 Oct 4 '19 at 6:04
  • 1
    $\begingroup$ I thought it was clear it was optimal solutions. It is not hard to come up with feasible solutions that are not on the boundary. Edited. $\endgroup$ – nicomezi Oct 4 '19 at 6:07
  • $\begingroup$ Yep, thanks for clarifying. I think that was why i was confused; because my intuition was that of a feasible region, described by half spaces, containing all feasible solutions - and I couldn't see how the equality constraints captured that. Between you and Gae. S., it has been made clear. Thanks! $\endgroup$ – guskenny83 Oct 4 '19 at 6:10

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.