I want help in formulating a mixed integer linear problem formulation

Solution 1:

Define a directed acyclic graph with nodes $N=\{0,1,\dots,n+1\}$ and arcs $(i,j)$ for $0 \le i < j \le n+1$. Let binary decision variable $x_{i,j}$ indicate whether $y_i=y_j=1$ and $y_{i+1}=\dots=y_{j-1}=0$. Let $L_i$ and $U_i$ be constant lower and upper bounds on $Q_i$. (In the linked question, $L_i=0$ and $U_i=i$.) Impose linear constraints \begin{align} y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\ \sum_{j=i+1}^{n+1} x_{i,j} &= y_i &&\text{for $i\in\{0,\dots,n\}$} \tag2 \\ \sum_{j=0}^{i-1} x_{j,i} &= y_i &&\text{for $i\in\{1,\dots,n+1\}$} \tag3 \\ L_i(1-y_i) \le Q_i &\le U_i(1-y_i) &&\text{for $i\in \{1,\dots,n\}$} \tag4 \\ Q_k &= \sum_{(i,j): i < k < j} P_{k-i} x_{i,j} &&\text{for $k\in \{1,\dots,n\}$} \tag5 \end{align} Constraints $(1)$ through $(3)$ yield a directed path from node $0$ to node $n+1$. Constraint $(4)$ enforces $y_i=1 \implies Q_i=0$. Constraint $(5)$ enforces $x_{i,j}=1 \implies Q_k = P_{k-i}$.

For your sample data, take $L_i=0$ and $U_i=\max_j P_j = 8$. The constraints look like this: \begin{equation} y_{0} = 1 \\ y_{7} = 1 \\ x_{0,1} + x_{0,2} + x_{0,3} + x_{0,4} + x_{0,5} + x_{0,6} + x_{0,7} = y_{0} \\ x_{1,2} + x_{1,3} + x_{1,4} + x_{1,5} + x_{1,6} + x_{1,7} = y_{1} \\ x_{2,3} + x_{2,4} + x_{2,5} + x_{2,6} + x_{2,7} = y_{2} \\ x_{3,4} + x_{3,5} + x_{3,6} + x_{3,7} = y_{3} \\ x_{4,5} + x_{4,6} + x_{4,7} = y_{4} \\ x_{5,6} + x_{5,7} = y_{5} \\ x_{6,7} = y_{6} \\ x_{0,1} = y_{1} \\ x_{0,2} + x_{1,2} = y_{2} \\ x_{0,3} + x_{1,3} + x_{2,3} = y_{3} \\ x_{0,4} + x_{1,4} + x_{2,4} + x_{3,4} = y_{4} \\ x_{0,5} + x_{1,5} + x_{2,5} + x_{3,5} + x_{4,5} = y_{5} \\ x_{0,6} + x_{1,6} + x_{2,6} + x_{3,6} + x_{4,6} + x_{5,6} = y_{6} \\ x_{0,7} + x_{1,7} + x_{2,7} + x_{3,7} + x_{4,7} + x_{5,7} + x_{6,7} = y_{7} \\ 0 \le Q_{1} \le 8(1-y_{1}) \\ 0 \le Q_{2} \le 8(1-y_{2}) \\ 0 \le Q_{3} \le 8(1-y_{3}) \\ 0 \le Q_{4} \le 8(1-y_{4}) \\ 0 \le Q_{5} \le 8(1-y_{5}) \\ 0 \le Q_{6} \le 8(1-y_{6}) \\ Q_{1} = 8x_{0,2} + 8x_{0,3} + 8x_{0,4} + 8x_{0,5} + 8x_{0,6} + 8x_{0,7} \\ Q_{2} = 5x_{0,3} + 5x_{0,4} + 5x_{0,5} + 5x_{0,6} + 5x_{0,7} + 8x_{1,3} + 8x_{1,4} + 8x_{1,5} + 8x_{1,6} + 8x_{1,7} \\ Q_{3} = 6x_{0,4} + 6x_{0,5} + 6x_{0,6} + 6x_{0,7} + 5x_{1,4} + 5x_{1,5} + 5x_{1,6} + 5x_{1,7} + 8x_{2,4} + 8x_{2,5} + 8x_{2,6} + 8x_{2,7} \\ Q_{4} = x_{0,5} + x_{0,6} + x_{0,7} + 6x_{1,5} + 6x_{1,6} + 6x_{1,7} + 5x_{2,5} + 5x_{2,6} + 5x_{2,7} + 8x_{3,5} + 8x_{3,6} + 8x_{3,7} \\ Q_{5} = 2x_{0,6} + 2x_{0,7} + x_{1,6} + x_{1,7} + 6x_{2,6} + 6x_{2,7} + 5x_{3,6} + 5x_{3,7} + 8x_{4,6} + 8x_{4,7} \\ Q_{6} = 3x_{0,7} + 2x_{1,7} + x_{2,7} + 6x_{3,7} + 5x_{4,7} + 8x_{5,7} \end{equation}

For your sample solution with $y_0=y_1=y_4=y_7=1$ and all other $y_i=0$, the constraints imply that $x_{0,1}=x_{1,4}=x_{4,7}=1$ and all other $x_{i,j}=0$. Now compute $Q$ based on these values of $x$ and $y$ to help understand how the formulation works.

Edit: You can omit $(4)$, which is already implied by $(2)$, $(3)$, and $(5)$.