Another possibility to relax the problem is via Lagrangean relaxation. Trivially speaking, the Lagrangean relaxation amounts to changing the constraints set here and putting part of the constraints into the objective function and multiplying this by a certain Lagrangean multipliers u. What we get by minimizing this new function is a certain value which depends on u and provides a lower bound. Then clearly what we want to do is maximising this value with respect to u because maximising this provides the best Lagrangean lower bound.