Binary assignment - distributing candies.

Question

Me and my sibling want candies. So, our parent brought us $n$ different candies. Both of us agree that the value of the $i$th candy is $c_i$. Now, we want to split the candies among ourselves so that the total value is as equitable as possible. How to come up with a binary assignment per candy, $x_i$ with $x_i=1$ meaning it goes to me and $x_i=0$ to the sibling?

---

My attempt: we can express this is an optimization problem with objective function being the sum of squares difference between the total values of my candies and the siblings candies:

$$\min_{x} \left(\sum\limits_{i=1}^n (c_ix_i) - \sum\limits_{i=1}^n c_i(1-x_i)\right)^2 $$

$$s.t. \;\;x_i \in \{0,1\}$$

This can be solved with integer programming software's, but it isn't easy to find free software's that solve these kinds of integer programs. Any thing that can be implemented from scratch in an efficient way?

Answer 1

An equivalent way to minimize the absolute difference is to minimize the maximum. That is, minimize $z$ subject to: \begin{align} \sum_i c_i x_i &\le z\\ \sum_i c_i (1 - x_i) &\le z\\ x_i &\in \{0,1\} \end{align}

Answer 2

You can make the problem marginally more solvable by turning it into an integer problem with linear constraints. One way to do that would be to assume that, in the event the candy cannot be divided evenly, that you get the larger share. Then we can say that the gap between your candy's value and your sibling's is $D = \sum{\left ( x_i c_i - (1 - x_i) c_i \right )} = 2\sum x_i c_i - \sum c_i$, and the aim is to minimise that sum while it is bounded by $D \ge 0$.

Funnily enough, our objective functions are actually equal to each other - since it's a binary problem, $x_i \in \{0, 1\}$ and so $x_i^2 = x_i$ and so you can rearrange your objective to equal mine (but your expression naturally captures the $D \ge 0$ restriction, whereas in mine it has to be added as a specific constraint.

Answer 3

@RobPratt's solution really came in handy because the optimization program I was using was only working for small problems with the way I formulated the problem. But the way he formulated it, it worked even for much larger inputs (vector $c$). Including the python code here for my future reference.

First, the necessary imports.

import numpy as np
import cvxpy as cp

This is my formulation (works for this problem but the solver bails for larger scale ones).

ci = np.array([10,7,6,3])
x = cp.Variable(len(ci),boolean=True)
objective = cp.Minimize(cp.sum_squares(ci*(2*x-1)))
problm = cp.Problem(objective,[x<=1,x>=0])
res = problm.solve()

This is @RobPratt's solution:

ci = np.array([10,7,6,3])
z = cp.Variable()
x = cp.Variable(len(ci),boolean=True)
constraints = [ci@x<=z, ci@(1-x)<=z]
objective = cp.Minimize(z+0*sum(x))
problm = cp.Problem(objective,constraints)
res = problm.solve()