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