Scippy

SoPlex

Sequential object-oriented simPlex

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-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 
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 "soplex/spxdefines.h"
26 #include "soplex/spxsolver.h"
27 #include "soplex/sorter.h"
28 
29 namespace soplex
30 {
31 
32 /**@brief Abstract pricer base class.
33  @ingroup Algo
34 
35  Class SPxPricer is a pure virtual class defining the interface for pricer
36  classes to be used by SoPlex. The pricer's task is to select a vector to
37  enter or leave the simplex basis, depending on the chosen simplex type.
38 
39  An SPxPricer first #load%s the SoPlex object for which pricing is to
40  be performed. Then, depending of the SPxSolverBase<R>::Type, methods
41  #selectEnter() and #entered4() (for entering Simplex) or #selectLeave()
42  and #left4() (for leaving Simplex) are called by SoPlex. The SPxPricer
43  object is informed of a change of the SPxSolverBase<R>::Type by calling method
44  #setType().
45 */
46 template <class R>
47 class SPxPricer
48 {
49 protected:
50 
51  //-------------------------------------
52  /**@name Data */
53  ///@{
54  /// name of the pricer
55  const char* m_name;
56  /// the solver
57 
59  thesolver; //@todo The template type should be identified? Do I have to defined two of them?
60  /// violation bound
61  R theeps;
62  ///@}
63 
64 
65  struct IdxElement
66  {
67  int idx;
68  R val;
69  };
70 
71  /// Compare class to sort idx/val pairs, used for hypersparse pricing leaving
72  struct IdxCompare
73  {
74  public:
75  /// constructor
77  : elements(0)
78  {}
79 
81 
83  IdxElement a,
84  IdxElement b
85  ) const
86  {
87  //the first case is needed to handle inf-values
88  return (a.val == b.val) ? 0 : b.val - a.val;
89  }
90  };
91 
93 
94 public:
95 
96  // violation types used for (hyper) sparse pricing
98  {
100  VIOLATED = 1,
102  };
103 
104  //-------------------------------------
105  /**@name Initialization */
106  ///@{
107  /// get name of pricer.
108  virtual const char* getName() const
109  {
110  return m_name;
111  }
112 
113  /// loads LP.
114  /** Loads the solver and LP for which pricing steps are to be performed.
115  */
116  virtual void load(SPxSolverBase<R>* p_solver)
117  {
118  thesolver = p_solver;
119  }
120 
121  /// unloads LP.
122  virtual void clear()
123  {
124  thesolver = 0;
125  }
126 
127  /// returns loaded SPxSolverBase object.
128  virtual SPxSolverBase<R>* solver() const
129  {
130  return thesolver;
131  }
132 
133  /// returns violation bound \ref soplex::SPxPricer::theeps "theeps".
134  virtual R epsilon() const
135  {
136  return theeps;
137  }
138 
139  /// sets violation bound.
140  /** Inequality violations are accepted, if their size is less than \p eps.
141  */
142  virtual void setEpsilon(R eps)
143  {
144  assert(eps >= 0.0);
145 
146  theeps = eps;
147  }
148 
149  /// sets pricing type.
150  /** Informs pricer about (a change of) the loaded SoPlex's Type. In
151  the sequel, only the corresponding select methods may be called.
152  */
153  virtual void setType(typename SPxSolverBase<R>::Type)
154  {
155  this->thesolver->weights.reDim(0);
156  this->thesolver->coWeights.reDim(0);
157  this->thesolver->weightsAreSetup = false;
158  }
159 
160  /// sets basis representation.
161  /** Informs pricer about (a change of) the loaded SoPlex's
162  Representation.
163  */
165  {}
166  ///@}
167 
168  //-------------------------------------
169  /**@name Pivoting */
170  ///@{
171  /// returns selected index to leave basis.
172  /** Selects the index of a vector to leave the basis. The selected index
173  i, say, must be in the range 0 <= i < solver()->dim() and its
174  tested value must fullfill solver()->test()[i] < -#epsilon().
175  */
176  virtual int selectLeave() = 0;
177 
178  /// performs leaving pivot.
179  /** Method #left4() is called after each simplex iteration in LEAVE
180  mode. It informs the SPxPricer that the \p n 'th variable has left
181  the basis for \p id to come in at this position. When being called,
182  all vectors of SoPlex involved in such an entering update are
183  setup correctly and may be accessed via the corresponding methods
184  (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()",
185  etc.). In general, argument \p n will be the one returned by the
186  SPxPricer at the previous call to #selectLeave(). However, one can not
187  rely on this.
188  */
189  virtual void left4(int /*n*/, SPxId /*id*/) {}
190 
191  /// selects Id to enter basis.
192  /** Selects the SPxId of a vector to enter the basis. The selected
193  id, must not represent a basic index (i.e. solver()->isBasic(id) must
194  be false). However, the corresponding test value needs not to be less
195  than -#epsilon(). If not, SoPlex will discard the pivot.
196 
197  Note:
198  When method #selectEnter() is called by the loaded SoPlex
199  object, all values from \ref SPxSolverBase<R>::coTest() "coTest()" are
200  up to date. However, whether the elements of
201  \ref SPxSolverBase<R>::test() "test()" are up to date depends on the
202  SPxSolverBase<R>::Pricing type.
203  */
204  virtual SPxId selectEnter() = 0;
205 
206  /// performs entering pivot.
207  /** Method #entered4() is called after each simplex iteration in ENTER
208  mode. It informs the SPxPricer that variable \p id has entered
209  at the \p n 'th position. When being called, all vectors of SoPlex
210  involved in such an entering update are setup correctly and may be
211  accessed via the corresponding methods
212  (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()",
213  etc.). In general, argument \p id will be the one returned by the
214  SPxPricer at the previous call to #selectEnter(). However, one can not
215  rely on this.
216  */
217  virtual void entered4(SPxId /*id*/, int /*n*/)
218  {}
219  ///@}
220 
221 
222  //-------------------------------------
223  /**@name Extension */
224  ///@{
225  /// \p n vectors have been added to loaded LP.
226  virtual void addedVecs(int /*n*/)
227  {}
228  /// \p n covectors have been added to loaded LP.
229  virtual void addedCoVecs(int /*n*/)
230  {}
231  ///@}
232 
233  //-------------------------------------
234  /**@name Shrinking */
235  ///@{
236  /// vector \p i was removed from loaded LP.
237  virtual void removedVec(int /*i*/)
238  {}
239  /// vectors given by \p perm have been removed from loaded LP.
240  virtual void removedVecs(const int* /*perm*/)
241  {}
242  /// covector \p i was removed from loaded LP.
243  virtual void removedCoVec(int /*i*/)
244  {}
245  /// covectors given by \p perm have been removed from loaded LP.
246  virtual void removedCoVecs(const int* /*perm*/)
247  {}
248  ///@}
249 
250  //-------------------------------------
251  /**@name Debugging */
252  ///@{
253  virtual bool isConsistent() const
254  {
255 #ifdef ENABLE_CONSISTENCY_CHECKS
256  return thesolver != 0;
257 #else
258  return true;
259 #endif
260  }
261  ///@}
262 
263  //-------------------------------------
264  /**@name Constructors / Destructors */
265  ///@{
266  /// constructor
267  explicit SPxPricer(const char* p_name)
268  : m_name(p_name)
269  , thesolver(0)
270  , theeps(0.0)
271  {}
272 
273  /// copy constructor
274  SPxPricer(const SPxPricer& old)
275  : m_name(old.m_name)
276  , thesolver(old.thesolver)
277  , theeps(old.theeps)
278  {}
279 
280  /// assignment operator
282  {
283  if(this != &rhs)
284  {
285  m_name = rhs.m_name;
286  thesolver = rhs.thesolver;
287  theeps = rhs.theeps;
288  assert(isConsistent());
289  }
290 
291  return *this;
292  }
293 
294  /// destructor.
295  virtual ~SPxPricer()
296  {
297  m_name = 0;
298  thesolver = 0;
299  }
300 
301  /// clone function for polymorphism
302  virtual SPxPricer* clone() const = 0;
303  ///@}
304 
305 };
306 
307 
308 } // namespace soplex
309 #endif // _SPXPRICER_H_
virtual void entered4(SPxId, int)
performs entering pivot.
Definition: spxpricer.h:217
Representation
LP basis representation.
Definition: spxsolver.h:116
virtual SPxId selectEnter()=0
selects Id to enter basis.
virtual void removedVecs(const int *)
vectors given by perm have been removed from loaded LP.
Definition: spxpricer.h:240
Sequential object-oriented SimPlex.SPxSolverBase is an LP solver class using the revised Simplex algo...
Definition: spxbasis.h:49
virtual void setRep(typename SPxSolverBase< R >::Representation)
sets basis representation.
Definition: spxpricer.h:164
SPxSolverBase< R > * thesolver
the solver
Definition: spxpricer.h:59
SPxPricer & operator=(const SPxPricer &rhs)
assignment operator
Definition: spxpricer.h:281
virtual bool isConsistent() const
Definition: spxpricer.h:253
virtual void setEpsilon(R eps)
sets violation bound.
Definition: spxpricer.h:142
virtual void removedCoVec(int)
covector i was removed from loaded LP.
Definition: spxpricer.h:243
virtual SPxSolverBase< R > * solver() const
returns loaded SPxSolverBase object.
Definition: spxpricer.h:128
virtual void setType(typename SPxSolverBase< R >::Type)
sets pricing type.
Definition: spxpricer.h:153
virtual SPxPricer * 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 void addedCoVecs(int)
n covectors have been added to loaded LP.
Definition: spxpricer.h:229
virtual void addedVecs(int)
n vectors have been added to loaded LP.
Definition: spxpricer.h:226
virtual void left4(int, SPxId)
performs leaving pivot.
Definition: spxpricer.h:189
virtual void clear()
unloads LP.
Definition: spxpricer.h:122
Compare class to sort idx/val pairs, used for hypersparse pricing leaving.
Definition: spxpricer.h:72
main LP solver class
Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ...
Definition: spxpricer.h:47
const char * m_name
name of the pricer
Definition: spxpricer.h:55
Generic QuickSort implementation.
virtual void removedCoVecs(const int *)
covectors given by perm have been removed from loaded LP.
Definition: spxpricer.h:246
Debugging, floating point type and parameter definitions.
Everything should be within this namespace.
IdxCompare compare
Definition: spxpricer.h:92
virtual R epsilon() const
returns violation bound theeps.
Definition: spxpricer.h:134
virtual const char * getName() const
get name of pricer.
Definition: spxpricer.h:108
R theeps
violation bound
Definition: spxpricer.h:61
virtual void load(SPxSolverBase< R > *p_solver)
loads LP.
Definition: spxpricer.h:116
SPxPricer(const char *p_name)
constructor
Definition: spxpricer.h:267
virtual void removedVec(int)
vector i was removed from loaded LP.
Definition: spxpricer.h:237
virtual int selectLeave()=0
returns selected index to leave basis.
SPxPricer(const SPxPricer &old)
copy constructor
Definition: spxpricer.h:274
R operator()(IdxElement a, IdxElement b) const
Definition: spxpricer.h:82
Type
Algorithmic type.
Definition: spxsolver.h:135
virtual ~SPxPricer()
destructor.
Definition: spxpricer.h:295
const IdxElement * elements
Definition: spxpricer.h:80