Accelerating an integer programming model

Question

I am working on a scheduling problem, where I am solving it through column generation. The pricing problem of this algorithm is an integer programming model as follows:

\begin{equation} F_1 \Big\{V^0 + \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}_k} \mathbb{E}_{\eta} [p^w_{koi}] \times V^w_{koi} + \sum_{k \in \mathcal{K}} \sum_{t \in \mathcal{T}^{'}} \sum_{c \in \mathcal{C}} \mathbb{E}_{\eta} [p^m_{ktc}] \times V^m_{ktc} \Big\} \end{equation}

\begin{equation} F_2 = \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}_k} \sum_{t \in \mathcal{T}} \sum_{c \in \mathcal{C}} \Big[z_{koitc} - \sum_{\substack{i^{'} \in \mathcal{I}_k \\ i^{'} = i+1}} \sum_{\substack{t^{'} \in \mathcal{T} \\ t^{'} = t-FR_k; t^{'} \geq 1}} z_{ko{i^{'}}{t^{'}}c} \Big] \times V^1_{kot} + \end{equation} \begin{equation} \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}_k} \Big(p^{w}_{koi} - \sum_{t \in \mathcal{T}} \sum_{c \in \mathcal{C}} \Big[z_{koitc} - \sum_{\substack{i^{'} \in \mathcal{I}_k \\ i^{'} = i+1}} \sum_{\substack{t^{'} \in \mathcal{T} \\ t^{'} = t-FR_k; t^{'} \geq 1}} z_{ko{i^{'}}{t^{'}}c} \Big] \Big) \times V^2_{ko} \end{equation}

Now I formulate the main objective function as follows (to find columns with negative reduced cost):

\begin{equation} \min \{F_2 - F_1\} \end{equation}

Subjected to:

\begin{equation} \sum_{t \in \mathcal{T}} \sum_{c \in \mathcal{C}} \Big[z_{koitc} - \sum_{\substack{i^{'} \in \mathcal{I}_k \\ i^{'} = i+1}} \sum_{\substack{t^{'} \in \mathcal{T} \\ t^{'} = t-FR_k; t^{'} \geq 1}} z_{ko{i^{'}}{t^{'}}c} \Big] \leq p^w_{koi} \hspace{0.5cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}_k \label{eqFC1} \end{equation} \begin{equation} z_{koitc} \geq z_{ko(i+1)(t-FR_k)c} \hspace{1cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}_k/I_k; t \in \mathcal{T}^{'}; t-FR_k \geq 1; c \in \mathcal{C} \label{eqFC2} \end{equation} \begin{equation} \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}_k} \sum_{t \in \mathcal{T}^{'}} \sum_{\substack{c \in \mathcal{C} \\ \sum_{b \in \mathcal{B}_c} G_{kb} = 0 \: \lor \: (i == I_k \land t > T)}} z_{koitc} = 0 \label{eqFC3} \end{equation} \begin{equation} \sum_{k \in \mathcal{K}} \sum_{o \in \mathcal{O}} \sum_{i \in \mathcal{I}_k} \sum_{\substack{t \in \mathcal{T} \\ t < AV_{ko} \: \lor \: t > T}} \sum_{c \in \mathcal{C}} \Big[z_{koitc} - \sum_{\substack{i^{'} \in \mathcal{I}_k \\ i^{'} = i+1}} \sum_{\substack{t^{'} \in \mathcal{T} \\ t^{'} = t-FR_k; t^{'} \geq 1}} z_{ko{i^{'}}{t^{'}}c} \Big] = 0 \label{eqFC4} \end{equation} \begin{equation} 0 \leq pw_{koi} \leq UB^w_{koi} \text{ and integer} \hspace{2cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}_k \end{equation} \begin{equation} 0 \leq pm_{ktc} \leq UB^m_{ktc} \text{ and integer} \hspace{2cm} \forall k \in \mathcal{K}; t \in \mathcal{T}; c \in \mathcal{C} \end{equation} \begin{equation} z_{koitc} \ge 0 \text{ and integer} \hspace{2cm} \forall k \in \mathcal{K}; o \in \mathcal{O}; i \in \mathcal{I}_k; t \in \mathcal{T}; c \in \mathcal{C} \end{equation}

where $V_0$, $V^w_{koi}$ and $V^m_{ktc}$ are dual prices of constraints of the master problem (in column generation). These parameters are initialized with zero matrices, and as the algorithm moves forward, further entries in these matrices get positive values. Note that the expected values in the objective function are based on some linear computations. Also, I generate the model only once, and do not generate it again.

Initially, I expected that solving this model should not be time-consuming. However, as the algorithm moves forward (further entries in the matrices of $V_0$, $V^w_{koi}$ and $V^m_{ktc}$ get positive values), solving the model becomes more time-consuming. For example, the following figure shows how the computational complexity of solving the model increases (and continues to grow...):

To deal with this growing complexity, I have adapted the following strategies.

• Strategy 1: Set mipgap to greater than zero (e.g., 5% or 10%)
• Strategy 2: Removing all useless constraints and variables
• Strategy 3: Applying a warmstart strategy (giving an initial solution to the solver - based on the solution found in the recent iteration)
• Strategy 4: Finding a solution with a negative reduced cost might be enough for column generation (not necessarily the most negative one). Therefore, find the first feasible solution with a negative reduced cost (start with mipgap=1 and decrease it until the condition is met).
• Strategy 5: Find a pool of solutions with negative reduced costs and pass all of them to the master problem (adding multiple columns)
• Strategy 6: Model the problem in another way (I am not providing the other model here for the sake of brevity. However, let me know if you would like to look at it.)

Unfortunately, the above strategies are not helping! What would be your suggestion to increase the speed of this algorithm? Also, I have the following questions:

• Isn't it strange that the CPU time increases? I am solving the same problem (or instance) and the only input parameters that change are $V_0$, $V^w_{koi}$ and $V^m_{ktc}$.

Note that developing a heuristic algorithm to solve the sub-problem is more difficult than other conventional problems (might be infeasible). This is because the right-hand side values in the first constraint set are variable ($p^w_{koi}$). Also, $p^m_{ktc}$ is a variable and is used in the objective function.

Answer 1

Isn't it strange that the CPU time increases?

Imagine we are solving $$\min_x c^Tx$$ $$A_nx\geq0$$

Where $A_0$ is a zero matrix the problem simplifies after trivial presolving to $\min_x c^Tx$. If we change up $A$ by $A_1(1,2) = A_1(1,8) = 1$ and $A_1(2,1) = A_1(2,5) = 1$. After presolving the problem now looks like this:

$$\min_x c^Tx \\ 1x_2 + 1x_8\geq0 \\ 1x_1 + 1x_5\geq0$$

So by making $A_n$ contain less zeros can effectively increase the number of constraints after presolving. So an increase of compute time with the number of iteration is not suprising. If this effect is the case in your problem, the problem size after presolving should increase.

EDIT: Same thing could apply to the objective where less zeros in $c$ means less variables eliminated during presolving or more non trivial symmetries in the problem which can not be removed during presolving.