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$
1
  • $\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
    Commented Oct 21, 2015 at 3:34

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .