1
$\begingroup$

I want to find an arrangement to evenly place 12 items ($a_1, a_2, ..., a_{12}$) into 4 boxes ($b_1, b_2, b_3, b_4$) such that the cost is minimal.

Let $b(x)$ be the index of the box that contains item $x$. The cost of an arrangement is

$$\sum_{i=1}^{12} \sum_{j=1}^{12} |b(a_i) - b(a_j)| M_{i,j}$$

where $M$ is a $12\times 12$ constant matrix where all values are non-negatives.


For this instance I could use brute force with $\frac{12!}{3!3!3!3!}$ iterations, but I hope to get a generalised solution that can solve for $N$ items and $K$ boxes in a faster way.

Is there a solution faster than brute force? I have tried some operations research library (such as Google OR tools, CVXPY) but am unable to reduce the problem into a readily acceptable representation.

My intuition tells me there is no faster solution than brute force. In that case, is there an approximation algorithm that can provide good enough solution?

$\endgroup$

1 Answer 1

1
$\begingroup$

You could try expressing this as an integer linear expression: let $v_{x,b}$ be 1 if item $x$ is placed in box $b$, and let $w_{x,x',b,b'}$ be 1 if $v_{x,b}=1$ and $v_{x',b'}=1$; then your objective function is a linear function of these zero-or-one variables. You can also enforce the relationship between the $v$'s and $w$'s, and ensure that the $v$'s represent a valid placement into boxes, using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP). Then, feed the resulting ILP to an off-the-shelf ILP solver. I don't know whether this would be faster than brute force, but it is something you could try.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.