Suppose we have a linear programming problem:
$\min_x c^T x, \ \ s.t. \ Ax \le b$
Suppose we know a priori that at an optimal solution $x^*$, one inequality $a^T x \le 1$ in the constraints is satisfied with strict inequality, i.e. $a^T x^* < 1$.
Question: Can we just remove the constraint $a^T x \le 1$ from the original problem, while $x^*$ will still be optimal to the new problem? Let's ignore the possibility of divergence. Thanks.
Yes. If the problem without the inequality has a solution $\hat{x}$ with $c^{T}\hat{x} < c^{T}x^{*}$, then along the line from $x^{*}$ to $\hat{x}$, the objective function would be monotone decreasing and by taking a small enough step toward $\hat{x}$ from $x^{*}$ we could find a solution that was feasible for the original LP with a better objective than $c^{T}x^{*}$.