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   	/**@file  spxratiotester.h
26   	 * @brief Abstract ratio test base class.
27   	 */
28   	#ifndef _SPXRATIOTESTER_H_
29   	#define _SPXRATIOTESTER_H_
30   	
31   	
32   	#include <assert.h>
33   	
34   	#include "soplex/spxdefines.h"
35   	#include "soplex/spxsolver.h"
36   	
37   	namespace soplex
38   	{
39   	
40   	/**@brief Abstract ratio test base class.
41   	   @ingroup Algo
42   	
43   	   Class SPxRatioTester is the virtual base class for computing the ratio
44   	   test within the Simplex algorithm driven by SoPlex. After a SoPlex
45   	   solver has been #load()%ed to an SPxRatioTester, the solver calls
46   	   #selectLeave() for computing the ratio test for the entering simplex and
47   	   #selectEnter() for computing the ratio test in leaving simplex.
48   	*/
49   	template <class R>
50   	class SPxRatioTester
51   	{
52   	protected:
53   	
54   	   //-------------------------------------
55   	   /**@name Data */
56   	   ///@{
57   	   /// the solver
58   	   SPxSolverBase<R>*  thesolver;
59   	   /// name of the ratio tester
60   	   const char* m_name;
61   	   /// internal storage of type
62   	   typename SPxSolverBase<R>::Type m_type;
63   	   /// allowed bound violation
64   	   R delta;
65   	   /// tolerances used by the solver
66   	   std::shared_ptr<Tolerances> _tolerances;
67   	   ///@}
68   	
69   	public:
70   	
71   	   //-------------------------------------
72   	   /**@name Access / modification */
73   	   ///@{
74   	   /// get name of ratio tester.
75   	   virtual const char* getName() const
76   	   {
77   	      return m_name;
78   	   }
79   	   /// loads LP.
80   	   /** Load the solver and LP for which pricing steps are to be performed.
81   	    */
82   	   virtual void load(SPxSolverBase<R>* p_solver)
83   	   {
84   	      thesolver = p_solver;
85   	   }
86   	
87   	   /// unloads LP.
88   	   virtual void clear()
89   	   {
90   	      thesolver = nullptr;
91   	   }
92   	
93   	   /// returns loaded LP solver.
94   	   virtual SPxSolverBase<R>* solver() const
95   	   {
96   	      return thesolver;
97   	   }
98   	
99   	   /// set allowed bound violation
100  	   virtual void setDelta(R newDelta)
101  	   {
102  	      if(newDelta <= this->tolerances()->epsilon())
103  	         delta = this->tolerances()->epsilon();
104  	      else
105  	         delta = newDelta;
106  	   }
107  	
108  	   /// get allowed bound violation
109  	   virtual R getDelta()
110  	   {
111  	      return delta;
112  	   }
113  	
114  	   /// set the _tolerances member variable
115  	   virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances)
116  	   {
117  	      this->_tolerances = newTolerances;
118  	   }
119  	   /// get the _tolerances member variable
120  	   const std::shared_ptr<Tolerances> tolerances() const
121  	   {
122  	      return _tolerances;
123  	   }
124  	   ///@}
125  	
126  	   //-------------------------------------
127  	   /**@name Entering / leaving */
128  	   ///@{
129  	   /// selects index to leave the basis.
130  	   /** Method #selectLeave() is called by the loaded SoPlex solver when
131  	       computing the entering simplex algorithm. Its task is to select and
132  	       return the index of the basis variable that is to leave the basis.
133  	       When being called,
134  	       \ref SPxSolverBase<R>::fVec() "fVec()" fullfills the basic bounds
135  	       \ref SPxSolverBase<R>::lbBound() "lbBound()" and
136  	       \ref SPxSolverBase<R>::ubBound() "ubBound()" within
137  	       \ref SPxSolverBase<R>::entertol() "entertol()".
138  	       fVec().delta() is the vector by
139  	       which fVec() will be updated in this simplex step. Its nonzero
140  	       indices are stored in sorted order in fVec().idx().
141  	
142  	       If \p val > 0, \p val is the maximum allowed update value for fVec(),
143  	       otherwise the minimum. Method #selectLeave() must chose \p val of the
144  	       same sign as passed, such that updating fVec() by \p val yields a
145  	       new vector that satisfies all basic bounds (within entertol). The
146  	       returned index, must be the index of an element of fVec(), that
147  	       reaches one of its bounds with this update.
148  	   */
149  	   virtual int selectLeave(R& val, R enterTest, bool polish = false) = 0;
150  	
151  	   /// selects variable Id to enter the basis.
152  	   /** Method #selectEnter() is called by the loaded SoPlex solver, when
153  	       computing the leaving simplex algorithm. It's task is to select and
154  	       return the Id of the basis variable that is to enter the basis.
155  	       When being called,
156  	       \ref SPxSolverBase<R>::pVec() "pVec()" fullfills the bounds
157  	       \ref SPxSolverBase<R>::lbBound() "lbBound()" and
158  	       \ref SPxSolverBase<R>::ubBound() "ubBound()" within
159  	       \ref SPxSolverBase<R>::leavetol() "leavetol()".
160  	       Similarly,
161  	       \ref SPxSolverBase<R>::coPvec() "coPvec()" fulfills the bounds
162  	       \ref SPxSolverBase<R>::lbBound() "lbBound()" and
163  	       \ref SPxSolverBase<R>::ubBound() "ubBound()" within
164  	       \ref SPxSolverBase<R>::leavetol() "leavetol()".
165  	       pVec().delta() and coPvec().delta() are
166  	       the vectors by which pVec() and coPvec() will be updated in this
167  	       simplex step. Their nonzero indices are stored in sorted order in
168  	       pVec().idx() and coPvec().idx().
169  	
170  	       If \p val > 0, \p val is the maximum allowed update value for pVec()
171  	       and coPvec(), otherwise the minimum. Method #selectEnter() must
172  	       chose \p val of the same sign as passed, such that updating pVec()
173  	       and coPvec() by \p val yields a new vector that satisfies all basic
174  	       bounds (within leavetol). The returned Id must be the Id of an
175  	       element of pVec() or coPvec(), that reaches one of its bounds
176  	       with this update.
177  	   */
178  	   virtual SPxId selectEnter(R& val, int leaveIdx, bool polish = false) = 0;
179  	
180  	   /// sets Simplex type.
181  	   /** Informs pricer about (a change of) the loaded SoPlex's Type. In
182  	       the sequel, only the corresponding select methods may be called.
183  	   */
184  	   virtual void setType(typename SPxSolverBase<R>::Type)
185  	   {}
186  	   ///@}
187  	
188  	   //-------------------------------------
189  	   /**@name Construction / destruction */
190  	   ///@{
191  	   /// default constructor
192  	   explicit SPxRatioTester(const char* name)
193  	      : thesolver(0)
194  	      , m_name(name)
195  	      , m_type(SPxSolverBase<R>::LEAVE)
196  	      , delta(1e-6)
197  	   {}
198  	   /// copy constructor
199  	   SPxRatioTester(const SPxRatioTester& old)
200  	      : thesolver(old.thesolver)
201  	      , m_name(old.m_name)
202  	      , m_type(old.m_type)
203  	      , delta(old.delta)
204  	   {}
205  	   /// assignment operator
206  	   SPxRatioTester& operator=(const SPxRatioTester& rhs)
207  	   {
208  	      if(this != &rhs)
209  	      {
210  	         m_name = rhs.m_name;
211  	         thesolver = rhs.thesolver;
212  	         m_type = rhs.m_type;
213  	         delta = rhs.delta;
214  	      }
215  	
216  	      return *this;
217  	   }
218  	   /// destructor.
219  	   virtual ~SPxRatioTester()
220  	   {
221  	      thesolver = nullptr;
222  	      m_name    = nullptr;
223  	   }
224  	   /// clone function for polymorphism
225  	   virtual SPxRatioTester* clone() const = 0;
226  	   ///@}
227  	
228  	};
229  	
230  	
231  	} // namespace soplex
232  	#endif // _SPXRATIOTESTER_H_
233