Let us say that we have a linear program $P={ (min C^tx | Ax=b,x\geq0)}$
Assume that $(P)$ has an optimal solution. Write a system of linear equations and inequalities $(P_1)$ such that any feasible solution to $(P_1)$ gives us an optimal solution to $(P)$.

What I thought: I just added the complementary slackness condition along with the dual constraints to the primal constraints and solve it, as it will satisfy:

1.Primal feasibility
2.Dual feasibility
3.Complementary slackness
Hence will get the optimal solution as a feasible solution to the Linear program
but Later I noticed that if I include complementary slackness the constraints are non-linear. So any suggestion?

  • $\begingroup$ If you have primal and dual feasibility then complementary slackness is equivalent to the statement that primal and dual objective values are equal. $\endgroup$ – Michal Adamaszek Nov 14 '19 at 11:27
  • $\begingroup$ but for optimallity dont we need the complementery slackness. $\endgroup$ – onlymath Nov 14 '19 at 11:36
  • 1
    $\begingroup$ math.stackexchange.com/questions/3370732/… $\endgroup$ – Kuifje Nov 14 '19 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.