source: trunk/Clp/src/ClpPrimalColumnSteepest.hpp @ 1525

Last change on this file since 1525 was 1525, checked in by mjs, 10 years ago

Formatted .cpp, .hpp, .c, .h files with "astyle -A4 -p". This matches the formatting used in the grand CBC reorganization.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 8.9 KB
Line 
1/* $Id: ClpPrimalColumnSteepest.hpp 1525 2010-02-26 17:27:59Z mjs $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef ClpPrimalColumnSteepest_H
5#define ClpPrimalColumnSteepest_H
6
7#include "ClpPrimalColumnPivot.hpp"
8#include <bitset>
9
10//#############################################################################
11class CoinIndexedVector;
12
13
14/** Primal Column Pivot Steepest Edge Algorithm Class
15
16See Forrest-Goldfarb paper for algorithm
17
18*/
19
20
21class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot {
22
23public:
24
25     ///@name Algorithmic methods
26     //@{
27
28     /** Returns pivot column, -1 if none.
29         The Packed CoinIndexedVector updates has cost updates - for normal LP
30         that is just +-weight where a feasibility changed.  It also has
31         reduced cost from last iteration in pivot row
32         Parts of operation split out into separate functions for
33         profiling and speed
34     */
35     virtual int pivotColumn(CoinIndexedVector * updates,
36                             CoinIndexedVector * spareRow1,
37                             CoinIndexedVector * spareRow2,
38                             CoinIndexedVector * spareColumn1,
39                             CoinIndexedVector * spareColumn2);
40     /// For quadratic or funny nonlinearities
41     int pivotColumnOldMethod(CoinIndexedVector * updates,
42                              CoinIndexedVector * spareRow1,
43                              CoinIndexedVector * spareRow2,
44                              CoinIndexedVector * spareColumn1,
45                              CoinIndexedVector * spareColumn2);
46     /// Just update djs
47     void justDjs(CoinIndexedVector * updates,
48                  CoinIndexedVector * spareRow2,
49                  CoinIndexedVector * spareColumn1,
50                  CoinIndexedVector * spareColumn2);
51     /// Update djs doing partial pricing (dantzig)
52     int partialPricing(CoinIndexedVector * updates,
53                        CoinIndexedVector * spareRow2,
54                        int numberWanted,
55                        int numberLook);
56     /// Update djs, weights for Devex using djs
57     void djsAndDevex(CoinIndexedVector * updates,
58                      CoinIndexedVector * spareRow2,
59                      CoinIndexedVector * spareColumn1,
60                      CoinIndexedVector * spareColumn2);
61     /// Update djs, weights for Steepest using djs
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     void 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     /// Gets rid of last update
112     virtual void unrollWeights();
113     /// Gets rid of all arrays
114     virtual void clearArrays();
115     /// Returns true if would not find any column
116     virtual bool looksOptimal() const;
117     /// Called when maximum pivots changes
118     virtual void maximumPivotsChanged();
119     //@}
120
121     /**@name gets and sets */
122     //@{
123     /// Mode
124     inline int mode() const {
125          return mode_;
126     }
127     /** Returns number of extra columns for sprint algorithm - 0 means off.
128         Also number of iterations before recompute
129     */
130     virtual int numberSprintColumns(int & numberIterations) const;
131     /// Switch off sprint idea
132     virtual void switchOffSprint();
133
134//@}
135
136     /** enums for persistence
137     */
138     enum Persistence {
139          normal = 0x00, // create (if necessary) and destroy
140          keep = 0x01 // create (if necessary) and leave
141     };
142
143     ///@name Constructors and destructors
144     //@{
145     /** Default Constructor
146         0 is exact devex, 1 full steepest, 2 is partial exact devex
147         3 switches between 0 and 2 depending on factorization
148         4 starts as partial dantzig/devex but then may switch between 0 and 2.
149         By partial exact devex is meant that the weights are updated as normal
150         but only part of the nonbasic variables are scanned.
151         This can be faster on very easy problems.
152     */
153     ClpPrimalColumnSteepest(int mode = 3);
154
155     /// Copy constructor
156     ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest & rhs);
157
158     /// Assignment operator
159     ClpPrimalColumnSteepest & operator=(const ClpPrimalColumnSteepest& rhs);
160
161     /// Destructor
162     virtual ~ClpPrimalColumnSteepest ();
163
164     /// Clone
165     virtual ClpPrimalColumnPivot * clone(bool copyData = true) const;
166
167     //@}
168
169     ///@name Private functions to deal with devex
170     /** reference would be faster using ClpSimplex's status_,
171         but I prefer to keep modularity.
172     */
173     inline bool reference(int i) const {
174          return ((reference_[i>>5] >> (i & 31)) & 1) != 0;
175     }
176     inline void setReference(int i, bool trueFalse) {
177          unsigned int & value = reference_[i>>5];
178          int bit = i & 31;
179          if (trueFalse)
180               value |= (1 << bit);
181          else
182               value &= ~(1 << bit);
183     }
184     /// Set/ get persistence
185     inline void setPersistence(Persistence life) {
186          persistence_ = life;
187     }
188     inline Persistence persistence() const {
189          return persistence_ ;
190     }
191
192     //@}
193     //---------------------------------------------------------------------------
194
195private:
196     ///@name Private member data
197     // Update weight
198     double devex_;
199     /// weight array
200     double * weights_;
201     /// square of infeasibility array (just for infeasible columns)
202     CoinIndexedVector * infeasible_;
203     /// alternate weight array (so we can unroll)
204     CoinIndexedVector * alternateWeights_;
205     /// save weight array (so we can use checkpoint)
206     double * savedWeights_;
207     // Array for exact devex to say what is in reference framework
208     unsigned int * reference_;
209     /** Status
210         0) Normal
211         -1) Needs initialization
212         1) Weights are stored by sequence number
213     */
214     int state_;
215     /**
216         0 is exact devex, 1 full steepest, 2 is partial exact devex
217         3 switches between 0 and 2 depending on factorization
218         4 starts as partial dantzig/devex but then may switch between 0 and 2.
219         5 is always partial dantzig
220         By partial exact devex is meant that the weights are updated as normal
221         but only part of the nonbasic variables are scanned.
222         This can be faster on very easy problems.
223
224         New dubious option is >=10 which does mini-sprint
225
226     */
227     int mode_;
228     /// Life of weights
229     Persistence persistence_;
230     /// Number of times switched from partial dantzig to 0/2
231     int numberSwitched_;
232     // This is pivot row (or pivot sequence round re-factorization)
233     int pivotSequence_;
234     // This is saved pivot sequence
235     int savedPivotSequence_;
236     // This is saved outgoing variable
237     int savedSequenceOut_;
238     // Iteration when last rectified
239     int lastRectified_;
240     // Size of factorization at invert (used to decide algorithm)
241     int sizeFactorization_;
242     //@}
243};
244
245#endif
Note: See TracBrowser for help on using the repository browser.