[SCIP] Solving the first node mip optimal

[Marc Pfetsch]

Hi Çiya,

as far as I know, there is no heuristic in SCIP that can do this, but in 
GCG (https://gcg.or.rwth-aachen.de/), there is the heuristic 
<heur_restmaster> that seems to be able to do this.

Best

Marc

On 16/05/2024 15:45, Çiya Aydoğan wrote:
> Hello,
> I implement a branch and price algorithm for a minimization problem 
> using SCIP in C++. I begin with artificial variables that have high 
> objective coefficients. I have a time limit for solving the problem. I 
> noticed that sometimes SCIP cannot find any better solution than the 
> initial solution. But, I write the lp file of the first node after 
> column generation is done and solve it by using the MIP solver. The 
> solver finds the optimal solution and it is much better than the initial 
> solution. Is there any way to solve mip of the first node after no 
> eligible variable is found?
> An example is below. After the first node is processed, the primal bound 
> is still 1.754146e+06. But, I know there exists a better solution if 
> it is solved as mixed integer programming.
> 
>   time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows 
> |cuts |sepa|confs|strbr|  dualbound   | primalbou
> nd  |  gap   | compl.
>   23.0s|     1 |     0 |  2410 |     - |  4995k |   0 |1060 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   24.0s|     1 |     0 |  2440 |     - |  5029k |   0 |1070 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   24.0s|     1 |     0 |  2457 |     - |  5029k |   0 |1080 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   24.0s|     1 |     0 |  2485 |     - |  5029k |   0 |1090 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   25.0s|     1 |     0 |  2507 |     - |  5029k |   0 |1100 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   25.0s|     1 |     0 |  2522 |     - |  5160k |   0 |1110 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   25.0s|     1 |     0 |  2534 |     - |  5160k |   0 |1120 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   26.0s|     1 |     0 |  2539 |     - |  5160k |   0 |1129 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   26.0s|     1 |     0 |  2545 |     - |  5160k |   0 |1136 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   26.0s|     1 |     0 |  2555 |     - |  5160k |   0 |1141 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   27.0s|     1 |     0 |  2563 |     - |  5160k |   0 |1146 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   27.0s|     1 |     0 |  2566 |     - |  5160k |   0 |1148 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   27.0s|     1 |     0 |  2573 |     - |  5214k |   0 |1152 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   28.0s|     1 |     0 |  2573 |     - |  5214k |   0 |1154 |  90 |  90 
> |   0 |  0 |   0 |   0 |      --      | 1.754146e
> +06 |    Inf | unknown
>   28.0s|     1 |     0 |  2573 |     - |  5295k |   0 |1154 |  90 |  90 
> |   0 |  0 |   0 |   0 | 5.548602e+05 | 1.754146e
> +06 | 216.14%| unknown
>   time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows 
> |cuts |sepa|confs|strbr|  dualbound   | primalbou
> nd  |  gap   | compl.
>   28.0s|     1 |     2 |  3744 |     - |  5637k |   0 |1154 |  90 |  90 
> |   0 |  1 |   0 |   0 | 5.548602e+05 | 1.754146e
> +06 | 216.14%| unknown
> r30.0s|     3 |     2 |  3874 | 309.0 |simplero|   2 |1201 |  90 |  92 | 
>    0 |  0 |   0 |   0 | 5.548602e+05 | 5.571678e
> +05 |   0.42%| unknown
> r53.0s|    10 |     4 |  5132 | 208.4 |simplero|   6 |1428 |  90 |  96 | 
>    0 |  0 |   0 |   0 | 5.555913e+05 | 5.559756e
> +05 |   0.07%|  30.94%
> 
> Best,
> Çiya
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip