<br><font size=2 face="sans-serif">Interested in CGL discussion? </font>
<br>
<br><font size=2 face="sans-serif">Subscribe to the cgl mailing list at
&nbsp;http://list.coin-or.org/mailman/listinfo/cgl</font>
<br>
<br><font size=2 face="sans-serif">We're moving the CGL design dicussion
to the cgl list.</font>
<br><font size=2 face="sans-serif"><br>
Robin</font>
<br><font size=2 face="sans-serif"><br>
----------------------------------------------------------------------------------<br>
Robin Lougee-Heimer<br>
IBM TJ Watson Research Center<br>
1101 Kitchawan Road, Yorktown Heights, NY 10598<br>
ph: 914-945-3032 &nbsp; fax: 914-945-3434 <br>
robinlh@us.ibm.com<br>
http://www.coin-or.org<br>
<br>
Program Chair, http://www.informs.org/Conf/PuertoRico07<br>
<br>
<br>
</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>&quot;Matthew Galati&quot;
&lt;Matthew.Galati@sas.com&gt;</b> </font>
<br><font size=1 face="sans-serif">Sent by: cgl-bounces@list.coin-or.org</font>
<p><font size=1 face="sans-serif">11/11/2006 10:58 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">&lt;cgl@list.coin-or.org&gt;</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td><font size=1 face="sans-serif">coin-discuss@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">[Cgl] CGL Design</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><tt><font size=2>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 &quot;raw&quot; 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>
 &nbsp;<br>
 &nbsp;//---<br>
 &nbsp;//--- Input : (1) a description of the feasible region<br>
 &nbsp;//--- &nbsp; &nbsp; &nbsp; &nbsp; (2) a point to separate<br>
 &nbsp;//--- Output: (1) a list of separating hyperplanes<br>
 &nbsp;//---<br>
 &nbsp;virtual int generateCuts(const CoinPackedMatrix &amp; matrix,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
collb, <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
colub, &nbsp; <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
obj,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
rowlb, <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
rowub,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const char &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
* coltype,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
currSol,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; vector&lt;CoinCut&gt; &nbsp; &nbsp; &nbsp; &nbsp;&amp;
cuts,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const CglTreeInfo &nbsp; &nbsp; &nbsp; &nbsp;info
= CglTreeInfo()) = 0;<br>
}<br>
 &nbsp;<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>
 &nbsp;//or... force them to use something like CoinModel<br>
 &nbsp;virtual int generateCuts(const CoinModel &nbsp; &nbsp; &nbsp; &nbsp;&amp;
model,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const double &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *
currSol,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; vector&lt;CoinCut&gt; &nbsp; &nbsp; &nbsp; &nbsp;&amp;
cuts,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; const CglTreeInfo &nbsp; &nbsp; &nbsp; &nbsp;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 &quot;wrapper classes&quot; for the base cuts clique,
knapsack, etc - so that CglOsi users will have uniformity - as they did
before.<br>
<br>
//---<br>
//--- &nbsp; Cgl &nbsp; &nbsp;depends on Coin (NOT on Osi)<br>
//--- &nbsp; CglOsi depends on Coin, Cgl and Osi<br>
//---<br>
class CglOsiCutGenerator {<br>
private:<br>
 &nbsp;OsiSolverInterface * si;<br>
...<br>
 &nbsp;virtual void generateCuts(const OsiSolverInterface &amp; si, <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp;OsiCuts &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp;&amp; cuts,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; const CglTreeInfo &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;info
= CglTreeInfo())=0;<br>
}<br>
<br>
<br>
So, an example derivation:<br>
<br>
class CglOsiGomory : public CglOsiCutGenerator {<br>
 &nbsp;//this is exactly the same as before, it is dependent on Osi<br>
 &nbsp;...<br>
};<br>
<br>
<br>
class CglClique : public CglCutGenerator {<br>
 &nbsp;//this is exactly the same as before, but no dependence on Osi<br>
 &nbsp;...<br>
};<br>
<br>
<br>
class CglOsiClique : public CglOsiCutGenerator {<br>
 &nbsp;//CglOsiClique is just a wrapper class for CglClique.<br>
private:<br>
 &nbsp;CglClique cglClique;<br>
...<br>
 &nbsp;virtual void generateCuts(const OsiSolverInterface &amp; si, <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp;OsiCuts &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp;&amp; cuts,<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; const CglTreeInfo &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;info
= CglTreeInfo()){<br>
<br>
 &nbsp; &nbsp;cglClique.generateCuts(si.getMatrixByRow(),<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; si.getColLowerBound(),<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; si.getColUpperBound(),<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; ... <br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; ...<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; );<br>
 &nbsp;}<br>
}<br>
<br>
In this way, the old users still can just &quot;add cut generators&quot;
- 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 &nbsp; 919-677-4444<br>
http://coral.ie.lehigh.edu/~magh<br>
http://www.sas.com/technologies/analytics/optimization/<br>
 &nbsp; <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>