Suppose we have the following primal-dual pair

Primal $$\text{minimize: } c'x$$ Subject to, $$Ax = b $$ $$x\geq0$$

Dual $$\text{maximize: } p'b$$ Subject to, $$p'A \leq c' $$

To convert it into a feasibility problem we do the following:

Converted problem $$\text{maximize: } 0$$ Subject to, $$Ax = b $$ $$p'A \leq c' $$ $$c'x \leq p'b $$ $$x\geq0$$

If there is an optimal solution to the primal-dual problem then the converted problem must be feasible and strong duality holds.

My question is why do we use the constraint $c'x \leq p'b $ instead of $c'x = p'b $? We know that if this converted problem is feasible then by strong duality the orginal primal-dual pair must have the same cost. How did we guarantee that in the converted problem the feasible solution will satisfy the constraint $c'x \leq p'b $ strictly?



You must log in to answer this question.

Browse other questions tagged .