[Cgl] CGL Design
Robin Lougee-Heimer
robinlh at us.ibm.com
Mon Nov 13 11:15:50 EST 2006
Matt:
Thanks for putting out the idea & thinking out loud. I think it's a neat
idea.
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.)
Robin
----------------------------------------------------------------------------------
Robin Lougee-Heimer
IBM TJ Watson Research Center
1101 Kitchawan Road, Yorktown Heights, NY 10598
ph: 914-945-3032 fax: 914-945-3434
robinlh at us.ibm.com
http://www.coin-or.org
Program Chair, http://www.informs.org/Conf/PuertoRico07
"Matthew Galati" <Matthew.Galati at sas.com>
Sent by: cgl-bounces at list.coin-or.org
11/11/2006 10:58 AM
To
<cgl at list.coin-or.org>
cc
coin-discuss at list.coin-or.org
Subject
[Cgl] CGL Design
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/
_______________________________________________
Cgl mailing list
Cgl at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/cgl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cgl/attachments/20061113/d0ef53c4/attachment.html
More information about the Cgl
mailing list