I have the following generalized assignment problem:

Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$

such that

$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\quad\quad\quad P1$

$\quad 2)\ \ \sum_{i=1}^{N} x_{ij}\leq N_{eq} \quad \forall j$

$\quad 3)\ \ \sum_{i=1}^{N} x_{ij}R_{ij} \leq R^u_{ij} \quad \forall j$

$\quad 4)\quad x_{ij} \in {0,1}$

The parameters $N, M, R_{ij},R^u_{ij}, N_{eq}$ are given. It might be useful to think of the problem as if we have $N$ items that we want to assign to $M$ knapsacks.

Fortunately, I found a paper that shows how to solve it based on Lagrangian relaxation (http://www.ece.utah.edu/~kalla/phy_des/lagrange-relax-tutorial-fisher.pdf). Note that C1 is a complicating constraint. Relaxing C1 yields M subproblems where each subproblem is a knapsack problem as following:

$Z_{D}(u)$= max $\sum_{j=1}^{M}\sum_{i=1}^{N} x_{ij}(R_{ij}+u_i)-\sum_{i=1}^{N}u_i$

such that

$\quad 2)\ \ \sum_{i=1}^{N} x_{ij}\leq N_{eq} \quad \forall j$ $\quad\quad\quad\quad\quad P2$

$\quad 3)\ \ \sum_{i=1}^{N} x_{ij}R_{ij} \leq R^u_{ij} \quad \forall j$

$\quad 4)\quad x_{ij} \in {0,1}$

where $u$ is a Lagrangian multiplier.

For a particular value of $u$, we have $M$ independent knapsack problems and $Z_D(u)$ is an upper bound on $Z$,i,e. $Z_D(u)\geq Z$. Therefore, we we want to find the best upper bound. That is we should solve the dual problem;

$Z_D$=min $Z_D(u)$. $\quad\quad\quad\quad\quad\quad\quad\quad\quad P3$

Noting that $Z_D(u)$ is a convex function, we can use subgradient method to solve it (dual function). I implemented a subgradient method in Matlab to solve $P3$. The solution for the vector $x$ violates C1 as expected due to the relaxation. The paper (http://www.ece.utah.edu/~kalla/phy_des/lagrange-relax-tutorial-fisher.pdf) explains a way of how to construct a feasible solution from infeasible solution (section 9). For items which have not been assigned, i,e. $\sum_{j=1}^{M}=0$, it says "it would be reasonable to choose the knapsack that maximizes $(u_i-c_{ij})/a_{ij}$". In my problem formulation, $R_{ij}=a_{ij}=c_{ij}$, so I should choose the knapsack that maximizes $(u_i-R_{ij})/R_{ij}$.

My question is exactly about this construction, why is it reasonable to do this?


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.