<br><font size=2 face="sans-serif">I will put in rhsSide if you can define
it - what do want for ranged rows? </font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">I will redo one of my cut generators
to see how it goes.</font>
<br>
<br><font size=2 face="sans-serif">John</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>"Matthew Galati"
<Matthew.Galati@sas.com></b> </font>
<p><font size=1 face="sans-serif">12/15/2006 09:21 AM</font>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif"><fmargot@andrew.cmu.edu>, John
J Forrest/Watson/IBM@IBMUS</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td><font size=1 face="sans-serif">"cgl" <cgl@list.coin-or.org></font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">RE: [Cgl] CGL Design - suggested CoinSnapshot</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><tt><font size=2>Hi - <br>
<br>
I am fine with whatever you decide.<br>
<br>
> generateCuts(const CoinSnapshot snap, OsiCuts &cuts, const <br>
> CglTreeInfo treeInfo)<br>
<br>
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.<br>
<br>
If one has to point to Osi headers or link with Osi to build a CGL application,
then we don't yet have independence. <br>
<br>
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.<br>
<br>
Cheers,<br>
Matt<br>
<br>
"CGL - revolt against the shackles of the OSI!"<br>
<br>
<br>
> -----Original Message-----<br>
> From: cgl-bounces@list.coin-or.org <br>
> [mailto:cgl-bounces@list.coin-or.org] On Behalf Of <br>
> fmargot@andrew.cmu.edu<br>
> Sent: Friday, December 15, 2006 9:04 AM<br>
> To: John J Forrest<br>
> Cc: cgl<br>
> Subject: Re: [Cgl] CGL Design - suggested CoinSnapshot<br>
> <br>
> <br>
> John:<br>
> <br>
> I think that CoinSnapshot is perfect (maybe <br>
> get/setRowRightHandSide() is missing) and if you think that <br>
> its place is in CoinUtils, I have no problem with that.<br>
> <br>
> For ease of use of the generators through CoinSnapshot, it is <br>
> maybe better to require that if the data a generator needs is <br>
> available in CoinSnapshot, then a method<br>
> <br>
> generateCuts(const CoinSnapshot snap, OsiCuts &cuts, const <br>
> CglTreeInfo treeInfo)<br>
> <br>
> returning cuts should be available. If the data the generator <br>
> needs is not in CoinSnapshot, then the method returns with 0 <br>
> cuts and possibly a warning (i.e. no derived class of <br>
> CoinSnapshot for a generator is allowed). <br>
> This would allow to use one CoinSnapshot object to call all <br>
> generators that can be called.<br>
> <br>
> Regarding CglParam, I agree that the instantiation with <br>
> CglParam is a gadget and that including parameters directly <br>
> in the CglCutGenerator class is a possibility (they would <br>
> keep company to Aggressiveness, the only parameter currently <br>
> in CglCutGenerator and ignored by all of them during cut <br>
> generation, I believe). The advantage of having a class for <br>
> the parameters is that it is self documenting. It is easy for <br>
> a user to see what parameters are available. But we could <br>
> obtain more or less the same benefit by requiring that the <br>
> Doxygen documentation of a generator regroups in one <br>
> "Parameters" section all the parameters of the generator
and <br>
> that get/set methods for all parameters are available.<br>
> <br>
> Francois<br>
> <br>
> On Thu, 14 Dec 2006, John J Forrest wrote:<br>
> <br>
> > Francois,<br>
> ><br>
> > I don't like things becoming more complicated than they are already
<br>
> > and I don't think it is going to help 99% of users, so I <br>
> would like to <br>
> > mitigate the damage I think this will cause.<br>
> ><br>
> > 1) I don't think CglParam is really necessary. Different
cut <br>
> > generators would need different values e.g. getMAX_SUPPORT()
so I <br>
> > don't think a user would pass a common CglParam into different
<br>
> > generators. Therefore I think it would be much easier to
<br>
> put common scalars into CglCutGenerator.<br>
> ><br>
> > 2) I don't like CglData being in Cgl. Osi does not know
<br>
> about Cgl and <br>
> > I think it would be useful to have Osi methods to populate this
new <br>
> > data structure.<br>
> ><br>
> > I suggest something in CoinUtils. As a straw man I have
added (and <br>
> > will probably delete in a few days) CoinSnapshot.hpp and <br>
> > CoinSnapshot.cpp to CoinUtils branches/devel for people to <br>
> look at. <br>
> > It has all the same method names as OsiSolverInterface to make
it <br>
> > easier to modify cut generators. It can either own arrays
<br>
> and matrices or just point to them.<br>
> > If a solution along these lines is adopted then it would be <br>
> trivial to <br>
> > put fillSnapshot into OsiSolverInterface to populate <br>
> CoinSnapshot from <br>
> > a solver.<br>
> ><br>
> > John Forrest<br>
> ><br>
> ><br>
> ><br>
> > fmargot@andrew.cmu.edu<br>
> > 12/14/2006 08:44 AM<br>
> ><br>
> > To<br>
> > John J Forrest/Watson/IBM@IBMUS<br>
> > cc<br>
> > cgl <cgl@list.coin-or.org><br>
> > Subject<br>
> > Re: [Cgl] CGL Design<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > John:<br>
> ><br>
> > I agree that the solution of using an OsiCglSolverInterface <br>
> instead of <br>
> > CglData has the big advantage of not requiring modifications
of the <br>
> > cut generators. However, as Lou pointed out, it creates an ugly
Osi <br>
> > class with most of the functionalities of a OsiSolverInterface
<br>
> > disabled and keeps users in the dark about what data each cut
<br>
> > generator needs.<br>
> ><br>
> > The modifications required for using CglData are not that <br>
> difficult or <br>
> > dangerous to implement. This can be done by replacing the existing
<br>
> > method<br>
> ><br>
> > generateCuts(const OsiSolverInterface & si, OsiCuts &
cs, const <br>
> > CglTreeInfo info)<br>
> ><br>
> > by three methods:<br>
> ><br>
> > A) generateCuts(const OsiSolverInterface & si, OsiCuts &
cs, const <br>
> > CglTreeInfo info)<br>
> ><br>
> > B) generateCuts(const CglData data, OsiCuts &cs, const CglTreeInfo
<br>
> > info)<br>
> ><br>
> > C) generateCuts(OsiCuts &cs, const CglTreeInfo info)<br>
> ><br>
> > The first two are just wrappers that call the third one, which
<br>
> > contains the code currently in generateCuts(). The <br>
> modifications to be <br>
> > done is to scan the code for reference to the OsiSolverInterface
si.<br>
> > Each line in C) (or other existing methods) of the form<br>
> ><br>
> > some = si.getSomething();<br>
> ><br>
> > is replaced by<br>
> ><br>
> > some = something;<br>
> ><br>
> > where something is a new member in the generator class and <br>
> putting in <br>
> > method A):<br>
> ><br>
> > something = si.getSomething();<br>
> ><br>
> > and in method B):<br>
> ><br>
> > something = data.getSomething();<br>
> ><br>
> > While mistakes can of course be introduced by doing this, this
does <br>
> > not require a major rewriting of the code. For generators <br>
> that have a <br>
> > const OsiSolverInterface si as parameter (and keep it that <br>
> way), I do <br>
> > not see how serious mistakes can be introduced. For generators
that <br>
> > are tightly related to the optimal simplex tableau (Gomory, <br>
> > Lift-and-Project and others) keeping access to the <br>
> OsiSolver is an option.<br>
> ><br>
> > Francois<br>
> ><br>
> ><br>
> > On Tue, 12 Dec 2006, John J Forrest wrote:<br>
> ><br>
> >> Francois suggested I might modify the cut generators for
<br>
> which I was <br>
> >> responsible to use CglData classes, so I looked more closely
at the<br>
> > ideas<br>
> >> put forward by Francois and Matt - and I strongly dislike
them - <br>
> >> there must be a better way.<br>
> >><br>
> >> Matt said he wanted to be independent of any solver or <br>
> solver interface.<br>
> > I<br>
> >> have no problem with the first, but I have with the <br>
> second. Instead <br>
> >> of<br>
> > a<br>
> >> known interface OsiSolverInterface it seems that a new CglData
<br>
> >> interface is being proposed which has less functionality
and a <br>
> >> totally different interface. The idea of a simple data
<br>
> object where <br>
> >> there is no virtual overhead for getting arrays such as <br>
> bounds is a <br>
> >> good idea. In fact Laci and I are using such a class
so <br>
> that we can <br>
> >> share coding between Cbc and BCP. Our attempt <br>
> >> (OsiBranchingInformation hidden in file<br>
> >> OsiBranchingObject.hpp) has practically the same <br>
> information as CglData.<br>
> >><br>
> >> I would suggest a new OsiXxxSolverInterface class derived
from <br>
> >> OsiSolverInterface. It could be filled from an OsiSolverInterface<br>
> > (either<br>
> >> owning arrays or not as the user wanted) and would throw
<br>
> an exception <br>
> >> if you try and solve anything. It could be extended
to have data <br>
> >> that is necessary for cuts and for using in a branch and
<br>
> bound code. <br>
> >> In that<br>
> > way<br>
> >> the existing cut generators could be used without re-writing
which <br>
> >> could lead to the introduction of bugs.<br>
> >><br>
> >> John Forrest<br>
> >><br>
> >><br>
> >><br>
> >> fmargot@andrew.cmu.edu<br>
> >> Sent by: cgl-bounces@list.coin-or.org<br>
> >> 12/04/2006 09:38 AM<br>
> >><br>
> >> To<br>
> >> Matthew Galati <Matthew.Galati@sas.com> cc cgl <br>
> <cgl@list.coin-or.org> <br>
> >> Subject<br>
> >> Re: [Cgl] CGL Design<br>
> >><br>
> >><br>
> >><br>
> >><br>
> >><br>
> >><br>
> >><br>
> >> I have implemented something similar to what Matt <br>
> suggested below for <br>
> >> getting rid of the dependence on the solver. Currently it
applies <br>
> >> only to the CglRedSplit generator. What I suggest is to <br>
> have a class <br>
> >> CglData containing the following members:<br>
> >><br>
> >> // Number of constraints<br>
> >> int nrow;<br>
> >><br>
> >> // Number of variables.<br>
> >> int ncol;<br>
> >><br>
> >> // Pointer on matrix of coefficients (ordered by columns).<br>
> >> CoinPackedMatrix const *matrixByCol;<br>
> >><br>
> >> // Pointer on matrix of coefficients (ordered by rows).<br>
> >> CoinPackedMatrix const *matrixByRow;<br>
> >><br>
> >> // Pointer on vector of objective coefficients.<br>
> >> const double *obj;<br>
> >><br>
> >> // Pointer on vector of lower bounds on variables.<br>
> >> const double *colLower;<br>
> >><br>
> >> // Pointer on vector of upper bounds for variables.<br>
> >> const double *colUpper;<br>
> >><br>
> >> // Pointer on vector of lower bounds for constraints.<br>
> >> const double *rowLower;<br>
> >><br>
> >> // Pointer on vector of upper bounds for constraints.<br>
> >> const double *rowUpper;<br>
> >><br>
> >> // Pointer on vector of upper bounds for constraints.<br>
> >> const double *rowRhs;<br>
> >><br>
> >> // Pointer on vector of activity of constraints (i.e.
<br>
> coefficient <br>
> >> matrix<br>
> >> // times separateThis)..<br>
> >> const double *rowActivity;<br>
> >><br>
> >> /** Pointer on vector of characters for columns types.<br>
> >> colType[i] can have values<br>
> >> <UL><br>
> >> <LI> 'C' : continuous<br>
> >> <LI> 'B' : binary<br>
> >> <LI> 'I' : integer<br>
> >> </UL><br>
> >> */<br>
> >> const char *colType;<br>
> >><br>
> >> // Pointer on vector for point to separate.<br>
> >> const double *separateThis;<br>
> >><br>
> >> // Pointer on tree information.<br>
> >> const CglTreeInfo *treeInfo;<br>
> >><br>
> >> /// Pointer on vector for point that should not be
cut; only for<br>
> > debug.<br>
> >> const double *doNotSeparateThis;<br>
> >><br>
> >> Each generator may derive a class (as I did with <br>
> CglRedSplitData) to <br>
> >> add additional data needed by the generator. If a <br>
> generator does not <br>
> >> require one of the members, the corresponding pointer may
be NULL.<br>
> >><br>
> >> Then there are two ways to call the generator:<br>
> >><br>
> >> // Use the following for calling the cut generator
<br>
> where rsdat is<br>
> >> // a CglRedSplitData object<br>
> >> cutGen.generateCuts(rsdat, cuts);<br>
> >><br>
> >> // Use the following for standard way to call
the cut generator<br>
> > where<br>
> >> // clp is an OsiSolverInterface<br>
> >> cutGen.generateCuts(*clp, cuts);<br>
> >><br>
> >> What seemed simplest to me was to define private data members
in <br>
> >> CglRedSplit to store pointers on the data needed by the generator.
<br>
> >> Each time generateCuts is called, all these data members
are set, <br>
> >> using either the information from the OsiSolverInterface
or the <br>
> >> information from the CglRedSplitData<br>
> > object.<br>
> >><br>
> >> Then, there is a private method CglRedSplit::generateCuts(OsiCuts
<br>
> >> &cs) that does the actual cut generation based on the
data <br>
> members in <br>
> >> CglRedSplit.<br>
> >> This seem quite easy to implement and will not disturb any
existing<br>
> > code.<br>
> >><br>
> >> I have also put a driver in <br>
> trunk/Cgl/example/cgl_data_test.cpp that <br>
> >> can be compiled from build/Cgl/examples/ using<br>
> >><br>
> >> make DRIVER=cgl_data_test<br>
> >><br>
> >> and run from that directory for example on p0033.mps as<br>
> >><br>
> >> ./cgl_data_test ../../Data/Sample/p0033.mps<br>
> >><br>
> >> The code shows how to use either methods to call generateCuts().<br>
> >> Comments are welcome.<br>
> >><br>
> >> One thing I do not like is the colType member in CglData.
<br>
> While it is <br>
> >> useful, I could not find an Osi method returning a pointer
on that <br>
> >> vector, implying that it must be constructed by the <br>
> calling method. <br>
> >> If we could replace<br>
> > it<br>
> >> with something equivalent existing in Osi, that would be
better.<br>
> >><br>
> >> Francois<br>
> >><br>
> >><br>
> >><br>
> >> On Sat, 11 Nov 2006, Matthew Galati wrote:<br>
> >><br>
> >>> At Informs, I spoke briefly with Francois Margot about
the CGL <br>
> >>> design<br>
> >> that I had suggested a while back (see old thread:<br>
> >> <br>
> http://list.coin-or.org/pipermail/coin-discuss/2006-March/001875.html<br>
> >> )<br>
> >>><br>
> >>> Here is a little more about what I had in mind. I have
not tried<br>
> >> anything like this, nor have I really worked out any <br>
> details - just <br>
> >> thinking out loud. Let me know what you think.<br>
> >>><br>
> >>> The main idea, is that I want to make CGL independent
of <br>
> any solver <br>
> >>> or<br>
> >> solver interface. In fact, a cut generator to me, is something
that<br>
> > solves<br>
> >> a separation problem - that is, find a separating hyperplane
that <br>
> >> cuts<br>
> > off<br>
> >> a particular point, and is valid to the feasible region defined
by <br>
> >> some model. Except for (simplex-based cuts, like Gomory and
<br>
> >> LiftandProject), there is no need to assume anything about
<br>
> where the <br>
> >> point is coming<br>
> > from.<br>
> >> I propose that CGL have a base class which is completely
<br>
> independent <br>
> >> of OSI. This would also allow the CGL library to be used
<br>
> by others, <br>
> >> without the burden of needing OSI.<br>
> >>><br>
> >>> It would also be nice to have a "raw" version
of generateCuts that<br>
> >> depends on no other COIN libs - but, given most cut <br>
> implementations <br>
> >> will make use of CoinUtils anyway, it is probably fine to
use <br>
> >> CoinUtils<br>
> > methods<br>
> >> and objects. But, this forces Cgl dependence on Coin.<br>
> >>><br>
> >>> Example prototype:<br>
> >>><br>
> >>> class CglCutGenerator{<br>
> >>><br>
> >>> //---<br>
> >>> //--- Input : (1) a description of the feasible
region<br>
> >>> //--- (2) a point to
separate<br>
> >>> //--- Output: (1) a list of separating hyperplanes<br>
> >>> //---<br>
> >>> virtual int generateCuts(const CoinPackedMatrix
& matrix,<br>
> >>>
const double
* collb,<br>
> >>>
const double
* colub,<br>
> >>>
const double
* obj,<br>
> >>>
const double
* rowlb,<br>
> >>>
const double
* rowub,<br>
> >>>
const char
* coltype,<br>
> >>>
const double
* currSol,<br>
> >>>
vector<CoinCut>
& cuts,<br>
> >>>
const CglTreeInfo
info =<br>
> > CglTreeInfo())<br>
> >> = 0;<br>
> >>> }<br>
> >>><br>
> >>> For this, the only new thing we'd need is CoinCut - which
<br>
> can just <br>
> >>> be a<br>
> >> replacement for OsiCut - it should not be tied to Osi, <br>
> since it has <br>
> >> nothing specific about any solver. A CoinModel could also
<br>
> help make <br>
> >> this cleaner.<br>
> >>><br>
> >>> //or... force them to use something like CoinModel<br>
> >>> virtual int generateCuts(const CoinModel
& model,<br>
> >>>
const double
* currSol,<br>
> >>>
vector<CoinCut>
& cuts,<br>
> >>>
const CglTreeInfo
info =<br>
> > CglTreeInfo())<br>
> >> = 0;<br>
> >>><br>
> >>> All the non-solver specific cuts will be derived from
<br>
> >>> CglCutGenerator<br>
> >> (as before) - just remove any dependence on Osi. This includes
<br>
> >> clique, knapsack, flowcover, etc.<br>
> >>><br>
> >>> Then, for deriving solver specific cuts (like Gomory)
- <br>
> we can have <br>
> >>> a<br>
> >> separate library. One that does depend on Osi (and Cgl).
Call it <br>
> >> libCglOsi. This can also include "wrapper classes"
for the <br>
> base cuts <br>
> >> clique, knapsack, etc - so that CglOsi users will have <br>
> uniformity - <br>
> >> as they did before.<br>
> >>><br>
> >>> //---<br>
> >>> //--- Cgl depends on Coin (NOT on
Osi)<br>
> >>> //--- CglOsi depends on Coin, Cgl and Osi<br>
> >>> //---<br>
> >>> class CglOsiCutGenerator {<br>
> >>> private:<br>
> >>> OsiSolverInterface * si;<br>
> >>> ...<br>
> >>> virtual void generateCuts(const OsiSolverInterface
& si,<br>
> >>>
OsiCuts
& cuts,<br>
> >>>
const <br>
> CglTreeInfo<br>
> >> info = CglTreeInfo())=0;<br>
> >>> }<br>
> >>><br>
> >>><br>
> >>> So, an example derivation:<br>
> >>><br>
> >>> class CglOsiGomory : public CglOsiCutGenerator { //this
<br>
> is exactly <br>
> >>> the same as before, it is dependent on Osi ...<br>
> >>> };<br>
> >>><br>
> >>><br>
> >>> class CglClique : public CglCutGenerator { //this
is exactly the <br>
> >>> same as before, but no dependence on Osi ...<br>
> >>> };<br>
> >>><br>
> >>><br>
> >>> class CglOsiClique : public CglOsiCutGenerator { <br>
> //CglOsiClique is <br>
> >>> just a wrapper class for CglClique.<br>
> >>> private:<br>
> >>> CglClique cglClique;<br>
> >>> ...<br>
> >>> virtual void generateCuts(const OsiSolverInterface
& si,<br>
> >>>
OsiCuts
& cuts,<br>
> >>>
const <br>
> CglTreeInfo<br>
> >> info = CglTreeInfo()){<br>
> >>><br>
> >>> cglClique.generateCuts(si.getMatrixByRow(),<br>
> >>>
si.getColLowerBound(),<br>
> >>>
si.getColUpperBound(),<br>
> >>>
...<br>
> >>>
...<br>
> >>>
);<br>
> >>> }<br>
> >>> }<br>
> >>><br>
> >>> In this way, the old users still can just "add cut
generators" - <br>
> >>> this<br>
> >> time, they are CglOsiCutGenerator(s), but non-OSI users still
have<br>
> > access<br>
> >> to cliques, knapsack, etc, via the base classes CglCutGenerator(s).<br>
> >>><br>
> >>> Thanks,<br>
> >>> Matt<br>
> >>><br>
> >>> Matthew Galati - Optimization Developer SAS Institute
- <br>
> Analytical <br>
> >>> Solutions Phone 919-531-0332, R5327<br>
> >>> Fax 919-677-4444<br>
> >>> http://coral.ie.lehigh.edu/~magh<br>
> >>> http://www.sas.com/technologies/analytics/optimization/<br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >>><br>
> >> _______________________________________________<br>
> >> Cgl mailing list<br>
> >> Cgl@list.coin-or.org<br>
> >> http://list.coin-or.org/mailman/listinfo/cgl<br>
> >><br>
> >><br>
> ><br>
> ><br>
> _______________________________________________<br>
> Cgl mailing list<br>
> Cgl@list.coin-or.org<br>
> http://list.coin-or.org/mailman/listinfo/cgl<br>
> <br>
</font></tt>
<br>