Find maximum distance between elements given constraints on some

Question

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

• The element 1 is in position 1, and element N must be at a position >= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
• Some elements must be within a certain distance from each other on the line.
• Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

• The number of elements
• A withinArray[][] where withinArray[x][y] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
• An atLeastArray[][] where atLeastArray[x][y] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray1[3] = 10, withinArray[2][4] = 20, and atLeastArray[2][3] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.

Answer 1

What you describe is a linear program. You can use the following formulation:

Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.

If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set $$ d_i+d_{i+1}+\cdots +d_{j-1} \le \ell^-_{ij}.$$ If they should be at least $\ell^+_{ij}$ away from each other you set $$ d_i+d_{i+1}+\cdots +d_{j-1} \ge \ell^+_{ij}.$$ Then maximize the objective function $\sum_{i=1}^{n-1} d_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.