1 /* $Id: ClpPrimalColumnSteepest.hpp 2385 2019-01-06 19:43:06Z unxusr $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others.  All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef ClpPrimalColumnSteepest_H
7 #define ClpPrimalColumnSteepest_H
8 
9 #include "ClpPrimalColumnPivot.hpp"
10 #include <bitset>
11 
12 //#############################################################################
13 class CoinIndexedVector;
14 
15 /** Primal Column Pivot Steepest Edge Algorithm Class
16 
17 See Forrest-Goldfarb paper for algorithm
18 
19 */
20 
21 class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot {
22 
23 public:
24   ///@name Algorithmic methods
25   //@{
26 
27   /** Returns pivot column, -1 if none.
28          The Packed CoinIndexedVector updates has cost updates - for normal LP
29          that is just +-weight where a feasibility changed.  It also has
30          reduced cost from last iteration in pivot row
31          Parts of operation split out into separate functions for
32          profiling and speed
33      */
34   virtual int pivotColumn(CoinIndexedVector *updates,
35     CoinIndexedVector *spareRow1,
36     CoinIndexedVector *spareRow2,
37     CoinIndexedVector *spareColumn1,
38     CoinIndexedVector *spareColumn2);
39   /// For quadratic or funny nonlinearities
40   int pivotColumnOldMethod(CoinIndexedVector *updates,
41     CoinIndexedVector *spareRow1,
42     CoinIndexedVector *spareRow2,
43     CoinIndexedVector *spareColumn1,
44     CoinIndexedVector *spareColumn2);
45   /// Just update djs
46   void justDjs(CoinIndexedVector *updates,
47     CoinIndexedVector *spareRow2,
48     CoinIndexedVector *spareColumn1,
49     CoinIndexedVector *spareColumn2);
50   /// Update djs doing partial pricing (dantzig)
51   int partialPricing(CoinIndexedVector *updates,
52     CoinIndexedVector *spareRow2,
53     int numberWanted,
54     int numberLook);
55   /// Update djs, weights for Devex using djs
56   void djsAndDevex(CoinIndexedVector *updates,
57     CoinIndexedVector *spareRow2,
58     CoinIndexedVector *spareColumn1,
59     CoinIndexedVector *spareColumn2);
60   /** Update djs, weights for Steepest using djs
61 	 sets best sequence (possibly) */
62   void djsAndSteepest(CoinIndexedVector *updates,
63     CoinIndexedVector *spareRow2,
64     CoinIndexedVector *spareColumn1,
65     CoinIndexedVector *spareColumn2);
66   /// Update djs, weights for Devex using pivot row
67   void djsAndDevex2(CoinIndexedVector *updates,
68     CoinIndexedVector *spareRow2,
69     CoinIndexedVector *spareColumn1,
70     CoinIndexedVector *spareColumn2);
71   /// Update djs, weights for Steepest using pivot row
72   void djsAndSteepest2(CoinIndexedVector *updates,
73     CoinIndexedVector *spareRow2,
74     CoinIndexedVector *spareColumn1,
75     CoinIndexedVector *spareColumn2);
76   /// Update weights for Devex
77   void justDevex(CoinIndexedVector *updates,
78     CoinIndexedVector *spareRow2,
79     CoinIndexedVector *spareColumn1,
80     CoinIndexedVector *spareColumn2);
81   /// Update weights for Steepest
82   void justSteepest(CoinIndexedVector *updates,
83     CoinIndexedVector *spareRow2,
84     CoinIndexedVector *spareColumn1,
85     CoinIndexedVector *spareColumn2);
86   /// Updates two arrays for steepest
87   int transposeTimes2(const CoinIndexedVector *pi1, CoinIndexedVector *dj1,
88     const CoinIndexedVector *pi2, CoinIndexedVector *dj2,
89     CoinIndexedVector *spare, double scaleFactor);
90 
91   /// Updates weights - part 1 - also checks accuracy
92   virtual void updateWeights(CoinIndexedVector *input);
93 
94   /// Checks accuracy - just for debug
95   void checkAccuracy(int sequence, double relativeTolerance,
96     CoinIndexedVector *rowArray1,
97     CoinIndexedVector *rowArray2);
98 
99   /// Initialize weights
100   void initializeWeights();
101 
102   /** Save weights - this may initialize weights as well
103          mode is -
104          1) before factorization
105          2) after factorization
106          3) just redo infeasibilities
107          4) restore weights
108          5) at end of values pass (so need initialization)
109      */
110   virtual void saveWeights(ClpSimplex *model, int mode);
111   /// redo infeasibilities
112   void redoInfeasibilities();
113   /// Gets rid of last update
114   virtual void unrollWeights();
115   /// Gets rid of all arrays
116   virtual void clearArrays();
117   /// Returns true if would not find any column
118   virtual bool looksOptimal() const;
119   /// Called when maximum pivots changes
120   virtual void maximumPivotsChanged();
121   //@}
122 
123   /**@name gets and sets */
124   //@{
125   /// Mode
mode() const126   inline int mode() const
127   {
128     return mode_;
129   }
130   /// Set mode
setMode(int mode)131   inline void setMode(int mode)
132   {
133     mode_ = mode;
134   }
135   /// square of infeasibility array (just for infeasible columns)
infeasible() const136   inline CoinIndexedVector *infeasible() const
137   {
138     return infeasible_;
139   }
140   /// Weights
weights() const141   inline const double *weights() const
142   {
143     return weights_;
144   }
145   /// alternate weight array
alternateWeights() const146   inline CoinIndexedVector *alternateWeights() const
147   {
148     return alternateWeights_;
149   }
150   /** Returns number of extra columns for sprint algorithm - 0 means off.
151          Also number of iterations before recompute
152      */
153   virtual int numberSprintColumns(int &numberIterations) const;
154   /// Switch off sprint idea
155   virtual void switchOffSprint();
156 
157   //@}
158 
159   /** enums for persistence
160      */
161   enum Persistence {
162     normal = 0x00, // create (if necessary) and destroy
163     keep = 0x01 // create (if necessary) and leave
164   };
165 
166   ///@name Constructors and destructors
167   //@{
168   /** Default Constructor
169          0 is exact devex, 1 full steepest, 2 is partial exact devex
170          3 switches between 0 and 2 depending on factorization
171          4 starts as partial dantzig/devex but then may switch between 0 and 2.
172          By partial exact devex is meant that the weights are updated as normal
173          but only part of the nonbasic variables are scanned.
174          This can be faster on very easy problems.
175      */
176   ClpPrimalColumnSteepest(int mode = 3);
177 
178   /// Copy constructor
179   ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest &rhs);
180 
181   /// Assignment operator
182   ClpPrimalColumnSteepest &operator=(const ClpPrimalColumnSteepest &rhs);
183 
184   /// Destructor
185   virtual ~ClpPrimalColumnSteepest();
186 
187   /// Clone
188   virtual ClpPrimalColumnPivot *clone(bool copyData = true) const;
189 
190   //@}
191 
192   ///@name Private functions to deal with devex
193   /** reference would be faster using ClpSimplex's status_,
194          but I prefer to keep modularity.
195      */
reference(int i) const196   inline bool reference(int i) const
197   {
198     return ((reference_[i >> 5] >> (i & 31)) & 1) != 0;
199   }
setReference(int i,bool trueFalse)200   inline void setReference(int i, bool trueFalse)
201   {
202     unsigned int &value = reference_[i >> 5];
203     int bit = i & 31;
204     if (trueFalse)
205       value |= (1 << bit);
206     else
207       value &= ~(1 << bit);
208   }
209   /// Set/ get persistence
setPersistence(Persistence life)210   inline void setPersistence(Persistence life)
211   {
212     persistence_ = life;
213   }
persistence() const214   inline Persistence persistence() const
215   {
216     return persistence_;
217   }
218 
219   //@}
220   //---------------------------------------------------------------------------
221 
222 protected:
223   ///@name Protected member data
224   // Update weight
225   double devex_;
226   /// weight array
227   double *weights_;
228   /// square of infeasibility array (just for infeasible columns)
229   CoinIndexedVector *infeasible_;
230   /// alternate weight array (so we can unroll)
231   CoinIndexedVector *alternateWeights_;
232   /// save weight array (so we can use checkpoint)
233   double *savedWeights_;
234   // Array for exact devex to say what is in reference framework
235   unsigned int *reference_;
236   /** Status
237          0) Normal
238          -1) Needs initialization
239          1) Weights are stored by sequence number
240      */
241   int state_;
242   /**
243          0 is exact devex, 1 full steepest, 2 is partial exact devex
244          3 switches between 0 and 2 depending on factorization
245          4 starts as partial dantzig/devex but then may switch between 0 and 2.
246          5 is always partial dantzig
247          By partial exact devex is meant that the weights are updated as normal
248          but only part of the nonbasic variables are scanned.
249          This can be faster on very easy problems.
250 
251          New dubious option is >=10 which does mini-sprint
252 
253      */
254   int mode_;
255   /* Infeasibility state i.e. array of infeasibilities and sequenceIn-
256 	0 - correct
257 	1 - needs correcting
258 	2 - not known but column sequence has been chosen
259      */
260   int infeasibilitiesState_;
261   /// Life of weights
262   Persistence persistence_;
263   /// Number of times switched from partial dantzig to 0/2
264   int numberSwitched_;
265   // This is pivot row (or pivot sequence round re-factorization)
266   int pivotSequence_;
267   // This is saved pivot sequence
268   int savedPivotSequence_;
269   // This is saved outgoing variable
270   int savedSequenceOut_;
271   // Iteration when last rectified
272   int lastRectified_;
273   // Size of factorization at invert (used to decide algorithm)
274   int sizeFactorization_;
275   //@}
276 };
277 
278 #endif
279 
280 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
281 */
282