Alternate approach to formulate this MIP

50 Views Asked by At

This is in concern to reformulating a previously formulated set of linear equations in my previous question: This is the link

\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}

I formulated a MIP problem based on the above. Unfortunately, the set of the above equations becomes very large that the MIP takes enormous amount of time to solve. I'm using GAMS/GUROBI.

I wanted to pose this question here, I wanted to know if we can simplify above set of equations, so that it may help.

1

There are 1 best solutions below

3
On

One simplification is to omit $(4)$, which was identified as redundant in the linked question. It is possible that the presolver already eliminates these, but it is worth trying explicitly omitting them.