2
$\begingroup$

Problem:

There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either:

  1. nothing, or
  2. 1 S, or
  3. 1 B, or
  4. 2 S, or
  5. 2 B, or
  6. 1 B and 2 S

We are given the weight (float not integer) of each ball (in array $w$). There are some constraints on the weights of the boxes and balls:

  1. The total weight of a box $ \leq T$
  2. In configurations 4 and 6 above, the difference of S should be $ \leq D$
  3. In configuration 6 above, the weight of 2 S should be $\geq$ weight of 1 B

Now I want to minimise the number of boxes used.

My approach

I have modelled this as a linear programming problem with binary variables.

Let there be $M$ boxes, $N_S$ small balls and $N_B$ big balls.

Decision variables:

  1. $b1_j$ is a binary variable which is $1$ if box $j$ is in configuration $1$, else $0$. Similarly for $b2_j, b3_j, b4_j, b5_j, b6_j$ for each box $j$.
  2. $x_{ij}$ is a binary variable which is $1$ if ith big ball is in box $j$, else $0$.
  3. $y_{ij}$ is a binary variable which is $1$ if ith small ball is in box $j$, else $0$.

Constraints:

  1. Total weight of any box $\leq T$ $$\sum_{i}x_{ij}w_i + \sum_{i}y_{ij}w_i \leq T \qquad \forall \, j$$
  2. Weight difference constraint: $$y_{ij}w_i-y_{kj} w_k \leq D \qquad \forall \, i,j,k$$
  3. Each ball used exactly once: $$\sum_{j}x_{ij}=1 \qquad \forall \, i$$ $$\sum_{j}y_{ij}=1\qquad \forall \, i$$
  4. Each box is exactly one configuration: $$b1_j+b2_j+b3_j+b4_j+b5_j+b6_j=1$$ Similarly for other constraints. I hope you get the way I am trying to solve this.

Now the problem is this approach is taking a lot of time to solve using PuLP. For just 15 balls and 10 boxes it took minutes and time is increasing exponentially as the balls increase. I want to solve this for at least 100 balls.

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ Well, solving IPs is NP hard. $\endgroup$ – Raphael Feb 5 '16 at 9:49
2
$\begingroup$

Integer linear programming

Let me suggest another way of formulating this with ILP that might be worth trying. Define combination to mean a list of all of the balls in a single box. For instance, the combination might be (7,15) meaning that the box contains ball 7 and ball 15. Of course, we can enumerate all legal values for the combination, i.e., for the contents of a single box. There will be at most $1+N_S+N_B+N_S(N_S-1)/2+N_B(N_B-1)/2+N_B N_S(N_S-1)/2$ different combinations (fewer in practice due to the constraints on the difference of weights and the total weight of a box).

Now introduce a binary variable $x_{ij}$ that is 1 if the $i$th box contains combination $j$. Here $j$ is an index that ranges over all possible legal choices for the combination, i.e., for the contents of a single box. (Don't include any illegal combinations.)

We get some linear inequalities from this:

  • For each box, we must select one combination for it to contain: $\sum_j x_{ij} \le 1$.

  • Each ball must be used exactly once: $\sum_i \sum_{j \in B_k} x_{ij}=1$, where $B_k$ is the set of legal combinations that include ball $k$.

Now you can test feasibility, i.e., test whether it is possible to pack all of the balls into some given number of boxes.

For example, suppose we have 5 big balls and 10 little balls and 10 boxes. Then there will be at most about 300 legal combinations (probably fewer), so there will be about 3000 binary variables. I don't know whether PuLP will be effective, but you could give it a try.

Exact cover

Even better yet, one can note that your problem is an instance of the exact cover problem. The universe is the set of balls; each combination is a subset of the universe; and we want to find a way to cover the universe by a disjoint union of the combinations.

There are dedicated algorithms for the exact cover problem that might be faster than expressing this as an integer linear program and applying an ILP solver.

$\endgroup$
  • $\begingroup$ Thanks a ton! Formulating in terms of combinations helped speed it up a lot. PS: I wish I could upvote your answer. $\endgroup$ – Aditya Feb 8 '16 at 13:51
  • $\begingroup$ Glad it helped, @Aditya! If this solved your problem, you can mark it as the accepted answer by clicking the "checkmark"/"tick mark" on the left beneath the vote count, and that acts kinda like an upvote. $\endgroup$ – D.W. Feb 8 '16 at 16:17

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.