[Cgl] Re: [Coin-discuss] CGL Design
Matthew Galati
Matthew.Galati at sas.com
Mon Nov 13 12:49:59 EST 2006
Jonathan: I completely agree. A cut "initialization" step is very important - and that data should be passed into the generators as an argument. In the current design, that could presumably be hidden inside CglTreeInfo, although we might think of a better name. I see this as a separate issue than the OSI dependence issue.
Robin: you have asked for a wiki page on this topic. Done - although, for now, its just a copy of the mailing list post: https://projects.coin-or.org/Cgl/wiki/CglOsiDep
Robin:
"I'm a big fan of having a requirement so there's something to direct the trade-offs in the design. The added layers of indirection can be a pain, so it'd be nice to know it would be getting used. Do you (or anyone else out there) have a need for this now? Or see yourselves using the independent CGL some time down the road?
We've got a "wish list" of to-dos, https://projects.coin-or.org/Cgl/wiki/WikiStart. How would you prioritize the independent-CGL vs. the other items? (FYI - I added "OSI independence" to the wish list at , if you want to alter it in any way -- pls do.) "
Do I have a need it in the near future? Need - no. Want - Yes. My DECOMP framework (soon to be submitted to COIN) tries to take advantage of structured points (not necessarily coming from a LP fractional point or a simplex solve). Often, these points come form combinatorial solvers (not OSI solvers). I want CGL independence from Osi. Right now, I fake it - but its ugly and poor design.
If I had to prioritize the 'wish-list'- I would actually put Jonathan's suggestion first. Here's my order preference:
(1) A design for interrogating the problem once up front (e.g., building implication tables), caching the information for use later on. <wisher: Robin Lougee-Heimer and many others, July 18, 2006>
(2) Make CGL independent of OSI.
(3) All cut generators use the same value for infinity <wisher: Cindy Phillips, July 18, 2006>
(4) Numerical stability of all cut generators <wisher: Francois Margot, July 19, 2006>
Another thing you might want to think about, is creating a "cut-pool" object - this would handle things like (4), defining different "ranking" criteria, etc. Presumably, CBC already does something like this. But, again, there is nothing specific about CBC (or even MILP, for that matter). A "cut-pool" object is just a container class for the objects that come out of CGLs.
Matt
-----Original Message-----
From: cgl-bounces at list.coin-or.org [mailto:cgl-bounces at list.coin-or.org] On Behalf Of Jonathan Eckstein
Sent: Monday, November 13, 2006 10:54 AM
To: Discussions about open source software for Operations Research
Cc: cgl at list.coin-or.org
Subject: [Cgl] Re: [Coin-discuss] CGL Design
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
_______________________________________________
Cgl mailing list
Cgl at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/cgl
More information about the Cgl
mailing list