[Cgl] CGL Design

Matthew Galati Matthew.Galati at sas.com
Sat Nov 11 10:58:44 EST 2006


At Informs, I spoke briefly with Francois Margot about the CGL design that I had suggested a while back (see old thread: http://list.coin-or.org/pipermail/coin-discuss/2006-March/001875.html)

Here is a little more about what I had in mind. I have not tried anything like this, nor have I really worked out any details - just thinking out loud. Let me know what you think.

The main idea, is that I want to make CGL independent of any solver or solver interface. In fact, a cut generator to me, is something that solves a separation problem - that is, find a separating hyperplane that cuts off a particular point, and is valid to the feasible region defined by some model. Except for (simplex-based cuts, like Gomory and LiftandProject), there is no need to assume anything about where the point is coming from. I propose that CGL have a base class which is completely independent of OSI. This would also allow the CGL library to be used by others, without the burden of needing OSI.

It would also be nice to have a "raw" version of generateCuts that depends on no other COIN libs - but, given most cut implementations will make use of CoinUtils anyway, it is probably fine to use CoinUtils methods and objects. But, this forces Cgl dependence on Coin.

Example prototype:

class CglCutGenerator{
  
  //---
  //--- Input : (1) a description of the feasible region
  //---         (2) a point to separate
  //--- Output: (1) a list of separating hyperplanes
  //---
  virtual int generateCuts(const CoinPackedMatrix & matrix,
                           const double           * collb, 
                           const double           * colub,   
                           const double           * obj,
                           const double           * rowlb, 
                           const double           * rowub,
                           const char             * coltype,
                           const double           * currSol,
                           vector<CoinCut>        & cuts,
                           const CglTreeInfo        info = CglTreeInfo()) = 0;
}
  
For this, the only new thing we'd need is CoinCut - which can just be a replacement for OsiCut - it should not be tied to Osi, since it has nothing specific about any solver. A CoinModel could also help make this cleaner.

  //or... force them to use something like CoinModel
  virtual int generateCuts(const CoinModel        & model,
                           const double           * currSol,
                           vector<CoinCut>        & cuts,
                           const CglTreeInfo        info = CglTreeInfo()) = 0;

All the non-solver specific cuts will be derived from CglCutGenerator (as before) - just remove any dependence on Osi. This includes clique, knapsack, flowcover, etc.

Then, for deriving solver specific cuts (like Gomory) - we can have a separate library. One that does depend on Osi (and Cgl). Call it libCglOsi. This can also include "wrapper classes" for the base cuts clique, knapsack, etc - so that CglOsi users will have uniformity - as they did before.

//---
//---   Cgl    depends on Coin (NOT on Osi)
//---   CglOsi depends on Coin, Cgl and Osi
//---
class CglOsiCutGenerator {
private:
  OsiSolverInterface * si;
...
  virtual void generateCuts(const OsiSolverInterface & si, 
                            OsiCuts                  & cuts,
			    const CglTreeInfo          info = CglTreeInfo())=0;
}


So, an example derivation:

class CglOsiGomory : public CglOsiCutGenerator {
  //this is exactly the same as before, it is dependent on Osi
  ...
};


class CglClique : public CglCutGenerator {
  //this is exactly the same as before, but no dependence on Osi
  ...
};


class CglOsiClique : public CglOsiCutGenerator {
  //CglOsiClique is just a wrapper class for CglClique.
private:
  CglClique cglClique;
...
  virtual void generateCuts(const OsiSolverInterface & si, 
                            OsiCuts                  & cuts,
			    const CglTreeInfo          info = CglTreeInfo()){

    cglClique.generateCuts(si.getMatrixByRow(),
                           si.getColLowerBound(),
                           si.getColUpperBound(),
                           ... 
                           ...
                           );
  }
}

In this way, the old users still can just "add cut generators" - this time, they are CglOsiCutGenerator(s), but non-OSI users still have access to cliques, knapsack, etc, via the base classes CglCutGenerator(s).

Thanks,
Matt

Matthew Galati - Optimization Developer
SAS Institute - Analytical Solutions
Phone 919-531-0332, R5327 
Fax   919-677-4444
http://coral.ie.lehigh.edu/~magh
http://www.sas.com/technologies/analytics/optimization/
   




More information about the Cgl mailing list