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

Last change on this file since 2030 was 1665, checked in by lou, 9 years ago

Add EPL license notice in src.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 8.9 KB
Line 
1/* $Id: ClpPrimalColumnSteepest.hpp 1665 2011-01-04 17:55:54Z forrest $ */
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);
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);
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);
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
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;
133     /// Switch off sprint idea
134     virtual void switchOffSprint();
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;
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
Note: See TracBrowser for help on using the repository browser.