Is an exact violated inequality constraint met as equal constraint in optimal solution?

Question

We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the optimal solution?

Answer 1

If I understand correctly, you have a linear programming problem $P$ and a basic solution $x^*$ with corresponding basic solution $y^*$ of the dual problem $D$ such that $y^*$ is feasible for $D$ but $x^*$ is not feasible for $P$ due to a single violated inequality constraint $C_i$.

Of course it's possible that there are no optimal solutions at all. It is also possible that there are optimal solutions in which your constraint $C_i$ is not an equality.

Consider the rather trivial linear programming problem $P$:

maximize $0$

subject to $$ \eqalign{x_1 &\le 1\cr x_1 &\le 2\cr x_1 &\ge 0\cr} $$ Let $s_1$ and $s_2$ be the slack variables corresponding to the two constraints. The basic solution for basis $x_1, s_1$ is $x_1 = 2$, $s_1 = -1$, $s_2 = 0$ which violates the first constraint. All basic solutions of the dual are $y_1 = 0$, $y_2 = 0$ which is feasible. There are optimal solutions $0 \le x_1 \le 1$.

EDIT: We can indeed say that if $P$ has an optimal solution, it has an optimal solution in which $C_i$ is an equality.

Proof: Suppose $x^{**}$ is an optimal solution of $P$ in which constraint $C_i$ is not an equality. Then an appropriate convex combination $x^{***}$ of $x^*$ (in which the slack variable corresponding to $C_i$ has a negative value) and $x^{**}$ (where it has a positive value) will have $C_i$ satisfied as an equality. Since both $x^{*}$ and $x^{**}$ satisfy all the other constraints, $x^{***}$ is feasible for $P$.

Now $x^*$ is an optimal solution for $P_i$: note that the dual variable value $y^*_i$ for the omitted constraint $C_i$ in $y^*$ must be $0$ by complementary slackness, so $y^*$ (with the $i$ component omitted) is still feasible for the dual of $P_i$. On the other hand, $x^{**}$ is feasible for $P_i$. Thus if $f$ is the objective function, $f(x^*) \ge f(x^{**})$, and $f(x^{***}) \ge f(x^{**})$. Thus $x^{***}$ is an optimal solution for $P$.