4
$\begingroup$

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...):

CPU time evolution

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.

$\endgroup$
4
  • $\begingroup$ Your first formula (starting with $F_1$) does not seem to be an equation or inequality. $\endgroup$
    – prubin
    Aug 17, 2022 at 19:52
  • $\begingroup$ How do the model dimensions (number of variables, constraints, nonzero matrix entries) change with each iteration? Are the constant, or is the model growing? $\endgroup$
    – prubin
    Aug 17, 2022 at 19:54
  • 1
    $\begingroup$ Could you post the log of the subproblem at different iterations? 10, 50 and 100 for example? $\endgroup$
    – fontanf
    Aug 18, 2022 at 7:44
  • 1
    $\begingroup$ Try plotting the complexity of the model after presolving, it could be that you are actually adding rows by changing the the $V$s. It could very well be that the effective number of constraints after presolving increases. Try different solvers (if you have problems for different iterations as .mps you could run them on different solvers on NEOS). $\endgroup$ Aug 18, 2022 at 13:41

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It doesn't seem straightforward to me that the number of non-zeros increases with the number of iterations $\endgroup$
    – fontanf
    Aug 18, 2022 at 18:36
  • $\begingroup$ "These parameters are initialized with zero matrices, and as the algorithm moves forward, further entries in these matrices get positive values." Positive number are non zero. This effect should be particularly strong when one starts from all zeros which OP does. $\endgroup$ Aug 19, 2022 at 0:06
  • $\begingroup$ $V_0$, $V^w_{koi}$ and $V^m_{ktc}$ do not appear on the constraints for my problem! They only appear in the objective function. $\endgroup$
    – mdslt
    Aug 19, 2022 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.