3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ All else failing, there is the greedy heuristic: sort the $p_{ij}$ in descending order, then make assignments in that order, tracking the remaining capacity of each agent and skipping assignments that would exceed that capacity. I did not put this in as an answer because it is such a low hanging fruit. $\endgroup$
    – prubin
    Jul 29 at 18:13
  • $\begingroup$ The problem that you wrote is not exactly the Generalized Assignment Problem, because the second set of constraints has $\le$ instead of $=$. This makes the problem much easier since finding a feasible solution is not an issue anymore in this case. Is it what you meant to write? $\endgroup$
    – fontanf
    Jul 29 at 20:22
  • $\begingroup$ @prubin Thank you. If there is no other way, I will use greedy algorithm. $\endgroup$
    – sakuya
    Jul 30 at 6:02
  • $\begingroup$ @fontanf Yes, I'm trying to solve the relaxation of the Generalized assignment problem. I've added this to the post $\endgroup$
    – sakuya
    Jul 30 at 6:11
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.