Duplicate Cuts

Exercise: Change the code so that we never add duplicate cuts.

In order to do this, we will store the set of cuts that have already been added in OsiCuts cutPool. Then, in generate_cuts(), we will first create an OsiRowCut rather than adding the cuts directly to the solver interface.

int UFL::generate_cuts(){

      ...

      double violation = sol[xind] - (demand[i] * sol[yind]);
      if(violation > tolerance){

	//Then, we have a violated constraint - so add it.
	CoinPackedVector cut;
	cut.insert(xind,  1.0);
	cut.insert(yind, -1.0 * demand[i]);


	CoinPackedVector cut;
	cut.insert(xind,  1.0);
	cut.insert(yind, -1.0 * demand[i]);

	OsiRowCut aCut;
	aCut.setRow(cut);
	aCut.setLb( -1.0 * si->getInfinity());
	aCut.setUb(0.0);
	aCut.setEffectiveness(violation);
	newcuts += checkAddCut(aCut);

Then, we will check whether or not this cut has already been added to the cut pool. If it is not a duplicate, then we add it to the interface and the cut pool.

The class OsiCuts contains an iterator that can be used to loop over the collection of cuts. To use this, define USE_OSICUTS_ITERATOR in the Makefile. Also, please refer to the discussion list and bug submission.
http://sagan.ie.lehigh.edu/pipermail/coin-lehigh/2003-May/000014.html
http://sagan.ie.lehigh.edu/pipermail/coin-lehigh/2003-May/000015.html

int UFL::checkAddCut(const OsiRowCut & cut){
  
  //check whether this cut has been generated before
  bool duplicate = false;

#ifdef USE_OSICUTS_ITERATOR
  for (OsiCuts::iterator it = cutPool.begin(); it != cutPool.end(); ++it){
    if (*(dynamic_cast<OsiRowCut* >(*it)) == cut){
      duplicate = true; break;
    }
  }
#else
  for (unsigned int i = 0; i < cutPool.sizeRowCuts(); ++i) {
    if (cutPool.rowCut(i) == cut) {
      duplicate = true; break;
    }
  }
#endif

  if ( ! duplicate ){ // if not duplicate, add cut
    cutPool.insert(cut);
    si->applyRowCuts(1, &cut);
    return 1;
  }
  return 0;
}

For generate_cuts_CGL(), we can create a cut list for each CGL and use the following function checkAddCuts().

int UFL::checkAddCuts(OsiCuts & cutPool, OsiCuts & cuts)
{

  const double* sol = si->getColSolution();

  int numAdded = 0;
  for (unsigned int i = 0; i < cuts.sizeRowCuts(); ++i) {

    //calculate the violation here - as a measure of cut effectivness
    OsiRowCut & cut = cuts.rowCut(i);
    cut.setEffectiveness(cut.violated(sol));

    //then check for duplicates
    numAdded += checkAddCut(cutPool, cuts.rowCut(i));
  }
  return numAdded;
}