0
$\begingroup$

I found this problem on page 96 of Alexander Schrijver's book Theory of Linear and Integer programming:(Robert Freund):

Given a system $Ax\le b$ of linear inequalities, describe a linear programming problem whose optimal solution immediately tells us which inequalities among $Ax\le b$ are always satisfied with equality.

I wonder if I could use the theorem: assume both optima of $\max{(c^Tx|Ax\le b)}=\min{(y^Tb|y\le0, y^TA=c^T)}$ are finite, then $x_0$ and $y_0$ are optimum solutions iff if a component of $y_0$ is positive, the corresponding inequality in $Ax\le b$ is satisfied by $x_0$ with equality $y_0^T(b-Ax_0)=0$.

$\endgroup$
  • $\begingroup$ Maybe for some constrains $A_i$, ith row of A, there exists $x_0$ satisfying $Ax_0\le b$ and $A_i x_0<b_i$. But maybe for some rows, the equalities always hold. $\endgroup$ – Connor Oct 21 '15 at 3:34
1
$\begingroup$

I think it runs down to look at $$ A x + y = b \\ y \ge 0 $$ where $y \in K^m$ is a slack variable. And then check $y$ for zero components (equation) or positive components (inequality).

This means we e.g. go from this problem $$ \begin{matrix} & \min c^\top x \\ \mbox{w.r.t.} & A x \le b \end{matrix} $$

to this problem \begin{align} x &\mapsto x' = (x^\top \, y^\top)^\top \in K^{n+m}\\ A &\mapsto A' = (A\, I_m) \in K^{m\times(n+m)}\\ A x \le b &\mapsto A' x' = b \wedge y = (0_{m\times n}\, I_m)\, x' = B x' \ge 0 \\ c &\mapsto c' = (c^\top\, 0_m^\top)^\top \in K^{n+m} \end{align} where $I_m$ is the identity of $K^{m\times m}$, $0_{m\times n}$ is the zero of $K^{m\times n}$ and $0_m$ is the zero of $K^m$, thus $$ \begin{matrix} & \min c'^\top x' \\ \mbox{w.r.t.} & A' x' = b \\ & B x' \ge 0 \end{matrix} $$

$\endgroup$

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.