invalid read in CbcModel::setBestSolution()

svigerske commented 2 years ago

We have recently updated to the latest releases of Cbc, Cgl, Osi, Clp, CoinUtils. On GAMS modellib model minlphix I sometimes get a crash on Windows (difficult to reproduce) and some serious complaints from valgrind on some memcopy within CbcModel.

The memcpy that is problematic is the last line of

  int n = CoinMax(numberColumns, solver_->getNumCols());
  delete[] bestSolution_;
  bestSolution_ = new double[n];
  memset(bestSolution_, 0, n * sizeof(double));
  memcpy(bestSolution_, solution, numberColumns * sizeof(double));

Somehow is reads more bytes from solution than have been allocated. (Note that numberColumns is here CoinMax(numberColumns, solver_->getNumCols()).)

The solution array has been allocated in the last line of:

    int n = solver_->getNumCols();
    int k;
    for (k = numberSavedSolutions_ - 1; k >= 0; k--) {
      double *sol = savedSolutions_[k];
      assert(static_cast< int >(sol[0]) == n);
      if (objectiveValue > sol[1])
        break;
    }
    k++; // where to put
    if (k < maximumSavedSolutions_) {
      if (numberSavedSolutions_ == maximumSavedSolutions_) {
        save = savedSolutions_[numberSavedSolutions_ - 1];
      } else {
        save = new double[n + 2];

Here, n is only solver_->getNumCols().

More detailed log:

╶ Supporting Hyperplane Optimization Toolkit (SHOT) ──────────────────────────────────────────────────────────────────╴

 Andreas Lundell and Jan Kronqvist, Åbo Akademi University, Finland.
 See documentation for full list of contributors and utilized software libraries.

 Version: 1.1. Git hash: 033622c6.

 For more information visit https://shotsolver.dev

 Performing bound tightening on reformulated problem.
  - Bounds for 66 variables tightened in 0.31 s and 2 passes.
  - Objective bounds are: [-1.79769e+308, 1.79769e+308]

╶ Problem instance ───────────────────────────────────────────────────────────────────────────────────────────────────╴

                                    Original             Reformulated

 Problem classification:            MINLP, nonconvex     MINLP, nonconvex

 Objective function direction:      minimize             minimize
 Objective function type:           nonlinear, nonconvex nonlinear, nonconvex

 Number of constraints:             104                  104
  - linear:                         96                   96
  - nonconvex nonlinear:            8                    8

 Number of variables:               84                   84
  - real:                           64                   64
  - binary:                         20                   20
  - nonlinear:                      36                   36

╶ Options ────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Options read from file:     shot.opt

 Options specified:

  - Dual.ESH.InteriorPoint.CuttingPlane.IterationLimit = 50
  - Dual.HyperplaneCuts.ConstraintSelectionFactor = 1
  - Dual.HyperplaneCuts.UseIntegerCuts = true
  - Dual.MIP.NumberOfThreads = 1
  - Dual.MIP.Presolve.UpdateObtainedBounds = false
  - Dual.MIP.SolutionLimit.Initial = 2147483647
  - Dual.MIP.Solver = 2
  - Dual.Relaxation.Use = false
  - Dual.TreeStrategy = 0
  - Model.BoundTightening.FeasibilityBased.TimeLimit = 5
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.Console.DualSolver.Show = true
  - Output.Console.Iteration.Detail = 0
  - Primal.FixedInteger.CallStrategy = 0
  - Primal.FixedInteger.OnlyUniqueIntegerCombinations = false
  - Primal.FixedInteger.Solver = 1
  - Primal.FixedInteger.Source = 0
  - Primal.Tolerance.TrustLinearConstraintValues = false
  - Subsolver.Ipopt.LinearSolver = 1
  - Termination.IterationLimit = 2147483647
  - Termination.ObjectiveGap.Absolute = 1e-10
  - Termination.ObjectiveGap.Relative = 0.0001
  - Termination.TimeLimit = 10000000000

 Dual strategy:              Multi-tree
  - cut algorithm:           ESH
  - solver:                  Cbc 2.10.8

 Primal NLP solver:          CONOPT (automatically selected) in GAMS 40.0

╶ Interior point search ──────────────────────────────────────────────────────────────────────────────────────────────╴

 Strategy selected:          cutting plane minimax

      | No integer variables - nothing to do 
      | processed model has 18 rows, 14 columns (0 integer (0 of which binary)) and 42 elements 
      | No integer variables - nothing to do 
    Iteration     │  Time  │    Cuts     │     Objective value     │  Objective diff.   
     #: type      │  tot.  │   + | tot.  │    problem | line srch  │    abs. | rel.    
╶─────────────────┴────────┴─────────────┴─────────────────────────┴──────────────────╴
     1: LP           7.89                      -1e+12 | -1e+12          inf. | inf.    
      | No integer variables - nothing to do 
      | processed model has 18 rows, 14 columns (0 integer (0 of which binary)) and 42 elements 
      | No integer variables - nothing to do 
     2: LP           8.63      2 | 2         -1365.34 | 35.66        1.4e+03 | 1.0e+00 
      | No integer variables - nothing to do 
      | processed model has 22 rows, 17 columns (0 integer (0 of which binary)) and 52 elements 
      | No integer variables - nothing to do 
     3: LP           8.85      2 | 4         -1100.04 | 21.0743      1.1e+03 | 1.0e+00 
      | No integer variables - nothing to do 
      | processed model has 24 rows, 19 columns (0 integer (0 of which binary)) and 58 elements 
      | No integer variables - nothing to do 
     4: LP           9.03      2 | 6                0 | 24.3679      2.4e+01 | 2.4e+11 
      | No integer variables - nothing to do 
      | processed model has 26 rows, 21 columns (0 integer (0 of which binary)) and 64 elements 
      | No integer variables - nothing to do 
     5: LP           9.24      2 | 8                0 | 3.24462      3.2e+00 | 3.2e+10 
      | No integer variables - nothing to do 
      | processed model has 25 rows, 21 columns (0 integer (0 of which binary)) and 63 elements 
      | No integer variables - nothing to do 
     6: LP           9.42      2 | 10               0 | 0.306896     3.1e-01 | 3.1e+09 
      | No integer variables - nothing to do 
      | processed model has 27 rows, 21 columns (0 integer (0 of which binary)) and 69 elements 
      | No integer variables - nothing to do 
     7: LP           9.61      2 | 12               0 | 0.0547926    5.5e-02 | 5.5e+08 
      | No integer variables - nothing to do 
      | processed model has 28 rows, 21 columns (0 integer (0 of which binary)) and 72 elements 
      | No integer variables - nothing to do 
     8: LP           9.80      2 | 14               0 | 0.011973     1.2e-02 | 1.2e+08 
      | No integer variables - nothing to do 
      | processed model has 29 rows, 21 columns (0 integer (0 of which binary)) and 75 elements 
      | No integer variables - nothing to do 
     9: LP          10.00      2 | 16               0 | 0.0028152    2.8e-03 | 2.8e+07 
      | No integer variables - nothing to do 
      | processed model has 30 rows, 21 columns (0 integer (0 of which binary)) and 78 elements 
      | No integer variables - nothing to do 
    10: LP          10.19      2 | 18               0 | 0.000683426  6.8e-04 | 6.8e+06 
      | No integer variables - nothing to do 
      | processed model has 31 rows, 21 columns (0 integer (0 of which binary)) and 81 elements 
      | No integer variables - nothing to do 
    11: LP          10.37      2 | 20               0 | 0.000168416  1.7e-04 | 1.7e+06 
      | No integer variables - nothing to do 
      | processed model has 32 rows, 21 columns (0 integer (0 of which binary)) and 84 elements 
      | No integer variables - nothing to do 
    12: LP          10.59      2 | 22               0 | 4.18052e-05  4.2e-05 | 4.2e+05 
      | No integer variables - nothing to do 
      | processed model has 33 rows, 21 columns (0 integer (0 of which binary)) and 87 elements 
      | No integer variables - nothing to do 
    13: LP          10.78      2 | 24               0 | 1.04144e-05  1.0e-05 | 1.0e+05 
      | No integer variables - nothing to do 
      | processed model has 34 rows, 21 columns (0 integer (0 of which binary)) and 90 elements 
      | No integer variables - nothing to do 
    14: LP          10.98      2 | 26               0 | 2.59899e-06  2.6e-06 | 2.6e+04 
      | No integer variables - nothing to do 
      | processed model has 35 rows, 21 columns (0 integer (0 of which binary)) and 93 elements 
      | No integer variables - nothing to do 
    15: LP          11.18      2 | 28               0 | 6.49175e-07  6.5e-07 | 6.5e+03 
      | No integer variables - nothing to do 
      | processed model has 36 rows, 21 columns (0 integer (0 of which binary)) and 96 elements 
      | No integer variables - nothing to do 
    16: LP          11.38      2 | 30    -3.24301e-07 | 2.83826e-07  6.1e-07 | 1.9e+00 
      | No integer variables - nothing to do 
      | processed model has 37 rows, 21 columns (0 integer (0 of which binary)) and 99 elements 
      | No integer variables - nothing to do 
    17: LP          11.57      2 | 32               0 | 2.43341e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 38 rows, 21 columns (0 integer (0 of which binary)) and 102 elements 
      | No integer variables - nothing to do 
    18: LP          11.76      2 | 34               0 | 2.43343e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 39 rows, 21 columns (0 integer (0 of which binary)) and 105 elements 
      | No integer variables - nothing to do 
    19: LP          11.96      2 | 36               0 | 2.43349e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 40 rows, 21 columns (0 integer (0 of which binary)) and 108 elements 
      | No integer variables - nothing to do 
    20: LP          12.16      2 | 38               0 | 2.43361e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 41 rows, 21 columns (0 integer (0 of which binary)) and 111 elements 
      | No integer variables - nothing to do 
    21: LP          12.37      2 | 40               0 | 2.43377e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 42 rows, 21 columns (0 integer (0 of which binary)) and 114 elements 
      | No integer variables - nothing to do 
    22: LP          12.61      2 | 42               0 | 2.43397e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 43 rows, 21 columns (0 integer (0 of which binary)) and 117 elements 
      | No integer variables - nothing to do 
    23: LP          12.84      2 | 44               0 | 2.43422e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 44 rows, 21 columns (0 integer (0 of which binary)) and 120 elements 
      | No integer variables - nothing to do 
    24: LP          13.08      2 | 46               0 | 2.43451e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 45 rows, 21 columns (0 integer (0 of which binary)) and 123 elements 
      | No integer variables - nothing to do 
    25: LP          13.32      2 | 48               0 | 2.43485e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 46 rows, 21 columns (0 integer (0 of which binary)) and 126 elements 
      | No integer variables - nothing to do 
    26: LP          13.56      2 | 50               0 | 2.43523e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 47 rows, 21 columns (0 integer (0 of which binary)) and 129 elements 
      | No integer variables - nothing to do 
    27: LP          13.76      2 | 52               0 | 2.43565e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 48 rows, 21 columns (0 integer (0 of which binary)) and 132 elements 
      | No integer variables - nothing to do 
    28: LP          13.97      2 | 54               0 | 2.43612e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 49 rows, 21 columns (0 integer (0 of which binary)) and 135 elements 
      | No integer variables - nothing to do 
    29: LP          14.22      2 | 56               0 | 2.43662e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 50 rows, 21 columns (0 integer (0 of which binary)) and 138 elements 
      | No integer variables - nothing to do 
    30: LP          14.45      2 | 58               0 | 2.43718e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 51 rows, 21 columns (0 integer (0 of which binary)) and 141 elements 
      | No integer variables - nothing to do 
    31: LP          14.66      2 | 60               0 | 2.43777e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 52 rows, 21 columns (0 integer (0 of which binary)) and 144 elements 
      | No integer variables - nothing to do 
    32: LP          14.88      2 | 62               0 | 2.4384e-07   2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 53 rows, 21 columns (0 integer (0 of which binary)) and 147 elements 
      | No integer variables - nothing to do 
    33: LP          15.10      2 | 64               0 | 2.43907e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 54 rows, 21 columns (0 integer (0 of which binary)) and 150 elements 
      | No integer variables - nothing to do 
    34: LP          15.32      2 | 66               0 | 2.43979e-07  2.4e-07 | 2.4e+03 
      | No integer variables - nothing to do 
      | processed model has 55 rows, 21 columns (0 integer (0 of which binary)) and 153 elements 
      | No integer variables - nothing to do 
    35: LP          15.54      2 | 68               0 | 2.44054e-07  2.4e-07 | 2.4e+03 

 Maximum deviation in interior point is too large: 0.000

 No interior point found!                            

╶ Main iteration step ────────────────────────────────────────────────────────────────────────────────────────────────╴

    Iteration     │  Time  │  Dual cuts  │     Objective value     │   Objective gap   │     Current solution
     #: type      │  tot.  │   + | tot.  │       dual | primal     │    abs. | rel.    │    obj.fn. | max.err.
╶─────────────────┴────────┴─────────────┴─────────────────────────┴───────────────────┴──────────────────────────────╴

      | 8 variables fixed 
      | 0 fixed, 0 tightened bounds, 10 strengthened rows, 1 substitutions 
      | processed model has 17 rows, 13 columns (5 integer (5 of which binary)) and 43 elements 
      | Initial state - 3 integers unsatisfied sum - 0.872028 
      | Pass   1: suminf.    0.00000 (0) obj. -1e+09 iterations 3 
      | Solution found of -1e+09 
      | Relaxing continuous gives -1e+09 
      | Before mini branch and bound, 2 integers at bound fixed and 5 continuous 
      | Mini branch and bound did not improve solution (0.56 seconds) 
      | After 0.58 seconds - Feasibility pump exiting with objective of -1e+09 - took 0.15 seconds 
      | Integer solution of -1e+09 found by feasibility pump after 0 iterations and 0 nodes (0.67 seconds) 
      | Search completed - best objective -1000000000, took 0 iterations and 0 nodes (0.71 seconds) 
      | Maximum depth 0, 0 variables fixed on reduced cost 
     1: MILP-F      16.72                       -inf. | inf.            inf. | inf.          -1e+09 | 101: 1.05e+02    
     1: NLPSOLPT-O  18.98                       -inf. | 582.236         inf. | inf.         582.236 | 8: 0.00e+00      
      | 8 variables fixed 
      | 0 fixed, 0 tightened bounds, 11 strengthened rows, 1 substitutions 
      | 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions 
      | processed model has 23 rows, 18 columns (6 integer (6 of which binary)) and 71 elements 
      | MIPStart provided solution with cost 582.236 
      | Integer solution of -117571.84 found by Reduced search after 0 iterations and 0 nodes (0.22 seconds) 
      | Integer solution of -117786.46 found by DiveCoefficient after 0 iterations and 0 nodes (0.34 seconds) 
==2011461== Invalid read of size 8
==2011461==    at 0x484F9C7: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2011461==    by 0x5CE9069: CbcModel::setBestSolution(double const*, int, double, bool) (CbcModel.cpp:15533)
==2011461==    by 0x5D3E9EC: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7370)
==2011461==    by 0x5954A27: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:711)
==2011461==    by 0x5C0F9A3: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:127)
==2011461==    by 0x5B85A7A: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==2011461==    by 0x5907CFF: SHOT::Solver::solveProblem() (Solver.cpp:653)
==2011461==    by 0x5A3F69B: shtCallSolver (EntryPointsGAMS.cpp:213)
==2011461==    by 0x5A3FCF3: C__shtCallSolver (EntryPointsGAMS.cpp:270)
==2011461==    by 0x5332AD5: GMSCONF_tgmsconf_DOT_sccallsolver(GMSCONF_tgmsconf_OD_S*, int, void*, void*) (gmsconf.c:2783)
==2011461==    by 0x53262AB: libsolver(unsigned char*, unsigned char*, unsigned char const*, GMOMDODEFEX_tgmomodel_OD_S**, GEVDOORG_tgmsenvironment_OD_S**) (gevdoorg.c:3091)
==2011461==    by 0x53279AE: GEVDOORG_tgmsenvironment_DOT_gevcallsolver(GEVDOORG_tgmsenvironment_OD_S*, void*, unsigned char const*, unsigned char const*, int, int, unsigned char const*, unsigned char const*, double, int, int, double, double, void**, unsigned char*) (gevdoorg.c:3480)
==2011461==  Address 0x4e70750 is 0 bytes after a block of size 160 alloc'd
==2011461==    at 0x48472E3: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2011461==    by 0x5CF1ADF: CbcModel::saveExtraSolution(double const*, double) (CbcModel.cpp:17680)
==2011461==    by 0x5CF1C36: CbcModel::saveBestSolution(double const*, double) (CbcModel.cpp:17698)
==2011461==    by 0x5CE0044: CbcModel::setBestSolution(CBC_Message, double&, double const*, int) (CbcModel.cpp:13213)
==2011461==    by 0x5CE9E61: CbcModel::doHeuristicsAtRoot(int) (CbcModel.cpp:15747)
==2011461==    by 0x5CB8481: CbcModel::branchAndBound(int) (CbcModel.cpp:2814)
==2011461==    by 0x5D3E485: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:7297)
==2011461==    by 0x5954A27: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:711)
==2011461==    by 0x5C0F9A3: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:127)
==2011461==    by 0x5B85A7A: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==2011461==    by 0x5907CFF: SHOT::Solver::solveProblem() (Solver.cpp:653)
==2011461==    by 0x5A3F69B: shtCallSolver (EntryPointsGAMS.cpp:213)
==2011461==

CC @jjhforrest

jjhforrest commented 2 years ago

Can't see any obvious recent changes to cause this. Looking at release 2_108, I think the call to setBestSolution at 7363 of CbcSolver.cpp is the one giving the error. Does the error go away if the argument model.solver()->getNumCols(), is changed to CoinMin(model.solver()->getNumCols(),babModel->solver()->getNumCols())

svigerske commented 2 years ago

Yes, that helps!

╶ Main iteration step ────────────────────────────────────────────────────────────────────────────────────────────────╴

    Iteration     │  Time  │  Dual cuts  │     Objective value     │   Objective gap   │     Current solution
     #: type      │  tot.  │   + | tot.  │       dual | primal     │    abs. | rel.    │    obj.fn. | max.err.
╶─────────────────┴────────┴─────────────┴─────────────────────────┴───────────────────┴──────────────────────────────╴

      | 8 variables fixed 
      | 0 fixed, 0 tightened bounds, 10 strengthened rows, 1 substitutions 
      | processed model has 17 rows, 13 columns (5 integer (5 of which binary)) and 43 elements 
      | Initial state - 3 integers unsatisfied sum - 0.872028 
      | Pass   1: suminf.    0.00000 (0) obj. -1e+09 iterations 3 
      | Solution found of -1e+09 
      | Relaxing continuous gives -1e+09 
      | Before mini branch and bound, 2 integers at bound fixed and 5 continuous 
      | Mini branch and bound did not improve solution (0.76 seconds) 
      | After 0.78 seconds - Feasibility pump exiting with objective of -1e+09 - took 0.19 seconds 
      | Integer solution of -1e+09 found by feasibility pump after 0 iterations and 0 nodes (0.88 seconds) 
      | Search completed - best objective -1000000000, took 0 iterations and 0 nodes (0.91 seconds) 
      | Maximum depth 0, 0 variables fixed on reduced cost 
     1: MILP-F      17.36                       -inf. | inf.            inf. | inf.          -1e+09 | 101: 1.05e+02    
     1: NLPSOLPT-O  19.17                       -inf. | 582.236         inf. | inf.         582.236 | 8: 0.00e+00      
      | 8 variables fixed 
      | 0 fixed, 0 tightened bounds, 11 strengthened rows, 1 substitutions 
      | 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions 
      | processed model has 23 rows, 18 columns (6 integer (6 of which binary)) and 71 elements 
      | MIPStart provided solution with cost 582.236 
      | Integer solution of -117571.84 found by Reduced search after 0 iterations and 0 nodes (0.21 seconds) 
      | Integer solution of -117786.46 found by DiveCoefficient after 0 iterations and 0 nodes (0.32 seconds) 
     2: MILP-O      21.10      6 | 6          -117837*| 582.236      1.2e+05 | 2.0e+02      -117837 | 8: 1.12e+03      
     2: NLPNEWDB-O  21.32      6 | 6          -117837*| 317.285         inf. | inf.         317.285 | 8: 0.00e+00

Thank you!

svigerske commented 2 years ago

Fixed by coin-or/Cbc@07f2287276c

coin-or / SHOT

invalid read in CbcModel::setBestSolution() #159