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//#############################################################################
13class CoinIndexedVector;
14
15
16/** Primal Column Pivot Steepest Edge Algorithm Class
17
18See Forrest-Goldfarb paper for algorithm
19
20*/
21
22
23class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot {
24
25public:
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
126 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 */
175 inline bool reference(int i) const {
176 return ((reference_[i>>5] >> (i & 31)) & 1) != 0;
177 }
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
187 inline void setPersistence(Persistence life) {
188 persistence_ = life;
189 }
190 inline Persistence persistence() const {
191 return persistence_ ;
192 }
193
194 //@}
195 //---------------------------------------------------------------------------
196
197private:
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