| 1 | <html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Matrix Classes</title><meta name="generator" content="DocBook XSL Stylesheets V1.66.1"><link rel="start" href="index.html" title="CLP User Guide"><link rel="up" href="ch03.html" title="Chapter 3. |
|---|
| 2 | Not-Quite-So-Basic Model Classes |
|---|
| 3 | "><link rel="prev" href="ch03.html" title="Chapter 3. |
|---|
| 4 | Not-Quite-So-Basic Model Classes |
|---|
| 5 | "><link rel="next" href="ch03s03.html" title="Message Handling"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Matrix Classes</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><th width="60%" align="center">Chapter 3. |
|---|
| 6 | Not-Quite-So-Basic Model Classes |
|---|
| 7 | </th><td width="20%" align="right"> <a accesskey="n" href="ch03s03.html">Next</a></td></tr></table><hr></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="matrixclasses"></a>Matrix Classes</h2></div></div></div><p> |
|---|
| 8 | The next abstract class of interest is <tt class="function">ClpMatrixBase</tt>. |
|---|
| 9 | CLP encapsulates its knowledge of how a matrix is stored in this class. The |
|---|
| 10 | default instance of this is the <tt class="function">ClpPackedMatrix</tt> class. |
|---|
| 11 | This is identical in format to <tt class="function">CoinPackedMatrix</tt>. Below |
|---|
| 12 | is a diagram summarizing the hierarchy of the most important matrix classes: |
|---|
| 13 | </p><div class="mediaobject"><img src="figures/clpbasicmatrixhier.gif"></div><p> |
|---|
| 14 | The important new methods implemented are for filling a basis, checking validity |
|---|
| 15 | of elements and faster "times" and "transposeTimes" when |
|---|
| 16 | the input array is sparse and/or we have a row copy of the matrix. Advanced |
|---|
| 17 | users should note that not all methods have to be implemented. In particular, |
|---|
| 18 | <tt class="function">scaling</tt> need not be implemented and |
|---|
| 19 | <tt class="function">reverseOrderedCopy</tt> can return <i class="parameter"><tt>NULL</tt></i> |
|---|
| 20 | if a row copy does not make sense. |
|---|
| 21 | </p><p> |
|---|
| 22 | In addition to the default class, there are two others at present: |
|---|
| 23 | <tt class="function">ClpPlusMinusOneMatrix</tt> and |
|---|
| 24 | <tt class="function">ClpNetworkMatrix</tt>. As the name implies, the first one is |
|---|
| 25 | useful when all elements are ±1. In this case multiplies are not needed |
|---|
| 26 | and more importantly less memory is used and there are fewer cache misses. A |
|---|
| 27 | class for a matrix where all elements are +1 would be trivial to create. If |
|---|
| 28 | there were fewer than 64000 rows one could even store row indices as shorts |
|---|
| 29 | etc. |
|---|
| 30 | </p><p> |
|---|
| 31 | The use of <tt class="function">ClpPlusMinusOneMatrix</tt> involves some work as one |
|---|
| 32 | cannot simply read-in an MPS file. The key is to use |
|---|
| 33 | <tt class="function">loadProblem</tt> to pass in a matrix. So if |
|---|
| 34 | <tt class="varname">matrix</tt> was a <tt class="function">CoinPackedMatrix</tt> one |
|---|
| 35 | could do the following: |
|---|
| 36 | </p><pre class="programlisting"> |
|---|
| 37 | ClpPlusMinusOneMatrix plusMinus(matrix); |
|---|
| 38 | assert (plusMinus.getIndices()); // would be zero if not +- one |
|---|
| 39 | model.loadProblem(plusMinus, |
|---|
| 40 | lowerColumn,upperColumn,objective, |
|---|
| 41 | lower,upper); |
|---|
| 42 | </pre><p> |
|---|
| 43 | <tt class="function">ClpNetworkMatrix</tt> is similar, but represents a network, |
|---|
| 44 | thus may only have one element per column. Fortunately, using is is very |
|---|
| 45 | easy. Given <tt class="varname">head</tt> and <tt class="varname">tail</tt>, one could |
|---|
| 46 | do the following: |
|---|
| 47 | </p><pre class="programlisting"> |
|---|
| 48 | ClpNetworkMatrix network(numberColumns,head,tail); |
|---|
| 49 | model.loadProblem(network, |
|---|
| 50 | lowerColumn,upperColumn,objective, |
|---|
| 51 | lower,upper); |
|---|
| 52 | </pre><p> |
|---|
| 53 | Actual code is in <tt class="filename">COIN/Clp/Test/unitTest.cpp</tt>. A quick |
|---|
| 54 | glance at the output of this program shows that use of |
|---|
| 55 | <tt class="function">ClpNetworkMatrix</tt> gives much faster run times. This is |
|---|
| 56 | not because of storage issues, but because CLP recognizes the network and uses |
|---|
| 57 | a network basis factorization which is much faster. However, in this mode CLP |
|---|
| 58 | is not a genuine network code as it does not take full advantage of the |
|---|
| 59 | structure by combining operations but it does have the advantage of |
|---|
| 60 | flexibility. |
|---|
| 61 | </p><p> |
|---|
| 62 | Other instances are possible. In particular, it should be possible to use the |
|---|
| 63 | abstract class for column generation or for dynamic matrices which change over |
|---|
| 64 | time. Minor modifications may be needed but it should work quite smoothly |
|---|
| 65 | (there is already a dummy "refresh" method which would be used). |
|---|
| 66 | </p></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch03.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch03.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch03s03.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 3. |
|---|
| 67 | Not-Quite-So-Basic Model Classes |
|---|
| 68 | </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Message Handling</td></tr></table></div></body></html> |
|---|
