[Cgl] CGL Design - suggested CoinSnapshot
fmargot at andrew.cmu.edu
fmargot at andrew.cmu.edu
Fri Dec 15 09:03:59 EST 2006
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
>>
>>
>
>
More information about the Cgl
mailing list