Combinatorics (Fall 2010)/Duality, Matroid

Duality

Consider the following LP:

[math]\displaystyle{ \begin{align} \text{minimize} && 7x_1+x_2+5x_3\\ \text{subject to} && x_1-x_2+3x_3 &\ge 10\\ && 5x_1-2x_2-x_3 &\ge 6\\ && x_1,x_2,x_3 &\ge 0 \end{align} }[/math]

Let [math]\displaystyle{ OPT }[/math] be the value of the optimal solution. We want to estimate the upper and lower bound of [math]\displaystyle{ OPT }[/math].

Since [math]\displaystyle{ OPT }[/math] is the minimum over the feasible set, every feasible solution forms an upper bound for [math]\displaystyle{ OPT }[/math]. For example [math]\displaystyle{ \boldsymbol{x}=(2,1,3) }[/math] is a feasible solution, thus [math]\displaystyle{ OPT\le 7\cdot 2+1+5\cdot 3=30 }[/math].

For the lower bound, all feasible solution [math]\displaystyle{ \boldsymbol{x} }[/math] satisfies the two constraints:

[math]\displaystyle{ \begin{align} x_1-x_2+3x_3 &\ge 10,\\ 5x_1-2x_2-x_3 &\ge 6.\\ \end{align} }[/math]

Since the [math]\displaystyle{ \boldsymbol{x} }[/math] is restricted to be nonnegative, term-by-term comparison of coefficients shows that

[math]\displaystyle{ 7x_1+x_2+5x_3\ge(x_1-x_2+3x_3)+(5x_1-2x_2-x_3)\ge 16. }[/math]

The idea behind this lower bound process is that we are finding suitable nonnegative multipliers (in the above case the multipliers are all 1s) for the constraints so that when we take their sum, the coefficient of each [math]\displaystyle{ x_i }[/math] in the sum is dominated by the coefficient in the objective function. It is important to ensure that the multipliers are nonnegative, so they do not reverse the direction of the constraint inequality.

To find the best lower bound, we need to choose the multipliers in such a way that the sum is as large as possible. Interestingly, the problem of finding the best lower bound can be formulated as another LP:

[math]\displaystyle{ \begin{align} \text{maximize} && 10y_1+6y_2\\ \text{subject to} && y_1+5y_2 &\le 7\\ && -y_1+2y_2 &\le 1\\ &&3y_1-y_2 &\le 5\\ && y_1,y_2&\ge 0 \end{align} }[/math]

Here [math]\displaystyle{ y_1 }[/math] and [math]\displaystyle{ y_2 }[/math] were chosen to be nonnegative multipliers for the first and the second constraint, respectively. We call the first LP the primal program and the second LP the dual program. By definition, every feasible solution to the dual program gives a lower bound for the primal program.

LP duality

Given an LP in canonical form, called the primal LP:

[math]\displaystyle{ \begin{align} \text{minimize} && \boldsymbol{c}^T\boldsymbol{x}\\ \text{subject to} && A\boldsymbol{x} &\ge\boldsymbol{b}\\ && \boldsymbol{x} &\ge \boldsymbol{0} \end{align} }[/math]

the dual LP is defined as follows:

[math]\displaystyle{ \begin{align} \text{maximum} && \boldsymbol{b}^T\boldsymbol{y}\\ \text{subject to} && A^T\boldsymbol{y} &\ge\boldsymbol{c}\\ && \boldsymbol{y} &\ge \boldsymbol{0} \end{align} }[/math]

Surviving problem (diet problem)

Let us consider the surviving problem. Suppose we have [math]\displaystyle{ n }[/math] types of natural food, each containing up to [math]\displaystyle{ m }[/math] types of vitamins. The [math]\displaystyle{ j }[/math]th food has [math]\displaystyle{ a_{ij} }[/math] amount of vitamin [math]\displaystyle{ i }[/math], and the price of the [math]\displaystyle{ j }[/math]th food is [math]\displaystyle{ c_j }[/math]. We need to consume [math]\displaystyle{ b_i }[/math] amount of vitamin [math]\displaystyle{ i }[/math] for each [math]\displaystyle{ 1\le i\le m }[/math] to keep a good health. We want to minimize the total costs of food while keeping healthy. The problem can be formalized as the following LP:

[math]\displaystyle{ \begin{align} \text{minimize} \quad& c_1x_1+c_2x_2+\cdots+c_nx_n\\ \begin{align} \text{subject to} \\ \\ \end{align} \quad & \begin{align} a_{i1}x_{1}+a_{i2}x_{2}+\cdots+a_{in}x_{n} &\le b_{i} &\quad& \forall 1\le i\le m\\ x_{j}&\ge 0 &\quad& \forall 1\le j\le n \end{align} \end{align} }[/math]

The dual LP is

[math]\displaystyle{ \begin{align} \text{maximize} \quad& b_1y_1+b_2y_2+\cdots+b_ny_m\\ \begin{align} \text{subject to} \\ \\ \end{align} \quad & \begin{align} a_{1j}y_{1}+a_{2j}y_{2}+\cdots+a_{mj}y_{m} &\le c_{j} &\quad& \forall 1\le j\le n\\ y_{i}&\ge 0 &\quad& \forall 1\le i\le m \end{align} \end{align} }[/math]

The problem can be interpreted as follows: A food company produces [math]\displaystyle{ m }[/math] types of vitamin pills. The company wants to design a pricing system such that

• The vitamin [math]\displaystyle{ i }[/math] has a nonnegative price [math]\displaystyle{ y_i }[/math].
• The price system should be competitive to any natural food. A costumer cannot replace the vitamins by any natural food and get a cheaper price, that is, [math]\displaystyle{ \sum_{i=1}^my_ja_{ij}\le c_j }[/math] for any [math]\displaystyle{ 1\le j\le n }[/math].
• The company wants to find the maximal profit, assuming that the customer only buy exactly the necessary amount of vitamins ([math]\displaystyle{ b_i }[/math] for vitamin [math]\displaystyle{ i }[/math]).

Maximum flow problem

Matroid

Matroids

Let [math]\displaystyle{ X }[/math] be a finite set and [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] be a family of subsets of [math]\displaystyle{ X }[/math]. A member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called maximal if [math]\displaystyle{ S\cup\{x\}\not\in\mathcal{F} }[/math] for any [math]\displaystyle{ x\in X\setminus S }[/math].

For [math]\displaystyle{ Y\subseteq X }[/math], denote [math]\displaystyle{ \mathcal{F}_Y=\{S\in\mathcal{F}\mid S\subseteq Y\} }[/math]. Clearly [math]\displaystyle{ \mathcal{F}_Y }[/math] is the restriction of [math]\displaystyle{ \mathcal{F} }[/math] over [math]\displaystyle{ 2^Y\, }[/math].

Definition

A set system [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a matroid if it satisfies: (hereditary) if [math]\displaystyle{ T\subseteq S\in\mathcal{F} }[/math] then [math]\displaystyle{ T\in\mathcal{F} }[/math]; (matroid property) for every [math]\displaystyle{ Y\subseteq X }[/math], all maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] have the same [math]\displaystyle{ |S| }[/math].

Suppose [math]\displaystyle{ \mathcal{F} }[/math] is a matroid. Some matroid terminologies:

• Each member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called an independent set.
• A maximal independent subset of a set [math]\displaystyle{ Y\subset X }[/math], i.e., a maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math], is called a basis of [math]\displaystyle{ Y }[/math].
• The size of the maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] is called the rank of [math]\displaystyle{ Y }[/math], denoted [math]\displaystyle{ r(Y) }[/math].