Opened 10 years ago

Closed 7 weeks ago

#82 closed defect (migrated)

CBC gives incorrect optimal solution when knapsack cuts are added

Reported by: guptasr Owned by: somebody
Priority: major Component: component1
Version: Keywords:
Cc:

Description

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;

}


Attachments (1)

g1.mps (11.0 KB) - added by guptasr 10 years ago.

Download all attachments as: .zip

Change History (2)

Changed 10 years ago by guptasr

comment:1 Changed 7 weeks ago by stefan

  • Resolution set to migrated
  • Status changed from new to closed

This ticket has been migrated to GitHub and will be resolved there: https://github.com/coin-or/Cbc/issues/82

Note: See TracTickets for help on using tickets.