<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.2963" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=110271315-12122006><FONT face=Arial
color=#0000ff size=2>Hi John,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=110271315-12122006><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=110271315-12122006><FONT face=Arial
color=#0000ff size=2>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).</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=110271315-12122006><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=110271315-12122006><FONT face=Arial
color=#0000ff size=2>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.</FONT></SPAN></DIV>
<DIV><FONT face=Arial color=#0000ff size=2></FONT> </DIV>
<DIV><SPAN class=110271315-12122006><FONT face=Arial color=#0000ff
size=2>Matt</FONT></SPAN></DIV><!-- Converted from text/rtf format -->
<P><SPAN lang=en-us><FONT face="Courier New" size=2>Matthew Galati -
Optimization Developer</FONT></SPAN> <BR><SPAN lang=en-us><FONT
face="Courier New" size=2>SAS Institute - Analytical Solutions</FONT></SPAN>
<BR><SPAN lang=en-us><FONT face="Courier New" size=2>Phone 919-531-0332, R5327
</FONT></SPAN><BR><SPAN lang=en-us><FONT face="Courier New"
size=2>Fax 919-677-4444</FONT></SPAN> <BR><SPAN lang=en-us><FONT
face="Courier New" size=2><A
href="http://coral.ie.lehigh.edu/~magh">http://coral.ie.lehigh.edu/~magh</A></FONT></SPAN>
<BR><SPAN lang=en-us><FONT face="Courier New" size=2><A
href="http://ordlnx2.na.sas.com/projects/OptWiki">http://ordlnx2.na.sas.com/projects/OptWiki</A></FONT></SPAN>
<BR><SPAN lang=en-us><FONT face="Courier New" size=2><A
href="http://www.sas.com/technologies/analytics/optimization/">http://www.sas.com/technologies/analytics/optimization/</A></FONT></SPAN>
</P>
<DIV> </DIV><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> cgl-bounces@list.coin-or.org
[mailto:cgl-bounces@list.coin-or.org] <B>On Behalf Of </B>John J
Forrest<BR><B>Sent:</B> Tuesday, December 12, 2006 10:06 AM<BR><B>Cc:</B> cgl;
cgl-bounces@list.coin-or.org<BR><B>Subject:</B> Re: [Cgl] CGL
Design<BR></FONT><BR></DIV>
<DIV></DIV><BR><FONT face=sans-serif size=2>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.</FONT> <BR><BR><FONT
face=sans-serif size=2>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.</FONT> <BR><BR><FONT face=sans-serif size=2>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.</FONT>
<BR><BR><FONT face=sans-serif size=2>John Forrest</FONT> <BR><BR><BR>
<TABLE width="100%">
<TBODY>
<TR vAlign=top>
<TD width="40%"><FONT face=sans-serif
size=1><B>fmargot@andrew.cmu.edu</B> </FONT><BR><FONT face=sans-serif
size=1>Sent by: cgl-bounces@list.coin-or.org</FONT>
<P><FONT face=sans-serif size=1>12/04/2006 09:38 AM</FONT> </P>
<TD width="59%">
<TABLE width="100%">
<TBODY>
<TR vAlign=top>
<TD>
<DIV align=right><FONT face=sans-serif size=1>To</FONT></DIV>
<TD><FONT face=sans-serif size=1>Matthew Galati
<Matthew.Galati@sas.com></FONT>
<TR vAlign=top>
<TD>
<DIV align=right><FONT face=sans-serif size=1>cc</FONT></DIV>
<TD><FONT face=sans-serif size=1>cgl
<cgl@list.coin-or.org></FONT>
<TR vAlign=top>
<TD>
<DIV align=right><FONT face=sans-serif size=1>Subject</FONT></DIV>
<TD><FONT face=sans-serif size=1>Re: [Cgl] CGL
Design</FONT></TR></TBODY></TABLE><BR>
<TABLE>
<TBODY>
<TR vAlign=top>
<TD>
<TD></TR></TBODY></TABLE><BR></TR></TBODY></TABLE><BR><BR><BR><TT><FONT
size=2><BR>I have implemented something similar to what Matt suggested below
for<BR>getting rid of the dependence on the solver. Currently<BR>it applies
only to the CglRedSplit generator. What I suggest is to<BR>have a class
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. coefficient 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 debug.<BR> const double
*doNotSeparateThis;<BR><BR>Each generator may derive a class (as I did with
CglRedSplitData) to add<BR>additional data needed by the generator. If a
generator does not require<BR>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 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 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
CglRedSplit<BR>to store pointers on the data needed by the generator. Each
time generateCuts<BR>is called, all these data members are set, using either
the information from<BR>the OsiSolverInterface or the information from the
CglRedSplitData object.<BR><BR>Then, there is a private method
CglRedSplit::generateCuts(OsiCuts &cs) that <BR>does the actual cut
generation based on the data members in CglRedSplit.<BR>This seem quite easy
to implement and will not disturb any existing code.<BR><BR>I have also put a
driver in 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. While it is useful,<BR>I could not find an
Osi method returning a pointer on that vector, implying<BR>that it must be
constructed by the calling method. If we could replace 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 design that I had suggested a while back (see old thread:
http://list.coin-or.org/pipermail/coin-discuss/2006-March/001875.html)<BR>><BR>>
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.<BR>><BR>> 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.<BR>><BR>> 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.<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
= CglTreeInfo()) = 0;<BR>> }<BR>><BR>> 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.<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 = CglTreeInfo()) = 0;<BR>><BR>> 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.<BR>><BR>> 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.<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
CglTreeInfo info = CglTreeInfo())=0;<BR>>
}<BR>><BR>><BR>> So, an example derivation:<BR>><BR>> class
CglOsiGomory : public CglOsiCutGenerator {<BR>> //this is exactly the
same as before, it is dependent on Osi<BR>> ...<BR>>
};<BR>><BR>><BR>> class CglClique : public CglCutGenerator {<BR>>
//this is exactly the same as before, but no dependence on Osi<BR>>
...<BR>> };<BR>><BR>><BR>> class CglOsiClique : public
CglOsiCutGenerator {<BR>> //CglOsiClique is just a wrapper class for
CglClique.<BR>> private:<BR>> CglClique cglClique;<BR>>
...<BR>> virtual void generateCuts(const OsiSolverInterface &
si,<BR>>
OsiCuts
& cuts,<BR>>
const CglTreeInfo 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" - this time, they
are CglOsiCutGenerator(s), but non-OSI users still have access to cliques,
knapsack, etc, via the base classes CglCutGenerator(s).<BR>><BR>>
Thanks,<BR>> Matt<BR>><BR>> Matthew Galati - Optimization
Developer<BR>> SAS Institute - Analytical Solutions<BR>> 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></FONT></TT><BR></BLOCKQUOTE></BODY></HTML>