[Cgl] CGL Design - suggested CoinSnapshot
fmargot at andrew.cmu.edu
fmargot at andrew.cmu.edu
Fri Dec 15 10:21:40 EST 2006
On Fri, 15 Dec 2006, John J Forrest wrote:
> I will put in rhsSide if you can define it - what do want for ranged rows?
As defined in the doc of OsiSolverInterface::getRightHandSide(),
it returns rowUpper for ranged rows.
>
>
> Matt - I am sure there is a good reason for your anti-Osi slant, but I
> can't see what it is. I can see about not wanting a solver but it seems
> odd to duplicate OsiCuts - I can't really see what you are going to do
> with cuts other than add them to a solver and as you say it would just be
> a copy of the code.
I agree that there is no reason to replace OsiCuts by anything else. The
generators need a cut class, the solvers need one and they better use
the same class. The location of the cut class can either be on the
generators side or the solvers side, and it is on the solvers side in COIN.
Francois
>
> I will redo one of my cut generators to see how it goes.
>
> John
>
>
>
> "Matthew Galati" <Matthew.Galati at sas.com>
> 12/15/2006 09:21 AM
>
> To
> <fmargot at andrew.cmu.edu>, John J Forrest/Watson/IBM at IBMUS
> cc
> "cgl" <cgl at list.coin-or.org>
> Subject
> RE: [Cgl] CGL Design - suggested CoinSnapshot
>
>
>
>
>
>
> Hi -
>
> I am fine with whatever you decide.
>
>> generateCuts(const CoinSnapshot snap, OsiCuts &cuts, const
>> CglTreeInfo treeInfo)
>
> Just a quick note - if you want full independence from Osi, you need to
> get rid of the OsiCuts reference in CGL. There really should be a CoinCut,
> or more abstractly, a CoinRow. These are very generic objects. Then, for
> backwards compatibility, have an Osi method that populates OsiCuts from
> CoinCuts.
>
> If one has to point to Osi headers or link with Osi to build a CGL
> application, then we don't yet have independence.
>
> To be honest, ideally, CGL should be able to be written independent of
> CoinUtils too - using all raw data. That would make it most useful and
> flexible. Then, provide interface methods from the other libraries. But,
> this is probably more work than it is worth.
>
> Cheers,
> Matt
>
> "CGL - revolt against the shackles of the OSI!"
>
>
>> -----Original Message-----
>> From: cgl-bounces at list.coin-or.org
>> [mailto:cgl-bounces at list.coin-or.org] On Behalf Of
>> fmargot at andrew.cmu.edu
>> Sent: Friday, December 15, 2006 9:04 AM
>> To: John J Forrest
>> Cc: cgl
>> Subject: Re: [Cgl] CGL Design - suggested CoinSnapshot
>>
>>
>> John:
>>
>> I think that CoinSnapshot is perfect (maybe
>> get/setRowRightHandSide() is missing) and if you think that
>> its place is in CoinUtils, I have no problem with that.
>>
>> For ease of use of the generators through CoinSnapshot, it is
>> maybe better to require that if the data a generator needs is
>> available in CoinSnapshot, then a method
>>
>> generateCuts(const CoinSnapshot snap, OsiCuts &cuts, const
>> CglTreeInfo treeInfo)
>>
>> returning cuts should be available. If the data the generator
>> needs is not in CoinSnapshot, then the method returns with 0
>> cuts and possibly a warning (i.e. no derived class of
>> CoinSnapshot for a generator is allowed).
>> This would allow to use one CoinSnapshot object to call all
>> generators that can be called.
>>
>> Regarding CglParam, I agree that the instantiation with
>> CglParam is a gadget and that including parameters directly
>> in the CglCutGenerator class is a possibility (they would
>> keep company to Aggressiveness, the only parameter currently
>> in CglCutGenerator and ignored by all of them during cut
>> generation, I believe). The advantage of having a class for
>> the parameters is that it is self documenting. It is easy for
>> a user to see what parameters are available. But we could
>> obtain more or less the same benefit by requiring that the
>> Doxygen documentation of a generator regroups in one
>> "Parameters" section all the parameters of the generator and
>> that get/set methods for all parameters are available.
>>
>> Francois
>>
>> On Thu, 14 Dec 2006, John J Forrest wrote:
>>
>>> Francois,
>>>
>>> I don't like things becoming more complicated than they are already
>>> and I don't think it is going to help 99% of users, so I
>> would like to
>>> mitigate the damage I think this will cause.
>>>
>>> 1) I don't think CglParam is really necessary. Different cut
>>> generators would need different values e.g. getMAX_SUPPORT() so I
>>> don't think a user would pass a common CglParam into different
>>> generators. Therefore I think it would be much easier to
>> put common scalars into CglCutGenerator.
>>>
>>> 2) I don't like CglData being in Cgl. Osi does not know
>> about Cgl and
>>> I think it would be useful to have Osi methods to populate this new
>>> data structure.
>>>
>>> I suggest something in CoinUtils. As a straw man I have added (and
>>> will probably delete in a few days) CoinSnapshot.hpp and
>>> CoinSnapshot.cpp to CoinUtils branches/devel for people to
>> look at.
>>> It has all the same method names as OsiSolverInterface to make it
>>> easier to modify cut generators. It can either own arrays
>> and matrices or just point to them.
>>> If a solution along these lines is adopted then it would be
>> trivial to
>>> put fillSnapshot into OsiSolverInterface to populate
>> CoinSnapshot from
>>> a solver.
>>>
>>> John Forrest
>>>
>>>
>>>
>>> fmargot at andrew.cmu.edu
>>> 12/14/2006 08:44 AM
>>>
>>> To
>>> John J Forrest/Watson/IBM at IBMUS
>>> cc
>>> cgl <cgl at list.coin-or.org>
>>> Subject
>>> Re: [Cgl] CGL Design
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> John:
>>>
>>> I agree that the solution of using an OsiCglSolverInterface
>> instead of
>>> CglData has the big advantage of not requiring modifications of the
>>> cut generators. However, as Lou pointed out, it creates an ugly Osi
>>> class with most of the functionalities of a OsiSolverInterface
>>> disabled and keeps users in the dark about what data each cut
>>> generator needs.
>>>
>>> The modifications required for using CglData are not that
>> difficult or
>>> dangerous to implement. This can be done by replacing the existing
>>> method
>>>
>>> generateCuts(const OsiSolverInterface & si, OsiCuts & cs, const
>>> CglTreeInfo info)
>>>
>>> by three methods:
>>>
>>> A) generateCuts(const OsiSolverInterface & si, OsiCuts & cs, const
>>> CglTreeInfo info)
>>>
>>> B) generateCuts(const CglData data, OsiCuts &cs, const CglTreeInfo
>>> info)
>>>
>>> C) generateCuts(OsiCuts &cs, const CglTreeInfo info)
>>>
>>> The first two are just wrappers that call the third one, which
>>> contains the code currently in generateCuts(). The
>> modifications to be
>>> done is to scan the code for reference to the OsiSolverInterface si.
>>> Each line in C) (or other existing methods) of the form
>>>
>>> some = si.getSomething();
>>>
>>> is replaced by
>>>
>>> some = something;
>>>
>>> where something is a new member in the generator class and
>> putting in
>>> method A):
>>>
>>> something = si.getSomething();
>>>
>>> and in method B):
>>>
>>> something = data.getSomething();
>>>
>>> While mistakes can of course be introduced by doing this, this does
>>> not require a major rewriting of the code. For generators
>> that have a
>>> const OsiSolverInterface si as parameter (and keep it that
>> way), I do
>>> not see how serious mistakes can be introduced. For generators that
>>> are tightly related to the optimal simplex tableau (Gomory,
>>> Lift-and-Project and others) keeping access to the
>> OsiSolver is an option.
>>>
>>> Francois
>>>
>>>
>>> On Tue, 12 Dec 2006, John J Forrest wrote:
>>>
>>>> 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
>>>>
>>>>
>>>
>>>
>> _______________________________________________
>> Cgl mailing list
>> Cgl at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/cgl
>>
>
>
More information about the Cgl
mailing list