11
$\begingroup$

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable?

Moreover, is there any usage of this problem as a sub-problem within a decomposition algorithm such as Lagrangian relaxation algorithms?

$\endgroup$
9
$\begingroup$

I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "natural" column generation master.

The way I implemented it was using CPLEX by first solving the LP relaxation at the root node, then I ran several cut-loops until I experienced too much trailing off. After that, I converted the problem to an IP and added a cut callback, which used the same separation routine as I used at the root node. After experimenting a bit, I found that I got the best results this way, as CPLEX wanted to stop the cut-loop at the root node earlier than I did. I am definitely not saying this is the best way to do it, but in my experience, it worked quite okay.

But, given that it is an NP-annoying (complexity class formally defined by @prubin, I think) problem, you will have to expect that in some cases the computation time explodes!

(You can find an implementation in c of a exact knapsack separation routine here: header source, the function you need is VICkpsep())

$\endgroup$
3
$\begingroup$

AFAIK, one of an efficient way to solve Generalized Assignment Problem (GAP), is using Branch and Price technique. I will hope, this or this link be useful.

$\endgroup$
1
  • 1
    $\begingroup$ right, if you have a compact model in LP/MPS format, you can directly give it to e.g., GCG and it will perform branch-price-and-cut on it. $\endgroup$ – Marco Lübbecke Sep 30 '19 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.