source: html/trunk/Clp/userguide/apa.html @ 974

Last change on this file since 974 was 974, checked in by jpfasano, 15 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.1 KB
Line 
1<html>
2        <head>
3                <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
4                <title>Appendix A. FAQ</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="index.html" title="CLP User Guide"><link rel="prev" href="ch06.html" title="Chapter 6. 
5  Messages
6  "><link rel="next" href="apb.html" title="Appendix B. Doxygen"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header">
7                                <tr>
8                                        <th colspan="3" align="center">
9                                                Appendix A. FAQ</th></tr>
10                                <tr>
11                                        <td width="20%" align="left"><a accesskey="p" href="ch06.html">Prev</a>
12                                        </td>
13                                        <th width="60%" align="center">
14                                        </th>
15                                        <td width="20%" align="right">
16                                                <a accesskey="n" href="apb.html">Next</a></td>
17                                </tr>
18                        </table>
19                        <hr>
20                </div>
21                <div class="appendix" lang="en"><div class="titlepage"><div><div><h2 class="title"><a name="id4782528"></a>Appendix
22                                                        A. FAQ</h2>
23                                        </div>
24                                </div>
25                        </div>
26                        <div class="qandaset"><dl>
27                                        <dt>Q: <a href="apa.html#id4782607">What is CLP? </a></dt><dt>Q: <a href="apa.html#id4782566">
28                                                        What are some of the features of CLP? </a></dt><dt>Q: <a href="apa.html#id4783559">
29                                                        How do I obtain and install CLP? </a></dt><dt>Q: <a href="apa.html#id4783595">Is
30                                                        CLP reliable? </a></dt><dt>Q: <a href="apa.html#id4783627">On which platforms
31                                                        does CLP run? </a></dt><dt>Q: <a href="apa.html#id4783678">Is there any
32                                                        documentation for CLP? </a></dt><dt>Q: <a href="apa.html#id4783716">Is CLP as
33                                                        fast as OSL? </a></dt><dt>Q: <a href="apa.html#id4783737">When will version 1.0
34                                                        of CLP be available? </a></dt><dt>Q: <a href="apa.html#id4783768">The barrier
35                                                        method sounds interesting, what are some of the details? </a></dt><dt>Q: <a href="apa.html#id4783794">
36                                                        Which Cholesky factorizations codes are supported by CLP's barrier method? </a>
37                                        </dt><dt>Q: <a href="apa.html#id4783858">When will CLP have a good native ordering? </a>
38                                        </dt><dt>Q: <a href="apa.html#id4783879">Is the barrier code as mature as the simplex
39                                                        code? </a></dt><dt>Q: <a href="apa.html#id4783904">Which algorithm should I use
40                                                        for quadratic programming and should I keep an eye open for any issues? </a>
41                                        </dt><dt>Q: <a href="apa.html#id4783936">What can the community do to help? </a></dt>
42                                </dl>
43                                <table border="0" summary="Q and A Set">
44                                        <col align="left" width="1%">
45                                                <tbody>
46                                                        <tr class="question">
47                                                                <td align="left" valign="top"><a name="id4782607"></a><a name="id4782610"></a><b>Q:</b></td>
48                                                                <td align="left" valign="top"><p>
49                                                                                What is <a href="http://www.coin-or.org/Clp/" target="_top">CLP</a>?
50                                                                        </p>
51                                                                </td>
52                                                        </tr>
53                                                        <tr class="answer">
54                                                                <td align="left" valign="top"><b>A:</b></td>
55                                                                <td align="left" valign="top"><p>
56                                                                                (DN 08/27/04) The <a href="http://www.coin-or.org/" target="_top">COIN-OR</a> LP
57                                                                                code is designed to be a high quality Simplex code provided under the terms of
58                                                                                the <a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public
59                                                                                        License</a>. CLP is written in C++, and is primarily intended to be used as
60                                                                                a callable library (though a rudimentary stand-alone executable exists). The
61                                                                                first release was version .90. The current release is version .99.9.
62                                                                        </p>
63                                                                </td>
64                                                        </tr>
65                                                        <tr class="question">
66                                                                <td align="left" valign="top"><a name="id4782566"></a><a name="id4782568"></a><b>Q:</b></td>
67                                                                <td align="left" valign="top"><p>
68                                                                                What are some of the features of CLP?
69                                                                        </p>
70                                                                </td>
71                                                        </tr>
72                                                        <tr class="answer">
73                                                                <td align="left" valign="top"><b>A:</b></td>
74                                                                <td align="left" valign="top"><p>
75                                                                                (DN 08/27/04) CLP includes primal and dual Simplex solvers. Both dual and
76                                                                                primal algorithms can use matrix storage methods provided by the user (0-1 and
77                                                                                network matrices are already supported in addition to the default sparse
78                                                                                matrix). The dual algorithm has Dantzig and Steepest edge row pivot choices;
79                                                                                new ones may be provided by the user. The same is true for the column pivot
80                                                                                choice of the primal algorithm. The primal can also use a non linear cost which
81                                                                                should work for piecewise linear convex functions. CLP also includes a barrier
82                                                                                method for solving LPs.
83                                                                        </p>
84                                                                </td>
85                                                        </tr>
86                                                        <tr class="question">
87                                                                <td align="left" valign="top"><a name="id4783559"></a><a name="id4783561"></a><b>Q:</b></td>
88                                                                <td align="left" valign="top"><p>
89                                                                                How do I obtain and install CLP?
90                                                                        </p>
91                                                                </td>
92                                                        </tr>
93                                                        <tr class="answer">
94                                                                <td align="left" valign="top"><b>A:</b></td>
95                                                                <td align="left" valign="top"><p>
96                                                                                (DN 08/27/04) Please see the <a href="http://www.coin-or.org/faqs.html" target="_top">
97                                                                                        COIN-OR FAQ</a> for details on how to <a href="http://www.coin-or.org/faqs.html#ObtainSrcCode" target="_top">
98                                                                                        obtain</a> and <a href="http://www.coin-or.org/faqs.html#BuildCode" target="_top">
99                                                                                        install</a> COIN-OR modules.
100                                                                        </p>
101                                                                </td>
102                                                        </tr>
103                                                        <tr class="question">
104                                                                <td align="left" valign="top"><a name="id4783595"></a><a name="id4783597"></a><b>Q:</b></td>
105                                                                <td align="left" valign="top"><p>
106                                                                                Is CLP reliable?
107                                                                        </p>
108                                                                </td>
109                                                        </tr>
110                                                        <tr class="answer">
111                                                                <td align="left" valign="top"><b>A:</b></td>
112                                                                <td align="left" valign="top"><p>
113                                                                                (DN 09/07/04) CLP has been tested on many problems of up to 1.5 million
114                                                                                constraints and has shown itself as reliable as OSL. It is also being tested in
115                                                                                the context of SBB ("Simple Branch and Bound", which is used to solve integer
116                                                                                programs), but more testing is needed before it can get to version 1.0. SBB has
117                                                                                been replaced by <a href="https://projects.coin-or.org/Cbc">Cbc</a>
118                                                                        </p>
119                                                                </td>
120                                                        </tr>
121                                                        <tr class="question">
122                                                                <td align="left" valign="top"><a name="id4783627"></a><a name="id4783629"></a><b>Q:</b></td>
123                                                                <td align="left" valign="top"><p>
124                                                                                On which platforms does CLP run?
125                                                                        </p>
126                                                                </td>
127                                                        </tr>
128                                                        <tr class="answer">
129                                                                <td align="left" valign="top"><b>A:</b></td>
130                                                                <td align="left" valign="top"><p>
131                                                                                (DN 08/27/04) CLP compiles and has been tested (to varying degrees) on the
132                                                                                following platforms:
133                                                                        </p>
134                                                                        <div class="itemizedlist"><ul type="disc">
135                                                                                        <li>
136                                                                                                <p>
137                                                                                                        Linux using g++ version 3.1.1 (or later)
138                                                                                                </p>
139                                                                                        </li>
140                                                                                        <li>
141                                                                                                <p>
142                                                                                                        Windows using Microsoft Visual C++ 6
143                                                                                                </p>
144                                                                                        </li>
145                                                                                        <li>
146                                                                                                <p>
147                                                                                                        Windows using cygwin
148                                                                                                </p>
149                                                                                        </li>
150                                                                                        <li>
151                                                                                                <p>
152                                                                                                        AIX using xIC (not supported in the current Makefile)
153                                                                                                </p>
154                                                                                        </li>
155                                                                                </ul>
156                                                                        </div>
157                                                                </td>
158                                                        </tr>
159                                                        <tr class="question">
160                                                                <td align="left" valign="top"><a name="id4783678"></a><a name="id4783680"></a><b>Q:</b></td>
161                                                                <td align="left" valign="top"><p>
162                                                                                Is there any documentation for CLP?
163                                                                        </p>
164                                                                </td>
165                                                        </tr>
166                                                        <tr class="answer">
167                                                                <td align="left" valign="top"><b>A:</b></td>
168                                                                <td align="left" valign="top"><p>
169                                                                                (DN 09/16/04) An early release of a User Guide is available on the <a href="http://www.coin-or.org/Clp/documentation.html" target="_top">
170                                                                                        CLP documentation webpage</a>. Also available is a list of <a href="http://www.coin-or.org/Doxygen/Clp/" target="_top">
171                                                                                        CLP class descriptions</a> generated by <a href="http://www.doxygen.org" target="_top">
172                                                                                        Doxygen</a>.
173                                                                        </p>
174                                                                </td>
175                                                        </tr>
176                                                        <tr class="question">
177                                                                <td align="left" valign="top"><a name="id4783716"></a><a name="id4783718"></a><b>Q:</b></td>
178                                                                <td align="left" valign="top"><p>
179                                                                                Is CLP as fast as OSL?
180                                                                        </p>
181                                                                </td>
182                                                        </tr>
183                                                        <tr class="answer">
184                                                                <td align="left" valign="top"><b>A:</b></td>
185                                                                <td align="left" valign="top"><p>
186                                                                                (DN 08/27/04) CLP uses sparse matrix techniques designed for very large
187                                                                                problems. The design criteria were for it not to be too slow. Some speed has
188                                                                                been sacrificed to make the code less opaque OSL (not difficult!).
189                                                                        </p>
190                                                                </td>
191                                                        </tr>
192                                                        <tr class="question">
193                                                                <td align="left" valign="top"><a name="id4783737"></a><a name="id4783739"></a><b>Q:</b></td>
194                                                                <td align="left" valign="top"><p>
195                                                                                When will version 1.0 of CLP be available?
196                                                                        </p>
197                                                                </td>
198                                                        </tr>
199                                                        <tr class="answer">
200                                                                <td align="left" valign="top"><b>A:</b></td>
201                                                                <td align="left" valign="top"><p>
202                                                                                (DN 08/27/04) It is expected that version 1.0 will be released in time for the
203                                                                                2004 <a href="http://www.informs.org" target="_top">INFORMS</a> <a href="http://www.informs.org/Conf/Denver2004/" target="_top">
204                                                                                        Annual Meeting</a> (24-27 October, 2004).
205                                                                        </p>
206                                                                </td>
207                                                        </tr>
208                                                        <tr class="question">
209                                                                <td align="left" valign="top"><a name="id4783768"></a><a name="id4783771"></a><b>Q:</b></td>
210                                                                <td align="left" valign="top"><p>
211                                                                                The barrier method sounds interesting, what are some of the details?
212                                                                        </p>
213                                                                </td>
214                                                        </tr>
215                                                        <tr class="answer">
216                                                                <td align="left" valign="top"><b>A:</b></td>
217                                                                <td align="left" valign="top"><p>
218                                                                                (DN 08/30/04) The CLP barrier method solves convex QPs as well as LPs. In
219                                                                                general, a barrier method requires implementation of the algorithm, as well as
220                                                                                a fast Cholesky factorization. CLP provides the algorithm, and is expected to
221                                                                                have a reasonable factorization implementation by the release of CLP version
222                                                                                1.0. However, the sparse factorization requires a good ordering algorithm,
223                                                                                which the user is expected to provide (perhaps a better factorization code as
224                                                                                well).
225                                                                        </p>
226                                                                </td>
227                                                        </tr>
228                                                        <tr class="question">
229                                                                <td align="left" valign="top"><a name="id4783794"></a><a name="id4783796"></a><b>Q:</b></td>
230                                                                <td align="left" valign="top"><p>
231                                                                                Which Cholesky factorizations codes are supported by CLP's barrier method?
232                                                                        </p>
233                                                                </td>
234                                                        </tr>
235                                                        <tr class="answer">
236                                                                <td align="left" valign="top"><b>A:</b></td>
237                                                                <td align="left" valign="top"><p>
238                                                                                (DN 09/16/04) The Cholesky interface is flexible enough so that a variety of
239                                                                                Cholesky ordering and factorization codes can be used. Interfaces are provided
240                                                                                to each of the following:
241                                                                        </p>
242                                                                        <div class="itemizedlist"><ul type="disc">
243                                                                                        <li>
244                                                                                                <p>
245                                                                                                        Anshul Gupta's WSSMP parallel enabled ordering and factorization code
246                                                                                                </p>
247                                                                                        </li>
248                                                                                        <li>
249                                                                                                <p>
250                                                                                                        Sivan Toledo's TAUCS parallel enabled factorization code (the package includes
251                                                                                                        third party ordering codes)
252                                                                                                </p>
253                                                                                        </li>
254                                                                                        <li>
255                                                                                                <p>
256                                                                                                        University of Florida's Approximate Minimum Degree (AMD) ordering code (the CLP
257                                                                                                        native factorization code is used with this ordering code)
258                                                                                                </p>
259                                                                                        </li>
260                                                                                        <li>
261                                                                                                <p>
262                                                                                                        CLP native code: very weak ordering but competitive nonparallel factorization
263                                                                                                </p>
264                                                                                        </li>
265                                                                                        <li>
266                                                                                                <p>
267                                                                                                        Fast dense factorization
268                                                                                                </p>
269                                                                                        </li>
270                                                                                </ul>
271                                                                        </div>
272                                                                        <p>
273                                                                        </p>
274                                                                </td>
275                                                        </tr>
276                                                        <tr class="question">
277                                                                <td align="left" valign="top"><a name="id4783858"></a><a name="id4783860"></a><b>Q:</b></td>
278                                                                <td align="left" valign="top"><p>
279                                                                                When will CLP have a good native ordering?
280                                                                        </p>
281                                                                </td>
282                                                        </tr>
283                                                        <tr class="answer">
284                                                                <td align="left" valign="top"><b>A:</b></td>
285                                                                <td align="left" valign="top"><p>
286                                                                                (DN 09/16/04) The best outcome would be to have an existing ordering code
287                                                                                available as part of the COIN distribution under the CPL. However, if this is
288                                                                                not possible, the native ordering will be made respectable.
289                                                                        </p>
290                                                                </td>
291                                                        </tr>
292                                                        <tr class="question">
293                                                                <td align="left" valign="top"><a name="id4783879"></a><a name="id4783881"></a><b>Q:</b></td>
294                                                                <td align="left" valign="top"><p>
295                                                                                Is the barrier code as mature as the simplex code?
296                                                                        </p>
297                                                                </td>
298                                                        </tr>
299                                                        <tr class="answer">
300                                                                <td align="left" valign="top"><b>A:</b></td>
301                                                                <td align="left" valign="top"><p>
302                                                                                (DN 09/16/04) The simplex code has been exposed to user testing for more than a
303                                                                                year and and the principal author, John Forrest, knows more about simplex
304                                                                                algorithms than interior point algorithms, so the answer is "no". However, it
305                                                                                performs well on test sets and seems to be more reliable than some commercially
306                                                                                available codes (including OSL).
307                                                                        </p>
308                                                                </td>
309                                                        </tr>
310                                                        <tr class="question">
311                                                                <td align="left" valign="top"><a name="id4783904"></a><a name="id4783906"></a><b>Q:</b></td>
312                                                                <td align="left" valign="top"><p>
313                                                                                Which algorithm should I use for quadratic programming and should I keep an eye
314                                                                                open for any issues?
315                                                                        </p>
316                                                                </td>
317                                                        </tr>
318                                                        <tr class="answer">
319                                                                <td align="left" valign="top"><b>A:</b></td>
320                                                                <td align="left" valign="top"><p>
321                                                                                (DN 09/16/04) The interior point algorithm for quadratic programming is much
322                                                                                more elegant and normally much faster than the quadratic simplex code. Caution
323                                                                                is suggested with the presolve as not all bugs have been found and squashed
324                                                                                when a quadratic objective is used. One may wish to switch off the crossover to
325                                                                                a basic feasible solution as the simplex code can be slow. The sequential
326                                                                                linear code is useful as a "crash" to the simplex code; its convergence is poor
327                                                                                but, say, 100 iterations could set up the problem well for the simplex code.
328                                                                        </p>
329                                                                </td>
330                                                        </tr>
331                                                        <tr class="question">
332                                                                <td align="left" valign="top"><a name="id4783936"></a><a name="id4783938"></a><b>Q:</b></td>
333                                                                <td align="left" valign="top"><p>
334                                                                                What can the community do to help?
335                                                                        </p>
336                                                                </td>
337                                                        </tr>
338                                                        <tr class="answer">
339                                                                <td align="left" valign="top"><b>A:</b></td>
340                                                                <td align="left" valign="top"><p>
341                                                                                (DN 09/09/04) A lot! A good first step would be to join the CLP <a href="http://www.coin-or.org/mail.html" target="_top">
342                                                                                        mailing lists</a>. Some other possibilities:
343                                                                        </p>
344                                                                        <div class="itemizedlist"><ul type="disc">
345                                                                                        <li>
346                                                                                                <p>
347                                                                                                        Comment on the design
348                                                                                                </p>
349                                                                                        </li>
350                                                                                        <li>
351                                                                                                <p>
352                                                                                                        Break the code, or better yet, mend it.
353                                                                                                </p>
354                                                                                        </li>
355                                                                                        <li>
356                                                                                                <p>
357                                                                                                        Add non-English language support in your own favo(u)rite language.
358                                                                                                </p>
359                                                                                        </li>
360                                                                                        <li>
361                                                                                                <p>
362                                                                                                        Improve the CLP executable. In particular it would be nice to be able to link
363                                                                                                        the executable's online help system with the existing CLP Samples (e.g.
364                                                                                                        entering <b class="userinput"><tt>presol???</tt></b> would give the user
365                                                                                                        references to all CLP Sample files which use presolve).
366                                                                                                </p>
367                                                                                        </li>
368                                                                                        <li>
369                                                                                                <p>
370                                                                                                        Implement a dual Simplex method for QPs (quadratic programs)
371                                                                                                </p>
372                                                                                        </li>
373                                                                                        <li>
374                                                                                                <p>
375                                                                                                        Implement a parametric Simplex method
376                                                                                                </p>
377                                                                                        </li>
378                                                                                        <li>
379                                                                                                <p>
380                                                                                                        Implement a true network Simplex method (network matrix and factorization are
381                                                                                                        already in place, but the method is not)
382                                                                                                </p>
383                                                                                        </li>
384                                                                                        <li>
385                                                                                                <p>
386                                                                                                        Fill the holes in the barrier method mentioned above.
387                                                                                                </p>
388                                                                                        </li>
389                                                                                </ul>
390                                                                        </div>
391                                                                </td>
392                                                        </tr>
393                                                </tbody></table>
394                        </div>
395                </div>
396                <div class="navfooter"><hr>
397                        <table width="100%" summary="Navigation footer">
398                                <tr>
399                                        <td width="40%" align="left"><a accesskey="p" href="ch06.html">Prev</a>
400                                        </td>
401                                        <td width="20%" align="center"><a accesskey="u" href="index.html">Up</a></td>
402                                        <td width="40%" align="right">
403                                                <a accesskey="n" href="apb.html">Next</a></td>
404                                </tr>
405                                <tr>
406                                        <td width="40%" align="left" valign="top">Chapter 6. Messages
407                                        </td>
408                                        <td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td>
409                                        <td width="40%" align="right" valign="top">
410                                                Appendix B. Doxygen</td>
411                                </tr>
412                        </table>
413                </div>
414        </body>
415</html>
Note: See TracBrowser for help on using the repository browser.