A slot with length $L$. I have $n$ segments, they have a positive integer length $x_1, x_2, \cdots, x_n$, respectively, and $\sum\limits_{i=1}^n x_i = L$. My goal is to fill the slot with these segments such that, for example, the distance between the $i$th segment and the $j$th segment is minimized, subject to some constraints, i.e., the 1st segment must be located in front of the 3rd, etc. These constraints always separate the segment $i$ and $j$ (they are not adjacent, no trivial solution).
Consider a simple example. A slot with length 12 and 4 segments with length $x_1=7, x_2=2, x_3=2, x_4=1$. I want to fill the slot such that the distance between the 4th segment and 2nd segment is minimized, subject to the constraints that 1st and 3rd segment must be located behind the 2nd slot but in front of the 4th slot. For this problem, only two feasible solutions exist, i.e., $[x_2, x_1, x_3, x_4]$ and $[x_2, x_3, x_1, x_4]$. Both of them lead to an optimal solution x_1+x_3=7+2=9, if you define the distance by the difference between the starting of $x_4$ and the ending of $x_2$ (it does not matter how you define the distance since the length of segments is fixed).
Is there any algorithm in literature corresponding to my problem? Or anyone has an idea how to formulate/solve this problem in general? I don't know if the title of my post is accurate enough. Any suggestion is appreciated. Thanks.
I don't know if this is a known problem, but it can be solved in linear time. View the problem as a directed graph $G$, with vertices $V(G) = \{x_1, \dots, x_n\}$ and an edge $uv$ whenever "$u$ precedes $v$" is a constraint. Finding a feasible solution to your problem is simply a topological sort of this graph.
To find an optimal solution, you want to guide your topological sort. For now, assume $x_i$ must precede $x_j$ (add the edge $x_ix_j$ if necessary). Begin with a "$x_i$-phobic topological sort", where we refuse to add $x_i$ to the list (i.e., never allow $x_i \in S$ in Kahn's algorithm from the wiki page), obtaining a list $L_1$. Now, perform a $x_j$-phobic topological sort, but follow edges backwards, obtaining a list $L_2$. Reverse $L_2$ to make it topologically sorted; also remove any elements in $L_1$ from it. We now simply need to add the remaining vertices between $L_1$ and $L_2$; this can be done with a topological sort rooted at $x_i$ which ignores all nodes in $L_1$ and $L_2$, obtaining a new list $L_3$. We finally construct $L = (L_1,L_3,L_2)$ as our answer.
The above certainly produces a topological sort (i.e., a feasible solution). I claim it is also optimal, and in fact, any element $x_k$ between $x_i$ and $x_j$ in $L$ must be between them for any feasible solution. Since $x_k$ is not in $L_1$, one can show that there is a path from $x_i$ to $x_k$; thus, $x_i$ must precede $x_k$. Similarly, since $x_k$ also wasn't found by $L_2$, there is a path from $x_k$ to $x_j$ (i.e., a path from $x_j$ to $x_k$ when the edges were reversed), so $x_k$ must precede $x_j$. Thus, our algorithm is optimal. Since topological sorting is linear in $|V(G)| + |E(G)|$, this is a linear-time algorithm.
Note that we have to run this process once for forcing $x_ix_j$, and once for $x_jx_i$. Also note that the segment lengths didn't matter.