Problem in CoinFactorization::pivotOneOtherRow when adding a constraint that contains a variable more than once

[svigerske]

Issue created by migration from Trac.

Original creator: falk

Original creation time: 2011-12-06 17:49:15

Assignee: @tkralphs

(I posted this on the mailing list before)

$ cat test.cc
#include <coin/OsiClpSolverInterface.hpp>
#include <coin/CbcModel.hpp>

int main() {
  CbcModel model = CbcModel(OsiClpSolverInterface());
  model.solver()->readLp("/dev/stdin");
  model.branchAndBound();
  return 0;
}


$ cat crash3.lp                                                                                                                                                                          
\Problem name: 

Minimize
obj: - x0
Subject To
cons0:  x0 + x0 <= 1
cons1:  x1 <= 1
Bounds
End


$ g++ -g -O3 -W -Wall -I /home/hueffner/opt/cbc-2.7/include test.cc -L/home/hueffner/opt/cbc-2.7/lib -lCbc -lCbcSolver -lCgl -lClp -lCoinUtils -lOsiClp -lOsi -lz -lrt && ./a.out < crash3.lp
Cbc3007W No integer variables - nothing to do
Clp0006I 0  Obj 0 Dual inf 0.9999999 (1)
Clp0006I 0  Obj 0 Dual inf 0.9999999 (1)
zsh: segmentation fault  ./a.out < crash3.lp

This is with cbc 2.7 from svn. The segfault sometimes disappears
depending on surrounding code. valgrind reports an invalid read in
CoinFactorization::pivotOneOtherRow. With 2.5.0, I get:

Cbc3007W No integer variables - nothing to do
Clp0006I 0  Obj 0 Dual inf 1 (1)
a.out: CoinFactorization1.cpp:2108: bool CoinFactorization::pivotOneOtherRow(int, int): Assertion `where < end' failed.
zsh: abort      ./a.out < crash3.lp

Maybe this is not a valid .lp file, but cbc probably shouldn't crash.

[svigerske]

Still an issue with current Cbc/master (or CoinUtils/master).

@jjhforrest Is this something that would be easy to fix?

[jjhforrest]

Checked lp file for duplicates

[svigerske]

There is something not yet correct with your changes in CoinUtils (r2117).
I'm getting this one:

$ g++ issue121.cpp -Iinclude -Iinclude/coin `cat share/coin/doc/Cbc/cbc_addlibs.txt` && ./a.out 
ERROR: CoinLpIO::readLp, ### ERROR: 32557 duplicates in objective and matrix

Cbc3007W No integer variables - nothing to do

The number of duplicates seems a bit high.

Under valgrind, I get

$ g++ issue121.cpp -Iinclude -Iinclude/coin `cat share/coin/doc/Cbc/cbc_addlibs.txt` && valgrind --track-origins=yes ./a.out 
==14182== Memcheck, a memory error detector
==14182== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==14182== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==14182== Command: ./a.out
==14182== 
==14182== Conditional jump or move depends on uninitialised value(s)
==14182==    at 0x53EF41: CoinLpIO::readLp() (CoinLpIO.cpp:2532)
==14182==    by 0x53BAD7: CoinLpIO::readLp(char const*) (CoinLpIO.cpp:1878)
==14182==    by 0x53B6DC: CoinLpIO::readLp(char const*, double) (CoinLpIO.cpp:1850)
==14182==    by 0x2B9F1F: OsiClpSolverInterface::readLp(char const*, double) (OsiClpSolverInterface.cpp:5794)
==14182==    by 0x121A91: main (in /home/stefan/work/coin/Cbc-trunk/build/a.out)
==14182==  Uninitialised value was created by a heap allocation
==14182==    at 0x483777F: malloc (vg_replace_malloc.c:299)
==14182==    by 0x53BE4C: CoinLpIO::readLp() (CoinLpIO.cpp:1916)
==14182==    by 0x53BAD7: CoinLpIO::readLp(char const*) (CoinLpIO.cpp:1878)
==14182==    by 0x53B6DC: CoinLpIO::readLp(char const*, double) (CoinLpIO.cpp:1850)
==14182==    by 0x2B9F1F: OsiClpSolverInterface::readLp(char const*, double) (OsiClpSolverInterface.cpp:5794)
==14182==    by 0x121A91: main (in /home/stefan/work/coin/Cbc-trunk/build/a.out)
==14182== 
==14182== Conditional jump or move depends on uninitialised value(s)
==14182==    at 0x53EFBF: CoinLpIO::readLp() (CoinLpIO.cpp:2539)
==14182==    by 0x53BAD7: CoinLpIO::readLp(char const*) (CoinLpIO.cpp:1878)
==14182==    by 0x53B6DC: CoinLpIO::readLp(char const*, double) (CoinLpIO.cpp:1850)
==14182==    by 0x2B9F1F: OsiClpSolverInterface::readLp(char const*, double) (OsiClpSolverInterface.cpp:5794)
==14182==    by 0x121A91: main (in /home/stefan/work/coin/Cbc-trunk/build/a.out)
==14182==  Uninitialised value was created by a heap allocation
==14182==    at 0x483777F: malloc (vg_replace_malloc.c:299)
==14182==    by 0x53BE4C: CoinLpIO::readLp() (CoinLpIO.cpp:1916)
==14182==    by 0x53BAD7: CoinLpIO::readLp(char const*) (CoinLpIO.cpp:1878)
==14182==    by 0x53B6DC: CoinLpIO::readLp(char const*, double) (CoinLpIO.cpp:1850)
==14182==    by 0x2B9F1F: OsiClpSolverInterface::readLp(char const*, double) (OsiClpSolverInterface.cpp:5794)
==14182==    by 0x121A91: main (in /home/stefan/work/coin/Cbc-trunk/build/a.out)
==14182== 
ERROR: CoinLpIO::readLp, ### ERROR: 1 duplicates in objective and matrix

Cbc3007W No integer variables - nothing to do

In the new code,

  for (int iRow = 0;iRow<numberRows_+cnt_obj;iRow++) {
    CoinBigIndex startRow = start[iRow];
    CoinBigIndex endRow = start[iRow+1];
    for (CoinBigIndex j=startRow;j<endRow;j++) {

it seems that start[iRow+1] is uninitialized for the last iRow (the objective one?).

[jjhforrest]

Don't know code well - so misunderstood way objective/rows were stored. Looks okay now.