SoPlex Doxygen Documentation
spxpricer.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-2012 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 
17 /**@file spxpricer.h
18  * @brief Abstract pricer base class.
19  */
20 #ifndef _SPXPRICE_H_
21 #define _SPXPRICE_H_
22 
23 #include <assert.h>
24 
25 #include "spxdefines.h"
26 #include "spxsolver.h"
27 
28 #define MAX_PRICING_CANDIDATES 8
29 #define IMPROVEMENT_STEPLENGTH 20
30 #define IMPROVEMENT_THRESHOLD 1
31 
32 namespace soplex
33 {
34 
35 /**@brief Abstract pricer base class.
36  @ingroup Algo
37 
38  Class SPxPricer is a pure virtual class defining the interface for pricer
39  classes to be used by SoPlex. The pricer's task is to select a vector to
40  enter or leave the simplex basis, depending on the chosen simplex type.
41 
42  An SPxPricer first #load%s the SoPlex object for which pricing is to
43  be performed. Then, depending of the SPxSolver::Type, methods
44  #selectEnter() and #entered4() (for entering Simplex) or #selectLeave()
45  and #left4() (for leaving Simplex) are called by SoPlex. The SPxPricer
46  object is informed of a change of the SPxSolver::Type by calling method
47  #setType().
48 */
49 class SPxPricer
50 {
51 protected:
52 
53  //-------------------------------------
54  /**@name Data */
55  //@{
56  /// name of the pricer
57  const char* m_name;
58  /// the solver
60  /// violation bound
62  //@}
63 
64 public:
65 
66  //-------------------------------------
67  /**@name Initialization */
68  //@{
69  /// get name of pricer.
70  virtual const char* getName() const
71  {
72  return m_name;
73  }
74 
75  /// loads LP.
76  /** Loads the solver and LP for which pricing steps are to be performed.
77  */
78  virtual void load(SPxSolver* p_solver)
79  {
80  thesolver = p_solver;
81  }
82 
83  /// unloads LP.
84  virtual void clear()
85  {
86  thesolver = 0;
87  }
88 
89  /// returns loaded SPxSolver object.
90  virtual SPxSolver* solver() const
91  {
92  return thesolver;
93  }
94 
95  /// returns violation bound \ref soplex::SPxPricer::theeps "theeps".
96  virtual Real epsilon() const
97  {
98  return theeps;
99  }
100 
101  /// sets violation bound.
102  /** Inequality violations are accepted, if their size is less than \p eps.
103  */
104  virtual void setEpsilon(Real eps)
105  {
106  assert(eps >= 0.0);
107 
108  theeps = eps;
109  }
110 
111  /// sets pricing type.
112  /** Informs pricer about (a change of) the loaded SoPlex's Type. In
113  the sequel, only the corresponding select methods may be called.
114  */
115  virtual void setType(SPxSolver::Type)
116  {}
117 
118  /// sets basis representation.
119  /** Informs pricer about (a change of) the loaded SoPlex's
120  Representation.
121  */
123  {}
124  //@}
125 
126  //-------------------------------------
127  /**@name Pivoting */
128  //@{
129  /// returns selected index to leave basis.
130  /** Selects the index of a vector to leave the basis. The selected index
131  i, say, must be in the range 0 <= i < solver()->dim() and its
132  tested value must fullfill solver()->test()[i] < -#epsilon().
133  */
134  virtual int selectLeave() = 0;
135 
136  /// performs leaving pivot.
137  /** Method #left4() is called after each simplex iteration in LEAVE
138  mode. It informs the SPxPricer that the \p n 'th variable has left
139  the basis for \p id to come in at this position. When being called,
140  all vectors of SoPlex involved in such an entering update are
141  setup correctly and may be accessed via the corresponding methods
142  (\ref SPxSolver::fVec() "fVec()", \ref SPxSolver::pVec() "pVec()",
143  etc.). In general, argument \p n will be the one returned by the
144  SPxPricer at the previous call to #selectLeave(). However, one can not
145  rely on this.
146  */
147  virtual void left4(int /*n*/, SPxId /*id*/) {}
148 
149  /// selects Id to enter basis.
150  /** Selects the SPxId of a vector to enter the basis. The selected
151  id, must not represent a basic index (i.e. solver()->isBasic(id) must
152  be false). However, the corresponding test value needs not to be less
153  than -#epsilon(). If not, SoPlex will discard the pivot.
154 
155  Note:
156  When method #selectEnter() is called by the loaded SoPlex
157  object, all values from \ref SPxSolver::coTest() "coTest()" are
158  up to date. However, whether the elements of
159  \ref SPxSolver::test() "test()" are up to date depends on the
160  SPxSolver::Pricing type.
161  */
162  virtual SPxId selectEnter() = 0;
163 
164  /// performs entering pivot.
165  /** Method #entered4() is called after each simplex iteration in ENTER
166  mode. It informs the SPxPricer that variable \p id has entered
167  at the \p n 'th position. When being called, all vectors of SoPlex
168  involved in such an entering update are setup correctly and may be
169  accessed via the corresponding methods
170  (\ref SPxSolver::fVec() "fVec()", \ref SPxSolver::pVec() "pVec()",
171  etc.). In general, argument \p id will be the one returned by the
172  SPxPricer at the previous call to #selectEnter(). However, one can not
173  rely on this.
174  */
175  virtual void entered4(SPxId /*id*/, int /*n*/)
176  {}
177  //@}
178 
179 
180  //-------------------------------------
181  /**@name Extension */
182  //@{
183  /// \p n vectors have been added to loaded LP.
184  virtual void addedVecs (int /*n*/)
185  {}
186  /// \p n covectors have been added to loaded LP.
187  virtual void addedCoVecs(int /*n*/)
188  {}
189  //@}
190 
191  //-------------------------------------
192  /**@name Shrinking */
193  //@{
194  /// vector \p i was removed from loaded LP.
195  virtual void removedVec(int /*i*/)
196  {}
197  /// vectors given by \p perm have been removed from loaded LP.
198  virtual void removedVecs(const int* /*perm*/)
199  {}
200  /// covector \p i was removed from loaded LP.
201  virtual void removedCoVec(int /*i*/)
202  {}
203  /// covectors given by \p perm have been removed from loaded LP.
204  virtual void removedCoVecs(const int* /*perm*/)
205  {}
206  //@}
207 
208  //-------------------------------------
209  /**@name Debugging */
210  //@{
211  virtual bool isConsistent() const
212  {
213 #ifdef ENABLE_CONSISTENCY_CHECKS
214  return thesolver != 0;
215 #else
216  return true;
217 #endif
218  }
219  //@}
220 
221  //-------------------------------------
222  /**@name Constructors / Destructors */
223  //@{
224  /// constructor
225  explicit SPxPricer(const char* p_name)
226  : m_name(p_name)
227  , thesolver(0)
228  , theeps(0.0)
229  {}
230 
231  /// copy constructor
232  SPxPricer(const SPxPricer& old)
233  : m_name(old.m_name)
234  , thesolver(old.thesolver)
235  , theeps(old.theeps)
236  {}
237 
238  /// assignment operator
240  {
241  if(this != &rhs)
242  {
243  m_name = rhs.m_name;
244  thesolver = rhs.thesolver;
245  theeps = rhs.theeps;
246 
247  assert(isConsistent());
248  }
249 
250  return *this;
251  }
252 
253  /// destructor.
254  virtual ~SPxPricer()
255  {
256  m_name = 0;
257  thesolver = 0;
258  }
259 
260  /// clone function for polymorphism
261  virtual SPxPricer* clone() const = 0;
262  //@}
263 
264 };
265 
266 
267 } // namespace soplex
268 #endif // _SPXPRICER_H_
269 
270 //-----------------------------------------------------------------------------
271 //Emacs Local Variables:
272 //Emacs mode:c++
273 //Emacs c-basic-offset:3
274 //Emacs tab-width:8
275 //Emacs indent-tabs-mode:nil
276 //Emacs End:
277 //-----------------------------------------------------------------------------