CBC gives incorrect optimal solution when knapsack cuts are added

[svigerske]

Issue created by migration from Trac.

Original creator: guptasr

Original creation time: 2009-09-29 22:04:38

Assignee: somebody

Version:

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;

  }

[svigerske]

Attachment g1.mps by guptasr created at 2009-09-29 22:05:18

[svigerske]

Looks good with current Cbc/master:

Coin0008I (null) read with 0 errors
Cbc0046I Root node pass 1, 79 rows, 0 total tight cuts  -  objective -592.5
Cbc0046I Root node pass 2, 83 rows, 4 total tight cuts  -  objective -592.5
Cbc0046I Root node pass 3, 85 rows, 6 total tight cuts  -  objective -592.0625
Cbc0046I Root node pass 4, 85 rows, 6 total tight cuts  -  objective -592
Cbc0031I 6 added rows had average density of 5
Cbc0013I At root node, 6 cuts changed objective from -592.5 to -592 in 4 passes
Cbc0014I Cut generator 0 (Knapsack) - 15 row cuts average 4.9 elements, 0 column cuts (0 active)
...
Cbc0001I Search completed - best objective -589, took 2392 iterations and 397 nodes (0.66 seconds)
Cbc0032I Strong branching done 1868 times (4825 iterations), fathomed 78 nodes and fixed 146 variables
Cbc0035I Maximum depth 14, 54 variables fixed on reduced cost
g1.mps took 0.662749 seconds, 397 nodes with objective -589 Finished
Cuts at root node changed objective from -592.5 to -592
--------------------------------------
     0 C0 20.000000
     1 C1 10.000000
     2 C2 10.000000
     3 C3 10.000000
     4 C4 20.000000
     6 C6 10.000000
     7 C7 10.000000
     8 C8 10.000000
    11 C11 20.000000
    25 C25 20.000000
    29 C29 10.000000
    30 C30 1.000000
    31 C31 1.000000
    32 C32 1.000000
    33 C33 1.000000
    34 C34 1.000000
    36 C36 1.000000
    37 C37 1.000000
    38 C38 1.000000
    41 C41 1.000000
    55 C55 1.000000
    59 C59 1.000000
--------------------------------------