I am trying to formulate a much bigger problem as an integer linear program, but I am stuck with one particular constraint and am not sure how to formulate it. To put it shortly, the problem deals with finding a feasible packing of packages (of different length but the same height) into a truck. Truck has three layers (bottom, middle and upper).
Due to many more constraints I have formulated the problem as follows:
I have binary variables $x_{ijp}$ where $i$ represents package ID (for each package its length is known to us), $j$ represents layer and $p$ represents position within a layer (for example starting from the front of the truck positions go as 1, 2, and so on). Then, $x_{ijp} = 1$ if package $i$ is placed in layer $j$ at position $p$.
The constraint with which I am stuck is the following:
We are given total loading length of truck $L$ and a fixed length $l<<L$. If we calculate:
$p_1$ = largest index so that length of first $p_1$ packages in the bottom most layer is $<= L-l$ (let us call this length $l_1$)
$p_2$ = smallest index so that the length of first $p_2$ packages in the upper most layer is $>=l$ (let us call this length $l_2$)
Then we want to ensure that there exits some index $p_0$, such that the length of the first $p_0$ packages in the middle layer is between $l_1$ and $l_2$.
Geometrically this would look as follows:
I.e. we are looking for existence of some kind of "little pyramid" within the layers. If the pyramid was general (not with regard to this fixed length $l$ then the problem would be easy, but the existence of the general pyramid does not imply that this constraint is satisfied).
Is formulating this constraint as linear constraint even possible? Would it perhaps be possible if I defined variables in some completely different way?
Let $w_i$ be the length of object $i$.
For each object $i$, each layer $j$ ($j = 1$ (bottom), $2$ (top) or $0$ (middle)), add a binary variable $d^j_i$ which is $1$ if object $i$ is on layer $j$ and its position is before $p_j$.
We add the constraints:
If the objects $i$ and $i'$ are on the same row and that $i'$ is before $p_j$ and after $i$, then $i$ is also before $p_j$. $$x_{i,j,p} + x_{i',j,p+1} + d^j_{i'} - 2 \leq d^j_i\;\;\forall i, i', j, p$$
The relations between the different lengths: $$l \leq l_2 = \sum_i w_id^2_i \leq \sum_i w_id^0_i \leq l_1 = \sum_i w_id^1_i \leq L-l$$