Re: [Help-glpk] Conflict graph is too big

[Andrew Makhorin]

> We are 3 students experiencing some problems with GLPK. 
> When we compile, the system says the following:
>  
> GLPSOL: GLPK LP/MIP Solver, v4.45
> Parameter(s) specified in the command line:
> --cover --clique --gomory --mir -m Production de verres.mod
> Reading model section from Production de verres.mod...
> Reading data section from Production de verres.mod...
> 103 lines were read
> Generating cout...
> Generating equilibre_de_stock1...
> Generating equilibre_de_stock2...
> Generating stock_final...
> Generating contrainte_physique...
> Generating contrainte_technique...
> Generating contrainte_spaciale...
> Generating contrainte_de_non_negativite_production...
> Generating contrainte_de_non_negativite_stock...
> Model has been successfully generated
> GLPK Integer Optimizer, v4.45
> 259 rows, 144 columns, 720 non-zeros
> 144 integer variables, none of which are binary
> Preprocessing...
> 108 rows, 144 columns, 426 non-zeros
> 144 integer variables, none of which are binary
> Scaling...
> A: min|aij| = 1.000e+000  max|aij| = 1.100e+001  ratio = 1.100e+001
> GM: min|aij| = 5.373e-001  max|aij| = 1.861e+000  ratio = 3.464e+000
> EQ: min|aij| = 2.887e-001  max|aij| = 1.000e+000  ratio = 3.464e+000
> 2N: min|aij| = 2.500e-001  max|aij| = 1.500e+000  ratio = 6.000e+000
> Constructing initial basis...
> Size of triangular part = 108
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.45
> 108 rows, 144 columns, 426 non-zeros
>       0: obj = -1.721240000e+005  infeas = 9.429e+003 (0)
> *    90: obj =  1.990017261e+005  infeas = 2.188e-016 (0)
> *   134: obj =  1.843621667e+005  infeas = 0.000e+000 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> Gomory's cuts enabled
> MIR cuts enabled
> Cover cuts enabled
> Clique cuts enabled
> Creating the conflict graph...
> The conflict graph is either empty or too big
> +   134: mip =     not found yet >=              -inf        (1; 0)
>  
> After this line, it keeps on searching infinitely for an optimal
> solution. 
> How come it doesn’t find it?

Your problem is hard for glpk to be solved to optimality. In such cases
you may either wait for a time or, if you are not interested in exact
optimum, specify a time limit (say, --tmlin 600) or a mip gap (say,
--mipgap 0.10).

I managed to solve your mip to optimality for 2 minutes using --gomory
(gomory cuts) and --pcost (pseudo-cost branching):

GLPSOL: GLPK LP/MIP Solver, v4.46
Parameter(s) specified in the command line:
 -m mip.mod --gomory --pcost -o mip.sol --log mip.log
Reading model section from mip.mod...
Reading data section from mip.mod...
103 lines were read
Generating cout...
Generating equilibre_de_stock1...
Generating equilibre_de_stock2...
Generating stock_final...
Generating contrainte_physique...
Generating contrainte_technique...
Generating contrainte_spaciale...
Generating contrainte_de_non_negativite_production...
Generating contrainte_de_non_negativite_stock...
Model has been successfully generated
GLPK Integer Optimizer, v4.46
259 rows, 144 columns, 720 non-zeros
144 integer variables, none of which are binary
Preprocessing...
108 rows, 144 columns, 426 non-zeros
144 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.100e+01  ratio =  1.100e+01
GM: min|aij| =  5.373e-01  max|aij| =  1.861e+00  ratio =  3.464e+00
EQ: min|aij| =  2.887e-01  max|aij| =  1.000e+00  ratio =  3.464e+00
2N: min|aij| =  2.500e-01  max|aij| =  1.500e+00  ratio =  6.000e+00
Constructing initial basis...
Size of triangular part = 108
Solving LP relaxation...
GLPK Simplex Optimizer, v4.46
108 rows, 144 columns, 426 non-zeros
      0: obj =  -1.721240000e+05  infeas =  9.429e+03 (0)
*    90: obj =   1.990017261e+05  infeas =  0.000e+00 (0)
*   134: obj =   1.843621667e+05  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Gomory's cuts enabled
+   134: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: gmi = 14;
Cuts on level 39: gmi = 28;
+   543: >>>>>   1.845850000e+05 >=   1.845110000e+05 < 0.1% (56; 4)
Cuts on level 35: gmi = 31;
+  1694: >>>>>   1.845820000e+05 >=   1.845110000e+05 < 0.1% (56; 112)
Cuts on level 36: gmi = 31;
+  1934: >>>>>   1.845790000e+05 >=   1.845110000e+05 < 0.1% (65; 141)
+  4140: mip =   1.845790000e+05 >=   1.845110000e+05 < 0.1% (57; 377)
+  6499: mip =   1.845790000e+05 >=   1.845110000e+05 < 0.1% (61; 616)
+  8945: mip =   1.845790000e+05 >=   1.845110000e+05 < 0.1% (99; 797)
Cuts on level 31: gmi = 33;
+ 10643: >>>>>   1.845680000e+05 >=   1.845110000e+05 < 0.1% (112; 942)
Cuts on level 26: gmi = 29;
+ 11388: >>>>>   1.845580000e+05 >=   1.845110000e+05 < 0.1% (82; 1158)
+ 13158: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (100; 1385)
+ 14518: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (115; 1503)
+ 15851: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (100; 1620)
+ 17542: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (99; 1820)
+ 19509: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (95; 2051)
+ 21341: mip =   1.845580000e+05 >=   1.845110000e+05 < 0.1% (141; 2279)
Cuts on level 40: gmi = 41;
+ 22206: >>>>>   1.845560000e+05 >=   1.845110000e+05 < 0.1% (134; 2395)
Time used: 60.0 secs.  Memory used: 1.0 Mb.
+ 23832: mip =   1.845560000e+05 >=   1.845110000e+05 < 0.1% (132; 2627)
+ 25312: mip =   1.845560000e+05 >=   1.845110000e+05 < 0.1% (151; 2777)
+ 27039: mip =   1.845560000e+05 >=   1.845110000e+05 < 0.1% (152; 2962)
+ 28902: mip =   1.845560000e+05 >=   1.845110000e+05 < 0.1% (119; 3276)
Cuts on level 24: gmi = 31;
+ 29896: >>>>>   1.845510000e+05 >=   1.845110000e+05 < 0.1% (127; 3375)
Cuts on level 22: gmi = 29;
+ 30797: >>>>>   1.845450000e+05 >=   1.845110000e+05 < 0.1% (122; 3480)
+ 32739: mip =   1.845450000e+05 >=   1.845110000e+05 < 0.1% (102; 3736)
+ 34739: mip =   1.845450000e+05 >=   1.845110000e+05 < 0.1% (96; 3945)
+ 36990: mip =   1.845450000e+05 >=   1.845110000e+05 < 0.1% (84; 4147)
+ 39325: mip =   1.845450000e+05 >=   1.845110000e+05 < 0.1% (74; 4363)
+ 41344: mip =   1.845450000e+05 >=   1.845110000e+05 < 0.1% (65; 4560)
+ 43305: mip =   1.845450000e+05 >=   1.845180000e+05 < 0.1% (45; 4788)
+ 45496: mip =   1.845450000e+05 >=   1.845220000e+05 < 0.1% (20; 5024)
Time used: 120.0 secs.  Memory used: 1.1 Mb.
+ 47284: mip =   1.845450000e+05 >=   1.845220000e+05 < 0.1% (17; 5212)
+ 48313: mip =   1.845450000e+05 >=     tree is empty   0.0% (0; 5327)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   127.5 secs
Memory used: 1.3 Mb (1402002 bytes)
Writing MIP solution to `mip.sol'...

>  And what does it mean that the conflict graph is either empty or too
> big?

The conflict graph can be built only for binary variables, but your
model has general integer variables.