0

I am new in stackexchange. I am having difficulty in answering the following question in Wolsey's Integer Programming Book.

enter image description here

I know that I can call P2 a relaxation of P1 if the feasible set in the former is larger or the objective function is greater. I also know that LP relaxation creates dual bound. I just don't know how to put together the words to prove it. It seems like the constraint of P2 is in just cx=c format. Any help here would be appreciated.

Moonzardisha
  • 9

1 Answers1

0

@LinAlg has outlined the proof.

Observe that \eqref{P1} can be concisely written as

$$\max\{cx \mid Ax = b, x \in B^n\} \tag{$P_1$} \label{P1},$$

where $$A = \begin{bmatrix} a_{11} & \cdots & a_{1j} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ a_{i1} & \cdots & a_{ij} & \cdots & a_{in} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mj} & \cdots & a_{mn} \end{bmatrix}.$$

It's more difficult make a similar observation for \eqref{P2}.

$$\max\{cx \mid u^TAx = u^Tb, x \in B^n\} \tag{$P_2$} \label{P2},$$

where $u \in \mathbb{R}^m$. Once you realize that, it's easily to verify @LinAlg's claim: left multiplication of $Ax = b$ by $u^T$ gives the desired conclusion.

To transform $\sum_j\sum_i u_i a_{ij} x_j$ into $u^TAx$:

  • order of $\sum_i$ and $\sum_j$ are not important, since it's a finite sum.
  • imagine the matrix $A = (a_{ij})_{i,j}$ when you see $a_{ij}$.
  • observe that $j$ is the index that appeared in both $a_{ij}$ and $x_j$. $j$ runs through the columns of each row of $A$. Remember that we have $\sum_j$, so this remind us right multiplication of $A$ by $x$: $Ax$.
  • note that $i$ is the index that appeared in both $a_{ij}$ and $u_i$. Remember that we have $\sum_i$, and $i$ runs through the rows of each column of $A$, so this remind us right multiplication of $A$ by "$u$": but $uA$ doesn't make sense, as $u$ is a "vertical" vector, so we take transpose and write $u^TA$.
  • combine the two: $\sum_i u_i (\sum_j a_{ij} x_j) = \sum_i u_i(Ax)_i = u^T Ax$

Remarks: When I need to denote the $i(,j)$-th element of a product of vectors and/or matrices, I personally like the wrapping it with a pair of parenthesis and appending the subscript $i(,j)$, whenever things like "$A$ and $(a_{ij})$" aren't possible. In the last point, I've done this on $Ax$. That helps us to understand how the matrix product formula helps to further condense the sum to a matrix product $u^TAx$.

GNUSupporter 8964民主女神 地下教會
  • 17,627