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  spxfastrt.h
26   	 * @brief Fast shifting ratio test.
27   	 */
28   	#ifndef _SPXFASTRT_H_
29   	#define _SPXFASTRT_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/spxdefines.h"
34   	#include "soplex/spxratiotester.h"
35   	
36   	namespace soplex
37   	{
38   	
39   	#define SOPLEX_FASTRT_EPSILON 1e-10
40   	
41   	/**@brief   Fast shifting ratio test.
42   	   @ingroup Algo
43   	
44   	   Class SPxFastRT is an implementation class of SPxRatioTester providing
45   	   fast and stable ratio test. Stability is achieved by allowing some
46   	   infeasibility to ensure numerical stability such as the Harris procedure.
47   	   Performance is achieved by skipping the second phase if the first phase
48   	   already shows a stable enough pivot.
49   	
50   	   See SPxRatioTester for a class documentation.
51   	*/
52   	template <class R>
53   	class SPxFastRT : public SPxRatioTester<R>
54   	{
55   	protected:
56   	   //-------------------------------------
57   	   /**@name Data */
58   	   ///@{
59   	   /// parameter for computing minimum stability requirement
60   	   R minStab;
61   	   /// zero tolerance used by the ratio tester
62   	   R epsilon;
63   	   /// currently allowed infeasibility.
64   	   R fastDelta;
65   	   /// flag used in methods minSelect/maxSelect to retrieve correct basis status
66   	   bool iscoid;
67   	   ///@}
68   	
69   	   //-------------------------------------
70   	   /**@name Private helpers */
71   	   ///@{
72   	   /// resets tolerances (epsilon).
73   	   void resetTols();
74   	   /// return epsilon
75   	   const R epsilonZero() const
76   	   {
77   	      return epsilon;
78   	   }
79   	   /// relaxes stability requirements.
80   	   void relax();
81   	   /// tightens stability requirements.
82   	   void tighten();
83   	   /// Compute stability requirement
84   	   R minStability(R maxabs);
85   	
86   	   /// Max phase 1 value.
87   	   /** Computes the maximum value \p val that could be used for updating \p update
88   	       such that it would still fulfill the upper and lower bounds \p upBound and
89   	       \p lowBound, respectively, within #delta. Return value is the index where the
90   	       maximum value is encountered. At the same time the maximum absolute value
91   	       of \p update.delta() is computed and returned in \p maxabs. Internally all
92   	       loops are started at \p start and incremented by \p incr.
93   	    */
94   	   int maxDelta(R& val, R& maxabs, UpdateVector<R>& update,
95   	                const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const;
96   	
97   	   ///
98   	   int maxDelta(R& val, R& maxabs);
99   	
100  	   ///
101  	   SPxId maxDelta(int& nr, R& val, R& maxabs);
102  	
103  	   /// Min phase 1 value.
104  	   /** Computes the minimum value \p val that could be used for updating \p update
105  	       such that it would still fulfill the upper and lower bounds \p upBound and
106  	       \p lowBound, respectively, within #delta. Return value is the index where the
107  	       minimum value is encountered. At the same time the maximum absolute value
108  	       of \p update.delta() is computed and returned in \p maxabs. Internally all
109  	       loops are started at \p start and incremented by \p incr.
110  	   */
111  	   int minDelta(R& val, R& maxabs, UpdateVector<R>& update,
112  	                const VectorBase<R>& lowBound, const VectorBase<R>& upBound, int start, int incr) const;
113  	
114  	   ///
115  	   int minDelta(R& val, R& maxabs);
116  	
117  	   ///
118  	   SPxId minDelta(int& nr, R& val, R& maxabs);
119  	
120  	   /// selects stable index for maximizing ratio test.
121  	   /** Selects from all update values \p val < \p max the one with the largest
122  	       value of \p upd.delta() which must be greater than \p stab and is
123  	       returned in \p stab. The index is returned as well as the corresponding
124  	       update value \p val. Internally all loops are started at \p start and
125  	       incremented by \p incr.
126  	   */
127  	   int maxSelect(R& val, R& stab, R& best, R& bestDelta,
128  	                 R max, const UpdateVector<R>& upd, const VectorBase<R>& low,
129  	                 const VectorBase<R>& up, int start = 0, int incr = 1) const;
130  	   ///
131  	   int maxSelect(R& val, R& stab, R& bestDelta, R max);
132  	   ///
133  	   SPxId maxSelect(int& nr, R& val, R& stab,
134  	                   R& bestDelta, R max);
135  	
136  	   /// selects stable index for minimizing ratio test.
137  	   /** Select from all update values \p val > \p max the one with the largest
138  	       value of \p upd.delta() which must be greater than \p stab and is
139  	       returned in \p stab. The index is returned as well as the corresponding
140  	       update value \p val. Internally all loops are started at \p start and
141  	       incremented by \p incr.
142  	   */
143  	   int minSelect(R& val, R& stab, R& best, R& bestDelta,
144  	                 R max, const UpdateVector<R>& upd, const VectorBase<R>& low,
145  	                 const VectorBase<R>& up, int start = 0, int incr = 1) const;
146  	   ///
147  	   int minSelect(R& val, R& stab,
148  	                 R& bestDelta, R max);
149  	   ///
150  	   SPxId minSelect(int& nr, R& val, R& stab,
151  	                   R& bestDelta, R max);
152  	
153  	   /// tests for stop after phase 1.
154  	   /** Tests whether a shortcut after phase 1 is feasible for the
155  	       selected leave pivot. In this case return the update value in \p sel.
156  	   */
157  	   bool minShortLeave(R& sel, int leave, R maxabs);
158  	   ///
159  	   bool maxShortLeave(R& sel, int leave, R maxabs);
160  	
161  	   /// numerical stability tests.
162  	   /** Tests whether the selected leave index needs to be discarded (and do so)
163  	       and the ratio test is to be recomputed.
164  	       If \p polish is set to true no shifts are applied.
165  	   */
166  	   bool minReLeave(R& sel, int leave, R maxabs, bool polish = false);
167  	   ///
168  	   bool maxReLeave(R& sel, int leave, R maxabs, bool polish = false);
169  	
170  	   /// numerical stability check.
171  	   /** Tests whether the selected enter \p id needs to be discarded (and do so)
172  	       and the ratio test is to be recomputed.
173  	   */
174  	   bool minReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false);
175  	   ///
176  	   bool maxReEnter(R& sel, R maxabs, const SPxId& id, int nr, bool polish = false);
177  	
178  	   /// Tests and returns whether a shortcut after phase 1 is feasible for the
179  	   /// selected enter pivot.
180  	   bool shortEnter(const SPxId& enterId, int nr, R max, R maxabs) const;
181  	   ///@}
182  	
183  	public:
184  	
185  	   //-------------------------------------
186  	   /**@name Construction / destruction */
187  	   ///@{
188  	   /// default constructor
189  	   SPxFastRT()
190  	      : SPxRatioTester<R>("Fast")
191  	      , minStab(SOPLEX_DEFAULT_BND_VIOL)
192  	      , epsilon(SOPLEX_DEFAULT_EPS_ZERO)
193  	      , fastDelta(SOPLEX_DEFAULT_BND_VIOL)
194  	      , iscoid(false)
195  	   {}
196  	   /// copy constructor
197  	   SPxFastRT(const SPxFastRT& old)
198  	      : SPxRatioTester<R>(old)
199  	      , minStab(old.minStab)
200  	      , epsilon(old.epsilon)
201  	      , fastDelta(old.fastDelta)
202  	      , iscoid(false)
203  	   {}
204  	   /// assignment operator
205  	   SPxFastRT& operator=(const SPxFastRT& rhs)
206  	   {
207  	      if(this != &rhs)
208  	      {
209  	         SPxRatioTester<R>::operator=(rhs);
210  	         minStab = rhs.minStab;
211  	         epsilon = rhs.epsilon;
212  	         fastDelta = rhs.fastDelta;
213  	         iscoid = false;
214  	      }
215  	
216  	      return *this;
217  	   }
218  	   /// bound flipping constructor
219  	   SPxFastRT(const char* name)
220  	      : SPxRatioTester<R>(name)
221  	      , minStab(SOPLEX_DEFAULT_BND_VIOL)
222  	      , epsilon(SOPLEX_DEFAULT_EPS_ZERO)
223  	      , fastDelta(SOPLEX_DEFAULT_BND_VIOL)
224  	      , iscoid(false)
225  	   {}
226  	   /// destructor
227  	   virtual ~SPxFastRT()
228  	   {}
229  	   /// clone function for polymorphism
230  	   inline virtual SPxRatioTester<R>* clone() const
231  	   {
232  	      return new SPxFastRT(*this);
233  	   }
234  	   ///@}
235  	
236  	   //-------------------------------------
237  	   /**@name Access / modification */
238  	   ///@{
239  	   ///
240  	   virtual void load(SPxSolverBase<R>* solver);
241  	   ///
242  	   virtual int selectLeave(R& val, R, bool polish = false);
243  	   ///
244  	   virtual SPxId selectEnter(R& val, int, bool polish = false);
245  	   ///
246  	   virtual void setType(typename SPxSolverBase<R>::Type type);
247  	   ///
248  	   virtual void setDelta(R newDelta)
249  	   {
250  	      if(newDelta <= this->tolerances()->epsilon())
251  	         newDelta = this->tolerances()->epsilon();
252  	
253  	      this->delta = newDelta;
254  	      fastDelta = newDelta;
255  	   }
256  	   ///
257  	   virtual R getDelta()
258  	   {
259  	      return fastDelta;
260  	   }
261  	   ///@}
262  	};
263  	} // namespace soplex
264  	
265  	#include "spxfastrt.hpp"
266  	
267  	#endif // _SPXFASTRT_H_
268