[Clp] Possible bug in setObjCoeff

Aleksandr M. Kazachkov akazachk at cmu.edu
Mon Oct 2 14:56:42 EDT 2017 

Hi John, thank you for the quick response. One follow-up, regarding
disableFactorization: are you suggesting not to use this at all? I was
under the impression that if I use enableFactorization to access getBInv
and such, then I should call disableFactorization before making any changes
to the model, resolving, etc. You say it is rarely used, so I wonder if my
impression was wrong. I use disableFactorization in other parts of my code
too, because I think I had run into "strange" behavior without it, but I
may be misremembering.

On Mon, Oct 2, 2017 at 2:19 PM John Forrest <john.forrest at fastercoin.com>
wrote:

> Aleksandr,
>
> I put
>
> modelPtr_->whatsChanged_ &= (0xffff&~64);
>
> into code anyway to make it match with other calls.
>
> I would think it was the disableFactorization that was the problem - there
> could easily be a bug and it is rarely used.
>
> As to the second part of your original post,  I would think that normally
> preprocessing it once would normally be faster.
>
> John Forrest
>
>
> On 02/10/17 18:25, Aleksandr M. Kazachkov wrote:
>
> 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
>>>
>>
>
> _______________________________________________
> Clp mailing listClp at list.coin-or.orghttps://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=44uzzR183Kli2FgqxthADCaew--5xHJeS3nKJLYUVZI&s=8eJH_mllKWgOQUaXosOa-DyBp4vzagFhEkszZeSTGBA&e=
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
>
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=S0ppFBpGWf1xOsmm_XdTdA&m=7zj5sW5Y0KTFAvNS6yD-HKZ67pNaJ4klIXuT4GwR_ms&s=qS69eiS-NyaJZsAvZYMIx8TuxS215bVfQ7Bb-RnK1ls&e=
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20171002/43b12b4c/attachment-0001.html>

More information about the Clp mailing list