[Cgl] Re: [Coin-discuss] CGL Design
Jonathan Eckstein
jeckstei at rci.rutgers.edu
Mon Nov 13 10:53:37 EST 2006
I think that giving CGL cut generators the ability to beindependent of
the state of a particular OSI interface is a good idea.
However, Matt's design does not address some other issues that the PICO
team has encountered when trying to incorporate CGL cuts into our MIP
code. The most important, I think, is that we should have separate
calls for initial setup/analysis and generation of cuts. For example,
the setup/analysis call could determine whether the constraints have the
necessary structure for the particular type of cuts involved, so this
work would not have to be repeated later. The setup/analysis call could
also return a flag stating whether subsequent cut generation calls will
be worth making. For example, if the cuts are knapsack covers and their
are no knapsack constraints, the setup/analysis call could return
"false" to indicate there is no point in trying to generate cuts (from
the core rows, at any rate).
There could still be a one-step call as Matt suggests, whose default
implementation would be to do setup/analysis, and then immediately
generate cuts.
Cindy may well have further suggestions.
-- Jonathan
Matthew Galati wrote:
> 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/
>
>
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
More information about the Cgl
mailing list