How to solve this very complicated assignment problem

Question

A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends only on the position within the stack but not on which stack it is placed in. The width of a stack is the maximum of the widths of z items placed in it. The objective is to place the items in the stacks so that the sum of the widths of the stacks is minimum. No position in the stacks could be left unassigned. That means we have to choose z x n items out of m items to be placed in the stacks.

I tried to map this problem to different types of assignment problem but could not find one that exactly matches the constraints and objectives. What would be a good approach to solve this problem?

Edited based on D.W. s comment: I am looking for a practical solution. The number of stacks n is not large..it would be around 10. The number of positions within a stack, z is at most 36, but 9 is the most frequent number of positions. The number of items m on average is around 100-200. The widths are NOT integers, but floating point values (precision of 0.01 is good enough). I have not tried the integer linear programming approach...I need a very fast solution that can work for online calculation of some scheduling in an embedded system.

Answer 1

I don't see a way to solve this using standard algorithms for the assignment problem.

If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP). You can introduce zero-or-one variables $x_{i,j,k}$, where $x_{i,j,k}=1$ means that item $i$ is placed in stack $j$ position $k$, and continuous variables $w_j$, where $w_j$ represents the width of stack $j$.

It's then not too hard to write down linear inequalities that capture all your requirements. For instance, we have $\sum_{j,k} x_{i,j,k} = 1$ (each item is placed in one location) and $\sum_i x_{i,j,k} = 1$ (two items can't be placed in the same location; every position must be full) and $c_{i,k} - w_j \le M (1-x_{i,j,k})$ where $c_{i,k}$ is the width of item $i$ if placed in position $k$ and $M$ is a sufficiently large constant (this ensures that the $w$'s represent the stack widths correctly). Then, you can minimize $\sum_j w_j$ with an off-the-shelf ILP solver.

I don't know how efficient it will be, or whether it will be adequate for online realtime calculation, but I suggest you give it a try and find out.

If it is too slow, there are some options. One option is that some ILP solvers come with a way to impose a time limit; the solver tries to find the best solution it can within the time limit, with no guarantee that it will find the optimal solution. Another option would be to try to craft some heuristic that doesn't necessarily yield the optimal solution, but is fast; maybe a greedy algorithm or something. For instance, here is an off-the-cuff idea. Associate with each item the smallest possible width it could have, among all the possible places it can be placed (out of the positions that remain open). Pick the item with the largest associated value, and place it in the position that minimizes its width. Update the associated values for all items, and repeat. No guarantees about the quality of the solution, but this will be fast. One could also use the smallest amount that it increases the total cost of the solution, out of all possible placements, rather than the smallest width, as the value associated with a particular item.

Answer 2

In the single-stack case, you can find an exact solution using a kind of binary search on the minimum stack width, in which an assignment problem is solved at each step of the binary search. Although this doesn't directly yield an optimal solution for the multi-stack case, it can be used as a subroutine for solving it heuristically: e.g., after randomly or heuristically partitioning the objects into stacks in a first step, each stack can be optimised independently; repeating this with many random partitions should give a good-quality solution.

Solving the single-stack case optimally

Because the cost is determined by the maximum width of any object contained in the stack, we have to work around the "true nature" of the assignment problem, which is to minimise (or maximise) a sum of costs. Instead of directly searching for the optimum width, we can choose a particular test width $w$, and then see if we can fit $z$ objects in the stack such that none of the objects exceeds this test width. This can be accomplished by creating $m$ "agent" vertices $u_1, \dots, u_m$ and $z$ "job" vertices $v_1, \dots, v_z$, and an edge of weight 1 for each pair $(u_i, v_j)$ such that the width of item $i$, when placed in slot $j$, is at most $w$. We then solve the resulting assignment problem, looking to maximise the total score. If and only if the solution has score exactly equal to $z$, then there is a selection of $z$ items that can be arranged in the stack so that no item has width exceeding $w$. The edges in the solution describe exactly which items go to which slots. Call such an instance solvable; an instance which produces a lower score is unsolvable.

With that step in place, it should be clear that we can find the smallest achievable width $w^*$ in $O(\log w^*)$ steps by binary-searching on $w$: Whenever the problem turns out to be solvable, we try a smaller value of $w$, while whenever it is not, we try a larger value. (To initially find a range of widths containing the minimum, start out with $w=1$, and keep doubling $w$ until we get a solvable assignment problem instance.)

A different heuristic

If we constrain the problem so that we use the same width threshold $w$ for each of the $n$ stacks, this problem can be optimally solved using the same technique: Just make $n$ copies of each of the "job" vertices, and replace the score threshold $z$ with $nz$, then proceed as before. Unfortunately this could miss optimal solutions to the original (less constrained) problem in which we allow some stacks to get very wide but keep others narrow -- but it could perhaps be useful in finding "difficult" items (items that remain unassigned when the test width $w < w^*$), so that extra effort can be focussed on dealing with them.