I am currently studying duality theory (for linear programming) and stumbled upon some confusion. Duality theory provides a useful tool to check if a given primal solution is optimal. A given primal solution is optimum iff the corresponding dual solution is feasible. Now, I want to check whether my solution for my primal is optimal without having to solve it using the simplex method. I can write the corresponding dual formulation, but I don't see how to obtain the corresponding dual variables from a primal solution to check for a violated dual constraint?

  • $\begingroup$ Have a look at this answer, especially point number 2 $\endgroup$ – David M. Jun 13 '18 at 16:53
  • $\begingroup$ Also, what do you mean by "the corresponding dual solution"? $\endgroup$ – David M. Jun 13 '18 at 16:54
  • 1
    $\begingroup$ 1. get the basis. 2. calculate $\pi^T = c_B^T B^{-1}$ $\endgroup$ – Erwin Kalvelagen Jun 14 '18 at 0:25

Given the primal: \begin{equation*} \begin{array}{lll} \textrm{maximize } & \sum\limits_{j=1}^n c_j x_j&\\ \textrm{subject to} & \sum\limits_{j=1}^n a_{ij} x_j \leq b_i & \textrm{ for } i=1,2\ldots,m\\ & x_j \geq 0 & \textrm{ for } j=1,2\ldots,n \end{array} \end{equation*}

The dual is: \begin{equation*} \begin{array}{lll} \textrm{minimize } & \sum\limits_{i=1}^m b_i y_i&\\ \textrm{subject to} & \sum\limits_{i=1}^m a_{ij} y_i \geq c_j & \textrm{ for } j=1,2\ldots,n\\ & y_i \geq 0 & \textrm{ for } i=1,2\ldots,m \end{array} \end{equation*}

Now given a solution $x^*$, use the complementary slackness theorem!

Either the primal variable is zero, or the associated dual constraint is tight: \begin{equation} {x^*_j = 0 \textrm{ or } \sum_{i=1}^m a_{ij}y^*_i = c_j \textrm{ (or both) for } j=1,2,\ldots,n} \end{equation} Either the primal constraint is tight, or the associated dual variable is zero: \begin{equation} \label{eq:CSC:2} {\sum_{j=1}^n a_{ij}x^*_j = b_i \textrm{ or } y^*_i = 0 \textrm{ (or both) for } i=1,2,\ldots,m} \end{equation}

If your solution $x^*$ is basic, you should find yourself with a system of equations with $n$ equations and $n$ unknowns. Solving it will give you a dual solution. If it is feasible on the dual, $x^*$ is optimal.


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.