<p>This can be solved by standard linear programming algorithms.  A set of weighted choices is described by variables $y_{ij}$, where $y_{ij}=w$ if we choose $a_i$ from the $j$th set with weight $w$.  To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected.  We then have four kinds of constraints:</p>

<ul>
<li>for each $i$, $j$: $0 \le y_{ij} \le 1$ if $a_i$ is in the $j$th set;</li>
<li>for each $i$, $j$: $y_{ij} = 0$ if $a_i$ is not in the $j$th set;</li>
<li>for each $j$: $\sum_i y_{ij}=1$ [choosing a total of 1 element from the $j$th set];</li>
<li>for each $i$: $m \le \sum_j y_{ij}$ [$m$ is at most the number of chosen $a_i$'s].</li>
</ul>

<p>We choose the $y_{ij}$'s to maximize $m$; the constraints and the objective function are linear.  (In the non-weighted case, we additionally require $y_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)</p>

<p>This formulation has the following geometric interpretation.  Identify $a_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$.  For each set, say $\{a_{i_0},\ldots,a_{i_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a_{i_j}$'s as vertices.  The <a href="http://en.wikipedia.org/wiki/Minkowski_addition" rel="nofollow">Minkowski sum</a> of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x_1,\ldots,x_n)$ of totals for the elements $a_1,\ldots,a_n$.  The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.</p>

CC BY-SA 3.0
2013-07-04T08:09:34.340Z
I think I get this, but could you go into further detail about how how I can use my evaluation function? Isn't it non-linear?
Clinton
CC BY-SA 3.0
2013-07-05T00:58:23.123Z
For each a_i, the number of occurrences of a_i is linear in the y_ij's.  You're trying to maximize the min of these, which as you say is nonlinear, but it's not too bad -- it's the min of a finite number of linear functions.  So you introduce the auxiliary variable m, and impose the (linear) constraints that m is at most the number of occurrences of each of the a_i's.  When you maximize m, m is forced to be the min you were looking for.
Tad
CC BY-SA 3.0
2013-07-04T04:32:08.933Z
2013-07-04T04:32:08.933Z
Tad
<p>Lets say I have a finite set of items like the following:</p>

<p>{$a_1, a_2, ... , a_n$}</p>

<p>And I have a finite list of sets of these items. For example:</p>

<p>[{$a_1$}, {$a_1, a_2$}, {$a_1, a_2, a_3$}, {$a_1, a_3$}, {$a_2$}, {$a_2$}, {$a_2$}, {$a_3$}]</p>

<p>I then take one item from each set. For example, in the above case, I could do:</p>

<p>$a_1$ &lt;- {$a_1$}<br>
$a_2$ &lt;- {$a_1, a_2$}<br>
$a_1$ &lt;- {$a_1, a_3$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_1$ &lt;- {$a_1, a_2, a_3$}<br>
$a_3$ &lt;- {$a_3$}  </p>

<p>In this case, the totals are:</p>

<p>$a_1$: 3<br>
$a_2$: 4<br>
$a_3$: 1  </p>

<p>And the minimum is 1.</p>

<p>But lets say I want to maximise the minimum. I could instead select the items like:</p>

<p>$a_1$ &lt;- {$a_1$}<br>
$a_2$ &lt;- {$a_1, a_2$}<br>
$a_3$ &lt;- {$a_1, a_3$} (changed)<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_1$ &lt;- {$a_1, a_2, a_3$}<br>
$a_3$ &lt;- {$a_3$}  </p>

<p>And the totals are:</p>

<p>$a_1$: 2<br>
$a_2$: 4<br>
$a_3$: 2  </p>

<p>And the minimum is 2.</p>

<p>Lets say also I allow the items to be assigned in a weighted way. Like the following:</p>

<p>$a_1$ &lt;- {$a_1$}<br>
$a_1$ &lt;- {$a_1, a_2$} (changed)<br>
$a_3$ &lt;- {$a_1, a_3$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_2$ &lt;- {$a_2$}<br>
$a_1: 0.5, a_3: 0.5$ &lt;- {$a_1, a_2, a_3$} (changed)<br>
$a_3$ &lt;- {$a_3$}  </p>

<p>And the totals are:</p>

<p>$a_1$: 2.5<br>
$a_2$: 3<br>
$a_3$: 2.5  </p>

<p>And the minimum is 2.5.</p>

<p>We can't evenly assign the items in these sets because three of them only contain {$a_2$}. </p>

<p>So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.</p>

<ds.algorithms>
Assigning items as evenly as possible
Clinton
# Assigning items as evenly as possible

(Asked by: username_0 on 2013-07-04)

Lets say I have a finite set of items like the following:

{$a\_1, a\_2, ... , a\_n$}

And I have a finite list of sets of these items. For example:

[{$a\_1$}, {$a\_1, a\_2$}, {$a\_1, a\_2, a\_3$}, {$a\_1, a\_3$}, {$a\_2$}, {$a\_2$}, {$a\_2$}, {$a\_3$}]

I then take one item from each set. For example, in the above case, I could do:

$a\_1$ <- {$a\_1$}  
$a\_2$ <- {$a\_1, a\_2$}  
$a\_1$ <- {$a\_1, a\_3$}  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_1$ <- {$a\_1, a\_2, a\_3$}  
$a\_3$ <- {$a\_3$}

In this case, the totals are:

$a\_1$: 3  
$a\_2$: 4  
$a\_3$: 1

And the minimum is 1.

But lets say I want to maximise the minimum. I could instead select the items like:

$a\_1$ <- {$a\_1$}  
$a\_2$ <- {$a\_1, a\_2$}  
$a\_3$ <- {$a\_1, a\_3$} (changed)  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_1$ <- {$a\_1, a\_2, a\_3$}  
$a\_3$ <- {$a\_3$}

And the totals are:

$a\_1$: 2  
$a\_2$: 4  
$a\_3$: 2

And the minimum is 2.

Lets say also I allow the items to be assigned in a weighted way. Like the following:

$a\_1$ <- {$a\_1$}  
$a\_1$ <- {$a\_1, a\_2$} (changed)  
$a\_3$ <- {$a\_1, a\_3$}  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_2$ <- {$a\_2$}  
$a\_1: 0.5, a\_3: 0.5$ <- {$a\_1, a\_2, a\_3$} (changed)  
$a\_3$ <- {$a\_3$}

And the totals are:

$a\_1$: 2.5  
$a\_2$: 3  
$a\_3$: 2.5

And the minimum is 2.5.

We can't evenly assign the items in these sets because three of them only contain {$a\_2$}.

So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2013-07-04. Score: 2

This can be solved by standard linear programming algorithms. A set of weighted choices is described by variables $y\_{ij}$, where $y\_{ij}=w$ if we choose $a\_i$ from the $j$th set with weight $w$. To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected. We then have four kinds of constraints:

* for each $i$, $j$: $0 \le y\_{ij} \le 1$ if $a\_i$ is in the $j$th set;
* for each $i$, $j$: $y\_{ij} = 0$ if $a\_i$ is not in the $j$th set;
* for each $j$: $\sum\_i y\_{ij}=1$ [choosing a total of 1 element from the $j$th set];
* for each $i$: $m \le \sum\_j y\_{ij}$ [$m$ is at most the number of chosen $a\_i$'s].

We choose the $y\_{ij}$'s to maximize $m$; the constraints and the objective function are linear. (In the non-weighted case, we additionally require $y\_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)

This formulation has the following geometric interpretation. Identify $a\_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$. For each set, say $\{a\_{i\_0},\ldots,a\_{i\_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a\_{i\_j}$'s as vertices. The [Minkowski sum](http://en.wikipedia.org/wiki/Minkowski_addition) of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x\_1,\ldots,x\_n)$ of totals for the elements $a\_1,\ldots,a\_n$. The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.

> **Comments:**
> **username_0**: I think I get this, but could you go into further detail about how how I can use my evaluation function? Isn't it non-linear?  
> **username_1**: For each a_i, the number of occurrences of a_i is linear in the y_ij's.  You're trying to maximize the min of these, which as you say is nonlinear, but it's not too bad -- it's the min of a finite number of linear functions.  So you introduce the auxiliary variable m, and impose the (linear) constraints that m is at most the number of occurrences of each of the a_i's.  When you maximize m, m is forced to be the min you were looking for.  

---

