[Clp] Possible bug in setObjCoeff
John Forrest
john.forrest at fastercoin.com
Tue Oct 3 04:40:24 EDT 2017
Aleksandr,
There may not be any bug in disableFactorization - it is used in
CglRedSplit cuts. It is just that it looks like the culprit. For
Gomory cuts, I used CoinFactorization directly as I thought that was
cleaner. I can find out the problem if I have code that reproduces it.
John Forrest
On 02/10/17 19:56, Aleksandr M. Kazachkov wrote:
> 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 <mailto: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 <mailto: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 <mailto: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 list
>> Clp at list.coin-or.org <mailto: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=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=44uzzR183Kli2FgqxthADCaew--5xHJeS3nKJLYUVZI&s=8eJH_mllKWgOQUaXosOa-DyBp4vzagFhEkszZeSTGBA&e=
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org <mailto: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/20171003/882bc1ba/attachment-0001.html>
More information about the Clp
mailing list