StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is different from an extension of the stable marriage problem, since as I understand the OP's question, the people in each group do not have an ordered list of who they want to work with from most to least; it's a binary relationship (willing/not willing).</p> <p>This can be formulated as an integer programming problem that can be solved quite quickly. I give the mathematical formulation of the problem below; you can use a package like glpk or AMPL/CPLEX to process the data.</p> <p>Define the following matrices:</p> <p><code>M1 = |A| x |B|</code> matrix, where</p> <p><code>M1(a,b) = 1</code> if a (given member of A) is willing to work with b (given member of B), and 0 otherwise</p> <p><code>M2 = |A| x |C|</code> matrix, where <code>M2(a,c) = 1</code> if a (given member of A) is willing to work with c (given member of C), and 0 otherwise</p> <p><code>M2 = |B| x |C|</code> matrix, where</p> <p><code>M3(b,c) = 1</code> if b (given member of B) is willing to work with c (given member of C), and 0 otherwise</p> <p>Now define a new matrix we will use for our maximization:</p> <p><code>X = |A| x |B| x |C|</code> matrix, where</p> <p><code>X(a,b,c) = 1</code> if we make a, b, and c work together.</p> <p>Now, define our objective function:</p> <p>//Maximize the number of groups</p> <p>maximize <code>Sum[(all a, all b, all c) X(a,b,c)]</code></p> <p>subject to the following constraints:</p> <p>//To ensure that nobody gets placed in two groups</p> <p>For all values of a: <code>Sum[(all j, k) X(a, j, k)] <= 1</code></p> <p>For all values of b: <code>Sum[(all i, k) X(i, b, k)] <= 1</code></p> <p>For all values of c: <code>Sum[(all i, j) X(i, j, c)] <= 1</code></p> <p>//To ensure that all groups are composed of compatible individuals</p> <p>For all a,b,c: <code>X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3</code></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload