[Cgl] CGL Design
Matthew Galati
Matthew.Galati at sas.com
Tue Dec 12 10:24:39 EST 2006
Hi John,
It is up to all of you how you want to do this - since you have to maintain it. But, I still think there is an advantage in having Cgl independent of any solver interface. That is, Cgl should not depend on anything OsiXXX. It should depend on Cgl objects only (and perhaps some CoinUtils objects, which should be completely generic). This allows folks to use Cgl completely separate of the rest of COIN - and opens the door for more widespread use and development. For backwards compatibility -- Osi algos that use Cgl -- it is easy enough to populate Cgl objects that contain the information that is currently being grabbed from Osi (use ptrs for efficiency). In fact, you might want to do that all for the user - something like what I suggested earlier (wrapper calls), or like you suggest below (an OsiCglSolverInterface layer).
I agree that re-writing Cgl code could introduce bugs - but, that is why we need good regression testing, etc. And, now that we have a reasonable release system, this can be worked on in its own branch and only pushed to stable when ready.
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://ordlnx2.na.sas.com/projects/OptWiki
http://www.sas.com/technologies/analytics/optimization/
________________________________
From: cgl-bounces at list.coin-or.org [mailto:cgl-bounces at list.coin-or.org] On Behalf Of John J Forrest
Sent: Tuesday, December 12, 2006 10:06 AM
Cc: cgl; cgl-bounces at list.coin-or.org
Subject: Re: [Cgl] CGL Design
Francois suggested I might modify the cut generators for which I was responsible to use CglData classes, so I looked more closely at the ideas put forward by Francois and Matt - and I strongly dislike them - there must be a better way.
Matt said he wanted to be independent of any solver or solver interface. I have no problem with the first, but I have with the second. Instead of a known interface OsiSolverInterface it seems that a new CglData interface is being proposed which has less functionality and a totally different interface. The idea of a simple data object where there is no virtual overhead for getting arrays such as bounds is a good idea. In fact Laci and I are using such a class so that we can share coding between Cbc and BCP. Our attempt (OsiBranchingInformation hidden in file OsiBranchingObject.hpp) has practically the same information as CglData.
I would suggest a new OsiXxxSolverInterface class derived from OsiSolverInterface. It could be filled from an OsiSolverInterface (either owning arrays or not as the user wanted) and would throw an exception if you try and solve anything. It could be extended to have data that is necessary for cuts and for using in a branch and bound code. In that way the existing cut generators could be used without re-writing which could lead to the introduction of bugs.
John Forrest
fmargot at andrew.cmu.edu
Sent by: cgl-bounces at list.coin-or.org
12/04/2006 09:38 AM
To
Matthew Galati <Matthew.Galati at sas.com>
cc
cgl <cgl at list.coin-or.org>
Subject
Re: [Cgl] CGL Design
I have implemented something similar to what Matt suggested below for
getting rid of the dependence on the solver. Currently
it applies only to the CglRedSplit generator. What I suggest is to
have a class CglData containing the following members:
// Number of constraints
int nrow;
// Number of variables.
int ncol;
// Pointer on matrix of coefficients (ordered by columns).
CoinPackedMatrix const *matrixByCol;
// Pointer on matrix of coefficients (ordered by rows).
CoinPackedMatrix const *matrixByRow;
// Pointer on vector of objective coefficients.
const double *obj;
// Pointer on vector of lower bounds on variables.
const double *colLower;
// Pointer on vector of upper bounds for variables.
const double *colUpper;
// Pointer on vector of lower bounds for constraints.
const double *rowLower;
// Pointer on vector of upper bounds for constraints.
const double *rowUpper;
// Pointer on vector of upper bounds for constraints.
const double *rowRhs;
// Pointer on vector of activity of constraints (i.e. coefficient matrix
// times separateThis)..
const double *rowActivity;
/** Pointer on vector of characters for columns types.
colType[i] can have values
<UL>
<LI> 'C' : continuous
<LI> 'B' : binary
<LI> 'I' : integer
</UL>
*/
const char *colType;
// Pointer on vector for point to separate.
const double *separateThis;
// Pointer on tree information.
const CglTreeInfo *treeInfo;
/// Pointer on vector for point that should not be cut; only for debug.
const double *doNotSeparateThis;
Each generator may derive a class (as I did with CglRedSplitData) to add
additional data needed by the generator. If a generator does not require
one of the members, the corresponding pointer may be NULL.
Then there are two ways to call the generator:
// Use the following for calling the cut generator where rsdat is
// a CglRedSplitData object
cutGen.generateCuts(rsdat, cuts);
// Use the following for standard way to call the cut generator where
// clp is an OsiSolverInterface
cutGen.generateCuts(*clp, cuts);
What seemed simplest to me was to define private data members in CglRedSplit
to store pointers on the data needed by the generator. Each time generateCuts
is called, all these data members are set, using either the information from
the OsiSolverInterface or the information from the CglRedSplitData object.
Then, there is a private method CglRedSplit::generateCuts(OsiCuts &cs) that
does the actual cut generation based on the data members in CglRedSplit.
This seem quite easy to implement and will not disturb any existing code.
I have also put a driver in trunk/Cgl/example/cgl_data_test.cpp that
can be compiled from build/Cgl/examples/ using
make DRIVER=cgl_data_test
and run from that directory for example on p0033.mps as
./cgl_data_test ../../Data/Sample/p0033.mps
The code shows how to use either methods to call generateCuts().
Comments are welcome.
One thing I do not like is the colType member in CglData. While it is useful,
I could not find an Osi method returning a pointer on that vector, implying
that it must be constructed by the calling method. If we could replace it
with something equivalent existing in Osi, that would be better.
Francois
On Sat, 11 Nov 2006, 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/
>
>
>
>
>
_______________________________________________
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/20061212/a727f093/attachment-0001.html
More information about the Cgl
mailing list