26
$\begingroup$

I am not a computer science theorist, but think this real world problem belongs here.

The problem

My company have several units accross the country.

We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.

That means: We'll allow a employee to left his unit if someone wants his place.

Example (ficticious) request data:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

The above, plotted: Visualization of the above data

See how we have to choose between the red, blue or black options?

The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization

The goal

Having collected all the requests, how to satisfy most of them?

Theory(?) application

Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.

Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).

The question

If this problem is expressed as

"How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph"?

Will we satisfy most of the requesters?

That being true, there is an algorithm to find that optimal set of cycles?

Will this greddy approach solve the problem?

  1. Find the biggest directed cycle on $G$;
  2. Remove it's edges from $G$;
  3. Repeat 1 until there is not a directed cycle on $G$;

Can you help me?

Do you know another way to describe the original problem (making most of requesters happy)?

Edit: changed department to unit, to better describe the problem.

$\endgroup$
  • 3
    $\begingroup$ Are you sure that you just want to avoid using the same edge more than once? From your description of the application, it looks to me that you should avoid using the same vertex more than once, which is a stronger condition. $\endgroup$ – Tsuyoshi Ito Apr 15 '12 at 12:51
  • 3
    $\begingroup$ @TsuyoshiIto: As I understand from the description, the condition is that at each vertex the indegree should be equal to the outdegree. So, vertex-disjointness is not needed. $\endgroup$ – Yoshio Okamoto Apr 15 '12 at 15:55
  • 7
    $\begingroup$ By the way, if my understanding is correct, the problem should be solvable in polynomial time by means of network flow. Namely, if we give a unit of profit for a unit of flow along an edge, and we give a unit capacity on each edge, the problem is to find a circulation of maximum profit. $\endgroup$ – Yoshio Okamoto Apr 15 '12 at 16:15
  • 3
    $\begingroup$ This post discusses a generalization of your problem okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html (think of each person as having one item to trade, namely their job placement). $\endgroup$ – Radu GRIGore Apr 15 '12 at 19:50
  • 4
    $\begingroup$ Awesome question, makes us feels like what we do can really be used in real life :). $\endgroup$ – Gopi Apr 16 '12 at 16:15
9
$\begingroup$

OK, I read the code of TradeMaximizer and I believe it solves the following, more general problem.

PROBLEM: Given is a directed graph whose arcs have costs. Find a set of vertex-disjoint cycles that maximizes the number of covered vertices first, and minimizes the total cost second.

To solve the question asked here, make the vertices be employees and draw an arc $x\to y$ of unit cost when $x$ would like the job of $y$. Note that employees are now vertices rather than edges. The nice thing is that an employee can say "I really want the job of $y$, but that of $z$ would do too".

Solution:

  1. Build a bipartite graph as follows: For each vertex $x$ in the original graph introduce a left vertex $x_L$, a right vertex $x_R$, and an arc $x_L\to x_R$ whose cost is huge (bigger than the sum of costs in the original graph). For each arc $x\to y$ in the original graph, introduce an arc $x_L\to y_R$ in the bipartite graph.

  2. Find a minimum cost perfect matching in the bipartite graph.

There is some preprocessing of the original graph too: Remove arcs between SCCs, then process all SCCs of size $>1$ as indicated above.

(In fact, TradeMaximizer iterates over all optimal solutions, according to the two criteria above, in order to heuristically optimize other things, such as the length of the biggest cycle. Big cycles increase the chance of a "deal" not going thru because one person changes their mind.)

PS: The author, Chris Okasaki, confirmed that this is what the code does, back at the blog post.

$\endgroup$
  • $\begingroup$ I managed to find a solution to the original problem using TradeMaximizer. I'll post detais tomorrow. $\endgroup$ – motobói Apr 17 '12 at 6:58
  • $\begingroup$ @motobói, but all you need to do is what I wrote in the second paragraph ... $\endgroup$ – Radu GRIGore Apr 17 '12 at 8:02
  • $\begingroup$ I found this explanation about the algorithm: boardgamegeek.com/wiki/page/TradeMaximizer $\endgroup$ – motobói Apr 19 '12 at 20:06
  • $\begingroup$ Could you explain or point to a explanation on why is necessary to remove arcs between Strong Comnected Components? $\endgroup$ – motobói Apr 23 '12 at 4:20
  • $\begingroup$ @motobói, It is an optimization (for the average case). Steps (1) and (2) should be sufficient. $\endgroup$ – Radu GRIGore Apr 23 '12 at 9:58
22
$\begingroup$

This is a standard minimum-cost circulation problem. Give each directed edge capacity $1$ and cost $-1$. Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.

Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time. This is almost the same as the obvious greedy algorithm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Here, the cost of a cycle is the sum of the costs of its edges. Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time. Each iteration reduces the cost of the current circulation by at least 1. The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$. Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.

This is not the fastest algorithm known.

$\endgroup$
  • $\begingroup$ think this works as long as a person does not want to work in more than one "unit", right? using phrasing of original question. but if people want to work in more than one unit, suspect this abstraction breaks down. OP stated problem in terms of only one unit, but this seems rather artificially constricting to me. [what human has only one preference...?] $\endgroup$ – vzn Apr 16 '12 at 4:04
  • 1
    $\begingroup$ What is a "person" and a "unit"? This is a question about graphs. $\endgroup$ – Jeffε Apr 16 '12 at 6:58
  • $\begingroup$ I am puzzled: Is my example not a counter example for this algorithm? After choosing C, the cycles C_1 and C_2 are no cycles anymore (because each cycles has one reversed edge); C won't be used again because it has positive cost after reversing its edges and there are no new cycles introduced. Are we talking about the same problem? Would love to have a mathematical formulation of the problem. $\endgroup$ – FiB Apr 16 '12 at 10:41
  • 3
    $\begingroup$ After choosing (and reversing) $C$, removing the edges of $C$ shared by $C_1$ and $C_2$ leaves one long directed cycle $C'$. Choosing (and reversing) $C'$ yields the same result as just choosing $C_1$ and $C_2$ from the beginning. (In short, $C' = C_1 + C_2 - C$.) Also: my answer is a mathematical formulation of the problem! $\endgroup$ – Jeffε Apr 16 '12 at 13:45
  • $\begingroup$ apparently a "unit" is something like a "department" and users are recording requests for transfers between departments [not exactly specific positions in the departments]? FIBs diagram seems to have units as vertices and edges as empl requests between units. FiB-- "would love to have a mathematical formulation of the problem".. it is really up to you to provide a precise formulation.. you seem to be halfway there.. $\endgroup$ – vzn Apr 16 '12 at 15:14
4
$\begingroup$

This greedy approach will not always give the best solution.

Consider a cycle $C$ with $n$ edges $\{(v_1, v_2),\dots,(v_n,v_1)\}$ and two disjoint cycles $C_1$ and $C_2$ each having $n-1$ edges and sharing one edge with $C$.

If you use the largest cycle $C$ first, you can make $n$ employees happy. Then the cycles $C_1$ and $C_2$ each lose one edge and are no cycles anymore.

But if you choose $C_1$ and $C_2$, you can make $2(n-1)=2n-2$ employees happy.

Aside: Instead of adding two cycles in the above example, you could add $\lfloor\frac{n}{2}\rfloor$ cycles which makes the greedy solution even worse.

$\endgroup$
-3
$\begingroup$

there is probably a graph theory way/formulation to solve this, but this problem sounds more like a permutation problem to me where some of all permutations are rejected and others are valid. the permutations are employees and the positions are "positions" in the company. a permutation is rejected if it doesnt fit the requirements of "person [x] wants position [y]". the distinction of units/depts/org boundaries is apparently somewhat superfluous to the solution in this case.

this type of permutation problem with constraints can be readily converted into a instance of SAT (satisfiability) problem. the boolean variable assignments represent employees, and the constraint clauses represent the "person [x] wants position [y]" constraints. there are nearby classic examples of this, one usually called the "dinner table" problem where you have seating positions and guests and not all guests want to sit next to each other (or very similarly some guests want to sit next to other guests).

and of course there are sophisticated SAT solvers for fairly large instances involving roughly up to hundreds of variables and clauses, on PC, and if the problem is not "hard", in the thousands.

see eg [1] for a professional reference and [2] for a class exercise. there is also some structural similarity to what are known as "pigeonhole problems" which are well studied in SAT circles where pigeons are assigned to pigeonholes and you have more or less holes than pigeons. in that case however the pigeons are generally seen as interchangeable. in other words the dinner table problem is like the pigeonhole problem with stronger constraints and the guests/pigeons have required preferences.

note of course/keep in mind that for these types of problems, depending on the constraints the answer may be "no such constrained solution exists".

[1] the dinner table algorithm, by crato

[2] CS402 princeton HW SAT

[3] Satisfiability problem, wikipedia

$\endgroup$
  • $\begingroup$ I tried the permutation using trademaximizer. Set a employee as a user wanting to trade his unit X for unit Y. But the software won't allow more than one user trading the same item (his unit). Each item has to be unique. To accommodate this, I would had had to have, say, [(Jones) wants to trade Unit-C-James for Unit-D-Laura or Unit-D-Sergio or Unit-D-Mary] $\endgroup$ – motobói Apr 16 '12 at 4:35

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.