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