[Cbc-tickets] [COIN-OR Branch-and-Cut MIP Solver] #82: CBC gives incorrect optimal solution when knapsack cuts are added
COIN-OR Branch-and-Cut MIP Solver
coin-trac at coin-or.org
Tue Sep 29 18:04:38 EDT 2009
#82: CBC gives incorrect optimal solution when knapsack cuts are added
------------------------+---------------------------------------------------
Reporter: guptasr | Owner: somebody
Type: defect | Status: new
Priority: major | Milestone:
Component: component1 | Version:
Keywords: |
------------------------+---------------------------------------------------
It seems CBC gives incorrect solution on the attached mps problem when
knapsack cuts are added. The code below reads in the mps file, adds the
knapsack cut generator, and solves the problem. The optimal solution is
(-589). When the knapsack cut generator is added to the model object, the
optimal solution is reported to be (-586); and when the knapsack cut
generator is not added (by commenting out the line:
model.addCutGenerator(&generator3,-99,"Knapsack");), then the optimal
solution is correctly reported to be (-589). It seems adding the knapsack
cut generator results in an incorrect optimal solution. I am using CBC
stable release 2.3.1.
----
#if defined(_MSC_VER)
// Turn off compiler warning about long names
# pragma warning(disable:4786)
#endif
#include <cassert>
#include <iomanip>
// For Branch and bound
#include "OsiSolverInterface.hpp"
#include "CbcModel.hpp"
#include "CbcCutGenerator.hpp"
#include "OsiClpSolverInterface.hpp"
#include "CglKnapsackCover.hpp"
#include "CoinTime.hpp"
int main ()
{
//read in the mps file;
OsiClpSolverInterface solver1;
std::string mpsFileName = "C:\\g1.mps";
int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(),"");
assert(numMpsReadErrors==0);
double time1 = CoinCpuTime();
CbcModel model(solver1);
model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintDo);
//solve root node;
model.initialSolve();
//add knapsack cut generator;
CglKnapsackCover generator3;
model.addCutGenerator(&generator3,-99,"Knapsack");
OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*>
(model.solver());
if (osiclp) {
osiclp->setSpecialOptions(128);
if(osiclp->getNumRows()<300&&osiclp->getNumCols()<500) {
osiclp->setupForRepeatedUse(0,0);
}
}
//solve;
model.branchAndBound();
std::cout<<mpsFileName<<" took "<<CoinCpuTime()-time1<<" seconds, "
<<model.getNodeCount()<<" nodes with objective "
<<model.getObjValue()
<<(!model.status() ? " Finished" : " Not finished")
<<std::endl;
// Print more statistics
std::cout<<"Cuts at root node changed objective from
"<<model.getContinuousObjective()
<<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
OsiSolverInterface * solver = model.solver();
int numberColumns = solver->getNumCols();
const double * solution = solver->getColSolution();
std::vector<std::string> columnNames =
*solver1.getModelPtr()->columnNames();
int iColumn;
std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
std::cout<<"--------------------------------------"<<std::endl;
for (iColumn=0;iColumn<numberColumns;iColumn++) {
double value=solution[iColumn];
if (fabs(value)>1.0e-7&&solver->isInteger(iColumn))
std::cout<<std::setw(6)<<iColumn<<" "
<<columnNames[iColumn]<<" "
<<value<<std::endl;
}
std::cout<<"--------------------------------------"<<std::endl;
std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
return 0;
}
----
--
Ticket URL: <https://projects.coin-or.org/Cbc/ticket/82>
COIN-OR Branch-and-Cut MIP Solver <http://projects.coin-or.org/Cbc>
An LP-based branch-and-cut MIP solver.
More information about the Cbc-tickets
mailing list