0
$\begingroup$

I'm new to integer programming and I'm reading the book GTM 271: Integer Programming written by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli.

I have trouble solving exercise 8.6:

Consider two different Lagrangian duals for the generalized assignment problem \begin{align*} z_I = \max &\sum_{i=1}^m \sum_{j=1}^n c_{ij}x_{ij} \\ &\sum_{j=1}^n x_{ij} \le 1 \qquad i=1,\dots,m \\ &\sum_{i=1}^m a_{j}x_{ij} \le b_{j} \qquad j=1,\dots,n \\ &x_{ij}\in\{0, 1\} \qquad i=1,\dots,m,j=1,\dots,n \end{align*} Discuss the relative merits of these two duals based on (i) the strength of the bound, (ii) ease of solution of the subproblems.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

There are two natural choices for dualization. Dualize either the first set of constraints, yielding a knapsack subproblem, or the second set of constraints, yielding a trivial subproblem that satisfies the integrality property.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .