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   spxboundflippingrt.h
26   	 * @brief  Bound flipping ratio test (long step dual) for SoPlex.
27   	 * @author Matthias Miltenberger
28   	 * @author Eva Ramlow
29   	 */
30   	#ifndef _SPXBOUNDFLIPPINGRT_H_
31   	#define _SPXBOUNDFLIPPINGRT_H_
32   	
33   	
34   	#include <assert.h>
35   	#include "soplex/spxdefines.h"
36   	#include "soplex/spxratiotester.h"
37   	#include "soplex/spxfastrt.h"
38   	
39   	namespace soplex
40   	{
41   	
42   	/**@brief   Bound flipping ratio test ("long step dual") for SoPlex.
43   	   @ingroup Algo
44   	
45   	   Class SPxBoundFlippingRT provides an implementation of the bound flipping
46   	   ratio test as a derived class of SPxRatioTester. Dual step length is
47   	   increased beyond some breakpoints and corresponding primal nonbasic
48   	   variables are set to their other bound to handle the resulting dual infeasibility.
49   	
50   	   The implementation mostly follows the papers
51   	   - I. Maros, "A generalized dual phase-2 simplex algorithm",
52   	     European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003
53   	   - A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems:
54   	     techniques for a fast and stable implementation",
55   	     Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008
56   	
57   	   See SPxRatioTester for a class documentation.
58   	*/
59   	template <class R>
60   	class SPxBoundFlippingRT : public SPxFastRT<R>
61   	{
62   	private:
63   	   /**@name substructures */
64   	   ///@{
65   	   /** enumerator to remember which vector we have been searching to find a breakpoint
66   	    */
67   	   enum BreakpointSource
68   	   {
69   	      FVEC               = -1,
70   	      PVEC               = 0,
71   	      COPVEC             = 1
72   	   };
73   	
74   	   /** breakpoint structure
75   	    */
76   	   struct Breakpoint
77   	   {
78   	      R               val;                /**< breakpoint value (step length) */
79   	      int                idx;                /**< index of corresponding row/column */
80   	      BreakpointSource   src;                /**< origin of breakpoint, i.e. vector which was searched */
81   	   };
82   	
83   	   /** Compare class for breakpoints
84   	    */
85   	   struct BreakpointCompare
86   	   {
87   	   public:
88   	      /** constructor
89   	       */
90   	      BreakpointCompare()
91   	         : entry(0)
92   	      {
93   	      }
94   	
95   	      const Breakpoint*  entry;
96   	
97   	      R operator()(
98   	         Breakpoint      i,
99   	         Breakpoint      j
100  	      ) const
101  	      {
102  	         return i.val - j.val;
103  	      }
104  	   };
105  	   ///@}
106  	
107  	   /**@name Data
108  	    */
109  	   ///@{
110  	   bool                  enableBoundFlips;   /**< enable or disable long steps in BoundFlippingRT */
111  	   bool                  enableRowBoundFlips;/**< enable bound flips also for row representation */
112  	   R
113  	   flipPotential;      /**< tracks bound flip history and decides which ratio test to use */
114  	   int                   relax_count;        /**< count rounds of ratio test */
115  	   Array<Breakpoint> breakpoints;        /**< array of breakpoints */
116  	   SSVectorBase<R>
117  	   updPrimRhs;         /**< right hand side vector of additional system to be solved after the ratio test */
118  	   SSVectorBase<R>
119  	   updPrimVec;         /**< allocation of memory for additional solution vector */
120  	   ///@}
121  	
122  	   /** store all available pivots/breakpoints in an array (positive pivot search direction) */
123  	   void collectBreakpointsMax(
124  	      int&               nBp,                /**< number of found breakpoints so far */
125  	      int&               minIdx,             /**< index to current minimal breakpoint */
126  	      const int*         idx,                /**< pointer to indices of current vector */
127  	      int                nnz,                /**< number of nonzeros in current vector */
128  	      const R*        upd,                /**< pointer to update values of current vector */
129  	      const R*        vec,                /**< pointer to values of current vector */
130  	      const R*        upp,                /**< pointer to upper bound/rhs of current vector */
131  	      const R*        low,                /**< pointer to lower bound/lhs of current vector */
132  	      BreakpointSource   src                 /**< type of vector (pVec or coPvec)*/
133  	   );
134  	
135  	   /** store all available pivots/breakpoints in an array (negative pivot search direction) */
136  	   void collectBreakpointsMin(
137  	      int&               nBp,                /**< number of found breakpoints so far */
138  	      int&               minIdx,             /**< index to current minimal breakpoint */
139  	      const int*         idx,                /**< pointer to indices of current vector */
140  	      int                nnz,                /**< number of nonzeros in current vector */
141  	      const R*        upd,                /**< pointer to update values of current vector */
142  	      const R*        vec,                /**< pointer to values of current vector */
143  	      const R*        upp,                /**< pointer to upper bound/rhs of current vector */
144  	      const R*        low,                /**< pointer to lower bound/lhs of current vector */
145  	      BreakpointSource   src                 /**< type of vector (pVec or coPvec)*/
146  	   );
147  	
148  	   /** get values for entering index and perform shifts if necessary */
149  	   bool getData(
150  	      R&              val,
151  	      SPxId&             enterId,
152  	      int                idx,
153  	      R               stab,
154  	      R               degeneps,
155  	      const R*        upd,
156  	      const R*        vec,
157  	      const R*        low,
158  	      const R*        upp,
159  	      BreakpointSource   src,
160  	      R               max
161  	   );
162  	
163  	   /** get values for leaving index and perform shifts if necessary */
164  	   bool getData(
165  	      R&              val,
166  	      int&             leaveIdx,
167  	      int                idx,
168  	      R               stab,
169  	      R               degeneps,
170  	      const R*        upd,
171  	      const R*        vec,
172  	      const R*        low,
173  	      const R*        upp,
174  	      BreakpointSource   src,
175  	      R               max
176  	   );
177  	
178  	   /** perform necessary bound flips to restore dual feasibility */
179  	   void flipAndUpdate(
180  	      int&               usedBp              /**< number of bounds that should be flipped */
181  	   );
182  	
183  	   /** comparison method for breakpoints */
184  	   static bool isSmaller(
185  	      Breakpoint         x,
186  	      Breakpoint         y
187  	   )
188  	   {
189  	      return (spxAbs(x.val) < spxAbs(y.val));
190  	   };
191  	
192  	public:
193  	
194  	   //-------------------------------------
195  	   /**@name Construction / destruction */
196  	   ///@{
197  	   /// default constructor
198  	   SPxBoundFlippingRT()
199  	      : SPxFastRT<R>("Bound Flipping")
200  	      , enableBoundFlips(true)
201  	      , enableRowBoundFlips(false)
202  	      , flipPotential(1)
203  	      , relax_count(0)
204  	      , breakpoints(10)
205  	      , updPrimRhs(0)
206  	      , updPrimVec(0)
207  	   {}
208  	   /// copy constructor
209  	   SPxBoundFlippingRT(const SPxBoundFlippingRT& old)
210  	      : SPxFastRT<R>(old)
211  	      , enableBoundFlips(old.enableBoundFlips)
212  	      , enableRowBoundFlips(old.enableRowBoundFlips)
213  	      , flipPotential(1)
214  	      , relax_count(0)
215  	      , breakpoints(10)
216  	      , updPrimRhs(0)
217  	      , updPrimVec(0)
218  	   {}
219  	   /// assignment operator
220  	   SPxBoundFlippingRT& operator=(const SPxBoundFlippingRT& rhs)
221  	   {
222  	      if(this != &rhs)
223  	      {
224  	         SPxFastRT<R>::operator=(rhs);
225  	      }
226  	
227  	      enableBoundFlips = rhs.enableBoundFlips;
228  	      enableRowBoundFlips = rhs.enableRowBoundFlips;
229  	      flipPotential = rhs.flipPotential;
230  	
231  	      return *this;
232  	   }
233  	   /// destructor
234  	   virtual ~SPxBoundFlippingRT()
235  	   {}
236  	   /// clone function for polymorphism
237  	   inline virtual SPxRatioTester<R>* clone() const
238  	   {
239  	      return new SPxBoundFlippingRT(*this);
240  	   }
241  	   ///@}
242  	
243  	   //-------------------------------------
244  	   /**@name Select enter/leave */
245  	   ///@{
246  	   ///
247  	   virtual int selectLeave(
248  	      R&              val,
249  	      R               enterTest,
250  	      bool               polish = false
251  	   );
252  	   ///
253  	   virtual SPxId selectEnter(
254  	      R&              val,
255  	      int                leaveIdx,
256  	      bool               polish = false
257  	   );
258  	
259  	   void useBoundFlips(bool bf)
260  	   {
261  	      enableBoundFlips = bf;
262  	   }
263  	
264  	   void useBoundFlipsRow(bool bf)
265  	   {
266  	      enableRowBoundFlips = bf;
267  	   }
268  	
269  	   /// set tolerances
270  	   void setTolerances(std::shared_ptr<Tolerances> tolerances)
271  	   {
272  	      this->_tolerances = tolerances;
273  	      this->updPrimRhs.setTolerances(tolerances);
274  	      this->updPrimVec.setTolerances(tolerances);
275  	   }
276  	   ///@}
277  	};
278  	
279  	} // namespace soplex
280  	
281  	#include "spxboundflippingrt.hpp"
282  	
283  	#endif // _SPXBOUNDFLIPPINGRT_H_
284