0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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^{*}$.

$\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.