How to solve large scale generalized assignment problem

Question

I am looking for a way to solve a large scale Generalized assignment problem(To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of $=$). Here, $m$ is the number of agents and $n$ is the number of tasks. $$ \begin{aligned} &\text{maximize} && \sum_{i}^{m} \sum_{j}^{n} p_{ij}x_{ij} \\\ &\text{subject to} && \sum_{j}^{n} w_{ij}x_{ij} \le t_{i} &&& \forall i \\\ & && \sum_{i}^{m} x_{ij} \le 1 &&& \forall j \\\ & && x_{ij} \in \{0, 1\} \end{aligned} $$

data size

• $m \le 1,000$
• $n \le 10,000,000$
• $p_{ij} \le 1,000$
• $w_{ij} \le 1,000$
• $t_i \le 200,000$
• valid agent-task pair(i.e. number of non zero $p_{ij}$) $\le 200,000,000$
• time limit : 6 hours

Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?

Also, are there any other approaches to solving large scale NP-hard problems? For example, I was wondering if it is possible to reduce the number of variables by clustering agents or tasks, but I did not find such a method.

Answer 1

The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$. Most algorithms designed for these instances won't be suitable for you.

What seems the most relevant in your case are the polynomial algorithms described in "Knapsack problems: algorithms and computer implementations" (Martello et Toth, 1990):

• Greedy: sort all agent-task pairs according to a given criterion, and then assign greedily from best to worst the unassigned tasks. Complexity: $O(n m \log (n m))$
• Regret greedy: for all tasks, sort its assignments according to a given criterion. At each step, assign the task with the greatest difference between its best assignment and its second-best assignment, and update the structures. Complexity: $O(n m \log m + n^2)$

Various sorting criteria have been proposed: pij, pij/wij, -wij, -wij/ti... -wij and -wij/ti are more suited for the case where all items have to be assigned. In your case pij and pij/wij might yield good results

Then, they propose to try to shift each task once to improve the solution. With at most one shift per task, the algorithms remain polynomial, but you can try more shifts if you have more time.

Note that these algorithms might be optimized if not all pairs are possible, as you indicate in your case.

I have some implementations here for the standard GAP (and a min objective). You can try to play with them to get an overview of what might work or not in your case

Answer 2

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP and simulated annealing would be possibilities. Tabu search is popular with some people, but the memory requirements of maintaining a table of tabu solutions might be prohibitive. I'm fond of genetic algorithms, but I think we can rule out a GA (or other "evolutionary" metaheuristic) based on memory considerations. Personally, I'd be tempted to check out GRASP first.