2
$\begingroup$

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?

$\endgroup$

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.