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