The issue to test some instance on GCG (PyGCGopt)

[abb-omidi]

Dear support team,

I am currently working on a real class of scheduling problem, let me call Molding process.
In short: the problem is categorized as $(P_{m},s_{1} | r_{j}, due_{j}, S_{i,j}, pred, cap | C_{max}/JIT)$. As the complexity of the problem is high and standard MIP solvers, like Gurobi and Cplex, cannot solve the problem in a reasonable amount of time, I presumably need to use a decomposition scheme.

I have tried to test some of the formulations to see how their modeling structure can perform better in the MIP solvers. Now, I have some questions and I was wondering if,

1. In the GCG doc, you mentioned that the problem structure can either be exploited by software or the user. Would you please, elaborate more on the second form?

2. In some instances, when the software detects the number of ways the problem can be decomposed, how does it really decide which one would be selected? (The one with the max $maxWhiteScore$?)

3. If the solver decides based on $maxWhiteScore$, in many instances, the problem with a lower score can be solved faster than the one with an upper score!!!

Please, see the following log:
0 Decomp scores: d.classicScore=-1.0000, d.borderAreaScore=-1.0000, d.maxWhiteScore=0.0000, d.maxForWhiteScore=0.0000

and corresponding matrix and the solving process is:

A Dantzig-Wolfe reformulation is applied to solve the original problem.
All blocks have been deleted since only deleted constraints are contained, no reformulation is done.
Chosen structure has 0 blocks, 12929 master-only (static) variables, and 566 linking constraints.
This decomposition has a maxwhite score of 0.000000.
---
  time | node  | left  |MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|rows |mcuts|confs|strbr|  dualbound   | primalbound  |  gap  
  93.3s|     1 |     0 |      0 |     - | 182M|   0 |  12k|   0 | 567 |   0 | 566 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
Computing relative interior point (time limit: 206.39, iter limit: 61770) ...
   128s|     1 |     0 |      0 |     - |1611M|   0 |  12k|   0 | 567 |   0 | 586 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   130s|     1 |     0 |      0 |     - |1611M|   0 |  12k|   0 | 567 |   0 | 598 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   130s|     1 |     0 |      0 |     - |1611M|   0 |  12k|   0 | 567 |   0 | 610 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   131s|     1 |     0 |      0 |     - |1611M|   0 |  12k|   0 | 567 |   0 | 617 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   131s|     1 |     0 |      0 |     - |1612M|   0 |  12k|   0 | 567 |   0 | 627 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   132s|     1 |     0 |      0 |     - |1612M|   0 |  12k|   0 | 567 |   0 | 634 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   132s|     1 |     0 |      0 |     - |1612M|   0 |  12k|   0 | 567 |   0 | 649 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   132s|     1 |     0 |      0 |     - |1613M|   0 |  12k|   0 | 567 |   0 | 662 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   133s|     1 |     0 |      0 |     - |1613M|   0 |  12k|   0 | 567 |   0 | 683 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   133s|     1 |     0 |      0 |     - |1613M|   0 |  12k|   0 | 567 |   0 | 698 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
   134s|     1 |     0 |      0 |     - |1613M|   0 |  12k|   0 | 567 |   0 | 714 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf
There are no pricing problems in the decomposition. The original problem will be solved directly.
   135s|     1 |     0 |   6414 |     - |1636M|   0 |  12k|  12k| 567 | 566 | 714 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf    
   146s|     1 |     2 |   8205 |     - |1638M|   0 |  12k|  12k| 567 | 566 | 714 |   0 |   0 |   0 | 9.700000e+01 |      --      |    Inf    
   193s|    91 |     8 | 105005 |1076.4 |1641M|   0 |  12k|  12k| 567 | 626 | 714 |   0 |   0 |   0 | 9.700000e+01 | 1.060000e+02*|   9.28%  
   time | node  | left  |MLP iter|LP it/n| mem |mdpt |ovars|mvars|ocons|mcons|rows |mcuts|confs|strbr|  dualbound   | primalbound  |  gap  
   194s|    91 |     1 | 105005 |1076.4 |1642M|   0 |  12k|  12k| 567 | 626 | 714 |   0 |   0 |   0 | 9.700000e+01 | 1.030000e+02*|   6.19%  
   194s|    91 |     1 | 105005 |1076.4 |1642M|   0 |  12k|  12k| 567 | 626 | 714 |   0 |   0 |   0 | 9.700000e+01 | 9.800000e+01*|   1.03%  
   203s|   100 |    10 | 139050 |1322.4 |1642M|   0 |  12k|  12k| 567 | 626 | 714 |   0 |   0 |   0 | 9.700000e+01 | 9.800000e+01*|   1.03%  
   274s|   171 |    53 | 314181 |1800.3 |1643M|   0 |  12k|  12k| 567 | 649 | 714 |   0 |   0 |   0 | 9.700000e+01 | 9.700000e+01*|   0.00%*o
   274s|   171 |     0 | 314181 |1800.3 |1643M|   0 |  12k|  12k| 567 | 649 | 714 |   0 |   0 |   0 | 9.700000e+01 | 9.700000e+01 |   0.00%
   274s|   171 |     0 | 314181 |1800.3 |1643M|   0 |  12k|  12k| 567 | 649 | 714 |   0 |   0 |   0 | 9.700000e+01 | 9.700000e+01 |   0.00%
---
SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 274.24
Solving Nodes      : 1
Primal Bound       : +9.70000000000000e+01 (1 solutions)
Dual Bound         : +9.70000000000000e+01
Gap  

while when I choose the number with a $maxWhiteScore$ of around 0.6, it takes so longer time to solve or even it stops at time limit criteria! (In many cases, cannot find any feasible solution). Would you say, is it normal behavior or I am missing something?

4. I assume that the performance of the GCG in the worst case would be the same as SCIP. While SCIP can solve the above problem almost in 209 seconds, GCG cannot reach a feasible solution also in many cases it can decompose the problem. Is my intuition correct? If not, please correct me.

All the best
Regards

[jurgen-lentz]

1. It is possible for the user to define a decomposition in pygcgopt if he has an idea of the structure.
2. Our default score is the set partitioning foreseeing max white score (spfwh). (see https://gcg.or.rwth-aachen.de/doc-3.5.0/detection-scores.html)
   3.-4. All scores are heuristics and topic of current research. GCG is mostly only better than SCIP on structured models.

[abb-omidi]

Dear @jurgen-lentz,

Thank you so much for your reply and comments.
Please, let me work more around what you proposed and I will get back to you if I have any issues.

All the best