Scippy

SoPlex

Sequential object-oriented simPlex

spxratiotester.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-2022 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 spxratiotester.h
17  * @brief Abstract ratio test base class.
18  */
19 #ifndef _SPXRATIOTESTER_H_
20 #define _SPXRATIOTESTER_H_
21 
22 
23 #include <assert.h>
24 
25 #include "soplex/spxdefines.h"
26 #include "soplex/spxsolver.h"
27 
28 namespace soplex
29 {
30 
31 /**@brief Abstract ratio test base class.
32  @ingroup Algo
33 
34  Class SPxRatioTester is the virtual base class for computing the ratio
35  test within the Simplex algorithm driven by SoPlex. After a SoPlex
36  solver has been #load()%ed to an SPxRatioTester, the solver calls
37  #selectLeave() for computing the ratio test for the entering simplex and
38  #selectEnter() for computing the ratio test in leaving simplex.
39 */
40 template <class R>
42 {
43 protected:
44 
45  //-------------------------------------
46  /**@name Data */
47  ///@{
48  /// the solver
50  /// name of the ratio tester
51  const char* m_name;
52  /// internal storage of type
54  /// allowed bound violation
55  R delta;
56  ///@}
57 
58 public:
59 
60  //-------------------------------------
61  /**@name Access / modification */
62  ///@{
63  /// get name of ratio tester.
64  virtual const char* getName() const
65  {
66  return m_name;
67  }
68  /// loads LP.
69  /** Load the solver and LP for which pricing steps are to be performed.
70  */
71  virtual void load(SPxSolverBase<R>* p_solver)
72  {
73  thesolver = p_solver;
74  }
75 
76  /// unloads LP.
77  virtual void clear()
78  {
79  thesolver = nullptr;
80  }
81 
82  /// returns loaded LP solver.
83  virtual SPxSolverBase<R>* solver() const
84  {
85  return thesolver;
86  }
87 
88  /// set allowed bound violation
89  virtual void setDelta(R newDelta)
90  {
91  if(newDelta <= DEFAULT_EPS_ZERO)
92  delta = DEFAULT_EPS_ZERO;
93  else
94  delta = newDelta;
95  }
96 
97  /// get allowed bound violation
98  virtual R getDelta()
99  {
100  return delta;
101  }
102  ///@}
103 
104  //-------------------------------------
105  /**@name Entering / leaving */
106  ///@{
107  /// selects index to leave the basis.
108  /** Method #selectLeave() is called by the loaded SoPlex solver when
109  computing the entering simplex algorithm. Its task is to select and
110  return the index of the basis variable that is to leave the basis.
111  When being called,
112  \ref SPxSolverBase<R>::fVec() "fVec()" fullfills the basic bounds
113  \ref SPxSolverBase<R>::lbBound() "lbBound()" and
114  \ref SPxSolverBase<R>::ubBound() "ubBound()" within
115  \ref SPxSolverBase<R>::entertol() "entertol()".
116  fVec().delta() is the vector by
117  which fVec() will be updated in this simplex step. Its nonzero
118  indices are stored in sorted order in fVec().idx().
119 
120  If \p val > 0, \p val is the maximum allowed update value for fVec(),
121  otherwise the minimum. Method #selectLeave() must chose \p val of the
122  same sign as passed, such that updating fVec() by \p val yields a
123  new vector that satisfies all basic bounds (within entertol). The
124  returned index, must be the index of an element of fVec(), that
125  reaches one of its bounds with this update.
126  */
127  virtual int selectLeave(R& val, R enterTest, bool polish = false) = 0;
128 
129  /// selects variable Id to enter the basis.
130  /** Method #selectEnter() is called by the loaded SoPlex solver, when
131  computing the leaving simplex algorithm. It's task is to select and
132  return the Id of the basis variable that is to enter the basis.
133  When being called,
134  \ref SPxSolverBase<R>::pVec() "pVec()" fullfills the bounds
135  \ref SPxSolverBase<R>::lbBound() "lbBound()" and
136  \ref SPxSolverBase<R>::ubBound() "ubBound()" within
137  \ref SPxSolverBase<R>::leavetol() "leavetol()".
138  Similarly,
139  \ref SPxSolverBase<R>::coPvec() "coPvec()" fulfills the bounds
140  \ref SPxSolverBase<R>::lbBound() "lbBound()" and
141  \ref SPxSolverBase<R>::ubBound() "ubBound()" within
142  \ref SPxSolverBase<R>::leavetol() "leavetol()".
143  pVec().delta() and coPvec().delta() are
144  the vectors by which pVec() and coPvec() will be updated in this
145  simplex step. Their nonzero indices are stored in sorted order in
146  pVec().idx() and coPvec().idx().
147 
148  If \p val > 0, \p val is the maximum allowed update value for pVec()
149  and coPvec(), otherwise the minimum. Method #selectEnter() must
150  chose \p val of the same sign as passed, such that updating pVec()
151  and coPvec() by \p val yields a new vector that satisfies all basic
152  bounds (within leavetol). The returned Id must be the Id of an
153  element of pVec() or coPvec(), that reaches one of its bounds
154  with this update.
155  */
156  virtual SPxId selectEnter(R& val, int leaveIdx, bool polish = false) = 0;
157 
158  /// sets Simplex type.
159  /** Informs pricer about (a change of) the loaded SoPlex's Type. In
160  the sequel, only the corresponding select methods may be called.
161  */
162  virtual void setType(typename SPxSolverBase<R>::Type)
163  {}
164  ///@}
165 
166  //-------------------------------------
167  /**@name Construction / destruction */
168  ///@{
169  /// default constructor
170  explicit SPxRatioTester(const char* name)
171  : thesolver(0)
172  , m_name(name)
173  , m_type(SPxSolverBase<R>::LEAVE)
174  , delta(1e-6)
175  {}
176  /// copy constructor
178  : thesolver(old.thesolver)
179  , m_name(old.m_name)
180  , m_type(old.m_type)
181  , delta(old.delta)
182  {}
183  /// assignment operator
185  {
186  if(this != &rhs)
187  {
188  m_name = rhs.m_name;
189  thesolver = rhs.thesolver;
190  m_type = rhs.m_type;
191  delta = rhs.delta;
192  }
193 
194  return *this;
195  }
196  /// destructor.
197  virtual ~SPxRatioTester()
198  {
199  thesolver = nullptr;
200  m_name = nullptr;
201  }
202  /// clone function for polymorphism
203  virtual SPxRatioTester* clone() const = 0;
204  ///@}
205 
206 };
207 
208 
209 } // namespace soplex
210 #endif // _SPXRATIOTESTER_H_
virtual SPxId selectEnter(R &val, int leaveIdx, bool polish=false)=0
selects variable Id to enter the basis.
virtual int selectLeave(R &val, R enterTest, bool polish=false)=0
selects index to leave the basis.
virtual void load(SPxSolverBase< R > *p_solver)
loads LP.
R delta
allowed bound violation
SPxRatioTester(const SPxRatioTester &old)
copy constructor
Sequential object-oriented SimPlex.SPxSolverBase is an LP solver class using the revised Simplex algo...
Definition: spxbasis.h:49
virtual R getDelta()
get allowed bound violation
virtual void setType(typename SPxSolverBase< R >::Type)
sets Simplex type.
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
virtual SPxSolverBase< R > * solver() const
returns loaded LP solver.
virtual SPxRatioTester * clone() const =0
clone function for polymorphism
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
virtual ~SPxRatioTester()
destructor.
virtual void setDelta(R newDelta)
set allowed bound violation
main LP solver class
#define DEFAULT_EPS_ZERO
default allowed additive zero: 1.0 + EPS_ZERO == 1.0
Definition: spxdefines.h:268
const char * m_name
name of the ratio tester
SPxRatioTester & operator=(const SPxRatioTester &rhs)
assignment operator
SPxRatioTester(const char *name)
default constructor
virtual const char * getName() const
get name of ratio tester.
Debugging, floating point type and parameter definitions.
Everything should be within this namespace.
SPxSolverBase< R >::Type m_type
internal storage of type
SPxSolverBase< R > * thesolver
the solver
virtual void clear()
unloads LP.
Type
Algorithmic type.
Definition: spxsolver.h:135