In this post, I will briefly review some basic ideas in polyhedral theory, which are the building blocks for more advanced MIP techniques.
$H$-representation, $V$-representation, and Minkowski-Weyl Theorem
$H$-formulation, or hyperplane formulation, uses finitely many linear constraints (hyperplane) to describe a polyhedron. The simplest $H$-formulation is like:
$$P=\{x:Ax\leqslant b\}.$$
$V$-formulation, on the other hand, tries to characterize a polyhedron with extreme points and extreme rays. In simple words, extreme points depict the corner of a polyhedron $P$, while extreme rays define the directions of some boundary edges of $P$ extending to $\infty$.
Now, assume for $P$ we have set of extreme points $V$ and set of extreme rays $R$. A $V$-formulation is like:
$$P=Conv(V)+Cone(R)$$
where $Conv$ is the convex hull and $Cone$ is the cone hull.
Naturally, these two formulations should be the same. Minkowski-Weyl Theorem formally states that, the $V$-formulation and the $H$-formulation are equivalent. Thus, for a given polyhedron $P$, we have two different ways to describe it. But which one is better?
Intuitively, $H$-formulation has more concise form, but the expression is not unique and redundancy is possible. $V$-formulation is usually far more complex (e.g. having exponential number of extreme points), but the expression is unique and uniform. Later we will see that, these two formulations provide not only different formulation performance, but also different approach methodology to MIP problems (inner approximation v.s. outer approximation).
Farkas’ lemma and Fundamental Theorem of Linear Inequality
The famous Farkas’ lemma states the following:
One of the two following systems is feasible:
a) $\{x\in R^n: Ax=b,x\geqslant 0\}$;
b) $\{y\in R^m: y^TA\geqslant 0, y^Tb<0\}$
From a geometric point of view, the first system says that $b$ is in the cone generated by columns of $A$: $b\in cone(A)$, while the second system says that we can find a hyperplane $y^Tx=0$ to separate $b$ from $cone(A)$. But can we find a good $y$ with more properties? Fundamental theorem of linear inequality shows that we can efficiently depict the boundary of the set of these $y$:
If $\{a_i\}_n,b\in R^m$ and $dim(L(a_1,\cdots,a_n,b))=m$, then one of the two following statements holds:
a) $b\in cone(\{a_i\}_n)$;
b) $\exists c\in R^m$ s.t. $c^Tb>0, c^Ta_i\leqslant 0$, and $c^Ta_j=0$ for $m-1$ independent $a_j$.
One reason why I mention Farkas’ lemma here is that it provides us ways to construct valid constraints. For example, let $P=\{x\in R^n: Ax\leqslant b\}$. Then, by Farkas’ lemma,
$P\subseteq\{x\in R^n: c^Tx\leqslant d\}$ iff $c=A^T\mu, d\geqslant b^T\mu$ for some $\mu\in R^m_+$.
In integer case, some of these cuts (Gomory cuts in this case) can be improved to $c^Tx\leqslant \lfloor d \rfloor$, and leads to stronger formulation.
Similarly, with same technique we can analyze the size of projection $Proj_x(P)$ where $P$ is extended formulation $P=\{(x,z): Ax+Dz\leqslant b\}$. I will discuss this in a later post (on extended formulation).