In the dual formulation of a linear program we associate every dual variable to a constaint in teh primal solution and a cosntraint to every variable in the primal solution. We seek for finding the best lower bound that is a linear combination of the dual variables subject to a set of constraints.

---