组合数学 (Fall 2011)/Optimization

Unimodularity

Integer Programming

Consider the maximum integral flow problem: given as input a flow network [math]\displaystyle{ (G(V,E),c,s,t) }[/math] where for every [math]\displaystyle{ uv\in E }[/math] the capacity [math]\displaystyle{ c_{uv} }[/math] is integer. We want to find the integral flow [math]\displaystyle{ f:E\rightarrow\mathbb{Z} }[/math] with maximum value.

The mathematical programming for the problem is:

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\in\mathbb{N} &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

where [math]\displaystyle{ \mathbb{N} }[/math] is the set of all nonnegative integers. Compared to the LP for the max-flow problem, we just replace the last line [math]\displaystyle{ f_{uv}\ge 0 }[/math] with [math]\displaystyle{ f_{uv}\in\mathbb{N} }[/math]. The resulting optimization is called an integer programming (IP), or more specific integer linear programming (ILP).

Due to the Flow Integrality Theorem, when capacities are integers, there must be an integral flow whose value is maximum among all flows (integral or not). This means the above IP can be efficiently solved by solving its LP-relaxation. This is usually impossible for general IPs.

Generally, an IP of canonical form is written as

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \boldsymbol{c}^T\boldsymbol{x}\\ \begin{align} \text{subject to} \\ \\ \\ \end{align} \quad & \begin{align} A\boldsymbol{x} &\ge\boldsymbol{b} \\ \boldsymbol{x}&\ge \boldsymbol{0}\\ \boldsymbol{x}&\in\mathbb{Z}^n \end{align} \end{align} }[/math]

Consider the 3SAT problem. Each instance is a 3CNF(conjunctive normal form): [math]\displaystyle{ \bigwedge_{i=1}^m(\ell_{i_1}\vee\ell_{i_2}\vee\ell_{i_3}) }[/math], where each [math]\displaystyle{ (\ell_{i_1}\vee\ell_{i_2}\vee\ell_{i_3}) }[/math] is a clause and each [math]\displaystyle{ \ell_{i_r}\in\{x_{j},\neg x_{j}\mid 1\le j\le n\} }[/math], called a literal, is either a boolean variable or a negation of a boolean variable. We want to determine whether there exists an truth assignment of the [math]\displaystyle{ n }[/math] boolean variables [math]\displaystyle{ x_1,\ldots,x_n }[/math] such that the input formula is satisfied (i.e., is true).

The following IP solves 3SAT:

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{i=1}^mz_i\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} z_i &\le y_{i_1}+y_{i_2}+y_{i_3} &\quad& \forall 1\le i\le m\\ y_{i_r}&\le x_{j} &\quad& \text{if }\ell_{i_r}=x_{j} \\ y_{i_r}&\le 1-x_{j} &\quad& \text{if }\ell_{i_r}=\neg x_{j} \\ z_i, x_j&\in\{0,1\} &\quad& \forall 1\le i\le m, 1\le j\le n \end{align} \end{align} }[/math]

Since 3SAT is NP-hard (actually it is the first problem known to be NP-hard), generally IP is NP-hard.

Integrality of polytopes

A point in an [math]\displaystyle{ n }[/math]-dimensional space is integral if it belongs to [math]\displaystyle{ \mathbb{Z}^n }[/math], i.e., if all its coordinates are integers.

A polyhedron is said to be integral if all its vertices are integral.

An easy observation is that an integer programming has the same optimal solutions as its LP-relaxation when the polyhedron defined by the LP-relaxation is integral.

Theorem (Hoffman 1974)

If a polyhedron [math]\displaystyle{ P }[/math] is integral then for all integer vectors [math]\displaystyle{ \boldsymbol{c} }[/math] there is an optimal solution to [math]\displaystyle{ \max\{\boldsymbol{c}^T\boldsymbol{x}\mid \boldsymbol{x}\in P\} }[/math] which is integral.

Proof. There always exists an optimal solution which is a vertex in [math]\displaystyle{ P }[/math]. For integral [math]\displaystyle{ P }[/math], all vertices are integral. [math]\displaystyle{ \square }[/math]

Unimodularity and total unimodularity

Definition (Unimodularity)

An [math]\displaystyle{ n\times n }[/math] integer matrix [math]\displaystyle{ A }[/math] is called unimodular if [math]\displaystyle{ \det(A)=\pm1 }[/math]. An [math]\displaystyle{ m\times n }[/math] integer matrix [math]\displaystyle{ A }[/math] is called total unimodular if every square submatrix [math]\displaystyle{ B }[/math] of [math]\displaystyle{ A }[/math] has [math]\displaystyle{ \det(B)\in\{1,-1,0\} }[/math], that is, every square, nonsingular submatrix of [math]\displaystyle{ A }[/math] is unimodular.

A totally unimodular matrix defines a integral convex polyhedron.

Theorem

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m\times n }[/math] integer matrix. If [math]\displaystyle{ A }[/math] is totally unimodualr, then for any integer vector [math]\displaystyle{ \boldsymbol{b}\in\mathbb{Z}^n }[/math] the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral.

Proof. Let [math]\displaystyle{ B }[/math] be a basis of [math]\displaystyle{ A }[/math], and let [math]\displaystyle{ \boldsymbol{b}' }[/math] be the corresponding coordinates in [math]\displaystyle{ \boldsymbol{b} }[/math]. A basic solution is formed by [math]\displaystyle{ B^{-1}\boldsymbol{b}' }[/math] and zeros. Since [math]\displaystyle{ A }[/math] is totally unimodular and [math]\displaystyle{ B }[/math] is a basis thus nonsingular, [math]\displaystyle{ \det(B)\in\{1,-1,0\} }[/math]. By Cramer's rule, [math]\displaystyle{ B^{-1} }[/math] has integer entries, thus [math]\displaystyle{ B^{-1}\boldsymbol{b}' }[/math] is integral. Therefore, any basic solution of [math]\displaystyle{ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0} }[/math] is integral, which means the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral. [math]\displaystyle{ \square }[/math]

Our next result is the famous Hoffman-Kruskal theorem.

Theorem (Hoffman-Kruskal 1956)

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m\times n }[/math] integer matrix. If [math]\displaystyle{ A }[/math] is totally unimodualr, then for any integer vector [math]\displaystyle{ \boldsymbol{b}\in\mathbb{Z}^n }[/math] the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral.

Proof. Let [math]\displaystyle{ A'=\begin{bmatrix}A & -I\end{bmatrix} }[/math]. We claim that [math]\displaystyle{ A' }[/math] is also totally unimodular. Any square submatrix [math]\displaystyle{ B }[/math] of [math]\displaystyle{ A }[/math] can be written in the following form after permutation: [math]\displaystyle{ B=\begin{bmatrix} C & 0\\ D & I \end{bmatrix} }[/math] where [math]\displaystyle{ C }[/math] is a square submatrix of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ I }[/math] is identity matrix. Therefore, [math]\displaystyle{ \det(B)=\det(C)\in\{1,-1,0\} }[/math], thus [math]\displaystyle{ A' }[/math] is totally unimodular. Add slack variables to transform the constraints to the standard form [math]\displaystyle{ A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0} }[/math]. The polyhedron [math]\displaystyle{ \{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral if the polyhedron [math]\displaystyle{ \{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\} }[/math] is integral, which is implied by the total unimodularity of [math]\displaystyle{ A'\, }[/math]. [math]\displaystyle{ \square }[/math]