Given a group of people, where each pair has a value, how can I find the configuration of pairings with the least total value?
<p>It's very much like the <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow">Assignment Problem</a>, except with a complete undirected graph rather than a bipartite graph.</p>

<p>The dumbest, most brute force-iest solution is something like this:</p>

<ol>
<li><p>Get all possible configurations of pairs...</p>

<p><code>groups = people.combination(2).to_a.combination(people.size/2).to_a</code></p></li>
<li><p>...rejecting all of the configurations that contain the same person more than once.</p>

<p><code>groups.reject! { |group| group.flatten.uniq.size &lt; people.size }</code></p></li>
<li><p>Then find the configuration with the minimum value.</p>

<p><code>groups.min_by { |group| group.inject(0) { |pair| value_for(pair) }</code></p></li>
</ol>

<p>Is there a modification of the Branch and Bound solution for the <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow">Assignment Problem</a> that takes into account that, here, the <em>Job</em> and <em>Person</em> are <strong>both</strong> People?</p>

<p>Could there be another combinatorics problem which more closely resembles what I've presented?</p>

<p>How can I get the best solution without frying my CPU?</p>

<p>Thanks!</p>