Algorithm to get minimum movement to avoid square overlap

Question

I have a problem in a chemistry optimization program that is equivalent to the following question. I can't find a good algorithm for it:

Suppose I get N identical free to move squares with known initial longitudes, fixed width, and M identical "obstacles" with fixed positions.

Is there a algorithm to get a "minimum" total horizontal movements of those squares that can:

1. retain the order of squares
2. result in no overlap ("no touching") of squares and obstacle; and no overlap between squares.

The "minimum total movements" generally describes the position difference of before & after the movement. It can be the sum of deviations, or root-mean-square deviation, etc, whichever is easier.

It doesn't have to be the minimum, but a close one is desired for a good optimization.

I may have up to 50 squares and 25 obstacles, so brute-force is too slow.

I also find this post. But it doesn't work with the fixed obstacles, and doesn't necessarily kept the order of squares.

Answer 1

O(|sq|^2 * |ob|) general complexity.

ob = [1, 5, 6, 7, 10, 13]
sq = [-3, 0, 3, 6, 8, 14]

Let f(i, j) represent the best solution where squares up to sq[i] must fit to the left of obstacle, ob[j]. Solve f(i, 0) for packing 1,2,3...50 squares where the right obstacle is ob[0]. Then, extending to obstacle ob[1], the solution will be

f(i, 1) = min(
  f(k, 0) + cost of placing squares sq[k+1...i] between ob[0] and ob[1]
)
for all k

Follow through for each j.

Answer 2

This feels NP-hard (although i'm not sure; a proof-attempt could be maybe based on some reduction to Bin-packing).

Edit: Ok... maybe there is a polynomial-solution (50/50 for me; i know it's not helping much). In this case the following will work, will be efficient enough to solve your problems i think, but it's unsure if it's a good idea to approach it through some proxy-problem which is NP-hard in general.

You can tackle it by (Mixed-)Integer-programming which can be used as exact-solver or to provide proven approximations.

• The general idea is to introduce N continuous variables which mark the left-position of each block
• Add constraints like: x_i + L <= x_i+1 (for all consecutive pairs; maybe a more redundant formulation helps: for all sorted pairs)
  • this will hold the order & forbid overlapping-blocks
  • x: position
  • L: length
• Now for not touching obstacles, you would need indicator-constraints and some boolean logic:
  • y_i = 1 iff x_i + L <= O_j_s (for all i for all o; s = left-pos obstacle)
  • z_i = 1 iff O_j_e <= x_i + L (e = right-pos)
  • forbid both are true: y_i + z_i <= 1 (for all i)
  • indicator-constraints will be based on additional binary-variables y, z
• If the objective is to minimize the total length of shifts:
  • objective is just the sum of differences between all x_i and a start-position for each block: linear-objective!
  • this absolute-value (which is needed) can be linearized (without introducing discrete variables); see lpsolve's tutorial on absolute values
• If the objective is to minimize the number of shifts:
  • more indicator-constraints (was moved <-> difference between start and final is > 0) + a sum over those indicator-vars -> linear-objective!

That's just a prototype-like idea. One has to carefully define what overlap means to you (inclusive, exclusive; and then a lot of boolean-approaches are described at StackOverflow: keyword: range-intersection). For formulating indicator-constraints, look up integer-programming guides or start here.

Answer 3

Here is an idea for an approximate solution, maybe it helps developing a better idea.

You could first discretize the possible positions for your rectangles. For your example these positions (intervals) could be (-5,-3), (-3, -1), (-1, 1), (2, 4), (7.5, 9.5), (10, 12), (13, 15), ... Of course you want to discretize in a way that you fit as many possible positions as possible in the space that is restricted by the obstacles.

Then you build a matrix that contains for each block the distance (that the block has to be moved) to each possible position.

With this matrix you can calculate the best assignment (yielding minimum movement) from blocks to possible positions using the Hungarian Algorithm.

After the assignment has been performed, you could adjust each box by moving it as much as possible (until hitting an obstacle) in the direction of its original position.