SoPlex Documentation
Loading...
Searching...
No Matches
spxbasis.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 spxbasis.h
26 * @brief Simplex basis.
27 */
28#ifndef _SPXBASIS_H_
29#define _SPXBASIS_H_
30
31/* undefine SOPLEX_DEBUG flag from including files; if SOPLEX_DEBUG should be defined in this file, do so below */
32#ifdef SOPLEX_DEBUG
33#define SOPLEX_DEBUG_SPXBASIS
34#undef SOPLEX_DEBUG
35#endif
36
37#include <assert.h>
38#include <iostream>
39#include <iomanip>
40#include <string.h>
41#include <sstream>
42
43#include "soplex/spxdefines.h"
44#include "soplex/spxlp.h"
45#include "soplex/svector.h"
46#include "soplex/ssvector.h"
47#include "soplex/dataarray.h"
48#include "soplex/slinsolver.h"
49#include "soplex/nameset.h"
50#include "soplex/spxout.h"
51#include "soplex/timerfactory.h"
52
53//#define MEASUREUPDATETIME
54
55namespace soplex
56{
57template <class R>
58class SPxSolverBase;
59
60/**@class SPxBasisBase
61 @brief Simplex basis.
62 @ingroup Algo
63
64 Consider the linear program as provided from class SPxLP:
65 \f[
66 \begin{array}{rl}
67 \hbox{max} & c^T x \\
68 \hbox{s.t.} & l_r \le Ax \le u_r \\
69 & l_c \le x \le u_c
70 \end{array}
71 \f]
72 where \f$c, l_c, u_c, x \in {\bf R}^n\f$, \f$l_r, u_r \in {\bf R}^m\f$ and
73 \f$A \in {\bf R}^{m \times n}\f$. Solving this LP with the simplex algorithm
74 requires the definition of a \em basis. Such can be defined as a set of
75 column vectors or a set of row vectors building a non-singular matrix. We
76 will refer to the first case as the \em columnwise \em representation and
77 the latter case will be called the \em rowwise \em representation. In both
78 cases, a \em basis is a set of vectors forming a non-singular matrix. The
79 dimension of the vectors is referred to as the basis' \em dimension,
80 whereas the number of vectors belonging to the LP is called the basis'
81 \em codimension.
82
83 Class SPxBasisBase is designed to represent a generic simplex basis, suitable
84 for both representations. At any time the representation can be changed by
85 calling method setRep().
86
87 Class SPxBasisBase provides methods for solving linear systems with the basis
88 matrix. However, SPxBasisBase does not provide a linear solver by its own.
89 Instead, a SLinSolver object must be #load%ed to a SPxBasisBase which will
90 be called for solving linear systems.
91*/
92template <class R> // theLP gets templated
94{
95public:
96
97 /// basis status.
98 /** Each SPxBasisBase is assigned a status flag, which can take on of the
99 above values.
100 */
102 {
103 NO_PROBLEM = -2, ///< No Problem has been loaded to the basis.
104 SINGULAR = -1, ///< Basis is singular.
105 REGULAR = 0, ///< Basis is not known to be dual nor primal feasible.
106 DUAL = 1, ///< Basis is dual feasible.
107 PRIMAL = 2, ///< Basis is primal feasible.
108 OPTIMAL = 3, ///< Basis is optimal, i.e. dual and primal feasible.
109 UNBOUNDED = 4, ///< LP has been proven to be primal unbounded.
110 INFEASIBLE = 5 ///< LP has been proven to be primal infeasible.
111 };
112
113
114 /// Basis descriptor.
115 class Desc
116 {
117 public:
118
119 //------------------------------------
120 ///@name Status
121 ///@{
122 /// Status of a variable.
123 /** A basis is described by assigning a Status to all of the LP
124 variables and covariables. This assignment is maintained by the
125 basis #Desc%riptor.
126
127 Variables and covariables (slackvariables) may have a primal or dual Status. The
128 first type specifies that a variable is set on a primal bound, while
129 the latter type indicates a dual variable to be set on a bound.
130 If a row variable has a primal status, say #P_ON_UPPER, this means
131 that the upper bound of the inequality is set to be tight. Hence,
132 in this case the upper bound must not be infinity.
133
134 Equivalently, if the status of a variable is dual, say #D_ON_UPPER,
135 it means that the dual variable corresponding to the upper bound
136 inequality of this variable is set to 0.
137
138 For a column basis, primal #Status%es correspond to nonbasic
139 variables, while dual ones are basic. This is reversed for a row
140 basis. We will now reveal in more detail the significance of
141 variable #Status%es.
142
143 <b>Primal Variables</b>
144
145 Consider a range inequality \f$l_r \le a^T x \le u_r\f$ or bounds on
146 a variable \f$l_c \le x_c \le u_c\f$. The following table reveals
147 what is implied if the corresponding variable or covariable is
148 assigned to a primal #Status:
149
150 \f[
151 \begin{array}{lcl}
152 l_c \le x_c \le u_c & \mbox{Status}(x_i) & l_r \le a^T x \le u_r \\
153 \hline
154 x_c = u_c < \infty & \mbox{P\_ON\_UPPER} & a^T x = u_r < \infty \\
155 x_c = l_c > -\infty & \mbox{P\_ON\_LOWER} & a^T x = l_r > -\infty \\
156 -\infty < l_c = x_c = u_c < \infty
157 & \mbox{P\_FIXED} &
158 -\infty < l_r = a^T x = u_r < \infty \\
159 -\infty = l_i < x_i=0 < u_i = \infty
160 & \mbox{P\_FREE} &
161 -\infty = l_r < a^T x = 0 < u_r = \infty \\
162 \end{array}
163 \f]
164
165 Note that to determine whether a variable with #Status stat is set to
166 its upper bound, one can compute the test (-stat | -#P_ON_UPPER).
167 This will yield true even if the variable is fixed, i.e., sitting on
168 both bounds at the same time.
169
170 <b>Dual Variables</b>
171
172 In principle for implementing the Simplex algorithm it would suffice
173 to use only one dual #Status. However, for performance reasons it
174 is advisable to introduce various dual status types, reflecting
175 the structure of the bounds. Given an upper bound \f$u\f$ and a lower
176 bound \f$l\f$ of a constraint or variable, the following table
177 indicates the setting of the dual Status of this variable.
178
179 \f[
180 \begin{array}{cl}
181 l \le ... \le u & \mbox{Status} \\
182 \hline
183 -\infty < l \ne u < \infty & \mbox{D\_ON\_BOTH} \\
184 -\infty < l \ne u = \infty & \mbox{D\_ON\_UPPER} \\
185 -\infty = l \ne u < \infty & \mbox{D\_ON\_LOWER} \\
186 -\infty < l = u < \infty & \mbox{D\_FREE} \\
187 -\infty = l \ne u = \infty & \mbox{D\_UNDEFINED} \\
188 \end{array}
189 \f]
190
191 Note that unbounded primal variables are reflected by an #D_UNDEFINED
192 dual variable, since no reduced costs exist for them. To facilitate
193 the assignment of dual #Status%es, class SPxBasisBase provides methods
194 #dualStatus(), #dualColStatus() and #dualRowStatus)().
195 */
197 {
198 P_ON_LOWER = -4, ///< primal variable is set to its lower bound
199 P_ON_UPPER = -2, ///< primal variable is set to its upper bound
200 P_FREE = -1, ///< primal variable is left free, but unset
201 P_FIXED = P_ON_UPPER + P_ON_LOWER, ///< primal variable is fixed to both bounds
202 D_FREE = 1, ///< dual variable is left free, but unset
203 D_ON_UPPER = 2, ///< dual variable is set to its upper bound
204 D_ON_LOWER = 4, ///< dual variable is set to its lower bound
205 D_ON_BOTH = D_ON_LOWER + D_ON_UPPER, ///< dual variable has two bounds
206 D_UNDEFINED = 8 ///< primal or dual variable is undefined
207 };
208 ///@}
209
211 template <class T> friend std::ostream& operator<< (std::ostream& os,
212 const Status& stat); //@todo is the <> required here?
213
214 private:
215
216 //------------------------------------
217 ///@name Data
218 ///@{
219 DataArray < Status > rowstat; ///< status of rows.
220 DataArray < Status > colstat; ///< status of columns.
221 DataArray < Status >* stat; ///< basis' status.
222 DataArray < Status >* costat; ///< cobasis' status.
223 ///@}
224
225 public:
226
227 //------------------------------------
228 ///@name Access / modification
229 ///@{
230 /// returns number of columns.
231 int nCols() const
232 {
233 return colstat.size();
234 }
235 /// returns number of rows.
236 int nRows() const
237 {
238 return rowstat.size();
239 }
240 /// returns dimension.
241 int dim() const
242 {
243 return stat->size();
244 }
245 /// returns codimension.
246 int coDim() const
247 {
248 return costat->size();
249 }
250 ///
252 {
253 return rowstat[i];
254 }
255 /// returns status of row \p i.
256 Status rowStatus(int i) const
257 {
258 return rowstat[i];
259 }
260 /// returns the array of row \ref soplex::SPxBasisBase<R>::Desc::Status "Status"es.
261 const Status* rowStatus(void) const
262 {
263 return rowstat.get_const_ptr();
264 }
265 ///
267 {
268 return colstat[i];
269 }
270 /// returns status of column \p i.
271 Status colStatus(int i) const
272 {
273 return colstat[i];
274 }
275 /// returns the array of column \ref soplex::SPxBasisBase<R>::Desc::Status "Status"es.
276 const Status* colStatus(void) const
277 {
278 return colstat.get_const_ptr();
279 }
280 ///
282 {
283 return (*stat)[i];
284 }
285 /// returns status of variable \p i.
286 Status status(int i) const
287 {
288 return (*stat)[i];
289 }
290 /// returns the array of variable \ref soplex::SPxBasisBase<R>::Desc::Status "Status"es.
291 const Status* status(void) const
292 {
293 return stat->get_const_ptr();
294 }
295 ///
297 {
298 return (*costat)[i];
299 }
300 /// returns status of covariable \p i.
301 Status coStatus(int i) const
302 {
303 return (*costat)[i];
304 }
305 /// returns the array of covariable \ref soplex::SPxBasisBase<R>::Desc::Status "Status"es.
306 const Status* coStatus(void) const
307 {
308 return costat->get_const_ptr();
309 }
310 /// resets dimensions.
311 void reSize(int rowDim, int colDim);
312 ///@}
313
314 //------------------------------------
315 ///@name Debugging
316 ///@{
317 /// Prints out status.
318 void dump() const;
319
320 /// consistency check.
321 bool isConsistent() const;
322 ///@}
323
324 //------------------------------------
325 ///@name Construction / destruction
326 ///@{
327 /// default constructor
329 : stat(0)
330 , costat(0)
331 {}
332 explicit Desc(const SPxSolverBase<R>& base);
333
334 /// copy constructor
335 Desc(const Desc& old);
336 /// assignment operator
337 Desc& operator=(const Desc& rhs);
338 ///@}
339 };
340
341protected:
342
343 //------------------------------------
344 //**@name Protected data
345 /**
346 For storing the basis matrix we keep two arrays: Array #theBaseId
347 contains the SPxId%s of the basis vectors, and #matrix the pointers to
348 the vectors themselfes. Method #loadMatrixVecs() serves for loading
349 #matrix according to the SPxId%s stored in #theBaseId. This method must
350 be called whenever the VectorBase<R> pointers may have
351 changed due to manipulations of the LP.
352 */
353 ///@{
354 /// the LP
356 /// SPxId%s of basic vectors.
358 /// pointers to the vectors of the basis matrix.
360 /// \c true iff the pointers in \ref soplex::SPxBasisBase<R>::matrix "matrix" are set up correctly.
362
363 /* @brief LU factorization of basis matrix
364 The factorization of the matrix is stored in #factor if #factorized != 0.
365 Otherwise #factor is undefined.
366 */
368 /// \c true iff \ref soplex::SPxBasisBase<R>::factor "factor" = \ref soplex::SPxBasisBase<R>::matrix "matrix" \f$^{-1}\f$.
370
371 /// number of updates before refactorization.
372 /** When a vector of the basis matrix is exchanged by a call to method
373 #change(), the LU factorization of the matrix is updated
374 accordingly. However, after atmost #maxUpdates updates of the
375 factorization, it is recomputed in order to regain numerical
376 stability and reduce fill in.
377 */
379
380 /// allowed increase of nonzeros before refactorization.
381 /** When the number of nonzeros in LU factorization exceeds
382 #nonzeroFactor times the number of nonzeros in B, the
383 basis matrix is refactorized.
384 */
386
387 /// allowed increase in relative fill before refactorization
388 /** When the real relative fill is bigger than fillFactor times lastFill
389 * the Basis will be refactorized.
390 */
392
393 /// allowed total increase in memory consumption before refactorization
395
396 /* Rank-1-updates to the basis may be performed via method #change(). In
397 this case, the factorization is updated, and the following members are
398 reset.
399 */
400 int iterCount; ///< number of calls to change() since last manipulation
401 int lastIterCount; ///< number of calls to change() before halting the simplex
402 int iterDegenCheck;///< number of calls to change() since last degeneracy check
403 int updateCount; ///< number of calls to change() since last factorize()
404 int totalUpdateCount; ///< number of updates
405 int nzCount; ///< number of nonzeros in basis matrix
406 int lastMem; ///< memory needed after last fresh factorization
407 R lastFill; ///< fill ratio that occured during last factorization
408 int lastNzCount; ///< number of nonzeros in basis matrix after last fresh factorization
409
410 Timer* theTime; ///< time spent in updates
411 Timer::TYPE timerType; ///< type of timer (user or wallclock)
412
413 SPxId lastin; ///< lastEntered(): variable entered the base last
414 SPxId lastout; ///< lastLeft(): variable left the base last
415 int lastidx; ///< lastIndex(): basis index where last update was done
416 R minStab; ///< minimum stability
417 ///@}
418
419private:
420
421 //------------------------------------
422 //**@name Private data */
423 ///@{
424 SPxStatus thestatus; ///< current status of the basis.
425 Desc thedesc; ///< the basis' Descriptor
426 bool freeSlinSolver; ///< true iff factor should be freed inside of this object
427 SPxOut* spxout; ///< message handler
428
429 ///@}
430
431public:
432
433 //------------------------------------------------
434 /**@name Status and Descriptor related Methods */
435 ///@{
436 /// returns current SPxStatus.
438 {
439 return thestatus;
440 }
441
442 /// sets basis SPxStatus to \p stat.
444 {
445
446 if(thestatus != stat)
447 {
448#ifdef SOPLEX_DEBUG
449 MSG_DEBUG(std::cout << "DBSTAT01 SPxBasisBase<R>::setStatus(): status: "
450 << int(thestatus) << " (" << thestatus << ") -> "
451 << int(stat) << " (" << stat << ")" << std::endl;)
452#endif
453
454 thestatus = stat;
455
456 if(stat == NO_PROBLEM)
457 invalidate();
458 }
459 }
460
461 // TODO control factorization frequency dynamically
462 /// change maximum number of iterations until a refactorization is performed
464 {
465 assert(maxUp >= 0);
467 }
468
469 /// returns maximum number of updates before a refactorization is performed
470 int getMaxUpdates() const
471 {
472 return maxUpdates;
473 }
474
475 ///
476 const Desc& desc() const
477 {
478 return thedesc;
479 }
480 /// returns current basis Descriptor.
482 {
483 return thedesc;
484 }
485
486 /// dual Status for the \p i'th column variable of the loaded LP.
487 typename Desc::Status dualColStatus(int i) const;
488
489 /// dual Status for the column variable with ID \p id of the loaded LP.
490 typename Desc::Status dualStatus(const SPxColId& id) const;
491
492 /// dual Status for the \p i'th row variable of the loaded LP.
493 typename Desc::Status dualRowStatus(int i) const;
494
495 /// dual Status for the row variable with ID \p id of the loaded LP.
496 typename Desc::Status dualStatus(const SPxRowId& id) const;
497
498 /// dual Status for the variable with ID \p id of the loaded LP.
499 /** It is automatically detected, whether the \p id is one of a
500 row or a column variable, and the correct row or column status
501 is returned.
502 */
503 typename Desc::Status dualStatus(const SPxId& id) const
504 {
505 return id.isSPxRowId()
506 ? dualStatus(SPxRowId(id))
507 : dualStatus(SPxColId(id));
508 }
509 ///@}
510
511
512 //-----------------------------------
513 /**@name Inquiry Methods */
514 ///@{
515 ///
516 inline SPxId& baseId(int i)
517 {
518 return theBaseId[i];
519 }
520 /// returns the Id of the \p i'th basis vector.
521 inline SPxId baseId(int i) const
522 {
523 return theBaseId[i];
524 }
525
526 /// returns the \p i'th basic vector.
527 const SVectorBase<R>& baseVec(int i) const
528 {
530 return *matrix[i];
531 }
532
533 /// returns SPxId of last VectorBase<R> included to the basis.
534 inline SPxId lastEntered() const
535 {
536 return lastin;
537 }
538
539 /// returns SPxId of last vector that left the basis.
540 inline SPxId lastLeft() const
541 {
542 return lastout;
543 }
544
545 /// returns index in basis where last update was done.
546 inline int lastIndex() const
547 {
548 return lastidx;
549 }
550
551 /// returns number of basis changes since last refactorization.
552 inline int lastUpdate() const
553 {
554 return updateCount;
555 }
556
557 /// returns number of basis changes since last \ref soplex::SPxBasisBase<R>::load() "load()".
558 inline int iteration() const
559 {
560 return iterCount;
561 }
562
563 /// returns the number of iterations prior to the last break in execution
564 inline int prevIteration() const
565 {
566 return lastIterCount;
567 }
568
569 /// returns the number of iterations since the last degeneracy check
570 inline int lastDegenCheck() const
571 {
572 return iterDegenCheck;
573 }
574
575 /// returns loaded solver.
576 inline SPxSolverBase<R>* solver() const
577 {
578 return theLP;
579 }
580 ///@}
581
582 //-----------------------------------
583 /**@name Linear Algebra */
584 ///@{
585 /// Basis-vector product.
586 /** Depending on the representation, for an SPxBasisBase B,
587 B.multBaseWith(x) computes
588 - \f$x \leftarrow Bx\f$ in the columnwise case, and
589 - \f$x \leftarrow x^TB\f$ in the rowwise case.
590
591 Both can be seen uniformly as multiplying the basis matrix \p B with
592 a vector \p x aligned the same way as the \em vectors of \p B.
593 */
595
596 /// Basis-vector product
598
599 /// Vector-basis product.
600 /** Depending on the representation, for a #SPxBasisBase B,
601 B.multWithBase(x) computes
602 - \f$x \leftarrow x^TB\f$ in the columnwise case and
603 - \f$x \leftarrow Bx\f$ in the rowwise case.
604
605 Both can be seen uniformly as multiplying the basis matrix \p B with
606 a vector \p x aligned the same way as the \em covectors of \p B.
607 */
609
610 /// VectorBase<R>-basis product
612
613 /* compute an estimated condition number for the current basis matrix
614 * by computing estimates of the norms of B and B^-1 using the power method.
615 * maxiters and tolerance control the accuracy of the estimate.
616 */
617 R condition(int maxiters = 10, R tolerance = 1e-6);
618
619 /* wrapper to compute an estimate of the condition number of the current basis matrix */
621 {
622 return condition(20, 1e-6);
623 }
624
625 /* wrapper to compute the exact condition number of the current basis matrix */
627 {
628 return condition(1000, 1e-9);
629 }
630
631 /** compute one of several matrix metrics based on the diagonal of the LU factorization
632 * type = 0: max/min ratio
633 * type = 1: trace of U (sum of diagonal elements)
634 * type = 2: determinant (product of diagonal elements)
635 */
636 R getMatrixMetric(int type = 0);
637
638 /// returns the stability of the basis matrix.
639 R stability() const
640 {
641 return factor->stability();
642 }
643 ///
645 {
646 if(rhs.dim() == 0)
647 {
648 x.clear();
649 return;
650 }
651
652 if(!factorized)
654
655 factor->solveRight(x, rhs);
656 }
657 ///
659 {
660 if(rhs.size() == 0)
661 {
662 x.clear();
663 return;
664 }
665
666 if(!factorized)
668
669 factor->solveRight(x, rhs);
670 }
671 /// solves linear system with basis matrix.
672 /** Depending on the representation, for a SPxBasisBase B,
673 B.solve(x) computes
674 - \f$x \leftarrow B^{-1}rhs\f$ in the columnwise case and
675 - \f$x \leftarrow rhs^TB^{-1}\f$ in the rowwise case.
676
677 Both can be seen uniformly as solving a linear system with the basis
678 matrix \p B and a right handside vector \p x aligned the same way as
679 the \em vectors of \p B.
680 */
682 {
683 if(rhs.size() == 0)
684 {
685 x.clear();
686 return;
687 }
688
689 if(!factorized)
691
692 factor->solveRight4update(x, rhs);
693 }
694 /// solves two systems in one call.
697 {
698 if(!factorized)
700
701 factor->solve2right4update(x, y, rhsx, rhsy);
702 }
703 /// solves two systems in one call using only sparse data structures
706 {
707 if(!factorized)
709
710 factor->solve2right4update(x, y, rhsx, rhsy);
711 }
712 /// solves three systems in one call.
715 {
716 if(!factorized)
718
719 assert(rhsy.isSetup());
720 assert(rhsy2.isSetup());
721 factor->solve3right4update(x, y, y2, rhsx, rhsy, rhsy2);
722 }
723 /// solves three systems in one call using only sparse data structures
726 {
727 if(!factorized)
729
730 assert(rhsy.isSetup());
731 assert(rhsy2.isSetup());
732 factor->solve3right4update(x, y, y2, rhsx, rhsy, rhsy2);
733 }
734 /// Cosolves linear system with basis matrix.
735 /** Depending on the representation, for a SPxBasisBase B,
736 B.coSolve(x) computes
737 - \f$x \leftarrow rhs^TB^{-1}\f$ in the columnwise case and
738 - \f$x \leftarrow B^{-1}rhs\f$ in the rowwise case.
739
740 Both can be seen uniformly as solving a linear system with the basis
741 matrix \p B and a right handside vector \p x aligned the same way as
742 the \em covectors of \p B.
743 */
745 {
746 if(rhs.dim() == 0)
747 {
748 x.clear();
749 return;
750 }
751
752 if(!factorized)
754
755 factor->solveLeft(x, rhs);
756 }
757 /// Sparse version of coSolve
759 {
760 if(rhs.size() == 0)
761 {
762 x.clear();
763 return;
764 }
765
766 if(!factorized)
768
769 factor->solveLeft(x, rhs);
770 }
771 /// solves two systems in one call.
774 {
775 if(!factorized)
777
778 factor->solveLeft(x, y, rhsx, rhsy);
779 }
780 /// Sparse version of solving two systems in one call.
783 {
784 if(!factorized)
786
787 factor->solveLeft(x, y, rhsx, rhsy);
788 }
789 /// solves three systems in one call. May be improved by using just one pass through the basis.
798 /// Sparse version of solving three systems in one call.
807 ///@}
808
809
810 //------------------------------------
811 /**@name Modification notification.
812 These methods must be called after the loaded LP has been modified.
813 */
814 ///@{
815 /// inform SPxBasisBase, that \p n new rows had been added.
816 void addedRows(int n);
817 /// inform SPxBasisBase that row \p i had been removed.
818 void removedRow(int i);
819 /// inform SPxBasisBase that rows in \p perm with negative entry were removed.
820 void removedRows(const int perm[]);
821 /// inform SPxBasisBase that \p n new columns had been added.
822 void addedCols(int n);
823 /// inform SPxBasisBase that column \p i had been removed.
824 void removedCol(int i);
825 /// inform SPxBasisBase that columns in \p perm with negative entry were removed.
826 void removedCols(const int perm[]);
827 /// inform SPxBasisBase that a row had been changed.
828 void changedRow(int);
829 /// inform SPxBasisBase that a column had been changed.
830 void changedCol(int);
831 /// inform SPxBasisBase that a matrix entry had been changed.
832 void changedElement(int, int);
833 ///@}
834
835
836 //--------------------------------
837 /**@name Miscellaneous */
838 ///@{
839 /// performs basis update.
840 /** Changes the \p i 'th vector of the basis with the vector associated to
841 \p id. This includes:
842 - updating the factorization, or recomputing it from scratch by
843 calling \ref soplex::SPxSolverBase<R>::factorize() "factorize()",
844 - resetting \ref soplex::SPxSolverBase<R>::lastEntered() "lastEntered()",
845 - resetting \ref soplex::SPxSolverBase<R>::lastIndex() "lastIndex()",
846 - resetting \ref soplex::SPxSolverBase<R>::lastLeft() "lastLeft()",
847 - resetting \ref soplex::SPxSolverBase<R>::lastUpdate() "lastUpdate()",
848 - resetting \ref soplex::SPxSolverBase<R>::iterations() "iterations()".
849
850 The basis descriptor is \em not \em modified, since #factor()
851 cannot know about how to set up the status of the involved variables
852 correctly.
853
854 A vector \p enterVec may be passed for a fast ETA update of the LU
855 factorization associated to the basis. It must be initialized with
856 the solution vector \f$x\f$ of the right linear system \f$Bx = b\f$
857 with the entering vector as right-hand side vector \f$b\f$, where \f$B\f$
858 denotes the basis matrix. This can be computed using method #solve().
859 When using FAST updates, a vector \p eta may be passed for
860 improved performance. It must be initialized by a call to
861 factor->solveRightUpdate() as described in SLinSolver. The
862 implementation hidden behind FAST updates depends on the
863 SLinSolver implementation class.
864 */
865 virtual void change(int i, SPxId& id,
866 const SVectorBase<R>* enterVec, const SSVectorBase<R>* eta = 0);
867
868 /** Load basis from \p in in MPS format. If \p rowNames and \p colNames
869 * are \c NULL, default names are used for the constraints and variables.
870 */
871 virtual bool readBasis(std::istream& in,
872 const NameSet* rowNames, const NameSet* colNames);
873
874 /** Write basis to \p os in MPS format. If \p rowNames and \p colNames are
875 * \c NULL, default names are used for the constraints and variables.
876 */
877 virtual void writeBasis(std::ostream& os,
878 const NameSet* rownames, const NameSet* colnames, const bool cpxFormat = false) const;
879
880 virtual void printMatrix() const;
881
882 /** Prints current basis matrix to a file using the MatrixMarket format:
883 * row col value
884 * The filename is basis/basis[number].mtx where number is a parameter.
885 */
886 void printMatrixMTX(int number);
887
888 /// checks if a Descriptor is valid for the current LP w.r.t. its bounds
889 virtual bool isDescValid(const Desc& ds);
890
891 /// sets up basis.
892 /** Loads a Descriptor to the basis and sets up the basis matrix and
893 all vectors accordingly. The Descriptor must have the same number of
894 rows and columns as the currently loaded LP.
895 */
896 virtual void loadDesc(const Desc&);
897
898 /// sets up linear solver to use.
899 /** If destroy is true, solver will be freed inside this object, e.g. in the destructor.
900 */
901 virtual void loadBasisSolver(SLinSolver<R>* solver, const bool destroy = false);
902
903 /// loads the LP \p lp to the basis.
904 /** This involves resetting all counters to 0 and setting up a regular
905 default basis consisting of slacks, artificial variables or bounds.
906 */
907 virtual void load(SPxSolverBase<R>* lp, bool initSlackBasis = true);
908
909 /// unloads the LP from the basis.
910 virtual void unLoad()
911 {
912 theLP = 0;
914 }
915
916 /// invalidates actual basis.
917 /** This method makes the basis matrix and vectors invalid. The basis will
918 be reinitialized if needed.
919 */
921
922 /// Restores initial basis.
923 /** This method changes the basis to that present just after loading the LP
924 (see addedRows() and addedCols()). This may be necessary if a row or a
925 column is changed, since then the current basis may become singular.
926 */
928
929 /// output basis entries.
930 void dump();
931
932 /// consistency check.
933 bool isConsistent() const;
934
935 /// time spent in updates
937 {
938 return theTime->time();
939 }
940 /// number of updates performed
942 {
943 return totalUpdateCount;
944 }
945
946 /// returns statistical information in form of a string.
947 std::string statistics() const
948 {
949 std::stringstream s;
950 s << factor->statistics()
951#ifdef MEASUREUPDATETIME
952 << "Updates : " << std::setw(10) << getTotalUpdateCount() << std::endl
953 << " Time spent : " << std::setw(10) << getTotalUpdateTime() << std::endl
954#endif
955 ;
956
957 return s.str();
958 }
959
961 {
963 }
964 ///@}
965
966 //--------------------------------------
967 /**@name Constructors / Destructors */
968 ///@{
969 /// default constructor.
971 /// copy constructor
973 /// assignment operator
975 /// destructor.
976 virtual ~SPxBasisBase<R>();
977 ///@}
978
979
980protected:
981
982 //--------------------------------------
983 /**@name Protected helpers */
984 ///@{
985 /// loads \ref soplex::SPxBasisBase<R>::matrix "matrix" according to the SPxId%s stored in \ref soplex::SPxBasisBase<R>::theBaseId "theBaseId".
986 /** This method must be called whenever there is a chance, that the vector
987 pointers may have changed due to manipulations of the LP.
988 */
990
991 /// resizes internal arrays.
992 /** When a new LP is loaded, the basis matrix and vectors become invalid
993 and possibly also of the wrong dimension. Hence, after loading an
994 LP, #reDim() is called to reset all arrays etc. accoriding to the
995 dimensions of the loaded LP.
996 */
997 void reDim();
998
999 /// factorizes the basis matrix.
1000 virtual void factorize();
1001
1002 /// sets descriptor representation according to loaded LP.
1003 void setRep();
1004 ///@}
1005
1006};
1007
1008
1009//
1010// Auxiliary functions.
1011//
1012
1013/// Pretty-printing of basis status.
1014template <class R>
1015std::ostream& operator<<(std::ostream& os,
1016 const typename SPxBasisBase<R>::SPxStatus& status);
1017
1018
1019/* For backwards compatibility */
1021
1022} // namespace soplex
1023
1024// General templated definitions
1025#include "spxbasis.hpp"
1026#include "spxdesc.hpp"
1027
1028/* reset the SOPLEX_DEBUG flag to its original value */
1029#undef SOPLEX_DEBUG
1030#ifdef SOPLEX_DEBUG_SPXBASIS
1031#define SOPLEX_DEBUG
1032#undef SOPLEX_DEBUG_SPXBASIS
1033#endif
1034
1035#endif // _SPXBASIS_H_
Safe arrays of data objects.
Definition dataarray.h:75
const T * get_const_ptr() const
get a const C pointer to the data.
Definition dataarray.h:128
void clear()
remove all elements.
Definition dataarray.h:221
int size() const
return nr. of elements.
Definition dataarray.h:227
Set of strings.
Definition nameset.h:71
Basis descriptor.
Definition spxbasis.h:116
Status & rowStatus(int i)
Definition spxbasis.h:251
DataArray< Status > * stat
basis' status.
Definition spxbasis.h:221
friend std::ostream & operator<<(std::ostream &os, const Status &stat)
bool isConsistent() const
consistency check.
int coDim() const
returns codimension.
Definition spxbasis.h:246
Desc(const SPxSolverBase< R > &base)
const Status * coStatus(void) const
returns the array of covariable Statuses.
Definition spxbasis.h:306
const Status * rowStatus(void) const
returns the array of row Statuses.
Definition spxbasis.h:261
void reSize(int rowDim, int colDim)
resets dimensions.
@ P_FIXED
primal variable is fixed to both bounds
Definition spxbasis.h:201
@ D_UNDEFINED
primal or dual variable is undefined
Definition spxbasis.h:206
@ D_ON_UPPER
dual variable is set to its upper bound
Definition spxbasis.h:203
@ P_ON_UPPER
primal variable is set to its upper bound
Definition spxbasis.h:199
@ D_ON_LOWER
dual variable is set to its lower bound
Definition spxbasis.h:204
@ P_FREE
primal variable is left free, but unset
Definition spxbasis.h:200
@ D_FREE
dual variable is left free, but unset
Definition spxbasis.h:202
@ P_ON_LOWER
primal variable is set to its lower bound
Definition spxbasis.h:198
@ D_ON_BOTH
dual variable has two bounds
Definition spxbasis.h:205
Status status(int i) const
returns status of variable i.
Definition spxbasis.h:286
Status colStatus(int i) const
returns status of column i.
Definition spxbasis.h:271
const Status * status(void) const
returns the array of variable Statuses.
Definition spxbasis.h:291
DataArray< Status > rowstat
status of rows.
Definition spxbasis.h:219
Status rowStatus(int i) const
returns status of row i.
Definition spxbasis.h:256
Status & colStatus(int i)
Definition spxbasis.h:266
Status & status(int i)
Definition spxbasis.h:281
DataArray< Status > colstat
status of columns.
Definition spxbasis.h:220
DataArray< Status > * costat
cobasis' status.
Definition spxbasis.h:222
int dim() const
returns dimension.
Definition spxbasis.h:241
Desc(const Desc &old)
copy constructor
Desc & operator=(const Desc &rhs)
assignment operator
Status & coStatus(int i)
Definition spxbasis.h:296
int nRows() const
returns number of rows.
Definition spxbasis.h:236
const Status * colStatus(void) const
returns the array of column Statuses.
Definition spxbasis.h:276
Status coStatus(int i) const
returns status of covariable i.
Definition spxbasis.h:301
Simplex basis.
Definition spxbasis.h:94
void changedRow(int)
inform SPxBasisBase that a row had been changed.
void setOutstream(SPxOut &newOutstream)
Definition spxbasis.h:960
int lastMem
memory needed after last fresh factorization
Definition spxbasis.h:406
R condition(int maxiters=10, R tolerance=1e-6)
int nzCount
number of nonzeros in basis matrix
Definition spxbasis.h:405
void coSolve(SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
solves three systems in one call. May be improved by using just one pass through the basis.
Definition spxbasis.h:790
const SVectorBase< R > & baseVec(int i) const
returns the i'th basic vector.
Definition spxbasis.h:527
SPxSolverBase< R > * theLP
the LP
Definition spxbasis.h:355
void removedRows(const int perm[])
inform SPxBasisBase that rows in perm with negative entry were removed.
virtual bool readBasis(std::istream &in, const NameSet *rowNames, const NameSet *colNames)
SPxBasisBase< R > & operator=(const SPxBasisBase< R > &rhs)
assignment operator
int totalUpdateCount
number of updates
Definition spxbasis.h:404
DataArray< SPxId > theBaseId
SPxIds of basic vectors.
Definition spxbasis.h:357
const Desc & desc() const
Definition spxbasis.h:476
int lastDegenCheck() const
returns the number of iterations since the last degeneracy check
Definition spxbasis.h:570
void printMatrixMTX(int number)
int iterDegenCheck
number of calls to change() since last degeneracy check
Definition spxbasis.h:402
SPxStatus thestatus
current status of the basis.
Definition spxbasis.h:424
void solve(SSVectorBase< R > &x, const SVectorBase< R > &rhs)
Definition spxbasis.h:658
Desc::Status dualStatus(const SPxId &id) const
dual Status for the variable with ID id of the loaded LP.
Definition spxbasis.h:503
int lastNzCount
number of nonzeros in basis matrix after last fresh factorization
Definition spxbasis.h:408
void solve4update(SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
solves two systems in one call using only sparse data structures
Definition spxbasis.h:704
void solve(VectorBase< R > &x, const VectorBase< R > &rhs)
Definition spxbasis.h:644
void coSolve(VectorBase< R > &x, const VectorBase< R > &rhs)
Cosolves linear system with basis matrix.
Definition spxbasis.h:744
void reDim()
resizes internal arrays.
int lastIndex() const
returns index in basis where last update was done.
Definition spxbasis.h:546
void removedCol(int i)
inform SPxBasisBase that column i had been removed.
Desc & desc()
returns current basis Descriptor.
Definition spxbasis.h:481
bool factorized
true iff factor = matrix .
Definition spxbasis.h:369
bool isConsistent() const
consistency check.
Desc::Status dualStatus(const SPxColId &id) const
dual Status for the column variable with ID id of the loaded LP.
int getTotalUpdateCount() const
number of updates performed
Definition spxbasis.h:941
void removedCols(const int perm[])
inform SPxBasisBase that columns in perm with negative entry were removed.
bool freeSlinSolver
true iff factor should be freed inside of this object
Definition spxbasis.h:426
void removedRow(int i)
inform SPxBasisBase that row i had been removed.
void coSolve(SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
Sparse version of solving two systems in one call.
Definition spxbasis.h:781
SPxOut * spxout
message handler
Definition spxbasis.h:427
VectorBase< R > & multBaseWith(VectorBase< R > &x) const
Basis-vector product.
int lastidx
lastIndex(): basis index where last update was done
Definition spxbasis.h:415
void addedRows(int n)
inform SPxBasisBase, that n new rows had been added.
R fillFactor
allowed increase in relative fill before refactorization
Definition spxbasis.h:391
virtual bool isDescValid(const Desc &ds)
checks if a Descriptor is valid for the current LP w.r.t. its bounds
void setStatus(SPxStatus stat)
sets basis SPxStatus to stat.
Definition spxbasis.h:443
void solve4update(SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
solves three systems in one call using only sparse data structures
Definition spxbasis.h:724
R lastFill
fill ratio that occured during last factorization
Definition spxbasis.h:407
R memFactor
allowed total increase in memory consumption before refactorization
Definition spxbasis.h:394
int getMaxUpdates() const
returns maximum number of updates before a refactorization is performed
Definition spxbasis.h:470
virtual void writeBasis(std::ostream &os, const NameSet *rownames, const NameSet *colnames, const bool cpxFormat=false) const
Timer * theTime
time spent in updates
Definition spxbasis.h:410
virtual void load(SPxSolverBase< R > *lp, bool initSlackBasis=true)
loads the LP lp to the basis.
DataArray< const SVectorBase< R > * > matrix
pointers to the vectors of the basis matrix.
Definition spxbasis.h:359
Desc thedesc
the basis' Descriptor
Definition spxbasis.h:425
virtual void factorize()
factorizes the basis matrix.
SLinSolver< R > * factor
Definition spxbasis.h:367
virtual void loadDesc(const Desc &)
sets up basis.
virtual void loadBasisSolver(SLinSolver< R > *solver, const bool destroy=false)
sets up linear solver to use.
void coSolve(SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
Sparse version of solving three systems in one call.
Definition spxbasis.h:799
void restoreInitialBasis()
Restores initial basis.
int iterCount
number of calls to change() since last manipulation
Definition spxbasis.h:400
SPxId lastEntered() const
returns SPxId of last VectorBase<R> included to the basis.
Definition spxbasis.h:534
void invalidate()
invalidates actual basis.
Timer::TYPE timerType
type of timer (user or wallclock)
Definition spxbasis.h:411
int iteration() const
returns number of basis changes since last load().
Definition spxbasis.h:558
Desc::Status dualStatus(const SPxRowId &id) const
dual Status for the row variable with ID id of the loaded LP.
void multBaseWith(SSVectorBase< R > &x, SSVectorBase< R > &result) const
Basis-vector product.
bool matrixIsSetup
true iff the pointers in matrix are set up correctly.
Definition spxbasis.h:361
int maxUpdates
number of updates before refactorization.
Definition spxbasis.h:378
void coSolve(SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
solves two systems in one call.
Definition spxbasis.h:772
SPxId lastLeft() const
returns SPxId of last vector that left the basis.
Definition spxbasis.h:540
SPxId lastin
lastEntered(): variable entered the base last
Definition spxbasis.h:413
void coSolve(SSVectorBase< R > &x, const SVectorBase< R > &rhs)
Sparse version of coSolve.
Definition spxbasis.h:758
int prevIteration() const
returns the number of iterations prior to the last break in execution
Definition spxbasis.h:564
SPxId baseId(int i) const
returns the Id of the i'th basis vector.
Definition spxbasis.h:521
void changedElement(int, int)
inform SPxBasisBase that a matrix entry had been changed.
SPxStatus status() const
returns current SPxStatus.
Definition spxbasis.h:437
R getMatrixMetric(int type=0)
int updateCount
number of calls to change() since last factorize()
Definition spxbasis.h:403
virtual void unLoad()
unloads the LP from the basis.
Definition spxbasis.h:910
R nonzeroFactor
allowed increase of nonzeros before refactorization.
Definition spxbasis.h:385
int lastUpdate() const
returns number of basis changes since last refactorization.
Definition spxbasis.h:552
SPxStatus
basis status.
Definition spxbasis.h:102
@ OPTIMAL
Basis is optimal, i.e. dual and primal feasible.
Definition spxbasis.h:108
@ INFEASIBLE
LP has been proven to be primal infeasible.
Definition spxbasis.h:110
@ NO_PROBLEM
No Problem has been loaded to the basis.
Definition spxbasis.h:103
@ UNBOUNDED
LP has been proven to be primal unbounded.
Definition spxbasis.h:109
@ DUAL
Basis is dual feasible.
Definition spxbasis.h:106
@ PRIMAL
Basis is primal feasible.
Definition spxbasis.h:107
@ SINGULAR
Basis is singular.
Definition spxbasis.h:104
@ REGULAR
Basis is not known to be dual nor primal feasible.
Definition spxbasis.h:105
void solve4update(SSVectorBase< R > &x, const SVectorBase< R > &rhs)
solves linear system with basis matrix.
Definition spxbasis.h:681
void dump()
output basis entries.
SPxId lastout
lastLeft(): variable left the base last
Definition spxbasis.h:414
void loadMatrixVecs()
loads matrix according to the SPxIds stored in theBaseId.
std::string statistics() const
returns statistical information in form of a string.
Definition spxbasis.h:947
R stability() const
returns the stability of the basis matrix.
Definition spxbasis.h:639
Real getTotalUpdateTime() const
time spent in updates
Definition spxbasis.h:936
void solve4update(SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
solves two systems in one call.
Definition spxbasis.h:695
virtual void printMatrix() const
VectorBase< R > & multWithBase(VectorBase< R > &x) const
Vector-basis product.
void addedCols(int n)
inform SPxBasisBase that n new columns had been added.
int lastIterCount
number of calls to change() before halting the simplex
Definition spxbasis.h:401
void setRep()
sets descriptor representation according to loaded LP.
void setMaxUpdates(int maxUp)
change maximum number of iterations until a refactorization is performed
Definition spxbasis.h:463
void multWithBase(SSVectorBase< R > &x, SSVectorBase< R > &result) const
VectorBase<R>-basis product.
virtual void change(int i, SPxId &id, const SVectorBase< R > *enterVec, const SSVectorBase< R > *eta=0)
performs basis update.
Desc::Status dualColStatus(int i) const
dual Status for the i'th column variable of the loaded LP.
Desc::Status dualRowStatus(int i) const
dual Status for the i'th row variable of the loaded LP.
R minStab
minimum stability
Definition spxbasis.h:416
void solve4update(SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
solves three systems in one call.
Definition spxbasis.h:713
SPxSolverBase< R > * solver() const
returns loaded solver.
Definition spxbasis.h:576
void changedCol(int)
inform SPxBasisBase that a column had been changed.
SPxId & baseId(int i)
Definition spxbasis.h:516
Ids for LP columns.
Definition spxid.h:46
Generic Ids for LP rows or columns.
Definition spxid.h:95
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition spxout.h:73
Ids for LP rows.
Definition spxid.h:65
Wrapper for the system time query methods.
Definition timer.h:86
TYPE
types of timers
Definition timer.h:109
virtual Real time() const =0
Save arrays of data objects.
Set of strings.
Everything should be within this namespace.
Sparse Linear Solver virtual base class.
Debugging, floating point type and parameter definitions.
#define MSG_DEBUG(x)
Definition spxdefines.h:180
Saving LPs in a form suitable for SoPlex.
Wrapper for different output streams and verbosity levels.
Semi sparse vector.
Sparse vectors.
TimerFactory class.