search

coin-or / Cgl

Cut Generator Library
Other
24 stars 14 forks source link

invalid write in Cgl012Cut::get_cut #45

Closed svigerske closed 5 years ago

svigerske commented 5 years ago

With the current Cbc/master and stable/2.10, I get valgrind complains on instance 012.mps.txt and crashes on Windows.

Welcome to the CBC MILP Solver 
Version: Trunk (unstable) 
Build Date: Apr  8 2019 
Revision Number: 2526 

command line - ./bin/cbc 012.mps (default strategy 1)
At line 1 NAME          BLANK     FREE
At line 2 ROWS
At line 9 COLUMNS
At line 113 RHS
At line 116 BOUNDS
At line 169 ENDATA
Problem BLANK has 5 rows, 53 columns and 204 elements
Coin0008I BLANK read with 0 errors
Continuous objective value is -2069.5 - 0.72 seconds
Cgl0003I 0 fixed, 1 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 3 rows, 51 columns (50 integer (50 of which binary)) and 151 elements
Cbc0038I Initial state - 3 integers unsatisfied sum - 0.478844
Cbc0038I Pass   1: suminf.    0.01042 (1) obj. -2059.22 iterations 6
Cbc0038I Pass   2: suminf.    0.24601 (2) obj. -2018.73 iterations 3
Cbc0038I Pass   3: suminf.    0.00000 (0) obj. -2011 iterations 2
Cbc0038I Solution found of -2011
Cbc0038I Relaxing continuous gives -2011
Cbc0038I Before mini branch and bound, 44 integers at bound fixed and 0 continuous
Cbc0038I Full problem 3 rows 51 columns, reduced to 3 rows 7 columns
Cbc0038I Mini branch and bound did not improve solution (2.34 seconds)
Cbc0038I Round again with cutoff of -2016.85
Cbc0038I Reduced cost fixing fixed 12 variables on major pass 2
Cbc0038I Pass   4: suminf.    0.01042 (1) obj. -2059.22 iterations 0
Cbc0038I Pass   5: suminf.    0.24601 (2) obj. -2018.73 iterations 3
Cbc0038I Pass   6: suminf.    0.07312 (1) obj. -2016.85 iterations 3
Cbc0038I Pass   7: suminf.    0.14063 (1) obj. -2022.25 iterations 1
Cbc0038I Pass   8: suminf.    1.06929 (4) obj. -2016.85 iterations 9
Cbc0038I Pass   9: suminf.    0.73594 (3) obj. -2016.85 iterations 5
Cbc0038I Pass  10: suminf.    0.13542 (1) obj. -2032.84 iterations 3
Cbc0038I Pass  11: suminf.    0.95885 (4) obj. -2016.85 iterations 8
Cbc0038I Pass  12: suminf.    0.63241 (2) obj. -2021.33 iterations 5
Cbc0038I Pass  13: suminf.    0.21272 (2) obj. -2016.85 iterations 2
Cbc0038I Pass  14: suminf.    0.52528 (2) obj. -2029.02 iterations 4
Cbc0038I Pass  15: suminf.    0.33158 (1) obj. -2028.12 iterations 3
Cbc0038I Pass  16: suminf.    0.40345 (2) obj. -2016.85 iterations 3
Cbc0038I Pass  17: suminf.    0.69434 (2) obj. -2043.89 iterations 2
Cbc0038I Pass  18: suminf.    1.31896 (4) obj. -2016.85 iterations 4
Cbc0038I Pass  19: suminf.    0.96725 (3) obj. -2016.85 iterations 2
Cbc0038I Pass  20: suminf.    0.78897 (3) obj. -2016.85 iterations 1
Cbc0038I Pass  21: suminf.    0.48931 (3) obj. -2016.85 iterations 6
Cbc0038I Pass  22: suminf.    0.37951 (3) obj. -2016.85 iterations 2
Cbc0038I Pass  23: suminf.    1.30062 (3) obj. -2016.85 iterations 4
Cbc0038I Pass  24: suminf.    1.30062 (3) obj. -2016.85 iterations 0
Cbc0038I Pass  25: suminf.    0.50436 (3) obj. -2016.85 iterations 2
Cbc0038I Pass  26: suminf.    0.45916 (2) obj. -2019.2 iterations 2
Cbc0038I Pass  27: suminf.    0.37071 (3) obj. -2016.85 iterations 4
Cbc0038I Pass  28: suminf.    0.29376 (2) obj. -2020.7 iterations 1
Cbc0038I Pass  29: suminf.    0.82477 (3) obj. -2016.85 iterations 6
Cbc0038I Pass  30: suminf.    0.78631 (2) obj. -2016.85 iterations 2
Cbc0038I Pass  31: suminf.    0.97732 (3) obj. -2036.12 iterations 3
Cbc0038I Pass  32: suminf.    0.70961 (3) obj. -2026.83 iterations 2
Cbc0038I Pass  33: suminf.    1.06690 (3) obj. -2016.85 iterations 1
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 32 integers at bound fixed and 0 continuous
Cbc0038I Full problem 3 rows 51 columns, reduced to 3 rows 19 columns
Cbc0038I Mini branch and bound improved solution from -2011 to -2031 (3.31 seconds)
Cbc0038I Round again with cutoff of -2038.7
Cbc0038I Reduced cost fixing fixed 22 variables on major pass 3
Cbc0038I Pass  33: suminf.    0.01099 (1) obj. -2059.23 iterations 2
Cbc0038I Pass  34: suminf.    0.39599 (2) obj. -2038.7 iterations 4
Cbc0038I Pass  35: suminf.    0.24624 (1) obj. -2038.7 iterations 2
Cbc0038I Pass  36: suminf.    0.63093 (2) obj. -2048.65 iterations 2
Cbc0038I Pass  37: suminf.    0.41258 (2) obj. -2047.17 iterations 1
Cbc0038I Pass  38: suminf.    0.77449 (3) obj. -2038.7 iterations 2
Cbc0038I Pass  39: suminf.    0.99161 (4) obj. -2038.7 iterations 6
Cbc0038I Pass  40: suminf.    0.93114 (4) obj. -2038.7 iterations 2
Cbc0038I Pass  41: suminf.    0.52202 (3) obj. -2038.7 iterations 3
Cbc0038I Pass  42: suminf.    0.24624 (1) obj. -2038.7 iterations 2
Cbc0038I Pass  43: suminf.    0.27604 (1) obj. -2041.08 iterations 1
Cbc0038I Pass  44: suminf.    1.07639 (4) obj. -2038.7 iterations 7
Cbc0038I Pass  45: suminf.    0.77789 (3) obj. -2038.7 iterations 2
Cbc0038I Pass  46: suminf.    1.09304 (3) obj. -2058.93 iterations 4
Cbc0038I Pass  47: suminf.    0.96287 (3) obj. -2038.7 iterations 2
Cbc0038I Pass  48: suminf.    0.38374 (1) obj. -2038.7 iterations 3
Cbc0038I Pass  49: suminf.    0.47396 (1) obj. -2051.7 iterations 2
Cbc0038I Pass  50: suminf.    0.44565 (1) obj. -2049.75 iterations 1
Cbc0038I Pass  51: suminf.    1.12687 (4) obj. -2038.7 iterations 4
Cbc0038I Pass  52: suminf.    0.78071 (4) obj. -2038.7 iterations 3
Cbc0038I Pass  53: suminf.    0.67418 (3) obj. -2038.7 iterations 3
Cbc0038I Pass  54: suminf.    0.50799 (2) obj. -2038.7 iterations 2
Cbc0038I Pass  55: suminf.    1.10780 (3) obj. -2046.67 iterations 4
Cbc0038I Pass  56: suminf.    0.50799 (2) obj. -2038.7 iterations 2
Cbc0038I Pass  57: suminf.    1.08186 (3) obj. -2038.7 iterations 5
Cbc0038I Pass  58: suminf.    0.53006 (3) obj. -2038.7 iterations 3
Cbc0038I Pass  59: suminf.    0.48903 (2) obj. -2049.85 iterations 4
Cbc0038I Pass  60: suminf.    0.48903 (2) obj. -2049.85 iterations 0
Cbc0038I Pass  61: suminf.    0.58337 (2) obj. -2038.7 iterations 1
Cbc0038I Pass  62: suminf.    0.97818 (4) obj. -2038.7 iterations 6
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 35 integers at bound fixed and 0 continuous
Cbc0038I Full problem 3 rows 51 columns, reduced to 3 rows 16 columns
Cbc0038I Mini branch and bound did not improve solution (3.73 seconds)
Cbc0038I After 3.74 seconds - Feasibility pump exiting with objective of -2031 - took 2.16 seconds
Cbc0012I Integer solution of -2031 found by feasibility pump after 0 iterations and 0 nodes (3.75 seconds)
Cbc0038I Full problem 3 rows 51 columns, reduced to 3 rows 6 columns
==5790== Invalid write of size 4
==5790==    at 0x3F473A: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1690)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790==  Address 0xf64f0b4 is 0 bytes after a block of size 4 alloc'd
==5790==    at 0x4839B65: calloc (vg_replace_malloc.c:752)
==5790==    by 0x3F469D: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1674)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790== 
==5790== Invalid read of size 4
==5790==    at 0x3F3ABC: Cgl012Cut::get_ori_cut_coef(int, int*, int*, int*, short) (Cgl012cut.cpp:1468)
==5790==    by 0x3F477E: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1693)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790==  Address 0xf64f0b4 is 0 bytes after a block of size 4 alloc'd
==5790==    at 0x4839B65: calloc (vg_replace_malloc.c:752)
==5790==    by 0x3F469D: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1674)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790== 
==5790== Invalid read of size 4
==5790==    at 0x3F3B50: Cgl012Cut::get_ori_cut_coef(int, int*, int*, int*, short) (Cgl012cut.cpp:1479)
==5790==    by 0x3F477E: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1693)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790==  Address 0xf64f0b4 is 0 bytes after a block of size 4 alloc'd
==5790==    at 0x4839B65: calloc (vg_replace_malloc.c:752)
==5790==    by 0x3F469D: Cgl012Cut::get_cut(cycle*) (Cgl012cut.cpp:1674)
==5790==    by 0x3F61E0: Cgl012Cut::basic_separation() (Cgl012cut.cpp:2239)
==5790==    by 0x3F8341: Cgl012Cut::sep_012_cut(int, int, int, int*, int*, int*, int*, int*, int*, int*, char*, double const*, bool, int*, int*, int**, int**, int**, int**, int**, char**) (Cgl012cut.cpp:3632)
==5790==    by 0x3D1107: CglZeroHalf::generateCuts(OsiSolverInterface const&, OsiCuts&, CglTreeInfo) (CglZeroHalf.cpp:49)
==5790==    by 0x210B9F: CbcCutGenerator::generateCuts(OsiCuts&, int, OsiSolverInterface*, CbcNode*) (CbcCutGenerator.cpp:312)
==5790==    by 0x28CAD1: CbcModel::serialCuts(OsiCuts&, CbcNode*, OsiCuts&, int) (CbcModel.cpp:9825)
==5790==    by 0x287A46: CbcModel::solveWithCuts(OsiCuts&, int, CbcNode*) (CbcModel.cpp:8450)
==5790==    by 0x271D67: CbcModel::branchAndBound(int) (CbcModel.cpp:3098)
==5790==    by 0x159A8C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7307)
==5790==    by 0x135DA9: main (CoinSolve.cpp:354)
==5790== 
Cbc0031I 8 added rows had average density of 28.75
Cbc0013I At root node, 8 cuts changed objective from -2069.4962 to -2056.6301 in 13 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 1 column cuts (1 active)  in 0.046 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 26 row cuts average 31.1 elements, 0 column cuts (0 active)  in 0.084 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 10 row cuts average 17.4 elements, 0 column cuts (0 active)  in 0.501 seconds - new frequency is 1
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.031 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 25 row cuts average 29.2 elements, 0 column cuts (0 active)  in 0.118 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 1 row cuts average 13.0 elements, 0 column cuts (0 active)  in 0.059 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 65 row cuts average 30.6 elements, 0 column cuts (0 active)  in 0.182 seconds - new frequency is 1
Cbc0014I Cut generator 7 (ZeroHalf) - 2 row cuts average 50.0 elements, 0 column cuts (0 active)  in 0.289 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, -2031 best solution, best possible -2056.6301 (5.94 seconds)
Cbc0012I Integer solution of -2038 found by DiveCoefficient after 202 iterations and 3 nodes (7.83 seconds)
Cbc0001I Search completed - best objective -2038.00002647658, took 613 iterations and 30 nodes (10.47 seconds)
Cbc0032I Strong branching done 262 times (1301 iterations), fathomed 5 nodes and fixed 8 variables
Cbc0035I Maximum depth 10, 163 variables fixed on reduced cost
Cuts at root node changed objective from -2069.5 to -2056.63
Probing was tried 68 times and created 10 cuts of which 0 were active after adding rounds of cuts (0.131 seconds)
Gomory was tried 62 times and created 48 cuts of which 0 were active after adding rounds of cuts (0.220 seconds)
Knapsack was tried 62 times and created 98 cuts of which 0 were active after adding rounds of cuts (1.918 seconds)
Clique was tried 13 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.031 seconds)
MixedIntegerRounding2 was tried 62 times and created 161 cuts of which 0 were active after adding rounds of cuts (0.435 seconds)
FlowCover was tried 13 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.059 seconds)
TwoMirCuts was tried 62 times and created 287 cuts of which 0 were active after adding rounds of cuts (0.586 seconds)
ZeroHalf was tried 13 times and created 2 cuts of which 0 were active after adding rounds of cuts (0.289 seconds)

Result - Optimal solution found

Objective value:                -2038.00002648
Enumerated nodes:               30
Total iterations:               613
Time (CPU seconds):             10.57
Time (Wallclock seconds):       11.06

Total time (CPU seconds):       10.83   (Wallclock seconds):       11.33
jjhforrest commented 5 years ago

I don't know much about this code, but I think we need

--- src/CglZeroHalf/Cgl012cut.cpp   (revision 1473)
+++ src/CglZeroHalf/Cgl012cut.cpp   (working copy)
@@ -1685,8 +1685,9 @@
   crhs = 0;
   for ( e = 0; e < s_cyc->length; e++ ) {
     i = (s_cyc->edge_list[e])->constr; 
-    if ( i >= 0 ) {
+    if ( i >= 0 && flag_comb[i] != IN) {
       /* the edge is not associated with a bound constraint */
+      assert (ncomb<inp_ilp->mr);
       comb[ncomb] = i; ncomb++; flag_comb[i] = IN;
     }
   }

Otherwise flag_comb is not used at all

svigerske commented 5 years ago

Yes, that seems to do it.

git blame told me that you added this cut generator some years ago (18d1a34f2), so I went straight to you :).

svigerske commented 5 years ago

I now remembered that you did some announcement for these cuts and explained where the original source comes from: https://list.coin-or.org/pipermail/cbc/2013-January/001002.html Thanks again for putting this in and also for the above patch (d09858105cf).