21
$\begingroup$

I can't seem to find any literature on algorithms which can be used to solve a many-to-many generalized assignment problem (GAP), i.e. models where not only can more tasks be assigned to one agent, but multiple agents can also be assigned to one task (one-to-one and one-to-many AP's are discussed in a paper by Pentico). I know next-to-nothing of assignment problems, but I came upon a problem like this during my research and would like to know more about how to solve them. Is it possible that such a many-to-many GAP is known under another name, or is there a different reason why so few literature on it can be found?

Pentico, D. Assignment Problems: A Golden Anniversary Survey. European Journal Of Operational Research (2007); 176(2):774-793.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hi GerritJan. Welcome to Scicomp! :) Are you familiar with thes lagrangian heuristic for the generalized assignment problem? sciencedirect.com/science/article/pii/S0898122110002609 or irma-international.org/viewtitle/58969 or crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ? $\endgroup$
    – Paul
    May 2, 2012 at 13:42
  • 1
    $\begingroup$ It seems to me that the case of assigning portions of a task to multiple agents can be modelled, at least in cases where costs are linearly apportioned, by treating the one task as if it were instead multiple subtasks. Without more details it's hard to know how your problems might be more "general" than generalized assignment problems. The Wikipeida article has some good exposition and links to a couple of references on the topic. $\endgroup$
    – hardmath ♦
    May 3, 2012 at 1:53
  • $\begingroup$ Thanks, @Paul. I will look into the papers, although they seem to be rather complicated to my untrained eye. Then again, I suspect the problem is complicated, and I will probably have to do some simplifying. hardmath, my problem is basically that of distributing energy in a network: supply- and demandnodes need to be matched using the (weighted) connections between them, in the most optimal way, with a minimum use of supply to fulfill all demand. Of course, additional constraints can be used, like maximal capacity on the connections, etc. $\endgroup$
    – Gerrit Jan
    May 3, 2012 at 7:19
  • 1
    $\begingroup$ @GerritJan: It's an np-hard problem, so it will require an approximation scheme. If you need a good approximation, your algorithm may have to be a bit complex. $\endgroup$
    – Paul
    May 3, 2012 at 19:08
  • 2
    $\begingroup$ @GerritJan: It means that the exact 'optimal' solution can only be guaranteed by checking all possible configurations. These possible solutions grow (at least) exponentially over time, making even relatively modest size problems virtually impossible to solve exactly in a reasonable amount of time. $\endgroup$
    – Paul
    May 4, 2012 at 13:57

2 Answers 2

Reset to default
1
$\begingroup$

Your problem doesn't seem to be, "that the sum of the "agents" have to supply exactly a discrete portion of energy or nothing for each single demand ...", right? Or you did not understand me. So I'll try to describe my problem better, also because I found a solution.

In my problem, I have a set of agents where each one has a budget of certain resources, who can share the cost of tasks, which should be "executed" 1 time or not (many-to-many-assignment without the need to "execute" every task). It means: the sum of partial solutions of agents for task x should be less or equal to cost of task x. The objective is to find the set of tasks with most value which agents can pay.

I'm working with gams software so i describe it in gams-style: set a agents, t tasks parameter cost(t), value(t) parameter resources(a)

positive variable y(a,t) (non-int), part of agent a for cost of task t objective: 

maxvalue =e= sum((a,t), value(t) * y(a,t) / cost(t) );
agentresource_max_constraint(a).. sum(t, y(a,t)) =l= resources(a);
taskcost_max_constraint.. sum(a, y(a,t)) =l= cost(t);

As I wrote, I had a solution but didn't know how to separate partial task solutions. But now I found out that I can build a constraint with a

binary variable z(t)

taskcost_bin_constraint z(t) =e= sum(a, y(a,t)) / cost(t);

sum(a, y(a,t)) / cost(t) in the equation formulation is something between 0 and 1 and by this constraint, z is 0 for all less than 1 and 1 for 1. with this taskcost_bin_constraint objective would be:

maxvalue =e= sum(t, value(t) * z(t));

I was wondering but this works and gives me better solutions under the constraint, to build a task full or not.

Maybe you can also add such a constraint? A Constraint to fullfill the demands exactly, expressed in a expression with value between 0 and 1.

Improve this answer
$\endgroup$
1
$\begingroup$

There is a deterministic annealing algorithm which solves the one-to-one assignment problem or equivalently the dyadic matrix partition problem.

However instead of using integer [0, 1] values one can use fractional values (so the algorithm remains the same) or even extend it to handle more than one assignment (by adding an inner loop and eseentially the matrix becomes a hyper-dimensional array or tensor)

The paper is here: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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