SoPlex Documentation
Loading...
Searching...
No Matches
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-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25
26/**@file spxpricer.h
27 * @brief Abstract pricer base class.
28 */
29#ifndef _SPXPRICE_H_
30#define _SPXPRICE_H_
31
32#include <assert.h>
33
34#include "soplex/spxdefines.h"
35#include "soplex/spxsolver.h"
36#include "soplex/sorter.h"
37
38namespace soplex
39{
40
41/**@brief Abstract pricer base class.
42 @ingroup Algo
43
44 Class SPxPricer is a pure virtual class defining the interface for pricer
45 classes to be used by SoPlex. The pricer's task is to select a vector to
46 enter or leave the simplex basis, depending on the chosen simplex type.
47
48 An SPxPricer first #load%s the SoPlex object for which pricing is to
49 be performed. Then, depending of the SPxSolverBase<R>::Type, methods
50 #selectEnter() and #entered4() (for entering Simplex) or #selectLeave()
51 and #left4() (for leaving Simplex) are called by SoPlex. The SPxPricer
52 object is informed of a change of the SPxSolverBase<R>::Type by calling method
53 #setType().
54*/
55template <class R>
57{
58protected:
59
60 //-------------------------------------
61 /**@name Data */
62 ///@{
63 /// name of the pricer
64 const char* m_name;
65 /// the solver
66
68 thesolver; //@todo The template type should be identified? Do I have to defined two of them?
69 /// violation bound
71 ///@}
72
73
75 {
76 int idx;
78 };
79
80 /// Compare class to sort idx/val pairs, used for hypersparse pricing leaving
82 {
83 public:
84 /// constructor
86 : elements(0)
87 {}
88
90
94 ) const
95 {
96 //the first case is needed to handle inf-values
97 return (a.val == b.val) ? 0 : b.val - a.val;
98 }
99 };
100
102
103public:
104
105 // violation types used for (hyper) sparse pricing
112
113 //-------------------------------------
114 /**@name Initialization */
115 ///@{
116 /// get name of pricer.
117 virtual const char* getName() const
118 {
119 return m_name;
120 }
121
122 /// loads LP.
123 /** Loads the solver and LP for which pricing steps are to be performed.
124 */
126 {
128 }
129
130 /// unloads LP.
131 virtual void clear()
132 {
133 thesolver = 0;
134 }
135
136 /// returns loaded SPxSolverBase object.
137 virtual SPxSolverBase<R>* solver() const
138 {
139 return thesolver;
140 }
141
142 /// returns violation bound \ref soplex::SPxPricer::theeps "theeps".
143 virtual R epsilon() const
144 {
145 return theeps;
146 }
147
148 /// sets violation bound.
149 /** Inequality violations are accepted, if their size is less than \p eps.
150 */
151 virtual void setEpsilon(R eps)
152 {
153 assert(eps >= 0.0);
154
155 theeps = eps;
156 }
157
158 /// sets pricing 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 this->thesolver->weights.reDim(0);
165 this->thesolver->coWeights.reDim(0);
166 this->thesolver->weightsAreSetup = false;
167 }
168
169 /// sets basis representation.
170 /** Informs pricer about (a change of) the loaded SoPlex's
171 Representation.
172 */
174 {}
175 ///@}
176
177 //-------------------------------------
178 /**@name Pivoting */
179 ///@{
180 /// returns selected index to leave basis.
181 /** Selects the index of a vector to leave the basis. The selected index
182 i, say, must be in the range 0 <= i < solver()->dim() and its
183 tested value must fullfill solver()->test()[i] < -#epsilon().
184 */
185 virtual int selectLeave() = 0;
186
187 /// performs leaving pivot.
188 /** Method #left4() is called after each simplex iteration in LEAVE
189 mode. It informs the SPxPricer that the \p n 'th variable has left
190 the basis for \p id to come in at this position. When being called,
191 all vectors of SoPlex involved in such an entering update are
192 setup correctly and may be accessed via the corresponding methods
193 (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()",
194 etc.). In general, argument \p n will be the one returned by the
195 SPxPricer at the previous call to #selectLeave(). However, one can not
196 rely on this.
197 */
198 virtual void left4(int /*n*/, SPxId /*id*/) {}
199
200 /// selects Id to enter basis.
201 /** Selects the SPxId of a vector to enter the basis. The selected
202 id, must not represent a basic index (i.e. solver()->isBasic(id) must
203 be false). However, the corresponding test value needs not to be less
204 than -#epsilon(). If not, SoPlex will discard the pivot.
205
206 Note:
207 When method #selectEnter() is called by the loaded SoPlex
208 object, all values from \ref SPxSolverBase<R>::coTest() "coTest()" are
209 up to date. However, whether the elements of
210 \ref SPxSolverBase<R>::test() "test()" are up to date depends on the
211 SPxSolverBase<R>::Pricing type.
212 */
213 virtual SPxId selectEnter() = 0;
214
215 /// performs entering pivot.
216 /** Method #entered4() is called after each simplex iteration in ENTER
217 mode. It informs the SPxPricer that variable \p id has entered
218 at the \p n 'th position. When being called, all vectors of SoPlex
219 involved in such an entering update are setup correctly and may be
220 accessed via the corresponding methods
221 (\ref SPxSolverBase<R>::fVec() "fVec()", \ref SPxSolverBase<R>::pVec() "pVec()",
222 etc.). In general, argument \p id will be the one returned by the
223 SPxPricer at the previous call to #selectEnter(). However, one can not
224 rely on this.
225 */
226 virtual void entered4(SPxId /*id*/, int /*n*/)
227 {}
228 ///@}
229
230
231 //-------------------------------------
232 /**@name Extension */
233 ///@{
234 /// \p n vectors have been added to loaded LP.
235 virtual void addedVecs(int /*n*/)
236 {}
237 /// \p n covectors have been added to loaded LP.
238 virtual void addedCoVecs(int /*n*/)
239 {}
240 ///@}
241
242 //-------------------------------------
243 /**@name Shrinking */
244 ///@{
245 /// vector \p i was removed from loaded LP.
246 virtual void removedVec(int /*i*/)
247 {}
248 /// vectors given by \p perm have been removed from loaded LP.
249 virtual void removedVecs(const int* /*perm*/)
250 {}
251 /// covector \p i was removed from loaded LP.
252 virtual void removedCoVec(int /*i*/)
253 {}
254 /// covectors given by \p perm have been removed from loaded LP.
255 virtual void removedCoVecs(const int* /*perm*/)
256 {}
257 ///@}
258
259 //-------------------------------------
260 /**@name Debugging */
261 ///@{
262 virtual bool isConsistent() const
263 {
264#ifdef ENABLE_CONSISTENCY_CHECKS
265 return thesolver != 0;
266#else
267 return true;
268#endif
269 }
270 ///@}
271
272 //-------------------------------------
273 /**@name Constructors / Destructors */
274 ///@{
275 /// constructor
276 explicit SPxPricer(const char* p_name)
277 : m_name(p_name)
278 , thesolver(0)
279 , theeps(0.0)
280 {}
281
282 /// copy constructor
288
289 /// assignment operator
291 {
292 if(this != &rhs)
293 {
294 m_name = rhs.m_name;
295 thesolver = rhs.thesolver;
296 theeps = rhs.theeps;
298 }
299
300 return *this;
301 }
302
303 /// destructor.
304 virtual ~SPxPricer()
305 {
306 m_name = 0;
307 thesolver = 0;
308 }
309
310 /// clone function for polymorphism
311 virtual SPxPricer* clone() const = 0;
312 ///@}
313
314};
315
316
317} // namespace soplex
318#endif // _SPXPRICER_H_
Safe arrays of data objects.
Definition dataarray.h:75
Generic Ids for LP rows or columns.
Definition spxid.h:95
Abstract pricer base class.
Definition spxpricer.h:57
virtual void removedCoVecs(const int *)
covectors given by perm have been removed from loaded LP.
Definition spxpricer.h:255
virtual void removedVecs(const int *)
vectors given by perm have been removed from loaded LP.
Definition spxpricer.h:249
virtual void entered4(SPxId, int)
performs entering pivot.
Definition spxpricer.h:226
SPxPricer(const SPxPricer &old)
copy constructor
Definition spxpricer.h:283
virtual void addedVecs(int)
n vectors have been added to loaded LP.
Definition spxpricer.h:235
virtual SPxPricer * clone() const =0
clone function for polymorphism
virtual void load(SPxSolverBase< R > *p_solver)
loads LP.
Definition spxpricer.h:125
virtual const char * getName() const
get name of pricer.
Definition spxpricer.h:117
virtual R epsilon() const
returns violation bound theeps.
Definition spxpricer.h:143
R theeps
violation bound
Definition spxpricer.h:70
virtual SPxSolverBase< R > * solver() const
returns loaded SPxSolverBase object.
Definition spxpricer.h:137
virtual void removedCoVec(int)
covector i was removed from loaded LP.
Definition spxpricer.h:252
virtual bool isConsistent() const
Definition spxpricer.h:262
virtual ~SPxPricer()
destructor.
Definition spxpricer.h:304
const char * m_name
name of the pricer
Definition spxpricer.h:64
virtual void clear()
unloads LP.
Definition spxpricer.h:131
virtual void setType(typename SPxSolverBase< R >::Type)
sets pricing type.
Definition spxpricer.h:162
SPxSolverBase< R > * thesolver
the solver
Definition spxpricer.h:68
SPxPricer(const char *p_name)
constructor
Definition spxpricer.h:276
virtual void setRep(typename SPxSolverBase< R >::Representation)
sets basis representation.
Definition spxpricer.h:173
SPxPricer & operator=(const SPxPricer &rhs)
assignment operator
Definition spxpricer.h:290
virtual void removedVec(int)
vector i was removed from loaded LP.
Definition spxpricer.h:246
IdxCompare compare
Definition spxpricer.h:101
virtual void setEpsilon(R eps)
sets violation bound.
Definition spxpricer.h:151
virtual SPxId selectEnter()=0
selects Id to enter basis.
virtual void left4(int, SPxId)
performs leaving pivot.
Definition spxpricer.h:198
virtual void addedCoVecs(int)
n covectors have been added to loaded LP.
Definition spxpricer.h:238
virtual int selectLeave()=0
returns selected index to leave basis.
Type
Algorithmic type.
Definition spxsolver.h:143
Representation
LP basis representation.
Definition spxsolver.h:124
Everything should be within this namespace.
Generic QuickSort implementation.
Debugging, floating point type and parameter definitions.
main LP solver class
Compare class to sort idx/val pairs, used for hypersparse pricing leaving.
Definition spxpricer.h:82
R operator()(IdxElement a, IdxElement b) const
Definition spxpricer.h:91
const IdxElement * elements
Definition spxpricer.h:89