Scippy

SoPlex

Sequential object-oriented simPlex

spxsolver.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2015 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file spxsolver.h
17  * @brief main LP solver class
18  */
19 #ifndef _SPXSOLVER_H_
20 #define _SPXSOLVER_H_
21 
22 #include <assert.h>
23 #include <iostream>
24 #include <iomanip>
25 #include <sstream>
26 
27 #include "spxdefines.h"
28 #include "timer.h"
29 #include "timerfactory.h"
30 #include "spxlp.h"
31 #include "spxbasis.h"
32 #include "array.h"
33 #include "random.h"
34 #include "unitvector.h"
35 #include "updatevector.h"
36 
37 #define HYPERPRICINGTHRESHOLD 5000 /**< do (auto) hyper pricing only if problem size (cols+rows) is larger than HYPERPRICINGTHRESHOLD */
38 #define HYPERPRICINGSIZE 100 /**< size of initial candidate list for hyper pricing */
39 #define SPARSITYFACTOR 0.6 /**< percentage of infeasibilities that is considered sparse */
40 #define DENSEROUNDS 5 /**< number of refactorizations until sparsity is tested again */
41 #define SPARSITY_TRADEOFF 0.8 /**< threshold to decide whether Ids or coIds are preferred to enter the basis;
42  * coIds are more likely to enter if SPARSITY_TRADEOFF is close to 0
43  */
44 #define MAXNCLCKSKIPS 32 /**< maximum number of clock skips (iterations without time measuring) */
45 #define SAFETYFACTOR 1e-2 /**< the probability to skip the clock when the time limit has been reached */
46 #define NINITCALLS 200 /**< the number of clock updates in isTimelimitReached() before clock skipping starts */
47 namespace soplex
48 {
49 class SPxPricer;
50 class SPxRatioTester;
51 class SPxStarter;
52 
53 /**@brief Sequential object-oriented SimPlex.
54  @ingroup Algo
55 
56  SPxSolver is an LP solver class using the revised Simplex algorithm. It
57  provids two basis representations, namely a column basis and a row basis
58  (see #Representation). For both representations, a primal and
59  dual algorithm is available (see \ref Type).
60 
61  In addition, SPxSolver can be custumized with various respects:
62  - pricing algorithms using SPxPricer
63  - ratio test using class SPxRatioTester
64  - computation of a start basis using class SPxStarter
65  - preprocessing of the LP using class SPxSimplifier
66  - termination criteria by overriding
67 
68  SPxSolver is derived from SPxLP that is used to store the LP to be solved.
69  Hence, the LPs solved with SPxSolver have the general format
70 
71  \f[
72  \begin{array}{rl}
73  \hbox{max} & \mbox{maxObj}^T x \\
74  \hbox{s.t.} & \mbox{lhs} \le Ax \le \mbox{rhs} \\
75  & \mbox{low} \le x \le \mbox{up}
76  \end{array}
77  \f]
78 
79  Also, SPxLP provide all manipulation methods for the LP. They allow
80  SPxSolver to be used within cutting plane algorithms.
81 */
82 class SPxSolver : public SPxLP, protected SPxBasis
83 {
84  friend class SoPlexLegacy;
85  friend class SPxFastRT;
86  friend class SPxBoundFlippingRT;
87 
88 public:
89 
90  //-----------------------------
91  /**@name Data Types */
92  //@{
93  /// LP basis representation.
94  /** Solving LPs with the Simplex algorithm requires the definition of a
95  * \em basis. A basis can be defined as a set of column vectors or a
96  * set of row vectors building a nonsingular matrix. We will refer to
97  * the first case as the \em columnwise representation and the latter
98  * case will be called the \em rowwise representation.
99  *
100  * Type Representation determines the representation of SPxSolver, i.e.
101  * a columnwise (#COLUMN == 1) or rowwise (#ROW == -1) one.
102  */
103  enum Representation
104  {
105  ROW = -1, ///< rowwise representation.
106  COLUMN = 1 ///< columnwise representation.
107  };
109  /// Algorithmic type.
110  /** SPxSolver uses the reviesed Simplex algorithm to solve LPs.
111  * Mathematically, one distinguishes the \em primal from the
112  * \em dual algorihm. Algorithmically, these relate to the two
113  * types #ENTER or #LEAVE. How they relate, depends on the chosen
114  * basis representation. This is desribed by the following table:
115  *
116  * <TABLE>
117  * <TR><TD>&nbsp;</TD><TD>ENTER </TD><TD>LEAVE </TD></TR>
118  * <TR><TD>ROW </TD><TD>DUAL </TD><TD>PRIMAL</TD></TR>
119  * <TR><TD>COLUMN</TD><TD>PRIMAL</TD><TD>DUAL </TD></TR>
120  * </TABLE>
121  */
122  enum Type
123  {
124  /// Entering Simplex.
125  /** The Simplex loop for the entering Simplex can be sketched
126  * as follows:
127  * - \em Pricing : Select a variable to #ENTER the basis.
128  * - \em Ratio-Test : Select variable to #LEAVE the
129  * basis such that the basis remains feasible.
130  * - Perform the basis update.
131  */
132  ENTER = -1,
133  /// Leaving Simplex.
134  /** The Simplex loop for the leaving Simplex can be sketched
135  * as follows:
136  * - \em Pricing: Select a variable to #LEAVE the basis.
137  * - \em Ratio-Test: Select variable to #ENTER the
138  * basis such that the basis remains priced.
139  * - Perform the basis update.
140  */
141  LEAVE = 1
142  };
144  /// Pricing type.
145  /** In case of the #ENTER%ing Simplex algorithm, for performance
146  * reasons it may be advisable not to compute and maintain up to
147  * date vectors #pVec() and #test() and instead compute only some
148  * of its elements explicitely. This is controled by the #Pricing type.
149  */
150  enum Pricing
151  {
152  /// Full pricing.
153  /** If #FULL pricing in selected for the #ENTER%ing Simplex,
154  * vectors #pVec() and #test() are kept up to date by
155  * SPxSolver. An SPxPricer only needs to select an Id such
156  * that the #test() or #coTest() value is < 0.
157  */
158  FULL,
159  /// Partial pricing.
160  /** When #PARTIAL pricing in selected for the #ENTER%ing
161  * Simplex, vectors #pVec() and #test() are not set up and
162  * updated by SPxSolver. However, vectors #coPvec() and
163  * #coTest() are still kept up to date by SPxSolver.
164  * An SPxPricer object needs to compute the values for
165  * #pVec() and #test() itself in order to select an
166  * appropriate pivot with #test() < 0. Methods \ref computePvec(int)
167  * "computePvec(i)" and \ref computeTest(int) "computeTest(i)"
168  * will assist the used to do so. Note
169  * that it may be feasible for a pricer to return an Id with
170  * #test() > 0; such will be rejected by SPxSolver.
171  */
172  PARTIAL
173  };
175  enum VarStatus
176  {
177  ON_UPPER, ///< variable set to its upper bound.
178  ON_LOWER, ///< variable set to its lower bound.
179  FIXED, ///< variable fixed to identical bounds.
180  ZERO, ///< free variable fixed to zero.
181  BASIC, ///< variable is basic.
182  UNDEFINED ///< nothing known about basis status (possibly due to a singular basis in transformed problem)
183  };
185  /**@todo In spxchange, change the status to
186  if (m_status > 0) m_status = REGULAR;
187  */
188  enum Status
189  {
190  ERROR = -13, ///< an error occured.
191  NO_RATIOTESTER = -12, ///< No ratiotester loaded
192  NO_PRICER = -11, ///< No pricer loaded
193  NO_SOLVER = -10, ///< No linear solver loaded
194  NOT_INIT = -9, ///< not initialised error
195  ABORT_CYCLING = -8, ///< solve() aborted due to detection of cycling.
196  ABORT_TIME = -7, ///< solve() aborted due to time limit.
197  ABORT_ITER = -6, ///< solve() aborted due to iteration limit.
198  ABORT_VALUE = -5, ///< solve() aborted due to objective limit.
199  SINGULAR = -4, ///< Basis is singular, numerical troubles?
200  NO_PROBLEM = -3, ///< No Problem has been loaded.
201  REGULAR = -2, ///< LP has a usable Basis (maybe LP is changed).
202  RUNNING = -1, ///< algorithm is running
203  UNKNOWN = 0, ///< nothing known on loaded problem.
204  OPTIMAL = 1, ///< LP has been solved to optimality.
205  UNBOUNDED = 2, ///< LP has been proven to be primal unbounded.
206  INFEASIBLE = 3, ///< LP has been proven to be primal infeasible.
207  INForUNBD = 4 ///< LP is primal infeasible or unbounded.
208  };
210  //@}
211 
212 private:
213 
214  //-----------------------------
215  /**@name Private data */
216  //@{
217  Type theType; ///< entering or leaving algortihm.
218  Pricing thePricing; ///< full or partial pricing.
219  Representation theRep; ///< row or column representation.
220  Timer* theTime; ///< time spent in last call to method solve()
221  Timer::TYPE timerType; ///< type of timer (user or wallclock)
222  Real theCumulativeTime; ///< cumulative time spent in all calls to method solve()
223  int maxIters; ///< maximum allowed iterations.
224  Real maxTime; ///< maximum allowed time.
225  int nClckSkipsLeft; ///< remaining number of times the clock can be safely skipped
226  long nCallsToTimelim; /// < the number of calls to the method isTimeLimitReached()
227  Real objLimit; ///< objective value limit.
228  Status m_status; ///< status of algorithm.
230  Real m_nonbasicValue; ///< nonbasic part of current objective value
231  bool m_nonbasicValueUpToDate; ///< true, if the stored objValue is up to date
233  Real m_entertol; ///< feasibility tolerance maintained during entering algorithm
234  Real m_leavetol; ///< feasibility tolerance maintained during leaving algorithm
235  Real theShift; ///< sum of all shifts applied to any bound.
236  Real lastShift; ///< for forcing feasibility.
237  int m_maxCycle; ///< maximum steps before cycling is detected.
238  int m_numCycle; ///< actual number of degenerate steps so far.
239  bool initialized; ///< true, if all vectors are setup.
241  SSVector* solveVector2; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
242  SSVector* solveVector2rhs; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
243  SSVector* solveVector3; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
244  SSVector* solveVector3rhs; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
245  SSVector* coSolveVector2; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
246  SSVector* coSolveVector2rhs; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
247  SSVector* coSolveVector3; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
248  SSVector* coSolveVector3rhs; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
250  bool freePricer; ///< true iff thepricer should be freed inside of object
251  bool freeRatioTester; ///< true iff theratiotester should be freed inside of object
252  bool freeStarter; ///< true iff thestarter should be freed inside of object
254  /* Store the index of a leaving variable if only an instable entering variable has been found.
255  instableLeave == true iff this instable basis change should be performed.
256  (see spxsolve.cpp and leave.cpp) */
257  int instableLeaveNum;
258  bool instableLeave;
261  /* Store the id of an entering row or column if only an instable pivot has been found.
262  instableEnter == true iff this instable basis change should be performed.
263  (see spxsolve.cpp and enter.cpp) */
265  bool instableEnter;
269  int displayFreq;
270  Real sparsePricingFactor; ///< enable sparse pricing when viols < factor * dim()
272  //@}
273 
274 protected:
275 
276  //-----------------------------
277  /**@name Protected data */
278  //@{
279  Array < UnitVector > unitVecs; ///< array of unit vectors
280  const SVSet* thevectors; ///< the LP vectors according to representation
281  const SVSet* thecovectors; ///< the LP coVectors according to representation
283  DVector primRhs; ///< rhs vector for computing the primal vector
284  UpdateVector primVec; ///< primal vector
285  DVector dualRhs; ///< rhs vector for computing the dual vector
286  UpdateVector dualVec; ///< dual vector
287  UpdateVector addVec; ///< storage for thePvec = &addVec
289  DVector theURbound; ///< Upper Row Feasibility bound
290  DVector theLRbound; ///< Lower Row Feasibility bound
291  DVector theUCbound; ///< Upper Column Feasibility bound
292  DVector theLCbound; ///< Lower Column Feasibility bound
294  /** In entering Simplex algorithm, the ratio test must ensure that all
295  * \em basic variables remain within their feasibility bounds. To give fast
296  * acces to them, the bounds of basic variables are copied into the
297  * following two vectors.
298  */
299  DVector theUBbound; ///< Upper Basic Feasibility bound
300  DVector theLBbound; ///< Lower Basic Feasibility bound
309  UpdateVector* theRPvec; ///< row pricing vector
310  UpdateVector* theCPvec; ///< column pricing vector
312  // The following vectors serve for the virtualization of shift bounds
313  //@todo In prinziple this schould be references.
314  DVector* theUbound; ///< Upper bound for vars
315  DVector* theLbound; ///< Lower bound for vars
316  DVector* theCoUbound; ///< Upper bound for covars
317  DVector* theCoLbound; ///< Lower bound for covars
319  // The following vectors serve for the virtualization of testing vectors
323  DSVector primalRay; ///< stores primal ray in case of unboundedness
324  DSVector dualFarkas; ///< stores dual farkas proof in case of infeasibility
326  int leaveCount; ///< number of LEAVE iterations
327  int enterCount; ///< number of ENTER iterations
328  int primalCount; ///< number of primal iterations
329 
330  int boundflips; ///< number of performed bound flips
331  int totalboundflips; ///< total number of bound flips
336  //@}
338  //-----------------------------
339  /**@name Precision */
340  //@{
341  /// is the solution precise enough, or should we increase delta() ?
342  virtual bool precisionReached(Real& newpricertol) const;
343  //@}
344 
345 public:
346 
347  /** For the leaving Simplex algorithm this vector contains the indices of infeasible basic variables;
348  * for the entering Simplex algorithm this vector contains the indices of infeasible slack variables.
349  */
351  /**For the entering Simplex algorithm these vectors contains the indices of infeasible basic variables.
352  */
354 
355  /// store indices that were changed in the previous iteration and must be checked in hyper pricing
359  /** Binary vectors to store whether basic indices are infeasible
360  * the i-th entry equals false, if the i-th basic variable is not infeasible
361  * the i-th entry equals true, if the i-th basic variable is infeasible
362  */
363  DataArray<int> isInfeasible; ///< 0: index not violated, 1: index violated, 2: index violated and among candidate list
364  DataArray<int> isInfeasibleCo; ///< 0: index not violated, 1: index violated, 2: index violated and among candidate list
366  /// These values enable or disable sparse pricing
367  bool sparsePricingLeave; ///< true if sparsePricing is turned on in the leaving Simplex
368  bool sparsePricingEnter; ///< true if sparsePricing is turned on in the entering Simplex for slack variables
369  bool sparsePricingEnterCo; ///< true if sparsePricing is turned on in the entering Simplex
370  bool hyperPricingLeave; ///< true if hyper sparse pricing is turned on in the leaving Simplex
371  bool hyperPricingEnter; ///< true if hyper sparse pricing is turned on in the entering Simplex
373  int remainingRoundsLeave; ///< number of dense rounds/refactorizations until sparsePricing is enabled again
377  SPxOut* spxout; ///< message handler
378 
379  //-----------------------------
380  void setOutstream(SPxOut& newOutstream)
381  {
382  spxout = &newOutstream;
383  SPxLPBase::spxout = &newOutstream;
384  }
385 
386  /**@name Access */
387  //@{
388  /// return the version of SPxSolver as number like 123 for 1.2.3
389  int version() const
390  {
392  }
393  /// return the internal subversion of SPxSolver as number
394  int subversion() const
395  {
397  }
398  /// return the current basis representation.
399  Representation rep() const
400  {
401  return theRep;
402  }
403 
404  /// return current Type.
405  Type type() const
406  {
407  return theType;
408  }
409 
410  /// return current Pricing.
411  Pricing pricing() const
412  {
413  return thePricing;
414  }
415 
416  /// return current starter.
417  SPxStarter* starter() const
418  {
419  return thestarter;
420  }
421  //@}
422 
423  //-----------------------------
424  /**@name Setup
425  * Before solving an LP with an instance of SPxSolver,
426  * the following steps must be performed:
427  *
428  * -# Load the LP by copying an external LP or reading it from an
429  * input stream.
430  * -# Setup the pricer to use by loading an \ref soplex::SPxPricer
431  * "SPxPricer" object (if not already done in a previous call).
432  * -# Setup the ratio test method to use by loading an
433  * \ref soplex::SPxRatioTester "SPxRatioTester" object
434  * (if not already done in a previous call).
435  * -# Setup the linear system solver to use by loading an
436  * \ref soplex::SLinSolver "SLinSolver" object
437  * (if not already done in a previous call).
438  * -# Optionally setup an start basis generation method by loading an
439  * \ref soplex::SPxStarter "SPxStarter" object.
440  * -# Optionally setup a start basis by loading a
441  * \ref soplex::SPxBasis::Desc "SPxBasis::Desc" object.
442  * -# Optionally switch to another basis
443  * \ref soplex::SPxSolver::Representation "Representation"
444  * by calling method \ref soplex::SPxSolver::setRep() "setRep()".
445  * -# Optionally switch to another algorithm
446  * \ref soplex::SPxSolver::Type "Type"
447  * by calling method \ref soplex::SPxSolver::setType() "setType()".
448  *
449  * Now the solver is ready for execution. If the loaded LP is to be solved
450  * again from scratch, this can be done with method
451  * \ref soplex::SPxSolver::reLoad() "reLoad()". Finally,
452  * \ref soplex::SPxSolver::clear() "clear()" removes the LP from the solver.
453  */
454  //@{
455  /// read LP from input stream.
456  virtual bool read(std::istream& in, NameSet* rowNames = 0,
457  NameSet* colNames = 0, DIdxSet* intVars = 0);
458 
459  /// copy LP.
460  virtual void loadLP(const SPxLP& LP);
461  /// setup linear solver to use. If \p destroy is true, \p slusolver will be freed in destructor.
462  virtual void setSolver(SLinSolver* slu, const bool destroy = false);
463  /// setup pricer to use. If \p destroy is true, \p pricer will be freed in destructor.
464  virtual void setPricer(SPxPricer* pricer, const bool destroy = false);
465  /// setup ratio-tester to use. If \p destroy is true, \p tester will be freed in destructor.
466  virtual void setTester(SPxRatioTester* tester, const bool destroy = false);
467  /// setup starting basis generator to use. If \p destroy is true, \p starter will be freed in destructor.
468  virtual void setStarter(SPxStarter* starter, const bool destroy = false);
469  /// set a start basis.
470  virtual void loadBasis(const SPxBasis::Desc&);
471 
472  /// initialize #ROW or #COLUMN representation.
473  void initRep (Representation p_rep);
474  /// switch to #ROW or #COLUMN representation if not already used.
475  void setRep (Representation p_rep);
476  /// set \ref soplex::SPxSolver::LEAVE "LEAVE" or \ref soplex::SPxSolver::ENTER "ENTER" algorithm.
477  void setType(Type tp);
478  /// set \ref soplex::SPxSolver::FULL "FULL" or \ref soplex::SPxSolver::PARTIAL "PARTIAL" pricing.
479  void setPricing(Pricing pr);
480 
481  /// reload LP.
482  virtual void reLoad();
483 
484  /// clear all data in solver.
485  virtual void clear();
486 
487  /** Load basis from \p filename in MPS format. If \p rowNames and \p
488  * colNames are \c NULL, default names are used for the constraints and
489  * variables.
490  */
491  virtual bool readBasisFile(const char* filename,
492  const NameSet* rowNames, const NameSet* colNames);
493 
494  /** Write basis to \p filename in MPS format. If \p rowNames and \p
495  * colNames are \c NULL, default names are used for the constraints and
496  * variables.
497  */
498  virtual bool writeBasisFile(const char* filename,
499  const NameSet* rowNames, const NameSet* colNames, const bool cpxFormat = false) const;
500 
501  /** Write current LP, basis, and parameter settings.
502  * LP is written in MPS format to "\p filename".mps, basis is written in "\p filename".bas, and parameters
503  * are written to "\p filename".set. If \p rowNames and \p colNames are \c NULL, default names are used for
504  * the constraints and variables.
505  */
506  virtual bool writeState(const char* filename,
507  const NameSet* rowNames = NULL, const NameSet* colNames = NULL, const bool cpxFormat = false) const;
508 
509  //@}
510 
511  /**@name Solving LPs */
512  //@{
513  /// solve loaded LP.
514  /** Solves the loaded LP by processing the Simplex iteration until
515  * the termination criteria is fullfilled (see #terminate()).
516  * The SPxStatus of the solver will indicate the reason for termination.
517  *
518  * @throw SPxStatusException if either no problem, solver, pricer
519  * or ratiotester loaded or if solve is still running when it shouldn't be
520  */
521  virtual Status solve();
522 
523  /// Status of solution process.
524  Status status() const;
525 
526  /// current objective value.
527  /**@return Objective value of the current solution vector
528  * (see #getPrimal()).
529  */
530  virtual Real value();
531 
532  // update nonbasic part of the objective value by the given amount
533  /**@return whether nonbasic part of objective is reliable
534  */
535  bool updateNonbasicValue(Real objChange);
536 
537  // trigger a recomputation of the nonbasic part of the objective value
539  {
541  m_nonbasicValueUpToDate = false;
542  }
543 
544 #if 0
545  /// returns dualsol^T b + min{(objvec^T - dualsol^T A) x} calculated in interval arithmetics
546  Real provedBound(Vector& dualsol, const Vector& objvec) const;
547 
548  /// proved dual bound for objective value.
549  virtual Real provedDualbound() const;
550 
551  /// returns whether an infeasible LP is proven to be infeasible.
552  virtual bool isProvenInfeasible() const;
553 #endif
554 
555  /// get solution vector for primal variables.
556  /** This method returns the Status of the basis.
557  * If it is #REGULAR or better,
558  * the primal solution vector of the current basis will be copied
559  * to the argument \p vector. Hence, \p vector must be of dimension
560  * #nCols().
561  *
562  * @throw SPxStatusException if not initialized
563  */
564  virtual Status getPrimal(Vector& vector) const;
565 
566  /// get vector of slack variables.
567  /** This method returns the Status of the basis.
568  * If it is #REGULAR or better,
569  * the slack variables of the current basis will be copied
570  * to the argument \p vector. Hence, \p vector must be of dimension
571  * #nRows().
572  *
573  * @warning Because SPxSolver supports range constraints as its
574  * default, slack variables are defined in a nonstandard way:
575  * Let \em x be the current solution vector and \em A the constraint
576  * matrix. Then the vector of slack variables is defined as
577  * \f$s = Ax\f$.
578  *
579  * @throw SPxStatusException if no problem loaded
580  */
581  virtual Status getSlacks (Vector& vector) const;
582 
583  /// get current solution vector for dual variables.
584  /** This method returns the Status of the basis.
585  * If it is #REGULAR or better,
586  * the vector of dual variables of the current basis will be copied
587  * to the argument \p vector. Hence, \p vector must be of dimension
588  * #nRows().
589  *
590  * @warning Even though mathematically, each range constraint would
591  * account for two dual variables (one for each inequaility), only
592  * #nRows() dual variables are setup via the following
593  * construction: Given a range constraint, there are three possible
594  * situations:
595  * - None of its inequalities is tight: The dual variables
596  * for both are 0. However, when shifting (see below)
597  * occurs, it may be set to a value other than 0, which
598  * models a perturbed objective vector.
599  * - Both of its inequalities are tight: In this case the
600  * range constraint models an equality and we adopt the
601  * standard definition.
602  * - One of its inequalities is tight while the other is not:
603  * In this case only the dual variable for the tight
604  * constraint is given with the standard definition, while
605  * the other constraint is implicitely set to 0.
606  *
607  * @throw SPxStatusException if no problem loaded
608  */
609  virtual Status getDual (Vector& vector) const;
610 
611  /// get vector of reduced costs.
612  /** This method returns the Status of the basis.
613  * If it is #REGULAR or better,
614  * the vector of reduced costs of the current basis will be copied
615  * to the argument \p vector. Hence, \p vector must be of dimension
616  * #nCols().
617  *
618  * Let \em d denote the vector of dual variables, as defined above,
619  * and \em A the LPs constraint matrix. Then the reduced cost vector
620  * \em r is defined as \f$r^T = c^T - d^TA\f$.
621  *
622  * @throw SPxStatusException if no problem loaded
623  */
624  virtual Status getRedCost (Vector& vector) const;
625 
626  /// get primal ray in case of unboundedness.
627  /// @throw SPxStatusException if no problem loaded
628  virtual Status getPrimalray (Vector& vector) const;
629 
630  /// get dual farkas proof of infeasibility.
631  /// @throw SPxStatusException if no problem loaded
632  virtual Status getDualfarkas (Vector& vector) const;
633 
634  /// print display line of flying table
635  virtual void printDisplayLine(const bool force = false);
636 
637  /// Termination criterion.
638  /** This method is called in each Simplex iteration to determine, if
639  * the algorithm is to terminate. In this case a nonzero value is
640  * returned.
641  *
642  * This method is declared virtual to allow for implementation of
643  * other stopping criteria or using it as callback method within the
644  * Simplex loop, by overriding the method in a derived class.
645  * However, all implementations must terminate with the
646  * statement \c return SPxSolver::#terminate(), if no own termination
647  * criteria is encountered.
648  *
649  * Note, that the Simplex loop stopped even when #terminate()
650  * returns 0, if the LP has been solved to optimality (i.e. no
651  * further pricing succeeds and no shift is present).
652  */
653  virtual bool terminate ();
654  //@}
655 
656  //-----------------------------
657  /**@name Control Parameters */
658  //@{
659  /// values \f$|x| < \epsilon\f$ are considered to be 0.
660  /** if you want another value for epsilon, use
661  * \ref soplex::Param::setEpsilon() "Param::setEpsilon()".
662  */
663  Real epsilon() const
664  {
666  }
667  /// feasibility tolerance maintained by ratio test during ENTER algorithm.
668  Real entertol() const
669  {
670  assert(m_entertol > 0.0);
671 
672  return m_entertol;
673  }
674  /// feasibility tolerance maintained by ratio test during LEAVE algorithm.
675  Real leavetol() const
676  {
677  assert(m_leavetol > 0.0);
678 
679  return m_leavetol;
680  }
681  /// allowed primal feasibility tolerance.
682  Real feastol() const
683  {
684  assert(m_entertol > 0.0);
685  assert(m_leavetol > 0.0);
686 
687  return theRep == COLUMN ? m_entertol : m_leavetol;
688  }
689  /// allowed optimality, i.e., dual feasibility tolerance.
690  Real opttol() const
691  {
692  assert(m_entertol > 0.0);
693  assert(m_leavetol > 0.0);
694 
695  return theRep == COLUMN ? m_leavetol : m_entertol;
696  }
697  /// guaranteed primal and dual bound violation for optimal solution, returning the maximum of feastol() and opttol(), i.e., the less tight tolerance.
698  Real delta() const
699  {
700  assert(m_entertol > 0.0);
701  assert(m_leavetol > 0.0);
702 
704  }
705  /// set parameter \p feastol.
706  void setFeastol(Real d);
707  /// set parameter \p opttol.
708  void setOpttol(Real d);
709  /// set parameter \p delta, i.e., set \p feastol and \p opttol to same value.
710  void setDelta(Real d);
711  /// set timing type
712  void setTiming(Timer::TYPE ttype)
713  {
715  timerType = ttype;
716  }
717  /// set timing type
719  {
720  assert(timerType == theTime->type());
721  return timerType;
722  }
723 
724  /// set display frequency
725  void setDisplayFreq(int freq)
726  {
727  displayFreq = freq;
728  }
729  // enable sparse pricing when viols < fac * dim()
730  void setSparsePricingFactor(Real fac)
731  {
733  }
734  /// enable or disable hyper sparse pricing
735  void hyperPricing(bool h);
736 
737  /** SPxSolver considers a Simplex step as degenerate if the
738  * steplength does not exceed #epsilon(). Cycling occurs if only
739  * degenerate steps are taken. To prevent this situation, SPxSolver
740  * perturbs the problem such that nondegenerate steps are ensured.
741  *
742  * maxCycle() controls how agressive such perturbation is
743  * performed, since no more than maxCycle() degenerate steps are
744  * accepted before perturbing the LP. The current number of consecutive
745  * degenerate steps is counted by numCycle().
746  */
747  /// maximum number of degenerate simplex steps before we detect cycling.
748  int maxCycle() const
749  {
750  return m_maxCycle;
751  }
752  /// actual number of degenerate simplex steps encountered so far.
753  int numCycle() const
754  {
755  return m_numCycle;
756  }
757  //@}
758 
759 private:
760 
761  //-----------------------------
762  /**@name Private helpers */
763  //@{
764  ///
765  void localAddRows(int start);
766  ///
767  void localAddCols(int start);
768  ///
769  void setPrimal(Vector& p_vector);
770  ///
771  void setSlacks(Vector& p_vector);
772  ///
773  void setDual(Vector& p_vector);
774  ///
775  void setRedCost(Vector& p_vector);
776  //@}
777 
778 protected:
779 
780  //-----------------------------
781  /**@name Protected helpers */
782  //@{
783  ///
784  virtual void addedRows(int n);
785  ///
786  virtual void addedCols(int n);
787  ///
788  virtual void doRemoveRow(int i);
789  ///
790  virtual void doRemoveRows(int perm[]);
791  ///
792  virtual void doRemoveCol(int i);
793  ///
794  virtual void doRemoveCols(int perm[]);
795  //@}
796 
797 public:
798 
799  //-----------------------------
800  /**@name Modification */
801  //@{
802  ///
803  virtual void changeObj(const Vector& newObj);
804  ///
805  virtual void changeObj(int i, const Real& newVal);
806  ///
807  virtual void changeObj(SPxColId p_id, const Real& p_newVal)
808  {
809  changeObj(number(p_id), p_newVal);
810  }
811  ///
812  virtual void changeMaxObj(const Vector& newObj);
813  ///
814  virtual void changeMaxObj(int i, const Real& newVal);
815  ///
816  virtual void changeMaxObj(SPxColId p_id, const Real& p_newVal)
817  {
818  changeMaxObj(number(p_id), p_newVal);
819  }
820  ///
821  virtual void changeRowObj(const Vector& newObj);
822  ///
823  virtual void changeRowObj(int i, const Real& newVal);
824  ///
825  virtual void changeRowObj(SPxRowId p_id, const Real& p_newVal)
826  {
827  changeRowObj(number(p_id), p_newVal);
828  }
829  ///
830  virtual void clearRowObjs()
831  {
833  unInit();
834  }
835  ///
836  virtual void changeLowerStatus(int i, Real newLower, Real oldLower = 0.0);
837  ///
838  virtual void changeLower(const Vector& newLower);
839  ///
840  virtual void changeLower(int i, const Real& newLower);
841  ///
842  virtual void changeLower(SPxColId p_id, const Real& p_newLower)
843  {
844  changeLower(number(p_id), p_newLower);
845  }
846  ///
847  virtual void changeUpperStatus(int i, Real newUpper, Real oldLower = 0.0);
848  ///
849  virtual void changeUpper(const Vector& newUpper);
850  ///
851  virtual void changeUpper(int i, const Real& newUpper);
852  ///
853  virtual void changeUpper(SPxColId p_id, const Real& p_newUpper)
854  {
855  changeUpper(number(p_id), p_newUpper);
856  }
857  ///
858  virtual void changeBounds(const Vector& newLower, const Vector& newUpper);
859  ///
860  virtual void changeBounds(int i, const Real& newLower, const Real& newUpper);
861  ///
862  virtual void changeBounds(
863  SPxColId p_id, const Real& p_newLower, const Real& p_newUpper)
864  {
865  changeBounds(number(p_id), p_newLower, p_newUpper);
866  }
867  ///
868  virtual void changeLhsStatus(int i, Real newLhs, Real oldLhs = 0.0);
869  ///
870  virtual void changeLhs(const Vector& newLhs);
871  ///
872  virtual void changeLhs(int i, const Real& newLhs);
873  ///
874  virtual void changeLhs(SPxRowId p_id, const Real& p_newLhs)
875  {
876  changeLhs(number(p_id), p_newLhs);
877  }
878  ///
879  virtual void changeRhsStatus(int i, Real newRhs, Real oldRhs = 0.0);
880  ///
881  virtual void changeRhs(const Vector& newRhs);
882  ///
883  virtual void changeRhs(int i, const Real& newRhs);
884  ///
885  virtual void changeRhs(SPxRowId p_id, const Real& p_newRhs)
886  {
887  changeRhs(number(p_id), p_newRhs);
888  }
889  ///
890  virtual void changeRange(const Vector& newLhs, const Vector& newRhs);
891  ///
892  virtual void changeRange(int i, const Real& newLhs, const Real& newRhs);
893  ///
894  virtual void changeRange(
895  SPxRowId p_id, const Real& p_newLhs, const Real& p_newRhs)
896  {
897  changeRange(number(p_id), p_newLhs, p_newRhs);
898  }
899  ///
900  virtual void changeRow(int i, const LPRow& newRow);
901  ///
902  virtual void changeRow(SPxRowId p_id, const LPRow& p_newRow)
903  {
904  changeRow(number(p_id), p_newRow);
905  }
906  ///
907  virtual void changeCol(int i, const LPCol& newCol);
908  ///
909  virtual void changeCol(SPxColId p_id, const LPCol& p_newCol)
910  {
911  changeCol(number(p_id), p_newCol);
912  }
913  ///
914  virtual void changeElement(int i, int j, const Real& val);
915  ///
916  virtual void changeElement(
917  SPxRowId rid, SPxColId cid, const Real& val)
918  {
919  changeElement(number(rid), number(cid), val);
920  }
921  ///
922  virtual void changeSense(SPxSense sns);
923  //@}
924 
925  //------------------------------------
926  /**@name Dimension and codimension */
927  //@{
928  /// dimension of basis matrix.
929  int dim() const
930  {
931  return thecovectors->num();
932  }
933  /// codimension.
934  int coDim() const
935  {
936  return thevectors->num();
937  }
938  //@}
939 
940  //------------------------------------
941  /**@name Variables and Covariables
942  * Class SPxLP introduces \ref soplex::SPxId "SPxIds" to identify
943  * row or column data of an LP. SPxSolver uses this concept to
944  * access data with respect to the chosen representation.
945  */
946  //@{
947  /// id of \p i 'th vector.
948  /** The \p i 'th Id is the \p i 'th SPxRowId for a rowwise and the
949  * \p i 'th SPxColId for a columnwise basis represenation. Hence,
950  * 0 <= i < #coDim().
951  */
952  SPxId id(int i) const
953  {
954  if (rep() == ROW)
955  {
956  SPxRowId rid = SPxLP::rId(i);
957  return SPxId(rid);
958  }
959  else
960  {
961  SPxColId cid = SPxLP::cId(i);
962  return SPxId(cid);
963  }
964  }
965 
966  /// id of \p i 'th covector.
967  /** The \p i 'th #coId() is the \p i 'th SPxColId for a rowwise and the
968  * \p i 'th SPxRowId for a columnwise basis represenation. Hence,
969  * 0 <= i < #dim().
970  */
971  SPxId coId(int i) const
972  {
973  if (rep() == ROW)
974  {
975  SPxColId cid = SPxLP::cId(i);
976  return SPxId(cid);
977  }
978  else
979  {
980  SPxRowId rid = SPxLP::rId(i);
981  return SPxId(rid);
982  }
983  }
984 
985  /// Is \p p_id an SPxId ?
986  /** This method returns wheather or not \p p_id identifies a vector
987  * with respect to the chosen representation.
988  */
989  bool isId(const SPxId& p_id) const
990  {
991  return p_id.info * theRep > 0;
992  }
993 
994  /// Is \p p_id a CoId.
995  /** This method returns wheather or not \p p_id identifies a coVector
996  * with respect to the chosen representation.
997  */
998  bool isCoId(const SPxId& p_id) const
999  {
1000  return p_id.info * theRep < 0;
1001  }
1002  //@}
1003 
1004  //------------------------------------
1005  /**@name Vectors and Covectors */
1006  //@{
1007  /// \p i 'th vector.
1008  /**@return a reference to the \p i 'th, 0 <= i < #coDim(), vector of
1009  * the loaded LP (with respect to the chosen representation).
1010  */
1011  const SVector& vector(int i) const
1012  {
1013  return (*thevectors)[i];
1014  }
1015 
1016  ///
1017  const SVector& vector(const SPxRowId& rid) const
1018  {
1019  assert(rid.isValid());
1020  return (rep() == ROW)
1021  ? (*thevectors)[number(rid)]
1022  : static_cast<const SVector&>(unitVecs[number(rid)]);
1023  }
1024  ///
1025  const SVector& vector(const SPxColId& cid) const
1026  {
1027  assert(cid.isValid());
1028  return (rep() == COLUMN)
1029  ? (*thevectors)[number(cid)]
1030  : static_cast<const SVector&>(unitVecs[number(cid)]);
1031  }
1032 
1033  /// vector associated to \p p_id.
1034  /**@return Returns a reference to the vector of the loaded LP corresponding
1035  * to \p id (with respect to the chosen representation). If \p p_id is
1036  * an id, a vector of the constraint matrix is returned, otherwise
1037  * the corresponding unit vector (of the slack variable or bound
1038  * inequality) is returned.
1039  * @todo The implementation does not exactly look like it will do
1040  * what is promised in the describtion.
1041  */
1042  const SVector& vector(const SPxId& p_id) const
1043  {
1044  assert(p_id.isValid());
1045 
1046  return p_id.isSPxRowId()
1047  ? vector(SPxRowId(p_id))
1048  : vector(SPxColId(p_id));
1049  }
1050 
1051  /// \p i 'th covector of LP.
1052  /**@return a reference to the \p i 'th, 0 <= i < #dim(), covector of
1053  * the loaded LP (with respect to the chosen representation).
1054  */
1055  const SVector& coVector(int i) const
1056  {
1057  return (*thecovectors)[i];
1058  }
1059  ///
1060  const SVector& coVector(const SPxRowId& rid) const
1061  {
1062  assert(rid.isValid());
1063  return (rep() == COLUMN)
1064  ? (*thecovectors)[number(rid)]
1065  : static_cast<const SVector&>(unitVecs[number(rid)]);
1066  }
1067  ///
1068  const SVector& coVector(const SPxColId& cid) const
1069  {
1070  assert(cid.isValid());
1071  return (rep() == ROW)
1072  ? (*thecovectors)[number(cid)]
1073  : static_cast<const SVector&>(unitVecs[number(cid)]);
1074  }
1075  /// coVector associated to \p p_id.
1076  /**@return a reference to the covector of the loaded LP
1077  * corresponding to \p p_id (with respect to the chosen
1078  * representation). If \p p_id is a coid, a covector of the constraint
1079  * matrix is returned, otherwise the corresponding unit vector is
1080  * returned.
1081  */
1082  const SVector& coVector(const SPxId& p_id) const
1083  {
1084  assert(p_id.isValid());
1085  return p_id.isSPxRowId()
1086  ? coVector(SPxRowId(p_id))
1087  : coVector(SPxColId(p_id));
1088  }
1089  /// return \p i 'th unit vector.
1090  const SVector& unitVector(int i) const
1091  {
1092  return unitVecs[i];
1093  }
1094  //@}
1095 
1096  //------------------------------------
1097  /**@name Variable status
1098  * The Simplex basis assigns a \ref soplex::SPxBasis::Desc::Status
1099  * "Status" to each variable and covariable. Depending on the
1100  * representation, the status indicates that the corresponding
1101  * vector is in the basis matrix or not.
1102  */
1103  //@{
1104  /// Status of \p i 'th variable.
1105  SPxBasis::Desc::Status varStatus(int i) const
1106  {
1107  return desc().status(i);
1108  }
1109 
1110  /// Status of \p i 'th covariable.
1111  SPxBasis::Desc::Status covarStatus(int i) const
1112  {
1113  return desc().coStatus(i);
1114  }
1115 
1116  /// does \p stat describe a basic index ?
1117  bool isBasic(SPxBasis::Desc::Status stat) const
1118  {
1119  return (stat * rep() > 0);
1120  }
1121 
1122  /// is the \p p_id 'th vector basic ?
1123  bool isBasic(const SPxId& p_id) const
1124  {
1125  assert(p_id.isValid());
1126  return p_id.isSPxRowId()
1127  ? isBasic(SPxRowId(p_id))
1128  : isBasic(SPxColId(p_id));
1129  }
1130 
1131  /// is the \p rid 'th vector basic ?
1132  bool isBasic(const SPxRowId& rid) const
1133  {
1134  return isBasic(desc().rowStatus(number(rid)));
1135  }
1136 
1137  /// is the \p cid 'th vector basic ?
1138  bool isBasic(const SPxColId& cid) const
1139  {
1140  return isBasic(desc().colStatus(number(cid)));
1141  }
1142 
1143  /// is the \p i 'th row vector basic ?
1144  bool isRowBasic(int i) const
1145  {
1146  return isBasic(desc().rowStatus(i));
1147  }
1148 
1149  /// is the \p i 'th column vector basic ?
1150  bool isColBasic(int i) const
1151  {
1152  return isBasic(desc().colStatus(i));
1153  }
1154 
1155  /// is the \p i 'th vector basic ?
1156  bool isBasic(int i) const
1157  {
1158  return isBasic(desc().status(i));
1159  }
1160 
1161  /// is the \p i 'th covector basic ?
1162  bool isCoBasic(int i) const
1163  {
1164  return isBasic(desc().coStatus(i));
1165  }
1166  //@}
1167 
1168  /// feasibility vector.
1169  /** This method return the \em feasibility vector. If it satisfies its
1170  * bound, the basis is called feasible (independently of the chosen
1171  * representation). The feasibility vector has dimension #dim().
1172  *
1173  * For the entering Simplex, #fVec is kept within its bounds. In
1174  * contrast to this, the pricing of the leaving Simplex selects an
1175  * element of #fVec, that violates its bounds.
1176  */
1177  UpdateVector& fVec() const
1178  {
1179  return *theFvec;
1180  }
1181  /// right-hand side vector for \ref soplex::SPxSolver::fVec "fVec"
1182  /** The feasibility vector is computed by solving a linear system with the
1183  * basis matrix. The right-hand side vector of this system is referred
1184  * to as \em feasibility, \em right-hand \em side \em vector #fRhs().
1185  *
1186  * For a row basis, #fRhs() is the objective vector (ignoring shifts).
1187  * For a column basis, it is the sum of all nonbasic vectors scaled by
1188  * the factor of their bound.
1189  */
1190  const Vector& fRhs() const
1191  {
1192  return *theFrhs;
1193  }
1194  /// upper bound for \ref soplex::SPxSolver::fVec "fVec".
1195  const Vector& ubBound() const
1196  {
1197  return theUBbound;
1198  }
1199  /// upper bound for #fVec, writable.
1200  /** This method returns the upper bound for the feasibility vector.
1201  * It may only be called for the #ENTER%ing Simplex.
1202  *
1203  * For the #ENTER%ing Simplex algorithms, the feasibility vector is
1204  * maintained to fullfill its bounds. As #fVec itself, also its
1205  * bounds depend on the chosen representation. Further, they may
1206  * need to be shifted (see below).
1207  */
1208  Vector& ubBound()
1209  {
1210  return theUBbound;
1211  }
1212  /// lower bound for \ref soplex::SPxSolver::fVec "fVec".
1213  const Vector& lbBound() const
1214  {
1215  return theLBbound;
1216  }
1217  /// lower bound for #fVec, writable.
1218  /** This method returns the lower bound for the feasibility vector.
1219  * It may only be called for the #ENTER%ing Simplex.
1220  *
1221  * For the #ENTER%ing Simplex algorithms, the feasibility vector is
1222  * maintained to fullfill its bounds. As #fVec itself, also its
1223  * bound depend on the chosen representation. Further, they may
1224  * need to be shifted (see below).
1225  */
1226  Vector& lbBound()
1227  {
1228  return theLBbound;
1229  }
1230 
1231  /// Violations of \ref soplex::SPxSolver::fVec "fVec"
1232  /** For the leaving Simplex algorithm, pricing involves selecting a
1233  * variable from #fVec that violates its bounds that is to leave
1234  * the basis. When a SPxPricer is called to select such a
1235  * leaving variable, #fTest() contains the vector of violations:
1236  * For #fTest()[i] < 0, the \c i 'th basic variable violates one of
1237  * its bounds by the given value. Otherwise no bound is violated.
1238  */
1239  const Vector& fTest() const
1240  {
1241  assert(type() == LEAVE);
1242  return theCoTest;
1243  }
1244 
1245  /// copricing vector.
1246  /** The copricing vector #coPvec along with the pricing vector
1247  * #pVec are used for pricing in the #ENTER%ing Simplex algorithm,
1248  * i.e. one variable is selected, that violates its bounds. In
1249  * contrast to this, the #LEAVE%ing Simplex algorithm keeps both
1250  * vectors within their bounds.
1251  */
1252  UpdateVector& coPvec() const
1253  {
1254  return *theCoPvec;
1255  }
1256 
1257  /// Right-hand side vector for \ref soplex::SPxSolver::coPvec "coPvec".
1258  /** The vector #coPvec is computed by solving a linear system with the
1259  * basis matrix and #coPrhs as the right-hand side vector. For
1260  * column basis representation, #coPrhs is build up of the
1261  * objective vector elements of all basic variables. For a row
1262  * basis, it consists of the thight bounds of all basic
1263  * constraints.
1264  */
1265  const Vector& coPrhs() const
1266  {
1267  return *theCoPrhs;
1268  }
1269 
1270  ///
1271  const Vector& ucBound() const
1272  {
1273  assert(theType == LEAVE);
1274  return *theCoUbound;
1275  }
1276  /// upper bound for #coPvec.
1277  /** This method returns the upper bound for #coPvec. It may only be
1278  * called for the leaving Simplex algorithm.
1279  *
1280  * For the leaving Simplex algorithms #coPvec is maintained to
1281  * fullfill its bounds. As #coPvec itself, also its bound depend
1282  * on the chosen representation. Further, they may need to be
1283  * shifted (see below).
1284  */
1285  Vector& ucBound()
1286  {
1287  assert(theType == LEAVE);
1288  return *theCoUbound;
1289  }
1290 
1291  ///
1292  const Vector& lcBound() const
1293  {
1294  assert(theType == LEAVE);
1295  return *theCoLbound;
1296  }
1297  /// lower bound for #coPvec.
1298  /** This method returns the lower bound for #coPvec. It may only be
1299  * called for the leaving Simplex algorithm.
1300  *
1301  * For the leaving Simplex algorithms #coPvec is maintained to
1302  * fullfill its bounds. As #coPvec itself, also its bound depend
1303  * on the chosen representation. Further, they may need to be
1304  * shifted (see below).
1305  */
1306  Vector& lcBound()
1307  {
1308  assert(theType == LEAVE);
1309  return *theCoLbound;
1310  }
1311 
1312  /// violations of \ref soplex::SPxSolver::coPvec "coPvec".
1313  /** In entering Simplex pricing selects checks vectors #coPvec()
1314  * and #pVec() for violation of its bounds. #coTest() contains
1315  * the violations for #coPvec() which are indicated by a negative
1316  * value. That is, if #coTest()[i] < 0, the \p i 'th element of #coPvec()
1317  * is violated by -#coTest()[i].
1318  */
1319  const Vector& coTest() const
1320  {
1321  assert(type() == ENTER);
1322  return theCoTest;
1323  }
1324  /// pricing vector.
1325  /** The pricing vector #pVec is the product of #coPvec with the
1326  * constraint matrix. As #coPvec, also #pVec is maintained within
1327  * its bound for the leaving Simplex algorithm, while the bounds
1328  * are tested for the entering Simplex. #pVec is of dimension
1329  * #coDim(). Vector #pVec() is only up to date for #LEAVE%ing
1330  * Simplex or #FULL pricing in #ENTER%ing Simplex.
1331  */
1332  UpdateVector& pVec() const
1333  {
1334  return *thePvec;
1335  }
1336  ///
1337  const Vector& upBound() const
1338  {
1339  assert(theType == LEAVE);
1340  return *theUbound;
1341  }
1342  /// upper bound for #pVec.
1343  /** This method returns the upper bound for #pVec. It may only be
1344  * called for the leaving Simplex algorithm.
1345  *
1346  * For the leaving Simplex algorithms #pVec is maintained to
1347  * fullfill its bounds. As #pVec itself, also its bound depend
1348  * on the chosen representation. Further, they may need to be
1349  * shifted (see below).
1350  */
1351  Vector& upBound()
1352  {
1353  assert(theType == LEAVE);
1354  return *theUbound;
1355  }
1356 
1357  ///
1358  const Vector& lpBound() const
1359  {
1360  assert(theType == LEAVE);
1361  return *theLbound;
1362  }
1363  /// lower bound for #pVec.
1364  /** This method returns the lower bound for #pVec. It may only be
1365  * called for the leaving Simplex algorithm.
1366  *
1367  * For the leaving Simplex algorithms #pVec is maintained to
1368  * fullfill its bounds. As #pVec itself, also its bound depend
1369  * on the chosen representation. Further, they may need to be
1370  * shifted (see below).
1371  */
1372  Vector& lpBound()
1373  {
1374  assert(theType == LEAVE);
1375  return *theLbound;
1376  }
1377 
1378  /// Violations of \ref soplex::SPxSolver::pVec "pVec".
1379  /** In entering Simplex pricing selects checks vectors #coPvec()
1380  * and #pVec() for violation of its bounds. Vector #test()
1381  * contains the violations for #pVec(), i.e., if #test()[i] < 0,
1382  * the i'th element of #pVec() is violated by #test()[i].
1383  * Vector #test() is only up to date for #FULL pricing.
1384  */
1385  const Vector& test() const
1386  {
1387  assert(type() == ENTER);
1388  return theTest;
1389  }
1390 
1391  /// compute and return \ref soplex::SPxSolver::pVec() "pVec()"[i].
1392  Real computePvec(int i);
1393  /// compute entire \ref soplex::SPxSolver::pVec() "pVec()".
1394  void computePvec();
1395  /// compute and return \ref soplex::SPxSolver::test() "test()"[i] in \ref soplex::SPxSolver::ENTER "ENTER"ing Simplex.
1396  Real computeTest(int i);
1397  /// compute test vector in \ref soplex::SPxSolver::ENTER "ENTER"ing Simplex.
1398  void computeTest();
1399 
1400  //------------------------------------
1401  /**@name Shifting
1402  * The task of the ratio test (implemented in SPxRatioTester classes)
1403  * is to select a variable for the basis update, such that the basis
1404  * remains priced (i.e. both, the pricing and copricing vectors satisfy
1405  * their bounds) or feasible (i.e. the feasibility vector satisfies its
1406  * bounds). However, this can lead to numerically instable basis matrices
1407  * or -- after accumulation of various errors -- even to a singular basis
1408  * matrix.
1409  *
1410  * The key to overcome this problem is to allow the basis to become "a
1411  * bit" infeasible or unpriced, in order provide a better choice for the
1412  * ratio test to select a stable variable. This is equivalent to enlarging
1413  * the bounds by a small amount. This is referred to as \em shifting.
1414  *
1415  * These methods serve for shifting feasibility bounds, either in order
1416  * to maintain numerical stability or initially for computation of
1417  * phase 1. The sum of all shifts applied to any bound is stored in
1418  * \ref soplex::SPxSolver::theShift "theShift".
1419  *
1420  * The following methods are used to shift individual bounds. They are
1421  * mainly intended for stable implenentations of SPxRatioTester.
1422  */
1423  //@{
1424  /// Perform initial shifting to optain an feasible or pricable basis.
1425  void shiftFvec();
1426  /// Perform initial shifting to optain an feasible or pricable basis.
1427  void shiftPvec();
1428 
1429  /// shift \p i 'th \ref soplex::SPxSolver::ubBound "ubBound" to \p to.
1430  void shiftUBbound(int i, Real to)
1431  {
1432  assert(theType == ENTER);
1433  theShift += to - theUBbound[i];
1434  theUBbound[i] = to;
1435  }
1436  /// shift \p i 'th \ref soplex::SPxSolver::lbBound "lbBound" to \p to.
1437  void shiftLBbound(int i, Real to)
1438  {
1439  assert(theType == ENTER);
1440  theShift += theLBbound[i] - to;
1441  theLBbound[i] = to;
1442  }
1443  /// shift \p i 'th \ref soplex::SPxSolver::upBound "upBound" to \p to.
1444  void shiftUPbound(int i, Real to)
1445  {
1446  assert(theType == LEAVE);
1447  theShift += to - (*theUbound)[i];
1448  (*theUbound)[i] = to;
1449  }
1450  /// shift \p i 'th \ref soplex::SPxSolver::lpBound "lpBound" to \p to.
1451  void shiftLPbound(int i, Real to)
1452  {
1453  assert(theType == LEAVE);
1454  theShift += (*theLbound)[i] - to;
1455  (*theLbound)[i] = to;
1456  }
1457  /// shift \p i 'th \ref soplex::SPxSolver::ucBound "ucBound" to \p to.
1458  void shiftUCbound(int i, Real to)
1459  {
1460  assert(theType == LEAVE);
1461  theShift += to - (*theCoUbound)[i];
1462  (*theCoUbound)[i] = to;
1463  }
1464  /// shift \p i 'th \ref soplex::SPxSolver::lcBound "lcBound" to \p to.
1465  void shiftLCbound(int i, Real to)
1466  {
1467  assert(theType == LEAVE);
1468  theShift += (*theCoLbound)[i] - to;
1469  (*theCoLbound)[i] = to;
1470  }
1471  ///
1472  void testBounds() const;
1473 
1474  /// total current shift amount.
1475  virtual Real shift() const
1476  {
1477  return theShift;
1478  }
1479  /// remove shift as much as possible.
1480  virtual void unShift(void);
1481 
1482  /// get violation of constraints.
1483  virtual void qualConstraintViolation(Real& maxviol, Real& sumviol) const;
1484  /// get violations of bounds.
1485  virtual void qualBoundViolation(Real& maxviol, Real& sumviol) const;
1486  /// get the residuum |Ax-b|.
1487  virtual void qualSlackViolation(Real& maxviol, Real& sumviol) const;
1488  /// get violation of optimality criterion.
1489  virtual void qualRedCostViolation(Real& maxviol, Real& sumviol) const;
1490  //@}
1491 
1492 private:
1493 
1494  //------------------------------------
1495  /**@name Perturbation */
1496  //@{
1497  ///
1498  void perturbMin(
1499  const UpdateVector& vec, Vector& low, Vector& up, Real eps, Real delta,
1500  int start = 0, int incr = 1);
1501  ///
1502  void perturbMax(
1503  const UpdateVector& vec, Vector& low, Vector& up, Real eps, Real delta,
1504  int start = 0, int incr = 1);
1505  ///
1506  Real perturbMin(const UpdateVector& uvec,
1507  Vector& low, Vector& up, Real eps, Real delta,
1508  const SPxBasis::Desc::Status* stat, int start, int incr) const;
1509  ///
1510  Real perturbMax(const UpdateVector& uvec,
1511  Vector& low, Vector& up, Real eps, Real delta,
1512  const SPxBasis::Desc::Status* stat, int start, int incr) const;
1513  //@}
1514 
1515  //------------------------------------
1516  /**@name The Simplex Loop
1517  * We now present a set of methods that may be usefull when implementing
1518  * own SPxPricer or SPxRatioTester classes. Here is, how
1519  * SPxSolver will call methods from its loaded SPxPricer and
1520  * SPxRatioTester.
1521  *
1522  * For the entering Simplex:
1523  * -# \ref soplex::SPxPricer::selectEnter() "SPxPricer::selectEnter()"
1524  * -# \ref soplex::SPxRatioTester::selectLeave() "SPxRatioTester::selectLeave()"
1525  * -# \ref soplex::SPxPricer::entered4() "SPxPricer::entered4()"
1526  *
1527  * For the leaving Simplex:
1528  * -# \ref soplex::SPxPricer::selectLeave() "SPxPricer::selectLeave()"
1529  * -# \ref soplex::SPxRatioTester::selectEnter() "SPxRatioTester::selectEnter()"
1530  * -# \ref soplex::SPxPricer::left4() "SPxPricer::left4()"
1531  */
1532  //@{
1533 public:
1534  /// Setup vectors to be solved within Simplex loop.
1535  /** Load vector \p y to be #solve%d with the basis matrix during the
1536  * #LEAVE Simplex. The system will be solved after #SPxSolver%'s call
1537  * to SPxRatioTester. The system will be solved along with
1538  * another system. Solving two linear system at a time has
1539  * performance advantages over solving the two linear systems
1540  * seperately.
1541  */
1542  void setup4solve(SSVector* p_y, SSVector* p_rhs)
1543  {
1544  assert(type() == LEAVE);
1545  solveVector2 = p_y;
1546  solveVector2rhs = p_rhs;
1547  }
1548  /// Setup vectors to be solved within Simplex loop.
1549  /** Load a second additional vector \p y2 to be #solve%d with the
1550  * basis matrix during the #LEAVE Simplex. The system will be
1551  * solved after #SPxSolver%'s call to SPxRatioTester.
1552  * The system will be solved along with at least one
1553  * other system. Solving several linear system at a time has
1554  * performance advantages over solving them seperately.
1555  */
1556  void setup4solve2(SSVector* p_y2, SSVector* p_rhs2)
1557  {
1558  assert(type() == LEAVE);
1559  solveVector3 = p_y2;
1560  solveVector3rhs = p_rhs2;
1561  }
1562  /// Setup vectors to be cosolved within Simplex loop.
1563  /** Load vector \p y to be #coSolve%d with the basis matrix during
1564  * the #ENTER Simplex. The system will be solved after #SPxSolver%'s
1565  * call to SPxRatioTester. The system will be solved along
1566  * with another system. Solving two linear system at a time has
1567  * performance advantages over solving the two linear systems
1568  * seperately.
1569  */
1570  void setup4coSolve(SSVector* p_y, SSVector* p_rhs)
1571  {
1572  assert(type() == ENTER);
1573  coSolveVector2 = p_y;
1574  coSolveVector2rhs = p_rhs;
1575  }
1576  /// Setup vectors to be cosolved within Simplex loop.
1577  /** Load a second vector \p z to be #coSolve%d with the basis matrix during
1578  * the #ENTER Simplex. The system will be solved after #SPxSolver%'s
1579  * call to SPxRatioTester. The system will be solved along
1580  * with two other systems.
1581  */
1582  void setup4coSolve2(SSVector* p_z, SSVector* p_rhs)
1583  {
1584  assert(type() == ENTER);
1585  coSolveVector3 = p_z;
1586  coSolveVector3rhs = p_rhs;
1587  }
1588 
1589  /// maximal infeasibility of basis
1590  /** This method is called before concluding optimality. Since it is
1591  * possible that some stable implementation of class
1592  * SPxRatioTester yielded a slightly infeasible (or unpriced)
1593  * basis, this must be checked before terminating with an optimal
1594  * solution.
1595  */
1596  virtual Real maxInfeas() const;
1597 
1598  /// Return current basis.
1599  /**@note The basis can be used to solve linear systems or use
1600  * any other of its (const) methods. It is, however, encuraged
1601  * to use methods #setup4solve() and #setup4coSolve() for solving
1602  * systems, since this is likely to have perfomance advantages.
1603  */
1604  const SPxBasis& basis() const
1605  {
1606  return *this;
1607  }
1608  ///
1609  SPxBasis& basis()
1610  {
1611  return *this;
1612  }
1613  /// return loaded SPxPricer.
1614  const SPxPricer* pricer() const
1615  {
1616  return thepricer;
1617  }
1618  /// return loaded SLinSolver.
1619  const SLinSolver* slinSolver() const
1620  {
1622  }
1623  /// return loaded SPxRatioTester.
1624  const SPxRatioTester* ratiotester() const
1625  {
1627  }
1628 
1629  /// Factorize basis matrix.
1630  /// @throw SPxStatusException if loaded matrix is singular
1631  virtual void factorize();
1632 
1633 private:
1634 
1635  /** let index \p i leave the basis and manage entering of another one.
1636  @returns \c false if LP is unbounded/infeasible. */
1637  bool leave(int i);
1638  /** let id enter the basis and manage leaving of another one.
1639  @returns \c false if LP is unbounded/infeasible. */
1640  bool enter(SPxId& id);
1641 
1642  /// test coVector \p i with status \p stat.
1643  Real coTest(int i, SPxBasis::Desc::Status stat) const;
1644  /// compute coTest vector.
1645  void computeCoTest();
1646  /// recompute coTest vector.
1647  void updateCoTest();
1648 
1649  /// test vector \p i with status \p stat.
1650  Real test(int i, SPxBasis::Desc::Status stat) const;
1651  /// recompute test vector.
1652  void updateTest();
1653 
1654  /// compute basis feasibility test vector.
1655  void computeFtest();
1656  /// update basis feasibility test vector.
1657  void updateFtest();
1658 
1659  //@}
1660 
1661  //------------------------------------
1662  /**@name Parallelization
1663  * In this section we present the methods, that are provided in order to
1664  * allow a parallel version to be implemented as a derived class, thereby
1665  * inheriting most of the code of SPxSolver.
1666  *
1667  * @par Initialization
1668  * These methods are used to setup all the vectors used in the Simplex
1669  * loop, that where described in the previous sectios.
1670  */
1671  //@{
1672 public:
1673  /// intialize data structures.
1674  /** If SPxSolver is not \ref isInitialized() "initialized", the method
1675  * #solve() calls #init() to setup all vectors and internal data structures.
1676  * Most of the other methods within this section are called by #init().
1677  *
1678  * Derived classes should add the initialization of additional
1679  * data structures by overriding this method. Don't forget,
1680  * however, to call SPxSolver::init().
1681  */
1682  virtual void init();
1683 
1684 protected:
1685 
1686  /// has the internal data been initialized?
1687  /** As long as an instance of SPxSolver is not initialized, no member
1688  * contains setup data. Initialization is performed via method
1689  * #init(). Afterwards all data structures are kept up to date (even
1690  * for all manipulation methods), until #unInit() is called. However,
1691  * some manipulation methods call #unInit() themselfs.
1692  */
1693  bool isInitialized() const
1694  {
1695  return initialized;
1696  }
1697 
1698  /// resets clock average statistics
1699  void resetClockStats();
1700 
1701  /// uninitialize data structures.
1702  virtual void unInit()
1703  {
1704  initialized = false;
1705  }
1706  /// setup all vecs fresh
1707  virtual void reinitializeVecs();
1708  /// reset dimensions of vectors according to loaded LP.
1709  virtual void reDim();
1710  /// compute feasibility vector from scratch.
1711  void computeFrhs();
1712  ///
1713  virtual void computeFrhsXtra();
1714  ///
1715  virtual void computeFrhs1(const Vector&, const Vector&);
1716  ///
1717  void computeFrhs2(const Vector&, const Vector&);
1718  /// compute \ref soplex::SPxSolver::theCoPrhs "theCoPrhs" for entering Simplex.
1719  virtual void computeEnterCoPrhs();
1720  ///
1721  void computeEnterCoPrhs4Row(int i, int n);
1722  ///
1723  void computeEnterCoPrhs4Col(int i, int n);
1724  /// compute \ref soplex::SPxSolver::theCoPrhs "theCoPrhs" for leaving Simplex.
1725  virtual void computeLeaveCoPrhs();
1726  ///
1727  void computeLeaveCoPrhs4Row(int i, int n);
1728  ///
1729  void computeLeaveCoPrhs4Col(int i, int n);
1730 
1731  /// Compute part of objective value.
1732  /** This method is called from #value() in order to compute the part of
1733  * the objective value resulting form nonbasic variables for #COLUMN
1734  * Representation.
1735  */
1736  Real nonbasicValue();
1737 
1738  /// Get pointer to the \p id 'th vector
1739  virtual const SVector* enterVector(const SPxId& p_id)
1740  {
1741  assert(p_id.isValid());
1742  return p_id.isSPxRowId()
1743  ? &vector(SPxRowId(p_id)) : &vector(SPxColId(p_id));
1744  }
1745  ///
1746  virtual void getLeaveVals(int i,
1747  SPxBasis::Desc::Status& leaveStat, SPxId& leaveId,
1748  Real& leaveMax, Real& leavebound, int& leaveNum, Real& objChange);
1749  ///
1750  virtual void getLeaveVals2(Real leaveMax, SPxId enterId,
1751  Real& enterBound, Real& newUBbound,
1752  Real& newLBbound, Real& newCoPrhs, Real& objChange);
1753  ///
1754  virtual void getEnterVals(SPxId id, Real& enterTest,
1755  Real& enterUB, Real& enterLB, Real& enterVal, Real& enterMax,
1756  Real& enterPric, SPxBasis::Desc::Status& enterStat, Real& enterRO, Real& objChange);
1757  ///
1758  virtual void getEnterVals2(int leaveIdx,
1759  Real enterMax, Real& leaveBound, Real& objChange);
1760  ///
1761  virtual void ungetEnterVal(SPxId enterId, SPxBasis::Desc::Status enterStat,
1762  Real leaveVal, const SVector& vec, Real& objChange);
1763  ///
1764  virtual void rejectEnter(SPxId enterId,
1765  Real enterTest, SPxBasis::Desc::Status enterStat);
1766  ///
1767  virtual void rejectLeave(int leaveNum, SPxId leaveId,
1768  SPxBasis::Desc::Status leaveStat, const SVector* newVec = 0);
1769  ///
1770  virtual void setupPupdate(void);
1771  ///
1772  virtual void doPupdate(void);
1773  ///
1774  virtual void clearUpdateVecs(void);
1775  ///
1776  virtual void perturbMinEnter(void);
1777  /// perturb basis bounds.
1778  virtual void perturbMaxEnter(void);
1779  ///
1780  virtual void perturbMinLeave(void);
1781  /// perturb nonbasic bounds.
1782  virtual void perturbMaxLeave(void);
1783  //@}
1784 
1785  //------------------------------------
1786  /** The following methods serve for initializing the bounds for dual or
1787  * primal Simplex algorithm of entering or leaving type.
1788  */
1789  //@{
1790  ///
1792  ///
1793  void setDualColBounds();
1794  ///
1795  void setDualRowBounds();
1796  /// setup feasibility bounds for entering algorithm
1797  void setPrimalBounds();
1798  ///
1799  void setEnterBound4Col(int, int);
1800  ///
1801  void setEnterBound4Row(int, int);
1802  ///
1803  virtual void setEnterBounds();
1804  ///
1805  void setLeaveBound4Row(int i, int n);
1806  ///
1807  void setLeaveBound4Col(int i, int n);
1808  ///
1809  virtual void setLeaveBounds();
1810  //@}
1811 
1812 public:
1813 
1814  //------------------------------------
1815  /** Limits and status inquiry */
1816  //@{
1817  /// set time limit.
1818  virtual void setTerminationTime(Real time = infinity);
1819  /// return time limit.
1820  virtual Real terminationTime() const;
1821  /// set iteration limit.
1822  virtual void setTerminationIter(int iteration = -1);
1823  /// return iteration limit.
1824  virtual int terminationIter() const;
1825  /// set objective limit.
1826  virtual void setTerminationValue(Real value = infinity);
1827  /// return objective limit.
1828  virtual Real terminationValue() const;
1829  /// get objective value of current solution.
1830  virtual Real objValue()
1831  {
1832  return value();
1833  }
1834  /// get all results of last solve.
1835  Status
1836  getResult( Real* value = 0, Vector* primal = 0,
1837  Vector* slacks = 0, Vector* dual = 0,
1838  Vector* reduCost = 0);
1839 
1840 protected:
1841 
1842  /**@todo put the following basis methods near the variable status methods!*/
1843  /// converts basis status to VarStatus
1845 
1846  /// converts VarStatus to basis status for rows
1848  const;
1849 
1850  /// converts VarStatus to basis status for columns
1852  const;
1853 
1854 public:
1855 
1856  /// gets basis status for a single row
1857  VarStatus getBasisRowStatus( int row ) const;
1858 
1859  /// gets basis status for a single column
1860  VarStatus getBasisColStatus( int col ) const;
1861 
1862  /// get current basis, and return solver status.
1863  Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize = -1, const int colsSize = -1) const;
1864 
1865  /// gets basis status
1867  {
1869  }
1870 
1871  /// check a given basis for validity.
1873 
1874  /// set the lp solver's basis.
1875  void setBasis(const VarStatus rows[], const VarStatus cols[]);
1876 
1877  /// set the lp solver's basis status.
1878  void setBasisStatus( SPxBasis::SPxStatus stat )
1879  {
1881  m_status = UNKNOWN;
1882  SPxBasis::setStatus( stat );
1883  }
1884 
1885  /// get number of dual norms
1886  void getNdualNorms(int& nnormsRow, int& nnormsCol) const;
1887 
1888  /// get dual norms
1889  bool getDualNorms(int& nnormsRow, int& nnormsCol, Real* norms) const;
1890 
1891  /// set dual norms
1892  bool setDualNorms(int nnormsRow, int nnormsCol, Real* norms);
1893 
1894  /// reset cumulative time counter to zero.
1895  void resetCumulativeTime()
1896  {
1898  }
1899 
1900  /// get number of bound flips.
1901  int boundFlips() const
1902  {
1904  }
1905 
1906  /// get number of iterations of current solution.
1907  int iterations() const
1908  {
1909  return basis().iteration();
1910  }
1911 
1912  /// return number of iterations done with primal algorithm
1913  int primalIterations()
1914  {
1915  assert(iterations() == 0 || primalCount <= iterations());
1916  return (iterations() == 0) ? 0 : primalCount;
1917  }
1918 
1919  /// return number of iterations done with primal algorithm
1920  int dualIterations()
1921  {
1923  }
1924 
1925  /// time spent in last call to method solve().
1926  Real time() const
1927  {
1928  return theTime->time();
1929  }
1930 
1931  /// returns whether current time limit is reached; call to time() may be skipped unless \p forceCheck is true
1932  ///
1933  bool isTimeLimitReached(const bool forceCheck = false);
1934 
1935  /// cumulative time spent in all calls to method solve().
1936  Real cumulativeTime() const
1937  {
1939  }
1940  /// return const lp's rows if available.
1941  const LPRowSet& rows() const
1942  {
1943  return *lprowset();
1944  }
1945 
1946  /// return const lp's cols if available.
1947  const LPColSet& cols() const
1948  {
1949  return *lpcolset();
1950  }
1951 
1952  /// copy lower bound vector to \p p_low.
1953  void getLower(Vector& p_low) const
1954  {
1955  p_low = SPxLP::lower();
1956  }
1957  /// copy upper bound vector to \p p_up.
1958  void getUpper(Vector& p_up) const
1959  {
1960  p_up = SPxLP::upper();
1961  }
1962 
1963  /// copy lhs value vector to \p p_lhs.
1964  void getLhs(Vector& p_lhs) const
1965  {
1966  p_lhs = SPxLP::lhs();
1967  }
1968 
1969  /// copy rhs value vector to \p p_rhs.
1970  void getRhs(Vector& p_rhs) const
1971  {
1972  p_rhs = SPxLP::rhs();
1973  }
1974 
1975  /// optimization sense.
1976  SPxSense sense() const
1977  {
1978  return spxSense();
1979  }
1980 
1981  /// returns statistical information in form of a string.
1982  std::string statistics() const
1983  {
1984  std::stringstream s;
1985  s << basis().statistics()
1986  << "Solution time : " << std::setw(10) << std::fixed << std::setprecision(2) << time() << std::endl
1987  << "Iterations : " << std::setw(10) << iterations() << std::endl;
1988 
1989  return s.str();
1990  }
1991  //@}
1992 
1993  //------------------------------------
1994  /** Mapping between numbers and Ids */
1995  //@{
1996  /// RowId of \p i 'th inequality.
1997  SPxRowId rowId(int i) const
1998  {
1999  return rId(i);
2000  }
2001  /// ColId of \p i 'th column.
2002  SPxColId colId(int i) const
2003  {
2004  return cId(i);
2005  }
2006  //@}
2007 
2008  //------------------------------------
2009  /** Constructors / destructors */
2010  //@{
2011  /// default constructor.
2012  explicit
2013  SPxSolver( Type type = LEAVE,
2015  Timer::TYPE ttype = Timer::USER_TIME);
2016  // virtual destructor
2017  virtual ~SPxSolver();
2018  //@}
2019 
2020  //------------------------------------
2021  /** Miscellaneous */
2022  //@{
2023  /// check consistency.
2024  bool isConsistent() const;
2025  //@}
2026 
2027  //------------------------------------
2028  /** assignment operator and copy constructor */
2029  //@{
2030  /// assignment operator
2031  SPxSolver& operator=(const SPxSolver& base);
2032  /// copy constructor
2033  SPxSolver(const SPxSolver& base);
2034  //@}
2035 
2036  void testVecs();
2037 };
2038 
2039 //
2040 // Auxiliary functions.
2041 //
2042 
2043 /// Pretty-printing of variable status.
2044 std::ostream& operator<<( std::ostream& os,
2045  const SPxSolver::VarStatus& status );
2046 
2047 /// Pretty-printing of solver status.
2048 std::ostream& operator<<( std::ostream& os,
2049  const SPxSolver::Status& status );
2050 
2051 /// Pretty-printing of algorithm.
2052 std::ostream& operator<<( std::ostream& os,
2053  const SPxSolver::Type& status );
2054 
2055 /// Pretty-printing of representation.
2056 std::ostream& operator<<( std::ostream& os,
2057  const SPxSolver::Representation& status );
2058 
2059 
2060 } // namespace soplex
2061 #endif // _SPXSOLVER_H_