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