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