2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ PARI GP online might help. or looking up thue-morse sequence. $\endgroup$ – user645636 Jan 19 at 23:06
  • $\begingroup$ Greedy algorithm. But really, without knowing where you got this problem and why you are trying to solve it, it’s hard to know what sort of answer you are looking for. $\endgroup$ – Morgan Rodgers Jan 19 at 23:07
  • $\begingroup$ Your objective function is also incorrect. You should carefully consider what you are trying to minimize, and what your function represents. (The function you have here will be constant over all choices of the $x_i$) $\endgroup$ – Morgan Rodgers Jan 19 at 23:11
  • $\begingroup$ @morganrogers - I need to solve this problem in an environment that has only python numpy and scipy. I want to be able to solve it in such an environment, where I'll be given the $c_i$ vector as a table. $\endgroup$ – Rohit Pandey Jan 19 at 23:20
  • $\begingroup$ @MorganRodgers - does the edited objective fn look better? Total value of all my candies subtract from total value of all sibling's candies and square the difference. $\endgroup$ – Rohit Pandey Jan 19 at 23:27
3
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Thanks! Neat trick. $\endgroup$ – Rohit Pandey Jan 19 at 23:58
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

@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()
$\endgroup$

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.