SoPlex Documentation
Loading...
Searching...
No Matches
slufactor_rational.h
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-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file slufactor_rational.h
26 * @brief Implementation of Sparse Linear Solver with Rational precision.
27 */
28#ifndef _SLUFACTOR_RATIONAL_H_
29#define _SLUFACTOR_RATIONAL_H_
30
31#include <assert.h>
32
33#include "soplex/spxdefines.h"
34#include "soplex/timerfactory.h"
37#include "soplex/rational.h"
38
39namespace soplex
40{
41/// maximum nr. of factorization updates allowed before refactorization.
42#define MAXUPDATES 1000
43
44/**@brief Implementation of Sparse Linear Solver with Rational precision.
45 * @ingroup Algo
46 *
47 * This class implements a SLinSolverRational interface by using the sparse LU
48 * factorization implemented in CLUFactorRational.
49 */
51{
52public:
53
54 //--------------------------------
55 /**@name Types */
56 ///@{
57 /// Specifies how to perform \ref soplex::SLUFactorRational::change "change" method.
59 {
60 ETA = 0, ///<
61 FOREST_TOMLIN ///<
62 };
63 /// for convenience
65 ///@}
66
67private:
68
69 //--------------------------------
70 /**@name Private data */
71 ///@{
72 VectorRational vec; ///< Temporary vector
73 SSVectorRational ssvec; ///< Temporary semi-sparse vector
74 ///@}
75
76protected:
77
78 //--------------------------------
79 /**@name Protected data */
80 ///@{
81 bool usetup; ///< TRUE iff update vector has been setup
82 UpdateType uptype; ///< the current \ref soplex::SLUFactor<R>::UpdateType "UpdateType".
85 forest; ///< ? Update vector set up by solveRight4update() and solve2right4update()
86 Rational lastThreshold; ///< pivoting threshold of last factorization
87 ///@}
88
89 //--------------------------------
90 /**@name Control Parameters */
91 ///@{
92 /// minimum threshold to use.
94 /// minimum stability to achieve by setting threshold.
96 /// Time spent in solves
99 /// Number of solves
101 ///@}
102
103protected:
104
105 //--------------------------------
106 /**@name Protected helpers */
107 ///@{
108 ///
109 void freeAll();
110 ///
112 ///@}
113
114
115public:
116
117 //--------------------------------
118 /**@name Update type */
119 ///@{
120 /// returns the current update type uptype.
122 {
123 return uptype;
124 }
125
126 /// sets update type.
127 /** The new UpdateType becomes valid only after the next call to
128 method load().
129 */
131 {
132 uptype = tp;
133 }
134
135 /// sets minimum Markowitz threshold.
137 {
138 if(m < 0.01)
139 {
140 minThreshold = 0.01;
141 lastThreshold = 0.01;
142 }
143 else if(m > 0.99)
144 {
145 minThreshold = 0.99;
146 lastThreshold = 0.99;
147 }
148 else
149 {
150 minThreshold = m;
152 }
153 }
154
155 /// returns Markowitz threshold.
157 {
158 return lastThreshold;
159 }
160 ///@}
161
162 //--------------------------------
163 /**@name Derived from SLinSolverRational
164 See documentation of \ref soplex::SLinSolverRational "SLinSolverRational" for a
165 documentation of these methods.
166 */
167 ///@{
168 ///
169 void clear();
170 ///
171 int dim() const
172 {
173 return thedim;
174 }
175 ///
176 int memory() const
177 {
178 return nzCnt + l.start[l.firstUnused];
179 }
180 ///
181 const char* getName() const
182 {
183 return (uptype == SLUFactorRational::ETA) ? "SLU-Eta" : "SLU-Forest-Tomlin";
184 }
185 ///
187 {
188 return Status(stat);
189 }
190 ///
192 ///
193 std::string statistics() const;
194 ///
196 ///@}
197
198public:
199
200 //--------------------------------
201 /**@name Solve */
202 ///@{
203 /// Solves \f$Ax=b\f$.
205 /// Solves \f$Ax=b\f$.
207 /// Solves \f$Ax=b\f$.
209 /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
212 /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
215 /// Solves \f$Ax=b\f$.
217 /// Solves \f$Ax=b\f$.
219 /// Solves \f$Ax=b\f$ and \f$Ay=d\f$.
222 /// Solves \f$Ax=b\f$, \f$Ay=d\f$ and \f$Az=e\f$.
225 ///
227 ///@}
228
229 //--------------------------------
230 /**@name Miscellaneous */
231 ///@{
232 /// time spent in factorizations
234 {
235 return factorTime->time();
236 }
237 /// set time limit on factorization
239 {
241 }
242 /// reset FactorTime
244 {
245 factorTime->reset();
246 }
247 /// number of factorizations performed
248 int getFactorCount() const
249 {
250 return factorCount;
251 }
252 /// time spent in solves
254 {
255 return solveTime->time();
256 }
257 /// reset SolveTime
259 {
260 solveTime->reset();
261 }
262 /// number of solves performed
263 int getSolveCount() const
264 {
265 return solveCount;
266 }
267 /// reset timers and counters
269 {
270 factorTime->reset();
271 solveTime->reset();
272 factorCount = 0;
273 solveCount = 0;
274 }
275 /// prints the LU factorization to stdout.
276 void dump() const;
277
278 /// consistency check.
279 bool isConsistent() const;
280 ///@}
281
282 //------------------------------------
283 /**@name Constructors / Destructors */
284 ///@{
285 /// default constructor.
288 , vec(1)
289 , ssvec(1)
290 , usetup(false)
292 , eta(1)
293 , forest(1)
294 , minThreshold(0.01)
295 , timerType(Timer::USER_TIME)
296 {
297 row.perm = 0;
298 row.orig = 0;
299 col.perm = 0;
300 col.orig = 0;
301 u.row.elem = 0;
302 u.row.idx = 0;
303 u.row.start = 0;
304 u.row.len = 0;
305 u.row.max = 0;
306 u.col.elem = 0;
307 u.col.idx = 0;
308 u.col.start = 0;
309 u.col.len = 0;
310 u.col.max = 0;
311 l.idx = 0;
312 l.start = 0;
313 l.row = 0;
314 l.ridx = 0;
315 l.rbeg = 0;
316 l.rorig = 0;
317 l.rperm = 0;
318
319 nzCnt = 0;
320 thedim = 0;
321
322 try
323 {
331
332 work = vec.get_ptr();
333
334 u.row.used = 0;
335 spx_alloc(u.row.elem, thedim);
336 u.row.val.reDim(1);
337 spx_alloc(u.row.idx, u.row.val.dim());
338 spx_alloc(u.row.start, thedim + 1);
339 spx_alloc(u.row.len, thedim + 1);
340 spx_alloc(u.row.max, thedim + 1);
341
342 u.row.list.idx = thedim;
343 u.row.start[thedim] = 0;
344 u.row.max [thedim] = 0;
345 u.row.len [thedim] = 0;
346
347 u.col.size = 1;
348 u.col.used = 0;
349 spx_alloc(u.col.elem, thedim);
350 spx_alloc(u.col.idx, u.col.size);
351 spx_alloc(u.col.start, thedim + 1);
352 spx_alloc(u.col.len, thedim + 1);
353 spx_alloc(u.col.max, thedim + 1);
354 u.col.val.reDim(0);
355
356 u.col.list.idx = thedim;
357 u.col.start[thedim] = 0;
358 u.col.max[thedim] = 0;
359 u.col.len[thedim] = 0;
360
361 l.val.reDim(1);
362 spx_alloc(l.idx, l.val.dim());
363
364 l.startSize = 1;
365 l.firstUpdate = 0;
366 l.firstUnused = 0;
367
370 }
371 catch(const SPxMemoryException& x)
372 {
373 freeAll();
374 throw x;
375 }
376
377 l.rval.reDim(0);
378 l.ridx = 0;
379 l.rbeg = 0;
380 l.rorig = 0;
381 l.rperm = 0;
382
383 SLUFactorRational::clear(); // clear() is virtual
384
385 factorCount = 0;
386 timeLimit = -1.0;
387 solveCount = 0;
388
389 assert(row.perm != 0);
390 assert(row.orig != 0);
391 assert(col.perm != 0);
392 assert(col.orig != 0);
393
394 assert(u.row.elem != 0);
395 assert(u.row.idx != 0);
396 assert(u.row.start != 0);
397 assert(u.row.len != 0);
398 assert(u.row.max != 0);
399
400 assert(u.col.elem != 0);
401 assert(u.col.idx != 0);
402 assert(u.col.start != 0);
403 assert(u.col.len != 0);
404 assert(u.col.max != 0);
405
406 assert(l.idx != 0);
407 assert(l.start != 0);
408 assert(l.row != 0);
409
411 }
412 /// assignment operator.
414 {
415
416 if(this != &old)
417 {
418 // we don't need to copy them, because they are temporary vectors
419 vec.clear();
420 ssvec.clear();
421
422 eta = old.eta;
423 forest = old.forest;
424
425 freeAll();
426
427 try
428 {
429 assign(old);
430 }
431 catch(const SPxMemoryException& x)
432 {
433 freeAll();
434 throw x;
435 }
436
438 }
439
440 return *this;
441 }
442
443 /// copy constructor.
447 , vec(1) // we don't need to copy it, because they are temporary vectors
448 , ssvec(1) // we don't need to copy it, because they are temporary vectors
449 , usetup(old.usetup)
450 , eta(old.eta)
451 , forest(old.forest)
453 {
454 row.perm = 0;
455 row.orig = 0;
456 col.perm = 0;
457 col.orig = 0;
458 u.row.elem = 0;
459 u.row.idx = 0;
460 u.row.start = 0;
461 u.row.len = 0;
462 u.row.max = 0;
463 u.col.elem = 0;
464 u.col.idx = 0;
465 u.col.start = 0;
466 u.col.len = 0;
467 u.col.max = 0;
468 l.idx = 0;
469 l.start = 0;
470 l.row = 0;
471 l.ridx = 0;
472 l.rbeg = 0;
473 l.rorig = 0;
474 l.rperm = 0;
475
476 solveCount = 0;
479
480 try
481 {
482 assign(old);
483 }
484 catch(const SPxMemoryException& x)
485 {
486 freeAll();
487 throw x;
488 }
489
491 }
492
493 /// destructor.
495 /// clone function for polymorphism
496 inline virtual SLinSolverRational* clone() const
497 {
498 return new SLUFactorRational(*this);
499 }
500 ///@}
501
502private:
503
504 //------------------------------------
505 /**@name Private helpers */
506 ///@{
507 /// used to implement the assignment operator
509 ///@}
510};
511
512} // namespace soplex
513#include "slufactor_rational.hpp"
514#endif // _SLUFACTOR_RATIONAL_H_
Implementation of sparse LU factorization with Rational precision.
int factorCount
Number of factorizations.
Timer * factorTime
Time spent in factorizations.
Rational * work
Working array: must always be left as 0!
Real timeLimit
Time limit on factorization or solves.
Perm col
column permutation matrices
Perm row
row permutation matrices
SLinSolverRational::Status stat
Status indicator.
VectorRational diag
Array of pivot elements.
int thedim
dimension of factorized matrix
int nzCnt
number of nonzeros in U
Safe arrays of data objects.
Definition dataarray.h:75
int max() const
return maximum number of elements.
Definition dataarray.h:256
int size() const
return nr. of elements.
Definition dataarray.h:227
Implementation of Sparse Linear Solver with Rational precision.
UpdateType
Specifies how to perform change method.
SSVectorRational forest
? Update vector set up by solveRight4update() and solve2right4update()
Rational stability() const
Timer * solveTime
Time spent in solves.
virtual SLinSolverRational * clone() const
clone function for polymorphism
SLUFactorRational()
default constructor.
void assign(const SLUFactorRational &old)
used to implement the assignment operator
Real getFactorTime() const
time spent in factorizations
bool isConsistent() const
consistency check.
void changeEta(int idx, SSVectorRational &eta)
void solve3right4update(SSVectorRational &x, VectorRational &y, VectorRational &z, const SVectorRational &b, SSVectorRational &d, SSVectorRational &e)
Solves , and .
SLinSolverRational::Status Status
for convenience
void resetSolveTime()
reset SolveTime
void resetFactorTime()
reset FactorTime
UpdateType utype() const
returns the current update type uptype.
void setUtype(UpdateType tp)
sets update type.
void resetCounters()
reset timers and counters
UpdateType uptype
the current UpdateType.
int solveCount
Number of solves.
const char * getName() const
bool usetup
TRUE iff update vector has been setup.
void solveRight4update(SSVectorRational &x, const SVectorRational &b)
Solves .
Rational markowitz()
returns Markowitz threshold.
void solveLeft(SSVectorRational &x, const SVectorRational &b)
Solves .
Rational minStability
minimum stability to achieve by setting threshold.
void setMarkowitz(const Rational &m)
sets minimum Markowitz threshold.
void solve2right4update(SSVectorRational &x, VectorRational &y, const SVectorRational &b, SSVectorRational &d)
Solves and .
virtual ~SLUFactorRational()
destructor.
void solveLeft(SSVectorRational &x, VectorRational &y, VectorRational &z, const SVectorRational &b, SSVectorRational &d, SSVectorRational &e)
Solves , and .
SLUFactorRational(const SLUFactorRational &old)
copy constructor.
void setTimeLimit(const Real limit)
set time limit on factorization
int getSolveCount() const
number of solves performed
Rational minThreshold
minimum threshold to use.
void solveRight(SSVectorRational &x, const SVectorRational &b)
Solves .
int getFactorCount() const
number of factorizations performed
VectorRational vec
Temporary vector.
Rational lastThreshold
pivoting threshold of last factorization
void solveLeft(SSVectorRational &x, VectorRational &y, const SVectorRational &b, SSVectorRational &d)
Solves and .
std::string statistics() const
SSVectorRational ssvec
Temporary semi-sparse vector.
void solveRight(VectorRational &x, const VectorRational &b)
Solves .
SLUFactorRational & operator=(const SLUFactorRational &old)
assignment operator.
Real getSolveTime() const
time spent in solves
void solveLeft(VectorRational &x, const VectorRational &b)
Solves .
void dump() const
prints the LU factorization to stdout.
Status change(int idx, const SVectorRational &subst, const SSVectorRational *eta=0)
Status load(const SVectorRational *vec[], int dim)
Sparse Linear Solver virtual base class with Rational precision.
Status
status flags of the SLinSolverRational class.
Exception class for out of memory exceptions.
Definition exceptions.h:80
void clear()
Clears vector.
static Timer * createTimer(Timer::TYPE ttype)
create timers and allocate memory for them
Wrapper for the system time query methods.
Definition timer.h:86
TYPE
types of timers
Definition timer.h:109
virtual void reset()=0
initialize timer, set timing accounts to zero.
virtual Real time() const =0
R * get_ptr()
Conversion to C-style pointer.
Definition vectorbase.h:494
void reDim(int newdim, const bool setZero=true)
Resets VectorBase's dimension to newdim.
Definition vectorbase.h:541
int dim() const
Dimension of vector.
Definition vectorbase.h:270
void clear()
Set vector to contain all-zeros (keeping the same length)
Definition vectorbase.h:308
Implementation of sparse LU factorization with Rational precision.
Everything should be within this namespace.
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition spxalloc.h:58
Sparse Linear Solver virtual base class with Rational precision.
Debugging, floating point type and parameter definitions.
VectorRational rval
values of rows of L
int * rorig
original row permutation
int * row
column indices of L vectors
int startSize
size of array start
int * ridx
indices of rows of L
int * rbeg
start of rows in rval and ridx
int * rperm
original row permutation
int * idx
array of size val.dim() storing indices of L vectors
VectorRational val
values of L vectors
int firstUpdate
number of first update L vector
int * start
starting positions in val and idx
int firstUnused
number of first unused L vector
int * orig
orig[p] original index from p
int * perm
perm[i] permuted index from i
struct soplex::CLUFactorRational::U::Col col
struct soplex::CLUFactorRational::U::Row row
TimerFactory class.