[Coin-lpsolver] CLP resolve after objective change?
Tobias Achterberg
achterberg at zib.de
Wed Aug 16 17:57:09 EDT 2006
Testing the CLP interface of SCIP I ran into a strange behavior of
CLP. After changing some of the objective coefficients of the columns
by calling clp->setObjCoeff() and resolving the LP by calling
clp->primal(0,1) the old solution is declared to be still optimal. The
same happens with clp->dual(0,1).
May it be that clp->setObjCoeff() does not invalidate some of the
internal data structures, in particular reduced cost values?
Could you (i.e., John) try to find out what's happening? Just to give
you a slight hint of what's going on in the primal resolve, I list my
debugging output of the clp->primal() call (CLP is in the current SVN
version from today, Aug 16):
=================================
Breakpoint 2, SCIPlpiSolvePrimal (lpi=0x8b91828) at
src/scip/lpi_clp.cpp:1416
1416 int status = lpi->clp->primal(0, lpi->validFactorization ?
3 : 1);
Current language: auto; currently c++
(gdb) step
ClpSimplex::primal (this=0x8b91888, ifValuesPass=0,
startFinishOptions=3) at ClpSimplex.cpp:4504
4504 if (objective_->type()>1&&objective_->activated())
(gdb) print problemStatus_
$1 = 0
(gdb) print whatsChanged_
$2 = 65471
(gdb) next
4507 CoinAssert (ifValuesPass>=0&&ifValuesPass<3);
(gdb)
4518 int returnCode = ((ClpSimplexPrimal *)
this)->primal(ifValuesPass,startFinishOptions);
(gdb) step
ClpSimplexPrimal::primal (this=0x8b91888, ifValuesPass=0,
startFinishOptions=3) at ClpSimplexPrimal.cpp:181
181 algorithm_ = +1;
(gdb) next
185 ClpDataSave data = saveData();
(gdb)
186 matrix_->refresh(this); // make sure matrix okay
(gdb)
189 int initialStatus=problemStatus_;
(gdb)
190 int initialIterations = numberIterations_;
(gdb)
191 int initialNegDjs=-1;
(gdb) print numberIterations_
$3 = 0
(gdb) print problemStatus_
$4 = 0
(gdb) next
193 if (!startup(ifValuesPass,startFinishOptions)) {
(gdb)
196 nonLinearCost_->setAverageTheta(1.0e3);
(gdb)
197 int lastCleaned=0; // last time objective or bounds cleaned up
(gdb)
200 pivotRow_=-2;
(gdb)
203 int factorType=0;
(gdb)
204 if (problemStatus_<0&&perturbation_<100) {
(gdb)
222 ClpSimplex * saveModel=NULL;
(gdb)
223 int stopSprint=-1;
(gdb)
224 int sprintPass=0;
(gdb)
225 int reasonableSprintIteration=0;
(gdb)
226 int lastSprintIteration=0;
(gdb)
227 double lastObjectiveValue=COIN_DBL_MAX;
(gdb)
229 progress_->startCheck();
(gdb)
241 while (problemStatus_<0) {
(gdb)
244 for (iRow=0;iRow<4;iRow++) {
(gdb)
245 rowArray_[iRow]->clear();
(gdb)
244 for (iRow=0;iRow<4;iRow++) {
(gdb)
245 rowArray_[iRow]->clear();
(gdb)
244 for (iRow=0;iRow<4;iRow++) {
(gdb)
245 rowArray_[iRow]->clear();
(gdb)
244 for (iRow=0;iRow<4;iRow++) {
(gdb)
245 rowArray_[iRow]->clear();
(gdb)
244 for (iRow=0;iRow<4;iRow++) {
(gdb)
248 for (iColumn=0;iColumn<2;iColumn++) {
(gdb)
249 columnArray_[iColumn]->clear();
(gdb)
248 for (iColumn=0;iColumn<2;iColumn++) {
(gdb)
249 columnArray_[iColumn]->clear();
(gdb)
248 for (iColumn=0;iColumn<2;iColumn++) {
(gdb)
254 matrix_->refresh(this);
(gdb)
257 if
(perturbation_<101&&numberIterations_>2*(numberRows_+numberColumns_)&&(specialOptions_&4)==0
(gdb)
264 if (lastGoodIteration_==numberIterations_&&factorType)
(gdb) print perturbation_
$5 = 100
(gdb) next
266 if (saveModel) {
(gdb)
281
statusOfProblemInPrimal(lastCleaned,factorType,progress_,true,ifValuesPass,saveModel);
(gdb) step
ClpSimplexPrimal::statusOfProblemInPrimal (this=0x8b91888,
lastCleaned=@0xbf90acc4, type=0, progress=0x8e1a2a8, doFactorization=true,
ifValuesPass=0, originalModel=0x0) at ClpSimplexPrimal.cpp:662
662 int saveFirstFree=firstFree_;
(gdb) next
664 int numberPivots = factorization_->pivots();
(gdb)
665 if (type==2) {
(gdb) print numberPivots
$6 = 0
(gdb) next
678 int saveThreshold = factorization_->sparseThreshold();
(gdb)
679 int tentativeStatus = problemStatus_;
(gdb)
680 int numberThrownOut=1; // to loop round on bad factorization
in values pass
(gdb)
681 double lastSumInfeasibility=COIN_DBL_MAX;
(gdb)
682 if (numberIterations_)
(gdb)
684 int nPass=0;
(gdb)
685 while (numberThrownOut) {
(gdb)
686 int nSlackBasic=0;
(gdb)
687 if (nPass) {
(gdb)
693 nPass++;
(gdb)
694 if (problemStatus_>-3||problemStatus_==-4) {
(gdb) print problemStatus_
$7 = -1
(gdb) next
700 if (doFactorization)
(gdb)
701 primalColumnPivot_->saveWeights(this,1);
(gdb)
703 if ((type&&doFactorization)||nSlackBasic==numberRows_) {
(gdb)
762 if (problemStatus_!=-4)
(gdb)
763 problemStatus_=-3;
(gdb)
770 dummy=4;
(gdb)
771 matrix_->generalExpanded(this,9,dummy);
(gdb)
772 numberThrownOut=gutsOfSolution(NULL,NULL,(firstFree_>=0));
(gdb)
773 double sumInfeasibility =
nonLinearCost_->sumInfeasibilities();
(gdb) print numberThrownOut
$8 = 0
(gdb) next
774 if (numberThrownOut||
(gdb) print sumInfeasibilit
No symbol "sumInfeasibilit" in current context.
(gdb) print sumInfeasibility
$9 = 0
(gdb) next
685 while (numberThrownOut) {
(gdb)
808 if (progress->lastIterationNumber(0)==numberIterations_) {
(gdb) print numberIterations_
$10 = 0
(gdb) print progress->lastIterationNumber(0)
$11 = -1
(gdb) next
815 if
((specialOptions_&1024)!=0&&!numberPrimalInfeasibilities_&&numberDualInfeasibilities_)
{
(gdb) print specialOptions_
$12 = 0
(gdb) print numberPrimalInfeasibilities_
$13 = 0
(gdb) print numberDualInfeasibilities_
$14 = 0
(gdb) next
824 if (type!=2&&!ifValuesPass)
(gdb) print type
$15 = 0
(gdb) print ifValuesPass
$16 = 0
(gdb) next
825 loop = progress->looping();
(gdb)
824 if (type!=2&&!ifValuesPass)
(gdb) print loop
$17 = -1
(gdb) next
828 if (loop>=0) {
(gdb)
840 } else if (loop<-1) {
(gdb)
851 if
(loop==-1&&!nonLinearCost_->numberInfeasibilities()&&progress->oddState()<0)
{
(gdb)
859 bool goToDual=false;
(gdb)
863 progressFlag_ = 0; //reset progress flag
(gdb)
866 <<numberIterations_<<nonLinearCost_->feasibleReportCost();
(gdb)
868
<<nonLinearCost_->sumInfeasibilities()<<nonLinearCost_->numberInfeasibilities();
(gdb)
870 <<sumDualInfeasibilities_<<numberDualInfeasibilities_;
(gdb)
873 <<numberDualInfeasibilitiesWithoutFree_;
(gdb)
874 handler_->message()<<CoinMessageEol;
(gdb)
875 if (!primalFeasible()) {
(gdb)
880 double trueInfeasibility =nonLinearCost_->sumInfeasibilities();
(gdb)
881 if
(!nonLinearCost_->numberInfeasibilities()&&infeasibilityCost_==1.0e10&&!ifValuesPass)
{
(gdb) print trueInfeasibility
$18 = 0
(gdb) next
883 infeasibilityCost_ =
CoinMin(CoinMax(100.0*sumDualInfeasibilities_,1.0e4),1.0e7);
(gdb)
885 *progress = ClpSimplexProgress();
(gdb)
886 trueInfeasibility = 1.123456e10;
(gdb)
888 if (trueInfeasibility>1.0) {
(gdb)
890 double testValue =
trueInfeasibility-1.0e-4*(10.0+trueInfeasibility);
(gdb)
891 double lastInf = progress->lastInfeasibility();
(gdb)
892 if(lastInf<testValue||trueInfeasibility==1.123456e10) {
(gdb)
893 if (infeasibilityCost_<1.0e14) {
(gdb)
894 infeasibilityCost_ *= 1.5;
(gdb)
896 *progress = ClpSimplexProgress();
(gdb)
898 gutsOfSolution(NULL,NULL,ifValuesPass!=0);
(gdb)
903 bool alwaysOptimal = (specialOptions_&1)!=0;
(gdb)
905 if (sumOfRelaxedDualInfeasibilities_ == 0.0&&
(gdb) print alwaysOptimal
$19 = false
(gdb) print sumOfRelaxedDualInfeasibilities_
$20 = 0
(gdb) print sumOfRelaxedPrimalInfeasibilities_
$21 = 0
(gdb) next
908 numberDualInfeasibilities_ = 0;
(gdb)
909 sumDualInfeasibilities_ = 0.0;
(gdb)
910 numberPrimalInfeasibilities_ = 0;
(gdb)
911 sumPrimalInfeasibilities_ = 0.0;
(gdb)
913 if (originalModel) {
(gdb)
919 if ((dualFeasible()||problemStatus_==-4)&&!ifValuesPass) {
(gdb) print problemStatus_
$22 = -3
(gdb) print dualFeasible()
$23 = true
(gdb) next
921 if (nonLinearCost_->numberInfeasibilities()&&
(gdb)
1004 if (perturbation_==101) {
(gdb) print perturbation_
$24 = 100
(gdb) next
1010 bool unflagged = unflag();
(gdb)
1011 if ( lastCleaned!=numberIterations_||unflagged) {
(gdb)
1089 problemStatus_=0; // optimal
(gdb) print lastCleaned
$25 = (int &) @0xbf90acc4: 0
(gdb) print numberIterations_
$26 = 0
(gdb) print unflagged
$27 = false
(gdb) next
1151 matrix_->generalExpanded(this,5,dummy);
(gdb)
1152 if (type==0||type==1) {
(gdb)
1153 if (type!=1||!saveStatus_) {
(gdb)
1155 delete [] saveStatus_;
(gdb)
1156 delete [] savedSolution_;
(gdb)
1157 saveStatus_ = new unsigned char
[numberRows_+numberColumns_];
(gdb)
1158 savedSolution_ = new double [numberRows_+numberColumns_];
(gdb)
1161 CoinMemcpyN(status_,numberColumns_+numberRows_,saveStatus_);
(gdb)
1163 numberRows_,savedSolution_+numberColumns_);
(gdb)
1164
CoinMemcpyN(columnActivityWork_,numberColumns_,savedSolution_);
(gdb)
1166 if (doFactorization) {
(gdb)
1168 if (tentativeStatus>-3)
(gdb)
1169 primalColumnPivot_->saveWeights(this,(type <2) ? 2 : 4);
(gdb)
1172 if (saveThreshold) {
(gdb)
1178 if (problemStatus_<0&&!changeMade_) {
(gdb)
1181 lastGoodIteration_ = numberIterations_;
(gdb)
1182 if (goToDual)
(gdb)
1185 if (firstFree_>=0&&saveFirstFree>=0) {
(gdb)
1203 }
(gdb)
ClpSimplexPrimal::primal (this=0x8b91888, ifValuesPass=0,
startFinishOptions=3) at ClpSimplexPrimal.cpp:282
282 if (initialStatus==10) {
(gdb)
303 if (numberDualInfeasibilities_==-776) {
(gdb)
312 int numberSprintIterations=0;
(gdb)
313 int numberSprintColumns =
primalColumnPivot_->numberSprintColumns(numberSprintIterations);
(gdb)
314 if (problemStatus_==777) {
(gdb)
322 } else if
(problemStatus_<0&&!saveModel&&numberSprintColumns&&firstFree_<0) {
(gdb)
394 factorType=1;
(gdb)
397 pivotRow_=-2;
(gdb)
400 if (problemStatus_>=0)
(gdb)
435 if (problemStatus_==1) {
(gdb) print problemStatus_
$28 = 0
(gdb) next
445 unflag();
(gdb)
446 finish(startFinishOptions);
(gdb)
447 restoreData(data);
(gdb)
448 return problemStatus_;
(gdb)
449 }
(gdb)
ClpSimplex::primal (this=0x8b91888, ifValuesPass=0,
startFinishOptions=3) at ClpSimplex.cpp:4519
4519 if (problemStatus_==10) {
(gdb)
4543 return returnCode;
(gdb)
4544 }
(gdb)
SCIPlpiSolvePrimal (lpi=0x8b91828) at src/scip/lpi_clp.cpp:1417
1417 lpi->validFactorization = true;
(gdb) q
=================================
Best, Tobias
--
Tobias Achterberg Konrad-Zuse-Zentrum fuer
Informationstechnik Berlin
Tel: +49 (0)30 84185-301 Takustr. 7
Email: achterberg at zib.de D-14195 Berlin, Germany
More information about the Clp
mailing list