Scippy

SoPlex

Sequential object-oriented simPlex

xternal.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2015 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file xternal.cpp
17  * @brief SoPlex documentation pages
18  * @author Ambros Gleixner
19  * @author Thorsten Koch
20  * @author Matthias Miltenberger
21  * @author Sebastian Orlowski
22  * @author Marc Pfetsch
23  * @author Andreas Tuchscherer
24  */
25 
26 /**@mainpage Overview
27  *
28  * @section MAIN What is SoPlex?
29  *
30  * SoPlex is an optimization package for solving linear programming problems
31  * (LPs) that can be used standalone via a command line interface and as a
32  * callable library. Its main features are:
33  *
34  * - an advanced implementation of the primal and dual revised simplex
35  * algorithm,
36  *
37  * - an object-oriented software design written in C++,
38  *
39  * - presolving, scaling, exploitation of sparsity, hot-starting from any
40  * regular basis,
41  *
42  * - column- and row-oriented form of the simplex algorithm,
43  *
44  * - a compile-time option to use 80bit extended ("quad") precision for
45  * numerically difficult LPs, and
46  *
47  * - special support for the exact solution of LPs over the rational numbers.
48  *
49  * SoPlex has been used in numerous reasearch and industry projects and is the
50  * standard LP solver linked to the constraint integer programming solver <a
51  * href="http://scip.zib.de/">SCIP</a>.
52  *
53  *@section INST Download, License, and Installation
54  *
55  * SoPlex can be downloaded in source code and as precompiled binaries from the
56  * <a href="http://soplex.zib.de">SoPlex</a> web page. It is also distributed
57  * as part of the <a href="http://scip.zib.de/">SCIP Optimization Suite</a>.
58  *
59  * SoPlex is distributed under the terms of the \ref LICENSE "ZIB Academic Licence"
60  * and can be freely used for academic research. See the <a
61  * href="http://soplex.zib.de">SoPlex</a> web page or contact us for more
62  * information.
63  *
64  * For help with installation please consult the \ref INSTALL "INSTALL" file in
65  * the distribution.
66  *
67  * @section GETTINGSTARTED Getting started
68  *
69  * - \ref FAQ "Frequently Asked Questions"
70  *
71  * - \ref CMD "How to use the SoPlex command line"
72  *
73  * - \ref LIB "How to use SoPlex as a callable library"
74  *
75  * - \ref PARS "Parameters in SoPlex"
76  *
77  * - \ref PROG "Programming with SoPlex"
78  *
79  * - \ref EXACT "How to use SoPlex as an exact LP solver"
80  *
81  * A tutorial article for getting started with the SCIP Optimization Suite,
82  * which includes SoPlex, is available as <a
83  * href="http://scip.zib.de/doc/ZR-12-27.pdf">ZIB-Report 12-27</a>.
84  *
85  * @section AUTHORS Authors
86  *
87  * The initial implementation of SoPlex has been developed by Roland Wunderling
88  * as part of his Ph.D. thesis <a
89  * href="http://www.zib.de/PaperWeb/abstracts/TR-96-09">"Paralleler und
90  * Objektorientierter Simplex-Algorithmus"</a> from 1996. Since then many
91  * developers have maintained and improved the underlying algorithms. See the
92  * <a href="http://soplex.zib.de">SoPlex</a> web page for a comprehensive list
93  * of all contributors.
94  *
95  * @version 2.2.0
96  */
97 
98 
99 /**@namespace soplex
100  @brief Everything should be within this namespace.
101 
102  We have put the whole class library in the namespace soplex.
103  If anything here is defined outside, this is a mistake and
104  should be reported.
105 */
106 
107 
108 /**@defgroup Elementary Elementary Classes
109  @brief General purpose classes.
110 
111  Elementary classes are provided for general purpose use in
112  projects way beyond the scope of numerical software or linear
113  programming.
114 */
115 
116 /**@defgroup Algebra Linear Algebra Classes
117  @brief Basic data types for linear algebra computations.
118 
119  Linear algebra classes provide basic data types for (sparse)
120  linear algebra computations. However, their functionality is
121  restricted to simple operations such as addition and scaling.
122  For complex tasks, such as solving linear systems of equations,
123  algorithmic classes are provided instead.
124 */
125 
126 /**@defgroup Algo Algorithmic Classes
127  @brief Implementation of numerical algorithms.
128 
129  Algorithmic classes serve for implementing a variety of
130  algorithms for solving numerical (sub-)problems.
131 */
132 
133 /**@page DataObjects Data Objects
134 
135  \em Data \em objects refer to C++ objects that do not allocate any
136  resources, particularly that do not allocate any memory. This
137  makes them behave just like ordinary C structures, in that both,
138  the copy constructor and assignment operator are equivalent to a
139  memcopy of the memory taken by the object. Examples for data
140  objects are all builtin types such as \c int or \c double or
141  \e simple classes such as \c complex.
142 
143  We distinguish \em data \em objects from general C++ objects that
144  may include some allocation of resources. (Note that for general
145  C++ objects that do allocate resources, this must be respected by
146  providing appropriate copy constructor and assignment operators.)
147  An example for a general C++ class is class DataArray.
148 
149  The distinction between data and general C++ objects becomes
150  relevant when using such objects in container classes such as
151  DataArray or Array.
152 */
153 
154 
155 /**@page LICENSE License
156  *
157  * \verbinclude COPYING
158  */
159 
160 
161 /**@page INSTALL Installation
162  *
163  * \verbinclude INSTALL
164  */
165 
166 
167 /**@page FAQ Frequently Asked Questions
168  * \htmlinclude faq.inc
169  */
170 
171 
172 /**@page CMD How to use the SoPlex command line
173  *
174  * Running the command line binary of SoPlex without any arguments displays a
175  * list of options. You can write a parameter file with default parameters by
176  * using option --saveset=FILENAME.set. After changing parameter values in this
177  * file you can use it by with --loadset=FILENAME.set. The most frequently used
178  * parameters have abbreviations.
179  *
180  * For compatibility the command line interface of SoPlex versions 1.x is
181  * available when you compile SoPlex with "make LEGACY=true" (using the provided
182  * Makefile) or compile with the preprocessor define SOPLEX_LEGACY.
183  */
184 
185 
186 /**@page LIB How to use SoPlex as a callable library
187  *
188  *@section LIB1 Namespace "soplex"
189  *
190  * The entire SoPlex code is contained in the namespace \ref soplex. Because of
191  * this, either all classes and methods must be qualified by the prefix
192  * "soplex::" or a "using namespace soplex;" must be present.
193  *
194  *@section LIB2 Interface class
195  *
196  * The main interface is given by the class \ref soplex::SoPlex "SoPlex", which
197  * handles the construction and modification of an LP, the solving process,
198  * allows to access and change parameters, and retrieve solution information.
199  *
200  * A basic example on how to construct and solve an LP via the class
201  * \ref soplex::SoPlex "SoPlex" is given in the file \ref example.cpp.
202  *
203  *@section LIB3 Deprecated 1.x interface
204  *
205  * With version 2.0, the SoPlex class has been updated significantly compared to
206  * the 1.x version. Although this is deprecated, it is still possible to use
207  * the 1.x interface class by compiling with LEGACY=true (using the provided
208  * Makefile) or compiling with the preprocessor flag SOPLEX_LEGACY. This
209  * deactivates the functionalities to solve LPs exactly.
210 */
211 
212 
213 /**@page PARS Parameters in SoPlex
214  *
215  * Since SoPlex 2.0, the main interface class \ref soplex::SoPlex "SoPlex" provides an improved management of
216  * parameters. Currently, there are three types of parameters for boolean, integer, and real values. A list of default
217  * parameters is provided \ref PARSLIST "here".
218  *
219  *@section PARS1 Setting parameters at the command line
220  *
221  * When using the command line interface, parameters can be changed with the generic option
222  *
223  * <code>\--&lt;type&gt;:&lt;name&gt;=&lt;val&gt;</code>
224  *
225  * where &lt;type&gt; is one of <code>bool</code>, <code>int</code>, or <code>real</code> and name is the name of the
226  * parameter. E.g., in order to deactivate the simplifier, one can use the option <code>\--bool:simplifier=0</code>.
227  *
228  *@section PARS2 Setting parameters via the callable library
229  *
230  * When using the callable library via the class \ref soplex::SoPlex "SoPlex" (of version 2.0 and above), parameters can
231  * be changed by the methods \ref soplex::SoPlex::setBoolParam() "setBoolParam()", \ref soplex::SoPlex::setIntParam()
232  * "setIntParam()", and \ref soplex::SoPlex::setRealParam() "setRealParam()". See their documentation for details.
233  */
234 
235 
236 /**@page PARSLIST List of all SoPlex parameters
237  *
238  * This page lists all parameters of the current SoPlex version. This list can
239  * easily be generated by the SoPlex command line interface using:
240  *
241  * <code>soplex \--saveset=&lt;file name&gt;.set</code>
242  *
243  * or via the method \ref soplex::SoPlex::saveSettingsFile() "saveSettingsFile(&quot;&lt;file name&gt;.set&quot;, true)" of the class \ref
244  * soplex::SoPlex "SoPlex".
245  *
246  * \verbinclude parameters.set
247  */
248 
249 
250 /**@page PROG Programming with SoPlex
251  *
252  * Besides the main interface class \ref soplex::SoPlex "SoPlex", the classes of
253  * the SoPlex library are categorized into three different types:
254  *
255  * - Elementary classes are provided for general purpose use in projects way
256  * beyond the scope of numerical software or linear programming.
257  *
258  * - Linear algebra classes provide basic data types for (sparse) linear algebra
259  * computations. However, their functionality is restricted to simple
260  * operations such as addition and scaling. For complex tasks, such as
261  * solving linear systems of equations, algorithmic classes are provided
262  * instead.
263  *
264  * - Algorithmic classes serve for implementing maybe a variety of algorithms
265  * for solving numerical (sub-)problems.
266  *
267  * The main class implementing the primal and dual simplex algorithm is the
268  * class \ref soplex::SPxSolver "SPxSolver". The following sections are
269  * dedicated to users who want to provide own components of the simplex
270  * algorithm such as pricers, ratio tests, start basis generators or LP
271  * simplifiers to use with SoPlex's standard floating-point simplex
272  * implementation.
273  *
274  *@section Representation Virtualizing the Representation
275  *
276  * The primal Simplex on the columnwise representation is structurally
277  * equivalent to the dual Simplex on the rowwise representation and vice versa
278  * (see below). Hence, it is desirable to treat both cases in a very similar
279  * manner. This is supported by the programmer's interface of SoPlex which
280  * provides access methods for all internal data in two ways: one is relative to
281  * the "physical" representation of the LP in rows and columns, while the other
282  * is relative to the chosen basis representation.
283  *
284  * If e.g. a \ref soplex::SPxPricer "SPxPricer" is written using the second type
285  * of methods only (which will generally be the case), the same code can be used
286  * for running SoPlex's simplex algorithm for both representations. We will now
287  * give two examples for this abstraction from the chosen representation.
288  *
289  * Methods \c vector() will return a column or a row vector, corresponding to
290  * the chosen basis representation. The other "vectors" will be referred to as
291  * \em covectors:
292  *
293  * <TABLE>
294  * <TR><TD>&nbsp; </TD><TD>ROW </TD><TD>COLUMN </TD></TR>
295  * <TR><TD>vector </TD><TD>rowVector</TD><TD>colVector</TD></TR>
296  * <TR><TD>coVector</TD><TD>colVector</TD><TD>rowVector</TD></TR>
297  * </TABLE>
298  *
299  * Whether the \ref soplex::SPxBasis::Desc::Status "SPxBasis::Desc::Status" of a
300  * variable indicates that the corresponding vector is in the basis matrix or
301  * not also depends on the chosen representation. Hence, methods \c isBasic()
302  * are provided to get the correct answer for both representations.
303  *
304  *@section Simplex Vectors and Bounds
305  *
306  * The Simplex algorithms keeps three vectors which are associated to each
307  * basis. Two of them are required for the pricing, while the third one is
308  * needed for detecting feasibility of the basis. For all three vectors, bounds
309  * are defined. The Simplex algorithm changes the basis until all three vectors
310  * satisfy their bounds, which means that the optimal solution has been found.
311  *
312  * With each update of the basis, also the three vectors need to be
313  * updated. This is best supported by the use of \c UpdateVectors.
314  *
315  *@subsection Variables
316  *
317  * The Simplex algorithm works with two types of variables, primals and duals.
318  * The primal variables are associated with each column of an LP, whereas the
319  * dual variables are associated with each row. However, for each row a slack
320  * variable must be added to the set of primals (to represent inequalities), and
321  * a reduced cost variable must be added for each column (to represent upper or
322  * lower bounds). Note, that mathematically, one dual variable for each bound
323  * (upper and lower) should be added. However, this variable would always yield
324  * the same value and can, hence, be implemented as one.
325  *
326  * To summarize, we have a primal variable for each LP column and row (i.e., its
327  * slack) as well as a dual variable for each LP row and column (i.e., its
328  * bounds). However, not all these values need to be stored and computed, since
329  * the structure of the Simplex algorithms allow to keep them implicitly.
330  *
331  * If the SPxBasis's Status of a row or column is one of \c P_ON_LOWER, \c
332  * P_ON_UPPER, \c P_FIXED or \c P_FREE, the value of the corresponding primal
333  * variable is the lower, upper or both bound(s) or 0, respectively. The
334  * corresponding dual variable needs to be computed. Equivalently, for a Status
335  * of \c D_FREE, \c D_ON_UPPER, \c D_ON_LOWER, \c D_ON_BOTH or \c D_UNDEFINED,
336  * the corresponding dual variable is 0, whereas the primal one needs to be
337  * computed.
338  *
339  * The following vectors are declared for holding the values to be computed: \c
340  * primRhs, \c primVec (with dimension \c nCols()) for the primal variables, and
341  * \c dualRhs, \c dualVec (with dimension \c nRows()) for the dual
342  * variables. The additional variable \c addvec (with dimension \c coDim())
343  * depends on the representation.
344  *
345  * @subsection Bounds
346  *
347  * Primal and dual variables are bounded (including \f$\pm\infty\f$ as bounds).
348  * If all primal variables are within their bounds, the Simplex basis is said to
349  * be primal feasible. Analogously, if all dual variables are within their
350  * bounds, its is called dual feasible. If a basis is both, primal and dual
351  * feasible, the optimal solution has been found.
352  *
353  * In the dual Simplex, the basis is maintained dual feasible, while primal
354  * feasibility is improved via basis updates. However, for numerical reasons
355  * dual feasibility must be relaxed from time to time. Equivalently, primal
356  * feasibility will be relaxed to retain numerical stability in the primal
357  * Simplex algorithm.
358  *
359  * Relaxation of (dual or primal) feasibility is achieved by relaxing the bounds
360  * of primal or dual variables. However, for each type of Simplex only the
361  * corresponding bounds need to be relaxed. Hence, we define only one vector of
362  * upper and lower bound for each row and column and initialize it with primal
363  * or dual bound, depending on the Simplex type (see \c theURbound, \c
364  * theLRbound, \c theUCbound, \c theLCbound).
365  */
366 
367 
368 /**@page EXACT How to use SoPlex as an exact LP solver
369  *
370  * Since version 1.7, SoPlex implements an \em iterative \em refinement procedure on the level of linear programs, which
371  * allows for computing extended-precision solutions beyond the limits of standard floating-point arithmetic. It may be
372  * particularly helpful for numerically troublesome LPs and applications that require solutions within tight feasibility
373  * tolerances. Since version 2.1 this has been extended to compute exact rational solutions.
374  *
375  * By default, SoPlex functions as a standard floating-point LP solver. In order to use SoPlex as an exact LP solver,
376  * you need to compile SoPlex with GMP support (default, see the \ref INSTALL "INSTALL" file) and change the following
377  * parameters from their default value:
378  *
379  * - <code>real:feastol = 0</code>
380  *
381  * - <code>real:opttol = 0</code>
382  *
383  * - <code>int:solvemode = 2</code>
384  *
385  * - <code>int:syncmode = 1</code>
386  *
387  * - <code>int:readmode = 1</code> (optional, activates exact parsing of input files)
388  *
389  * - <code>int:checkmode = 2</code> (optional, activates exact final check of feasibility and optimality at the command
390  * line)
391  *
392  * See \ref PARS "this page" how to change parameters and the \ref PARSLIST "list of all SoPlex parameters" for their
393  * detailed description. A settings file <code>exact.set</code> for exact solving is provided in the directory
394  * <code>settings</code> of the distribution. On the command line, this can be read with option
395  * <code>\--loadset=settings/exact.set</code>.
396  *
397  * If you have questions on particularly this feature you can contact <a href="http://www.zib.de/gleixner/">Ambros
398  * Gleixner</a> or post them on the SoPlex mailing list.
399  *
400  *
401  *@section EXACT4 References
402  *
403  * The mathematical background of the underlying methods is described in the papers
404  *
405  * - Ambros M. Gleixner, Daniel E. Steffy, Kati Wolter. <i>Improving the Accuracy of Linear Programming Solvers with
406  * Iterative Refinement</i>. Proc. of ISSAC '12, pages 187--194, 2012, available as <a
407  * href="http://nbn-resolving.de/urn:nbn:de:0297-zib-15451">ZIB-Report 12-19</a>.
408  *
409  * - Ambros M. Gleixner, Daniel E. Steffy, Kati Wolter. <i>Iterative Refinement for Linear Programming</i>. <a
410  * href="http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55118">ZIB-Report 15-15</a>, Zuse Institute
411  * Berlin, 2015.
412  *
413  * <b>When using SoPlex as an exact LP solver, please cite the above papers.</b>
414  */