2
$\begingroup$

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm misunderstanding. Also, as far as I know, there is no published errata for the book.

On page 555, Proposition A.4 states that

If $P = \{\mathbf{x} \in \mathbb{R}^n | \mathbf{Ax \geq b}\} \neq \emptyset$ and $ P \subset \mathbb{R}^n$, then $\dim(P) + rank(A^=,b^=) = n$

where $(\mathbf{ A^=x\geq b^=})$ are the subset of inequalities of $\mathbf{Ax \geq b}$ which are satisfied at equality for any feasible $\mathbf{x}$.

First, the error may be that I'm misinterpreting $rank(A,b)$. I can't find a definition in the book, but I'm assuming that the $(A,b)$ notation means the $m \times n + 1$ matrix made by appending $b$ as a column of $A$.

Now, the example from the book works out that the dimension of the following polyhedron is 2:

$x_1 + x_2 + x_3 \geq 2$

$x_1 + x_2 \leq 1$

$x_3 \leq 1$

$x_1 \leq \frac{1}{2}$

$x_1, x_2, x_3 \geq 0$

The reasoning in the book is that adding the second and third constraints gives $x_1 + x_2 + x_3 \leq 2$. Combining with constraint 1 gives $x_1 + x_2 + x_3 = 2$. This is one constraint that is satisfied at equality for all feasible solutions, and $rank(A^=, b^=) = 1$. By Proposition A.4 above, $\dim(P) = 3 - 1 = 2$.

Here's where I'm not getting it.

Negating the second constraint and adding it to the first, we get $x_3 \geq 1$, and so constraint $x_3 \leq 1$ is always satisfied at equality. It's easy to verify that you can get feasible solutions with the other constraints all satisfied at strict inequality (interior points of the polyhedron).

Then $(A^=, b^=)$ is

\begin{bmatrix} 1 & 1 & 1 & 2 \\ 0 & 0 & -1 & -1 \\ \end{bmatrix}

which has rank 2, so the dimension of $P = 3-2 = 1$. What am I doing wrong here?

Edit: More information. I used the software polymake to compute the dimension of the polyhedron, the output was dimension one.

If anyone is interested, the code

$inequalities=new Matrix<Rational>([[-2,1,1,1],[1,-1,-1,0],[1,0,0,-1],[1/2,-1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]); 
    $p=new Polytope<Rational>(INEQUALITIES=>$inequalities);    
    print $p->DIM;
$\endgroup$
1
+50
$\begingroup$

Your logic makes sense. P dimension has to be at least 3-2 since every point in it must satisfy two linear independent equalities in R3. Since P has more than one point, it's dim must be exactly one. You are right and the book wrong. The way to read math books is always with pen and pencil next and don't trust everything until you can replicate. :-)

$\endgroup$
  • $\begingroup$ I had a typo - it should have said "that is satisfied at equality for all feasible solutions, and rank(A=,b=)=1". I'm sorry, I'm not sure what you mean when you say you don't see the contradiction. Line 20 is where the book's answer ends, and my contradictory answer begins. $\endgroup$ – raoulcousins Nov 9 '13 at 22:23
  • $\begingroup$ Thanks for your help! I gave you the bounty. Could you move your comment to your answer? $\endgroup$ – raoulcousins Nov 10 '13 at 18:42
  • $\begingroup$ @raolcousins: I moved it. Thanks. $\endgroup$ – Sergio Parreiras Nov 11 '13 at 3:52

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.