Scippy

SoPlex

Sequential object-oriented simPlex

spxbasis.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-2016 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 #include <assert.h>
17 #include <cstdio>
18 #include <iostream>
19 #include <iomanip>
20 #include <sstream>
21 
22 #include "spxdefines.h"
23 #include "spxbasis.h"
24 #include "didxset.h"
25 #include "dvector.h"
26 #include "spxsolver.h"
27 #include "mpsinput.h"
28 #include "spxout.h"
29 #include "exceptions.h"
30 
31 namespace soplex
32 {
35 {
36  return dualColStatus(static_cast<SPxLP*>(theLP)->number(id));
37 }
38 
41 {
42  return dualRowStatus((static_cast<SPxLP*>(theLP))->number(id));
43 }
44 
47 {
48  assert(theLP != 0);
49 
50  if (theLP->rhs(i) < infinity)
51  {
52  if (theLP->lhs(i) > -infinity)
53  {
54  if (theLP->lhs(i) == theLP->rhs(i))
55  return Desc::D_FREE;
56  else
57  return Desc::D_ON_BOTH;
58  }
59  else
60  return Desc::D_ON_LOWER;
61  }
62  else if (theLP->lhs(i) > -infinity)
63  return Desc::D_ON_UPPER;
64  else
65  return Desc::D_UNDEFINED;
66 }
67 
70 {
71  assert(theLP != 0);
72 
73  if (theLP->SPxLP::upper(i) < infinity)
74  {
75  if (theLP->SPxLP::lower(i) > -infinity)
76  {
77  if (theLP->SPxLP::lower(i) == theLP->SPxLP::upper(i))
78  return Desc::D_FREE;
79  else
80  return Desc::D_ON_BOTH;
81  }
82  else
83  return Desc::D_ON_LOWER;
84  }
85  else if (theLP->SPxLP::lower(i) > -infinity)
86  return Desc::D_ON_UPPER;
87  else
88  return Desc::D_UNDEFINED;
89 }
90 
92 {
93  assert(theLP != 0);
94  assert(theLP->dim() == matrix.size());
95 
96  MSG_INFO3( (*spxout), (*spxout) << "IBASIS01 loadMatrixVecs() invalidates factorization" << std::endl; )
97 
98  int i;
99  nzCount = 0;
100  for (i = theLP->dim() - 1; i >= 0; --i)
101  {
102  matrix[i] = &theLP->vector(baseId(i));
103  nzCount += matrix[i]->size();
104  }
105  matrixIsSetup = true;
106  factorized = false;
107  if (factor != 0)
108  factor->clear();
109 }
110 
112 {
113 
114  assert(status() > NO_PROBLEM);
115  assert(theLP != 0);
116 
117  int basisdim;
118 
119  if ( ds.nRows() != theLP->nRows() || ds.nCols() != theLP->nCols() )
120  {
121  MSG_DEBUG( std::cout << "IBASIS20 Dimension mismatch\n" );
122  return false;
123  }
124 
125  basisdim = 0;
126  for ( int row = ds.nRows()-1; row >= 0; --row )
127  {
128  if ( ds.rowstat[row] >= 0 )
129  {
130  if ( ds.rowstat[row] != dualRowStatus(row) )
131  {
132  MSG_DEBUG( std::cout << "IBASIS21 Basic row " << row << " with incorrect dual status " << dualRowStatus(row) << "\n");
133  return false;
134  }
135  }
136  else
137  {
138  basisdim++;
139  if ( (ds.rowstat[row] == Desc::P_FIXED && theLP->SPxLP::lhs(row) != theLP->SPxLP::rhs(row))
140  || (ds.rowstat[row] == Desc::P_ON_UPPER && theLP->SPxLP::rhs(row) >= infinity)
141  || (ds.rowstat[row] == Desc::P_ON_LOWER && theLP->SPxLP::lhs(row) <= -infinity) )
142  {
143  MSG_DEBUG( std::cout << "IBASIS22 Nonbasic row with incorrect status: lhs=" << theLP->SPxLP::lhs(row) << ", rhs=" << theLP->SPxLP::rhs(row) << ", stat=" << ds.rowstat[row] << "\n");
144  return false;
145  }
146  }
147  }
148 
149  for ( int col = ds.nCols()-1; col >= 0; --col )
150  {
151  if ( ds.colstat[col] >= 0 )
152  {
153  if ( ds.colstat[col] != dualColStatus(col) )
154  {
155  MSG_DEBUG( std::cout << "IBASIS23 Basic column " << col << " with incorrect dual status " << ds.colstat[col] << " != " << dualColStatus(col) << "\n");
156  return false;
157  }
158  }
159  else
160  {
161  basisdim++;
162  if ( (ds.colstat[col] == Desc::P_FIXED && theLP->SPxLP::lower(col) != theLP->SPxLP::upper(col))
163  || (ds.colstat[col] == Desc::P_ON_UPPER && theLP->SPxLP::upper(col) >= infinity)
164  || (ds.colstat[col] == Desc::P_ON_LOWER && theLP->SPxLP::lower(col) <= -infinity) )
165  {
166  MSG_DEBUG( std::cout << "IBASIS24 Nonbasic column with incorrect status: lower=" << theLP->SPxLP::lower(col) << ", upper=" << theLP->SPxLP::upper(col) << ", stat=" << ds.colstat[col] << "\n");
167  return false;
168  }
169  }
170  }
171 
172  if ( basisdim != theLP->nCols() )
173  {
174  MSG_DEBUG( std::cout << "IBASIS25 Incorrect basis dimension " << basisdim << " != " << theLP->nCols() << "\n" );
175  return false;
176  }
177 
178  // basis descriptor valid
179  return true;
180 }
181 
182 /*
183  Loading a #Desc# into the basis can be done more efficiently, by
184  explicitely programming both cases, for the rowwise and for the columnwise
185  representation. This implementation hides this distingtion in the use of
186  methods #isBasic()# and #vector()#.
187  */
188 void SPxBasis::loadDesc(const Desc& ds)
189 {
190  assert(status() > NO_PROBLEM);
191  assert(theLP != 0);
192  assert(ds.nRows() == theLP->nRows());
193  assert(ds.nCols() == theLP->nCols());
194 
195  SPxId none;
196  int i;
197  int j;
198 
199  MSG_INFO3( (*spxout), (*spxout) << "IBASIS02 loading of Basis invalidates factorization" << std::endl; )
200 
201  lastin = none;
202  lastout = none;
203  lastidx = -1;
204  iterCount = 0;
205  updateCount = 0;
206 
207  if (&ds != &thedesc)
208  {
209  thedesc = ds;
210  setRep();
211  }
212 
213  assert(theLP->dim() == matrix.size());
214 
215  nzCount = 0;
216  for (j = i = 0; i < theLP->nRows(); ++i)
217  {
218  /* for columns and rows with D_... status, the correct D_... status depends on bounds and sides; if a basis
219  * descriptor is loaded after changing bounds or sides, e.g. in the refine() method, we have to correct them
220  */
221  if (thedesc.rowStatus(i) >= 0)
223  else if (thedesc.rowStatus(i) == SPxBasis::Desc::P_FIXED && theLP->SPxLP::lhs(i) != theLP->SPxLP::rhs(i))
224  {
225  if (theLP->SPxLP::lhs(i) > -infinity && theLP->SPxLP::maxRowObj(i) < 0.0)
227  else if (theLP->SPxLP::rhs(i) < infinity)
229  else
231  }
232 
233  if (theLP->isBasic(thedesc.rowStatus(i)))
234  {
235  assert(theLP->dim() == matrix.size());
236  assert(j < matrix.size());
237 
238  SPxRowId id = theLP->SPxLP::rId(i);
239  theBaseId[j] = id;
240  matrix[j] = &theLP->vector(id);
241  nzCount += matrix[j++]->size();
242  }
243  }
244 
245  for (i = 0; i < theLP->nCols(); ++i)
246  {
247  /* for columns and rows with D_... status, the correct D_... status depends on bounds and sides; if a basis
248  * descriptor is loaded after changing bounds or sides, e.g. in the refine() method, we have to correct them
249  */
250  if (thedesc.colStatus(i) >= 0)
252  else if (thedesc.colStatus(i) == SPxBasis::Desc::P_FIXED && theLP->SPxLP::lower(i) != theLP->SPxLP::upper(i))
253  {
254  if (theLP->SPxLP::lower(i) <= -infinity && theLP->SPxLP::upper(i) >= infinity)
256  else if (theLP->SPxLP::upper(i) >= infinity || (theLP->SPxLP::lower(i) > -infinity && theLP->SPxLP::maxObj(i) < 0.0))
258  else
260  }
261 
262  if (theLP->isBasic(thedesc.colStatus(i)))
263  {
264  assert(theLP->dim() == matrix.size());
265  assert(j < matrix.size());
266 
267  SPxColId id = theLP->SPxLP::cId(i);
268  theBaseId[j] = id;
269  matrix[j] = &theLP->vector(id);
270  nzCount += matrix[j++]->size();
271  }
272  }
273 
274  /* if dimensions are inconsistent, restore slack basis */
275  if( j != matrix.size() )
277 
278  assert(isDescValid(thedesc));
279 
280  matrixIsSetup = true;
281  factorized = false;
282  if (factor != 0)
283  factor->clear();
284 }
285 
287 {
288  assert(theLP != 0);
289 
290  reDim();
291  minStab = 0.0;
292 
293  if (theLP->rep() == SPxSolver::ROW)
294  {
297  }
298  else
299  {
302  }
303 }
304 
306 {
307  assert(lp != 0);
308  theLP = lp;
309 
311 
312  setRep();
313 
315 
316  loadDesc(thedesc);
317 }
318 
319 void SPxBasis::loadSolver(SLinSolver* p_solver, const bool destroy)
320 {
321 
322  assert(!freeSlinSolver || factor != 0);
323 
324  setOutstream(*p_solver->spxout);
325 
326  MSG_INFO3( (*spxout), (*spxout) << "IBASIS03 loading of Solver invalidates factorization"
327  << std::endl; )
328 
329 
330  if(freeSlinSolver)
331  {
332  delete factor;
333  factor = 0;
334  }
335 
336  factor = p_solver;
337  factorized = false;
338  factor->clear();
339  freeSlinSolver = destroy;
340 }
341 
342 
343 
344 
345 /**
346  * The specification is taken from the
347  *
348  * ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 543.
349  *
350  * This routine should read valid BAS format files.
351  *
352  * @return true if the file was read correctly.
353  *
354  * Here is a very brief outline of the format:
355  *
356  * The format is in a form similar to an MPS file. The basic assumption is that all (column)
357  * variables are nonbasic at their lower bound and all row (variables) are basic; only the
358  * differences to this rule are given. Each data line contains an indicator, a variable name and
359  * possibly a row/constraint name. The following meaning applies with respect to the indicators:
360  *
361  * - XU: the variable is basic, the row is nonbasic at its upper bound
362  * - XL: the variable is basic, the row is nonbasic at its lower bound
363  * - UL: the variable is nonbasic and at its upper bound
364  * - LL: the variable is nonbasic and at its lower bound
365  *
366  * The CPLEX format contains an additional indicator 'BS', but this is unsupported here.
367  *
368  * Nonbasic variables without lower bound have the following default status for SoPlex:
369  * - at their upper bound if finite,
370  * - at zero if free.
371  */
373  std::istream& is,
374  const NameSet* rowNames,
375  const NameSet* colNames)
376 {
377  assert(theLP != 0);
378 
379  /* prepare names */
380  const NameSet* rNames = rowNames;
381  const NameSet* cNames = colNames;
382 
383  NameSet* p_colNames = 0;
384  NameSet* p_rowNames = 0;
385 
386  if ( colNames == 0 )
387  {
388  int nCols = theLP->nCols();
389  std::stringstream name;
390 
391  spx_alloc(p_colNames);
392  p_colNames = new (p_colNames) NameSet();
393  p_colNames->reMax(nCols);
394  for (int j = 0; j < nCols; ++j)
395  {
396  name << "x" << j;
397  DataKey key = theLP->colId(j);
398  p_colNames->add(key, name.str().c_str());
399  }
400  cNames = p_colNames;
401  }
402 
403  if ( rNames == 0 )
404  {
405  int nRows = theLP->nRows();
406  std::stringstream name;
407 
408  spx_alloc(p_rowNames);
409  p_rowNames = new (p_rowNames) NameSet();
410  p_rowNames->reMax(nRows);
411  for (int i = 0; i < nRows; ++i)
412  {
413  name << "C" << i;
414  DataKey key = theLP->rowId(i);
415  p_rowNames->add(key, name.str().c_str());
416  }
417  rNames = p_rowNames;
418  }
419 
420  /* load default basis if necessary */
421  if (status() == NO_PROBLEM)
422  load(theLP);
423 
424  /* initialize with standard settings */
425  Desc l_desc(thedesc);
426 
427  for (int i = 0; i < theLP->nRows(); i++)
428  l_desc.rowstat[i] = dualRowStatus(i);
429 
430  for (int i = 0; i < theLP->nCols(); i++)
431  {
432  if (theLP->SPxLP::lower(i) == theLP->SPxLP::upper(i))
433  l_desc.colstat[i] = Desc::P_FIXED;
434  else if (theLP->SPxLP::lower(i) <= -infinity && theLP->SPxLP::upper(i) >= infinity)
435  l_desc.colstat[i] = Desc::P_FREE;
436  else if (theLP->SPxLP::lower(i) <= -infinity)
437  l_desc.colstat[i] = Desc::P_ON_UPPER;
438  else
439  l_desc.colstat[i] = Desc::P_ON_LOWER;
440  }
441 
442  MPSInput mps(is);
443 
444  if (mps.readLine() && (mps.field0() != 0) && !strcmp(mps.field0(), "NAME"))
445  {
446  while (mps.readLine())
447  {
448  int c = -1;
449  int r = -1;
450 
451  if ((mps.field0() != 0) && !strcmp(mps.field0(), "ENDATA"))
452  {
454  break;
455  }
456  if ((mps.field1() == 0) || (mps.field2() == 0))
457  break;
458 
459  if ((c = cNames->number(mps.field2())) < 0)
460  break;
461 
462  if (*mps.field1() == 'X')
463  if (mps.field3() == 0 || (r = rNames->number(mps.field3())) < 0)
464  break;
465 
466  if (!strcmp(mps.field1(), "XU"))
467  {
468  l_desc.colstat[c] = dualColStatus(c);
469  if( theLP->LPRowSet::type(r) == LPRow::GREATER_EQUAL )
470  l_desc.rowstat[r] = Desc::P_ON_LOWER;
471  else if( theLP->LPRowSet::type(r) == LPRow::EQUAL )
472  l_desc.rowstat[r] = Desc::P_FIXED;
473  else
474  l_desc.rowstat[r] = Desc::P_ON_UPPER;
475  }
476  else if (!strcmp(mps.field1(), "XL"))
477  {
478  l_desc.colstat[c] = dualColStatus(c);
479  if( theLP->LPRowSet::type(r) == LPRow::LESS_EQUAL )
480  l_desc.rowstat[r] = Desc::P_ON_UPPER;
481  else if( theLP->LPRowSet::type(r) == LPRow::EQUAL )
482  l_desc.rowstat[r] = Desc::P_FIXED;
483  else
484  l_desc.rowstat[r] = Desc::P_ON_LOWER;
485  }
486  else if (!strcmp(mps.field1(), "UL"))
487  {
488  l_desc.colstat[c] = Desc::P_ON_UPPER;
489  }
490  else if (!strcmp(mps.field1(), "LL"))
491  {
492  l_desc.colstat[c] = Desc::P_ON_LOWER;
493  }
494  else
495  {
496  mps.syntaxError();
497  break;
498  }
499  }
500  }
501  if (!mps.hasError())
502  {
503  if (mps.section() == MPSInput::ENDATA)
504  {
505  // force basis to be different from NO_PROBLEM
506  // otherwise the basis will be overwritten at later stages.
508  loadDesc(l_desc);
509  }
510  else
511  mps.syntaxError();
512  }
513 
514  if ( rowNames == 0 )
515  {
516  p_rowNames->~NameSet();
517  spx_free(p_rowNames);
518  }
519  if ( colNames == 0 )
520  {
521  p_colNames->~NameSet();
522  spx_free(p_colNames);
523  }
524 
525 #ifndef NDEBUG
526  MSG_DEBUG( thedesc.dump() );
527 #endif
528 
529  return !mps.hasError();
530 }
531 
532 
533 /* Get row name - copied from spxmpswrite.cpp
534  *
535  * @todo put this in a common file and unify accross different formats (mps, lp, basis).
536  */
537 static const char* getRowName(
538  const SPxLP* lp,
539  int idx,
540  const NameSet* rnames,
541  char* buf)
542 {
543  assert(buf != 0);
544  assert(idx >= 0);
545  assert(idx < lp->nRows());
546 
547  if (rnames != 0)
548  {
549  DataKey key = lp->rId(idx);
550 
551  if (rnames->has(key))
552  return (*rnames)[key];
553  }
554  std::sprintf(buf, "C%d", idx);
555 
556  return buf;
557 }
558 
559 /* Get column name - copied from spxmpswrite.cpp
560  *
561  * @todo put this in a common file and unify accross different formats (mps, lp, basis).
562  */
563 static const char* getColName(
564  const SPxLP* lp,
565  int idx,
566  const NameSet* cnames,
567  char* buf)
568 {
569  assert(buf != 0);
570  assert(idx >= 0);
571  assert(idx < lp->nCols());
572 
573  if (cnames != 0)
574  {
575  DataKey key = lp->cId(idx);
576 
577  if (cnames->has(key))
578  return (*cnames)[key];
579  }
580  std::sprintf(buf, "x%d", idx);
581 
582  return buf;
583 }
584 
585 /* writes a file in MPS basis format to \p os.
586  *
587  * See SPxBasis::readBasis() for a short description of the format.
588  */
590  std::ostream& os,
591  const NameSet* rowNames,
592  const NameSet* colNames,
593  const bool cpxFormat
594  ) const
595 {
596  assert(theLP != 0);
597 
598  os.setf(std::ios::left);
599  os << "NAME soplex.bas\n";
600 
601  /* do not write basis if there is none */
602  if (status() == NO_PROBLEM)
603  {
604  os << "ENDATA" << std::endl;
605  return;
606  }
607 
608  /* start writing */
609  char buf[255];
610  int row = 0;
611  for (int col = 0; col < theLP->nCols(); col++)
612  {
613  if ( thedesc.colStatus(col) > 0 )
614  {
615  /* Find non basic row */
616  for (; row < theLP->nRows(); row++)
617  {
618  if ( thedesc.rowStatus(row) < 0 )
619  break;
620  }
621 
622  assert( row != theLP->nRows() );
623 
624  if( thedesc.rowStatus( row ) == Desc::P_ON_UPPER && (!cpxFormat || theLP->LPRowSet::type(row) == LPRow::RANGE) )
625  os << " XU ";
626  else
627  os << " XL ";
628 
629  os << std::setw(8) << getColName(theLP, col, colNames, buf);
630 
631  /* break in two parts since buf is reused */
632  os << " "
633  << getRowName(theLP, row, rowNames, buf)
634  << std::endl;
635 
636  row++;
637  }
638  else
639  {
640  if ( thedesc.colStatus( col ) == Desc::P_ON_UPPER )
641  {
642  os << " UL "
643  << getColName(theLP, col, colNames, buf)
644  << std::endl;
645  }
646  else
647  {
648  /* Default is all non-basic variables on lower bound (if finite) or at zero (if free).
649  * nothing to do in this case.
650  */
651  assert(theLP->lower(col) <= -infinity || thedesc.colStatus(col) == Desc::P_ON_LOWER || thedesc.colStatus(col) == Desc::P_FIXED);
652  assert(theLP->lower(col) > -infinity || theLP->upper(col) < infinity || thedesc.colStatus(col) == Desc::P_FREE);
653  }
654  }
655  }
656 
657 #ifndef NDEBUG
658  MSG_DEBUG( thedesc.dump() );
659 
660  // Check that we covered all nonbasic rows - the remaining should be basic.
661  for (; row < theLP->nRows(); row++)
662  {
663  if ( thedesc.rowStatus(row) < 0 )
664  break;
665  }
666  assert( row == theLP->nRows() );
667 
668 #endif // NDEBUG
669 
670  os << "ENDATA" << std::endl;
671 }
672 
674 {
675 
676  assert(matrixIsSetup);
677 
678  for( int i = 0; i < matrix.size(); i++ )
679  {
680  std::cout << "C" << i << "=" << *matrix[i] << std::endl;
681  }
682 }
683 
684 void SPxBasis::printMatrixMTX(int number)
685 {
686  int dim;
687  int nnz;
688  char filename[30];
689 
690  dim = matrix.size();
691  nnz = nzCount;
692  sprintf(filename, "basis/basis%d.mtx",number);
693  std::cout << "printing basis matrix to file " << filename << "\n";
694  FILE * basisfile;
695  basisfile = fopen (filename,"w");
696  // print marker necessary for reading the file in Matlab
697  fprintf(basisfile, "%%%%MatrixMarket matrix coordinate real general\n");
698  // print matrix information
699  fprintf(basisfile, "%d %d %d\n", dim, dim, nnz );
700  // print matrix data
701  for( int i = 0; i < matrix.size(); ++i )
702  {
703  for( int j = 0; j < baseVec(i).size(); ++j )
704  {
705  int idx = baseVec(i).index(j);
706  Real val = baseVec(i).value(j);
707  fprintf(basisfile, "%d %d %.13" REAL_FORMAT "\n",i+1,idx+1,val);
708  }
709  }
710  fclose (basisfile);
711 
712  return;
713 }
714 
716  int i,
717  SPxId& id,
718  const SVector* enterVec,
719  const SSVector* eta)
720 {
721 
722  assert(matrixIsSetup);
723  assert(!id.isValid() || (enterVec != 0));
724  assert(factor != 0);
725 
726  lastidx = i;
727  lastin = id;
728 
729  if (id.isValid() && i >= 0)
730  {
731  assert(enterVec != 0);
732 
733  nzCount = nzCount - matrix[i]->size() + enterVec->size();
734  matrix[i] = enterVec;
735  lastout = theBaseId[i];
736  theBaseId[i] = id;
737 
738  ++iterCount;
739  ++updateCount;
740 
741  // never factorize? Just do it !
742  if (!factorized)
743  factorize();
744  // relative fill too high ?
745  else if (Real(factor->memory()) > lastFill * Real(nzCount))
746  {
747  MSG_INFO3( (*spxout), (*spxout) << "IBASIS04 fill factor triggers refactorization"
748  << " memory= " << factor->memory()
749  << " nzCount= " << nzCount
750  << " lastFill= " << lastFill
751  << std::endl; )
752 
753  factorize();
754  }
755  // absolute fill too high ?
756  else if (nzCount > lastNzCount)
757  {
758  MSG_INFO3( (*spxout), (*spxout) << "IBASIS05 nonzero factor triggers refactorization"
759  << " nzCount= " << nzCount
760  << " lastNzCount= " << lastNzCount
761  << " nonzeroFactor= " << nonzeroFactor
762  << std::endl; )
763  factorize();
764  }
765  // too many updates ?
766  else if (updateCount >= maxUpdates)
767  {
768  MSG_INFO3( (*spxout), (*spxout) << "IBASIS06 update count triggers refactorization"
769  << " updateCount= " << updateCount
770  << " maxUpdates= " << maxUpdates
771  << std::endl; )
772  factorize();
773  }
774  else
775  {
776  try
777  {
778 #ifdef MEASUREUPDATETIME
779  theTime.start();
780 #endif
781  factor->change(i, *enterVec, eta);
783 #ifdef MEASUREUPDATETIME
784  theTime.stop();
785 #endif
786  }
787  catch( ... )
788  {
789  MSG_INFO3( (*spxout), (*spxout) << "IBASIS13 problems updating factorization; refactorizing basis"
790  << std::endl; )
791 
792 #ifdef MEASUREUPDATETIME
793  theTime.stop();
794 #endif
795 
796  // singularity was detected in update; we refactorize
797  factorize();
798 
799  // if factorize() detects singularity, an exception is thrown, hence at this point we have a regular basis
800  // and can try the update again
801  assert(status() >= SPxBasis::REGULAR);
802  try
803  {
804 #ifdef MEASUREUPDATETIME
805  theTime.start();
806 #endif
807  factor->change(i, *enterVec, eta);
809 #ifdef MEASUREUPDATETIME
810  theTime.stop();
811 #endif
812  }
813  // with a freshly factorized, regular basis, the update is unlikely to fail; if this happens nevertheless,
814  // we have to invalidate the basis to have the statuses correct
815  catch( const SPxException& F )
816  {
817  MSG_INFO3( (*spxout), (*spxout) << "IBASIS14 problems updating factorization; invalidating factorization"
818  << std::endl; )
819 
820 #ifdef MEASUREUPDATETIME
821  theTime.stop();
822 #endif
823 
824  factorized = false;
825  throw F;
826  }
827  }
828 
829  assert(minStab > 0.0);
830 
832  {
833  MSG_INFO3( (*spxout), (*spxout) << "IBASIS07 stability triggers refactorization"
834  << " stability= " << factor->stability()
835  << " minStab= " << minStab
836  << std::endl; )
837  factorize();
838  }
839  }
840  }
841  else
842  lastout = id;
843 }
844 
846 {
847 
848  assert(factor != 0);
849 
850  if (!matrixIsSetup)
851  loadDesc(thedesc);
852 
853  assert(matrixIsSetup);
854 
855  updateCount = 0;
856 
857  switch(factor->load(matrix.get_ptr(), matrix.size()))
858  {
859  case SLinSolver::OK :
860  if (status() == SINGULAR)
862 
863  factorized = true;
864  minStab = factor->stability();
865 
866  // This seems allways be about 1e-7
867  if (minStab > 1e-4)
868  minStab *= 0.001;
869  if (minStab > 1e-5)
870  minStab *= 0.01;
871  if (minStab > 1e-6)
872  minStab *= 0.1;
873  break;
874  case SLinSolver::SINGULAR :
876  factorized = false;
877  break;
878  default :
879  MSG_ERROR( std::cerr << "EBASIS08 error: unknown status of factorization.\n"; )
880  factorized = false;
881  throw SPxInternalCodeException("XBASIS01 This should never happen.");
882  }
883 
884  lastMem = factor->memory();
885  lastFill = fillFactor * Real(factor->memory()) / Real(nzCount > 0 ? nzCount : 1);
886  lastNzCount = int(nonzeroFactor * Real(nzCount > 0 ? nzCount : 1));
887 
888  if (status() == SINGULAR)
889  {
890  throw SPxStatusException("Cannot factorize singular matrix");
891  }
892 }
893 
895 {
896  assert(status() > SINGULAR);
897  assert(theLP->dim() == x.dim());
898 
899  int i;
900  DVector tmp(x);
901 
902  if (!matrixIsSetup)
903  (const_cast<SPxBasis*>(this))->loadDesc(thedesc);
904 
905  assert( matrixIsSetup );
906 
907  for (i = x.dim() - 1; i >= 0; --i)
908  x[i] = *(matrix[i]) * tmp;
909 
910  return x;
911 }
912 
913 void SPxBasis::multWithBase(SSVector& x, SSVector& result) const
914 {
915  assert(status() > SINGULAR);
916  assert(theLP->dim() == x.dim());
917  assert(x.dim() == result.dim());
918 
919  if (!matrixIsSetup)
920  (const_cast<SPxBasis*>(this))->loadDesc(thedesc);
921 
922  assert(matrixIsSetup);
923 
924  for( int i = 0; i < x.dim(); ++i )
925  result.setValue(i, (*matrix[i]) * x);
926 
927  return;
928 }
929 
930 
932 {
933  assert(status() > SINGULAR);
934  assert(theLP->dim() == x.dim());
935 
936  int i;
937  DVector tmp(x);
938 
939  if (!matrixIsSetup)
940  (const_cast<SPxBasis*>(this))->loadDesc(thedesc);
941 
942  assert( matrixIsSetup );
943 
944  x.clear();
945  for (i = x.dim() - 1; i >= 0; --i)
946  {
947  if (tmp[i] != 0.0)
948  x.multAdd(tmp[i], *(matrix[i]));
949  }
950 
951  return x;
952 }
953 
954 void SPxBasis::multBaseWith(SSVector& x, SSVector& result) const
955 {
956  assert(status() > SINGULAR);
957  assert(theLP->dim() == x.dim());
958  assert(x.dim() == result.dim());
959 
960  if (!matrixIsSetup)
961  (const_cast<SPxBasis*>(this))->loadDesc(thedesc);
962 
963  assert(matrixIsSetup);
964 
965  result.clear();
966  for( int i = 0; i < x.size(); ++i )
967  {
968  result.multAdd(x[i], (*matrix[i]));
969  }
970 
971  return;
972 }
973 
974 /* compute an estimated condition number for the current basis matrix
975  * by computing estimates of the norms of B and B^-1 using the power method.
976  * maxiters and tolerance control the accuracy of the estimate.
977  */
978 Real SPxBasis::condition(int maxiters, Real tolerance)
979 {
980  int dimension = matrix.size();
981  int i;
982  int c;
983  Real norm;
984  Real norminv;
985  Real norm1;
986  Real norm2;
987 
988  SSVector x(dimension);
989  SSVector y(dimension);
990 
991  // check whether a regular basis matrix is available
992  if( status() < REGULAR )
993  return 0;
994 
995  if (!matrixIsSetup)
996  (const_cast<SPxBasis*>(this))->loadDesc(thedesc);
997 
998  // initialize vectors
999  norm1 = 1.0 / (Real) dimension;
1000  for( i = 0; i < dimension; i++ )
1001  x.add(i, norm1);
1002  y = x;
1003 
1004  // compute norm of B
1005  for( c = 0; c < maxiters; ++c )
1006  {
1007  norm2 = norm1;
1008 
1009  // y = B*x
1010  multBaseWith(x, y);
1011  norm1 = y.length();
1012 
1013  // stop if converged
1014  if( spxAbs(norm1 - norm2) < tolerance * norm1 )
1015  break;
1016 
1017  // x = B^T*y and normalize
1018  multWithBase(y, x);
1019  x *= 1.0 / x.length();
1020  }
1021  norm = norm1;
1022 
1023  // reinitialize vectors
1024  norm1 = 1.0 / (Real) dimension;
1025  for( i = 0; i < dimension; i++ )
1026  x.setValue(i, norm1);
1027  y = x;
1028 
1029  // compute norm of B^-1
1030  for( c = 0; c < maxiters; ++c )
1031  {
1032  norm2 = norm1;
1033 
1034  // y = B^-1*x
1035  factor->solveRight(x, y);
1036  norm1 = x.length();
1037 
1038  // stop if converged
1039  if( spxAbs(norm1 - norm2) < tolerance * norm1 )
1040  break;
1041 
1042  // x = B^-T*y and normalize
1043  factor->solveLeft(y, x);
1044  y *= 1.0 / y.length();
1045  }
1046  norminv = norm1;
1047 
1048  return norm * norminv;
1049 }
1050 
1052 {
1053  assert(status() > NO_PROBLEM);
1054  assert(theLP != 0);
1055  assert(thedesc.nRows() == theLP->nRows());
1056  assert(thedesc.nCols() == theLP->nCols());
1057  assert(theLP->dim() == matrix.size());
1058 
1059  int i, basesize;
1060 
1061  // Dump regardless of the verbosity level if this method is called.
1062 
1063  std::cout << "DBASIS09 Basis entries:";
1064  basesize = 0;
1065  for (i = 0; i < theLP->nRows(); ++i)
1066  {
1067  if (theLP->isBasic(thedesc.rowStatus(i)))
1068  {
1069  if(basesize % 10 == 0)
1070  std::cout << std::endl << "DBASIS10 ";
1071  SPxRowId id = theLP->SPxLP::rId(i);
1072  std::cout << "\tR" << theLP->number(id);
1073  basesize++;
1074  }
1075  }
1076 
1077  for (i = 0; i < theLP->nCols(); ++i)
1078  {
1079  if (theLP->isBasic(thedesc.colStatus(i)))
1080  {
1081  if(basesize % 10 == 0)
1082  std::cout << std::endl << "DBASIS11 ";
1083  SPxColId id = theLP->SPxLP::cId(i);
1084  std::cout << "\tC" << theLP->number(id);
1085  basesize++;
1086  }
1087  }
1088  std::cout << std::endl;
1089 
1090  assert(basesize == matrix.size());
1091 }
1092 
1093 
1095 {
1096 #ifdef ENABLE_CONSISTENCY_CHECKS
1097  int primals = 0;
1098  int i;
1099 
1100  if (status() > NO_PROBLEM)
1101  {
1102  if (theLP == 0)
1103  return MSGinconsistent("SPxBasis");
1104 
1105  if (theBaseId.size() != theLP->dim() || matrix.size() != theLP->dim())
1106  return MSGinconsistent("SPxBasis");
1107 
1108  if (thedesc.nCols() != theLP->nCols() || thedesc.nRows() != theLP->nRows())
1109  return MSGinconsistent("SPxBasis");
1110 
1111  for (i = 0; i < thedesc.nRows(); ++i)
1112  {
1113  if (thedesc.rowStatus(i) >= 0)
1114  {
1115  if (thedesc.rowStatus(i) != dualRowStatus(i))
1116  return MSGinconsistent("SPxBasis");
1117  }
1118  else
1119  ++primals;
1120  }
1121 
1122  for (i = 0; i < thedesc.nCols(); ++i)
1123  {
1124  if (thedesc.colStatus(i) >= 0)
1125  {
1126  if (thedesc.colStatus(i) != dualColStatus(i))
1127  return MSGinconsistent("SPxBasis");
1128  }
1129  else
1130  ++primals;
1131  }
1132  if (primals != thedesc.nCols())
1133  return MSGinconsistent("SPxBasis");
1134  }
1135  return thedesc.isConsistent() && theBaseId.isConsistent()
1136  && matrix.isConsistent() && factor->isConsistent();
1137 #else
1138  return true;
1139 #endif // CONSISTENCY_CHECKS
1140 }
1141 
1143  : theLP (0)
1144  , matrixIsSetup (false)
1145  , factor (0)
1146  , factorized (false)
1147  , maxUpdates (180)
1148  , nonzeroFactor(10.0)
1149  , fillFactor(5.0)
1150  , iterCount (0)
1151  , updateCount(0)
1152  , totalUpdateCount(0)
1153  , nzCount (1)
1154  , lastMem(0)
1155  , lastFill(0)
1156  , lastNzCount(0)
1157  , theTime(0)
1158  , timerType(ttype)
1159  , lastidx(0)
1160  , minStab(0.0)
1161  , thestatus (NO_PROBLEM)
1162  , freeSlinSolver(false)
1163  , spxout(0)
1164 {
1165  // info: is not consistent at this moment, e.g. because theLP == 0
1166 
1168 }
1169 
1170 /**@warning Do not change the LP object.
1171  * Only pointer to that object is copied.
1172  * Hint: no problem, we use this function for copy
1173  * constructor of SPxSolver
1174  */
1176  : theLP(old.theLP)
1177  , theBaseId(old.theBaseId)
1178  , matrix(old.matrix)
1180  , factor(old.factor)
1181  , factorized(old.factorized)
1182  , maxUpdates(old.maxUpdates)
1184  , fillFactor(old.fillFactor)
1185  , iterCount(old.iterCount)
1186  , updateCount(old.updateCount)
1188  , nzCount(old.nzCount)
1189  , lastMem(old.lastMem)
1190  , lastFill(old.lastFill)
1191  , lastNzCount(old.lastNzCount)
1192  , theTime(old.theTime)
1193  , timerType(old.timerType)
1194  , lastin(old.lastin)
1195  , lastout(old.lastout)
1196  , lastidx(old.lastidx)
1197  , minStab(old.minStab)
1198  , thestatus(old.thestatus)
1199  , thedesc(old.thedesc)
1200  , spxout(old.spxout)
1201 {
1202 
1203  this->factor = old.factor->clone();
1204  freeSlinSolver = true;
1205 
1206  assert(SPxBasis::isConsistent());
1207 }
1208 
1210 {
1211 
1212  assert(!freeSlinSolver || factor != 0);
1213 
1214  if(freeSlinSolver)
1215  {
1216  delete factor;
1217  factor = 0;
1218  }
1219 
1220  spx_free(theTime);
1221 }
1222 
1223 
1224 /**@warning Note that we do not create a deep copy of the corresponding SPxSolver object.
1225  * Only the reference to that object is copied.
1226  */
1228 {
1229 
1230  assert(!freeSlinSolver || factor != 0);
1231 
1232  if (this != &rhs)
1233  {
1234  theLP = rhs.theLP;
1235  theBaseId = rhs.theBaseId;
1236  matrix = rhs.matrix;
1238 
1239  if(freeSlinSolver)
1240  {
1241  delete factor;
1242  factor = 0;
1243  }
1244  factor = rhs.factor->clone();
1245  freeSlinSolver = true;
1246 
1247  factorized = rhs.factorized;
1248  maxUpdates = rhs.maxUpdates;
1250  fillFactor = rhs.fillFactor;
1251  iterCount = rhs.iterCount;
1252  nzCount = rhs.nzCount;
1253  lastFill = rhs.lastFill;
1254  lastNzCount = rhs.lastNzCount;
1255  lastin = rhs.lastin;
1256  lastout = rhs.lastout;
1257  lastidx = rhs.lastidx;
1258  minStab = rhs.minStab;
1259  thestatus = rhs.thestatus;
1260  thedesc = rhs.thedesc;
1261 
1262  assert(SPxBasis::isConsistent());
1263  }
1264 
1265  return *this;
1266 }
1267 
1268 
1269 //
1270 // Auxiliary functions.
1271 //
1272 
1273 // Pretty-printing of basis status.
1274 std::ostream& operator<<( std::ostream& os,
1275  const SPxBasis::SPxStatus& status )
1276 {
1277  switch ( status )
1278  {
1279  case SPxBasis::NO_PROBLEM:
1280  os << "NO_PROBLEM";
1281  break;
1282  case SPxBasis::SINGULAR:
1283  os << "SINGULAR";
1284  break;
1285  case SPxBasis::REGULAR:
1286  os << "REGULAR";
1287  break;
1288  case SPxBasis::DUAL:
1289  os << "DUAL";
1290  break;
1291  case SPxBasis::PRIMAL:
1292  os << "PRIMAL";
1293  break;
1294  case SPxBasis::OPTIMAL:
1295  os << "OPTIMAL";
1296  break;
1297  case SPxBasis::UNBOUNDED:
1298  os << "UNBOUNDED";
1299  break;
1300  case SPxBasis::INFEASIBLE:
1301  os << "INFEASIBLE";
1302  break;
1303  default:
1304  os << "?other?";
1305  break;
1306  }
1307  return os;
1308 }
1309 
1310 
1311 } // namespace soplex
int lastMem
memory needed after last fresh factorization
Definition: spxbasis.h:388
int nzCount
number of nonzeros in basis matrix
Definition: spxbasis.h:387
Rational spxAbs(const Rational &r)
Absolute.
Definition: rational.cpp:3925
int dim() const
dimension of basis matrix.
Definition: spxsolver.h:936
virtual Status change(int idx, const SVector &subst, const SSVector *eta=0)=0
Substitute column idx with subst.
Desc::Status dualRowStatus(int i) const
dual Status for the i&#39;th row variable of the loaded LP.
Definition: spxbasis.cpp:46
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
Definition: exceptions.h:109
Basis is dual feasible.
Definition: spxbasis.h:95
Real fillFactor
allowed increase in realtive fill before refactorization
Definition: spxbasis.h:379
Representation rep() const
return the current basis representation.
Definition: spxsolver.h:406
virtual Status load(const SVector *vec[], int dim)=0
loads dim column vectors vec into the solver.
virtual void load(SPxSolver *lp)
loads the LP lp to the basis.
Definition: spxbasis.cpp:305
Basis is not known to be dual nor primal feasible.
Definition: spxbasis.h:94
virtual void clear()=0
unloads any matrix.
primal variable is fixed to both bounds
Definition: spxbasis.h:190
SPxOut * spxout
message handler
Definition: slinsolver.h:209
primal or dual variable has no status
Definition: spxbasis.h:195
Desc::Status dualStatus(const SPxColId &id) const
dual Status for the column variable with ID id of the loaded LP.
Definition: spxbasis.cpp:34
SPxOut * spxout
message handler
Definition: spxsolver.h:384
Read MPS format files.
static const char * getRowName(const SPxLP *lp, int idx, const NameSet *rnames, char *buf)
Definition: spxbasis.cpp:537
void reMax(int newmax=0)
resets max() to newmax.
Definition: nameset.cpp:138
virtual void solveRight(Vector &x, const Vector &b)=0
Solves .
int updateCount
number of calls to change() since last factorize()
Definition: spxbasis.h:385
SPxStatus status() const
returns current SPxStatus.
Definition: spxbasis.h:419
Basis is optimal, i.e. dual and primal feasible.
Definition: spxbasis.h:97
Dymnamic index set.
Exception classes for SoPlex.
Status & rowStatus(int i)
Definition: spxbasis.h:239
virtual bool isDescValid(const Desc &ds)
checks if a Descriptor is valid for the current LP w.r.t. its bounds
Definition: spxbasis.cpp:111
DataArray< Status > * stat
basis&#39; status.
Definition: spxbasis.h:209
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition: spxlpbase.h:450
const char * field0() const
Definition: mpsinput.h:144
const char * field2() const
Definition: mpsinput.h:148
virtual ~SPxBasis()
destructor.
Definition: spxbasis.cpp:1209
void setValue(int i, R x)
Sets i &#39;th element to x.
Definition: ssvectorbase.h:218
int size() const
Number of used indices.
Definition: svectorbase.h:152
void syntaxError()
Definition: mpsinput.h:198
int lastNzCount
number of nonzeros in basis matrix after last fresh factorization
Definition: spxbasis.h:390
const VectorBase< R > & lower() const
Returns lower bound vector.
Definition: spxlpbase.h:420
int nCols() const
returns number of columns.
Definition: spxbasis.h:219
R & value(int n)
Reference to value of n &#39;th nonzero.
Definition: svectorbase.h:254
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
Definition: spxid.h:36
static const char * getColName(const SPxLP *lp, int idx, const NameSet *cnames, char *buf)
Definition: spxbasis.cpp:563
bool factorized
true iff factor = matrix .
Definition: spxbasis.h:357
void setRep()
sets descriptor representation according to loaded LP.
Definition: spxbasis.cpp:286
Sparse Linear Solver virtual base class.Class SLinSolver provides a class for solving sparse linear s...
Definition: slinsolver.h:43
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition: spxlpbase.h:402
#define REAL_FORMAT
Definition: spxdefines.h:204
rowwise representation.
Definition: spxsolver.h:107
virtual void printMatrix() const
Definition: spxbasis.cpp:673
Basis is singular.
Definition: spxbasis.h:93
SPxStatus thestatus
current status of the basis.
Definition: spxbasis.h:406
Entry identifier class for items of a DataSet.Every item in a DataSet is assigned a DataKey by which ...
Definition: datakey.h:46
Vector & multWithBase(Vector &x) const
Vector-basis product.
Definition: spxbasis.cpp:894
dual variable is left free, but unset
Definition: spxbasis.h:191
Wrapper for different output streams and verbosity levels.
Section section() const
Definition: mpsinput.h:140
virtual void start()=0
start timer, resume accounting user, system and real time.
virtual Real stop()=0
stop timer, return accounted user time.
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition: spxalloc.h:48
int maxUpdates
number of updates before refactorization.
Definition: spxbasis.h:366
bool readLine()
reads an MPS format data line and parse the fields.
Definition: mpsinput.cpp:57
primal variable is set to its upper bound
Definition: spxbasis.h:188
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
void reDim()
resizes internal arrays.
double Real
SOPLEX_DEBUG.
Definition: spxdefines.h:200
virtual void solveLeft(Vector &x, const Vector &b)=0
solves .
void setStatus(SPxStatus stat)
sets basis SPxStatus to stat.
Definition: spxbasis.h:425
Real lastFill
fill ratio that occured during last factorization
Definition: spxbasis.h:389
#define MSG_DEBUG(x)
Definition: spxdefines.h:127
bool isConsistent() const
consistency check.
Definition: spxbasis.cpp:1094
int & index(int n)
Reference to index of n &#39;th nonzero.
Definition: svectorbase.h:236
Desc::Status dualColStatus(int i) const
dual Status for the i&#39;th column variable of the loaded LP.
Definition: spxbasis.cpp:69
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
Definition: basevectors.h:1087
Dynamic vectors.
SPxRowId rId(int n) const
Returns the row identifier for row n.
Definition: spxlpbase.h:470
virtual Status status() const =0
returns the Status of the SLinSolver.
int nCols() const
Returns number of columns in LP.
Definition: spxlpbase.h:133
dual variable is set to its upper bound
Definition: spxbasis.h:192
virtual bool isConsistent() const =0
consistency check.
virtual bool readBasis(std::istream &in, const NameSet *rowNames, const NameSet *colNames)
Definition: spxbasis.cpp:372
main LP solver class
primal variable is left free, but unset
Definition: spxbasis.h:189
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
Definition: spxdefines.h:109
void clear()
Clears vector.
Definition: ssvectorbase.h:572
Basis descriptor.
Definition: spxbasis.h:104
virtual Real stability() const =0
returns a stability number (0: singularity, 1: perfect stability).
int dim() const
Dimension of vector.
Definition: vectorbase.h:174
void add(const char *str)
Definition: nameset.cpp:25
SPxRowId rowId(int i) const
RowId of i &#39;th inequality.
Definition: spxsolver.h:2024
SPxId lastout
lastLeft(): variable left the base last
Definition: spxbasis.h:396
Real minStab
minimum stability
Definition: spxbasis.h:398
SSVectorBase< R > & multAdd(S xx, const SVectorBase< T > &vec)
Addition of a scaled vector.
Definition: basevectors.h:440
static Timer * createTimer(Timer::TYPE ttype)
create timers and allocate memory for them
Definition: timerfactory.h:43
Real length() const
Floating point approximation of euclidian norm (without any approximation guarantee).
Definition: ssvectorbase.h:520
Status & colStatus(int i)
Definition: spxbasis.h:254
void setSection(Section p_section)
Definition: mpsinput.h:171
SPxId & baseId(int i)
Definition: spxbasis.h:497
DataArray< Status > rowstat
status of rows.
Definition: spxbasis.h:207
void loadMatrixVecs()
loads matrix according to the SPxIds stored in theBaseId.
Definition: spxbasis.cpp:91
virtual void change(int i, SPxId &id, const SVector *enterVec, const SSVector *eta=0)
performs basis update.
Definition: spxbasis.cpp:715
Timer::TYPE timerType
type of timer (user or wallclock)
Definition: spxbasis.h:393
Debugging, floating point type and parameter definitions.
Simplex basis.Consider the linear program as provided from class SPxLP: where , and ...
Definition: spxbasis.h:82
Set of strings.Class NameSet implements a symbol or name table. It allows to store or remove names (i...
Definition: nameset.h:61
int nRows() const
Returns number of rows in LP.
Definition: spxlpbase.h:127
void restoreInitialBasis()
Restores initial basis.
Simplex basis.
void dump()
output basis entries.
Definition: spxbasis.cpp:1051
bool hasError() const
Definition: mpsinput.h:162
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
Definition: spxsolver.h:84
virtual SLinSolver * clone() const =0
clone function for polymorphism
Real condition(int maxiters=10, Real tolerance=1e-6)
Definition: spxbasis.cpp:978
VectorBase< R > & multAdd(const S &x, const VectorBase< T > &vec)
Addition of scaled vector.
Definition: vectorbase.h:369
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
Definition: exceptions.h:32
const char * field1() const
Definition: mpsinput.h:146
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition: spxlpbase.h:242
Desc thedesc
the basis&#39; Descriptor
Definition: spxbasis.h:407
Everything should be within this namespace.
const char * field3() const
Definition: mpsinput.h:150
TYPE
types of timers
Definition: timer.h:99
SLinSolver * factor
Definition: spxbasis.h:355
void setOutstream(SPxOut &newOutstream)
Definition: spxbasis.h:872
SPxOut * spxout
message handler
Definition: spxbasis.h:409
SPxBasis & operator=(const SPxBasis &rhs)
assignment operator
Definition: spxbasis.cpp:1227
DataArray< SPxId > theBaseId
SPxIds of basic vectors.
Definition: spxbasis.h:345
SPxColId cId(int n) const
Returns the column identifier for column n.
Definition: spxlpbase.h:476
primal variable is set to its lower bound
Definition: spxbasis.h:187
bool isConsistent() const
consistency check.
Definition: spxdesc.cpp:130
const SVector & vector(int i) const
i &#39;th vector.
Definition: spxsolver.h:1018
int totalUpdateCount
number of updates
Definition: spxbasis.h:386
int lastidx
lastIndex(): basis index where last update was done
Definition: spxbasis.h:397
SPxSolver * theLP
the LP
Definition: spxbasis.h:343
Vector & multBaseWith(Vector &x) const
Basis-vector product.
Definition: spxbasis.cpp:931
virtual void factorize()
factorizes the basis matrix.
Definition: spxbasis.cpp:845
int number(const DataKey &pkey) const
returns number of name with DataKey pkey in NameSet.
Definition: nameset.h:212
virtual void loadSolver(SLinSolver *solver, const bool destroy=false)
sets up linear solver to use.
Definition: spxbasis.cpp:319
virtual int memory() const =0
returns current memory consumption.
void clear()
Set vector to 0.
Definition: vectorbase.h:219
dual variable is set to its lower bound
Definition: spxbasis.h:193
DataArray< Status > * costat
cobasis&#39; status.
Definition: spxbasis.h:210
void dump() const
Prints out status.
Definition: spxdesc.cpp:113
virtual void loadDesc(const Desc &)
sets up basis.
Definition: spxbasis.cpp:188
const Real infinity
Definition: spxdefines.cpp:26
int dim() const
Dimension of VectorBase.
Definition: ssvectorbase.h:532
const SVector & baseVec(int i) const
returns the i&#39;th basic vector.
Definition: spxbasis.h:508
SPxStatus
basis status.
Definition: spxbasis.h:90
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition: spxlpbase.h:224
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
Definition: spxsolver.h:1124
int nRows() const
returns number of rows.
Definition: spxbasis.h:224
DataArray< Status > colstat
status of columns.
Definition: spxbasis.h:208
Sparse vectors.Class SVectorBase provides packed sparse vectors. Such are a sparse vectors...
Definition: dvectorbase.h:31
dual variable has two bounds
Definition: spxbasis.h:194
Exception class for status exceptions during the computationsThis class is derived from the SoPlex ex...
Definition: exceptions.h:89
The loaded matrix is singular.
Definition: slinsolver.h:60
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
Definition: spxid.h:55
#define MSGinconsistent(name)
Definition: spxdefines.h:121
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Definition: spxdefines.h:117
SPxId lastin
lastEntered(): variable entered the base last
Definition: spxbasis.h:395
int iterCount
number of calls to change() since last manipulation
Definition: spxbasis.h:384
virtual void writeBasis(std::ostream &os, const NameSet *rownames, const NameSet *colnames, const bool cpxFormat=false) const
Definition: spxbasis.cpp:589
Status
Status of a variable.
Definition: spxbasis.h:185
void add(int i, R x)
Adds nonzero (i, x) to SSVectorBase.
Definition: ssvectorbase.h:208
LP has been proven to be primal unbounded.
Definition: spxbasis.h:98
SPxColId colId(int i) const
ColId of i &#39;th column.
Definition: spxsolver.h:2029
bool has(int pnum) const
does NameSet has a name with number pnum?
Definition: nameset.h:231
void printMatrixMTX(int number)
Definition: spxbasis.cpp:684
Timer * theTime
time spent in updates
Definition: spxbasis.h:392
~NameSet()
destructor.
Definition: nameset.cpp:259
Real nonzeroFactor
allowed increase of nonzeros before refactorization.
Definition: spxbasis.h:373
SPxBasis(Timer::TYPE ttype=Timer::USER_TIME)
default constructor.
Definition: spxbasis.cpp:1142
bool freeSlinSolver
true iff factor should be freed inside of this object
Definition: spxbasis.h:408
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:109
int size() const
Returns the number of nonzeros.
Definition: ssvectorbase.h:199
Basis is primal feasible.
Definition: spxbasis.h:96
bool matrixIsSetup
true iff the pointers in matrix are set up correctly.
Definition: spxbasis.h:349
LP has been proven to be primal infeasible.
Definition: spxbasis.h:99
No Problem has been loaded to the basis.
Definition: spxbasis.h:92
DataArray< const SVector * > matrix
pointers to the vectors of the basis matrix.
Definition: spxbasis.h:347