[Clp] Possible bug in setObjCoeff
Aleksandr M. Kazachkov
akazachk at cmu.edu
Mon Oct 2 13:25:09 EDT 2017
I am not 100% sure of what the error was, but I believe I have solved my
memory issue (at least valgrind says so), and maybe someone will see where
is/was the bug based on my fix. Please let me know if you have an idea, as
I would like to know to prevent future mistakes on my part, and it may also
help others.
My hunch is that my mistake had to do with some interaction between
factorization and other parts of the code.
My process was, when inputting / solving the problem:
1. Set up a new row-ordered CoinPackedMatrix. I initially have
setDimensions(0, num_cols), where num_cols is the known total # of columns.
I also reserve space for the rows using the "reserve" method. I have an
estimate for the max number of rows and maxSize.
2. Input rows one at a time into the matrix by "appendRow" (the reason for
this, instead of putting the matrix in all at once, is that the rows will
be sorted in a special order that is useful to me).
3. "New" an OsiClpSolverInterface* instance and use "loadProblem" to load
the problem from the constructed matrix and lower and upper bounds on the
rows/columns.
4. Call the method disableFactorization().
5. Call the method "getModelPtr()->cleanMatrix()" to clean the matrix.
6. With the 0 objective function still, call initialSolve() to check
feasibility.
7. Next, set each objective coefficient, one at a time, to 1 (what I
actually do is set only the coefficients of the columns for which
getVectorSize is > 0, but the memory corruption happened as long as all the
coefficients were being set one at a time).
8. Call resolve().
9. Delete the solver we created and exit out.
This process caused some memory problem. Any (i.e., just one) of the
following changes made valgrind happy:
1. Do not call disableFactorization. That seems unnecessary anyway, as
factorization would be disabled by default, I think. This was probably left
from some earlier version of my code. Though I don't quite understand why
it would cause a problem.
2. Make a call to getMatrixByRow() after step 5. (I have no idea why this
helps.)
3. Replace step 7 by a call to setObjective(...) where we set up in advance
a non-sparse vector for inputting the objective coefficients.
4. Replace step 8 by an initialSolve().
5. Instead of step 5, call cleanMatrix() directly on the row-ordered matrix
before inputting it into the OsiClpSolverInterface instance. This makes
more sense, in any case.
I would guess fixes #1 or #5 are the important ones, with regards to
understanding the problem.
Again, if anyone has an idea on where in particular I went wrong, and/or
why it was wrong, please let me know.
Thanks again, and sorry for the barrage of emails,
Aleksandr Kazachkov
On Mon, Oct 2, 2017 at 11:16 AM Aleksandr M. Kazachkov <akazachk at cmu.edu>
wrote:
> I apologize; I am not sure my report is a bug. In the case of changing a
> single objective coefficient (at a time), the proper modification to
> whatsChanged_ seems to be done in ClpSimplex (I had been looking at
> ClpModel). I am still getting a memory error, and I am trying to figure out
> how it happens.
>
> In case someone has any suggestions, below is the (abridged) valgrind
> output, which says that memory is being written to after it has been
> deleted. In particular, the issue appears to be with the call
> "alternateWeights_->clear();" at ClpPrimalColumnSteepest.cpp:3041, which
> seems to be accessing memory freed via a conditionalDelete() of
> "nextCount_" at CoinFactorization1.cpp:1734 (and 1735, for lastCount_). I
> am not sure how these arrays are connected.
>
> I would appreciate any advice, and thank you,
> Alex
>
> ==22103== 7 errors in context 1 of 2:
> ==22103== Invalid write of size 8
> ==22103== at 0xA39E10: CoinIndexedVector::clear()
> (CoinIndexedVector.cpp:51)
> ==22103== by 0x8B742D:
> ClpPrimalColumnSteepest::saveWeights(ClpSimplex*, int)
> (ClpPrimalColumnSteepest.cpp:3041)
> ==22103== by 0x95939D: ClpSimplexPrimal::statusOfProblemInPrimal(int&,
> int, ClpSimplexProgress*, bool, int, ClpSimplex*)
> (ClpSimplexPrimal.cpp:1636)
> ==22103== by 0x953FCE: ClpSimplexPrimal::primal(int, int)
> (ClpSimplexPrimal.cpp:361)
> ==22103== by 0x8DC44E: ClpSimplex::primal(int, int)
> (ClpSimplex.cpp:5971)
> ==22103== by 0x70A3E6: OsiClpSolverInterface::resolve()
> (OsiClpSolverInterface.cpp:1056)
> // abridged
> ==22103== Address 0x784dbc8 is 744 bytes inside a block of size 2,248
> free'd
> ==22103== at 0x4A07D8E: operator delete[](void*) (in
> /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==22103== by 0xA42F12: CoinArrayWithLength::conditionalDelete()
> (CoinIndexedVector.cpp:1841)
> ==22103== by 0x9E9CE2: CoinFactorization::cleanup()
> (CoinFactorization1.cpp:1734)
> ==22103== by 0x9E7E63: CoinFactorization::factor()
> (CoinFactorization1.cpp:1184)
> ==22103== by 0x8575AD: ClpFactorization::factorize(ClpSimplex*, int,
> bool) (ClpFactorization.cpp:2255)
> ==22103== by 0x8C8254: ClpSimplex::internalFactorize(int)
> (ClpSimplex.cpp:1992)
> ==22103== by 0x9554CF: ClpSimplexPrimal::statusOfProblemInPrimal(int&,
> int, ClpSimplexProgress*, bool, int, ClpSimplex*) (ClpSimplexPrimal.cpp:855)
> ==22103== by 0x953FCE: ClpSimplexPrimal::primal(int, int)
> (ClpSimplexPrimal.cpp:361)
> ==22103== by 0x8DC44E: ClpSimplex::primal(int, int)
> (ClpSimplex.cpp:5971)
> ==22103== by 0x70A3E6: OsiClpSolverInterface::resolve()
> (OsiClpSolverInterface.cpp:1056)
>
> ==22103== 8 errors in context 2 of 2:
> ==22103== Invalid write of size 8
> ==22103== at 0xA39DF3: CoinIndexedVector::clear()
> (CoinIndexedVector.cpp:50)
> ==22103== by 0x8B742D:
> ClpPrimalColumnSteepest::saveWeights(ClpSimplex*, int)
> (ClpPrimalColumnSteepest.cpp:3041)
> ==22103== by 0x95939D: ClpSimplexPrimal::statusOfProblemInPrimal(int&,
> int, ClpSimplexProgress*, bool, int, ClpSimplex*)
> (ClpSimplexPrimal.cpp:1636)
> ==22103== by 0x953FCE: ClpSimplexPrimal::primal(int, int)
> (ClpSimplexPrimal.cpp:361)
> ==22103== by 0x8DC44E: ClpSimplex::primal(int, int)
> (ClpSimplex.cpp:5971)
> ==22103== by 0x70A3E6: OsiClpSolverInterface::resolve()
> (OsiClpSolverInterface.cpp:1056)
> // abridged
> ==22103== Address 0x784e818 is 1,576 bytes inside a block of size 2,248
> free'd
> ==22103== at 0x4A07D8E: operator delete[](void*) (in
> /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==22103== by 0xA42F12: CoinArrayWithLength::conditionalDelete()
> (CoinIndexedVector.cpp:1841)
> ==22103== by 0x9E9CF7: CoinFactorization::cleanup()
> (CoinFactorization1.cpp:1735)
> ==22103== by 0x9E7E63: CoinFactorization::factor()
> (CoinFactorization1.cpp:1184)
> ==22103== by 0x8575AD: ClpFactorization::factorize(ClpSimplex*, int,
> bool) (ClpFactorization.cpp:2255)
> ==22103== by 0x8C8254: ClpSimplex::internalFactorize(int)
> (ClpSimplex.cpp:1992)
> ==22103== by 0x9554CF: ClpSimplexPrimal::statusOfProblemInPrimal(int&,
> int, ClpSimplexProgress*, bool, int, ClpSimplex*) (ClpSimplexPrimal.cpp:855)
> ==22103== by 0x953FCE: ClpSimplexPrimal::primal(int, int)
> (ClpSimplexPrimal.cpp:361)
> ==22103== by 0x8DC44E: ClpSimplex::primal(int, int)
> (ClpSimplex.cpp:5971)
> ==22103== by 0x70A3E6: OsiClpSolverInterface::resolve()
> (OsiClpSolverInterface.cpp:1056)
>
> On Mon, Oct 2, 2017 at 2:11 AM Aleksandr M. Kazachkov <akazachk at cmu.edu>
> wrote:
>
>> Hi all, I have a possible bug report, as well as a (related) question.
>>
>> 1. In OsiClpSolverInterface::setObjCoeff (when setting just one
>> coefficient), I think (unless I am misunderstanding something, in which
>> case I apologize) that line 6125
>>
>> modelPtr_->whatsChanged_ &= 0xffff;
>>
>> should be
>>
>> modelPtr_->whatsChanged_ &= (0xffff&~64);
>>
>> same as in OsiClpSolverInterface::setObjective, as the 64 bit corresponds
>> to "OBJECTIVE_SAME". This was (ultimately) causing a memory corruption
>> error for me after I would set the objective (coefficient by coefficient,
>> because my objective is sparse), resolve, then delete my solver object.
>>
>> 2. I am working with an instance in n-dimensional space, but the majority
>> of these columns are empty. In my context, I will be solving the instance
>> repeatedly with different objective functions. The first solve is an
>> "initialSolve" and subsequent solves, unless some issue is encountered, are
>> "resolve" calls.
>>
>> Is it better (faster in the long run, given the multiple resolves) to
>> preprocess the instance in advance to have no empty columns, or is that a
>> waste of time? My first thought was that it would not make much difference
>> since internally the matrix is kept in sparse form and anyway presolve
>> would catch this, but I am not sure I am right.
>>
>> Thank you in advance for your input,
>> Aleksandr Kazachkov
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20171002/ce2e895b/attachment.html>
More information about the Clp
mailing list