source: branches/pre/include/ClpPrimalColumnSteepest.hpp @ 212

Last change on this file since 212 was 212, checked in by forrest, 16 years ago

lots of stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.3 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpPrimalColumnSteepest_H
4#define ClpPrimalColumnSteepest_H
5
6#include "ClpPrimalColumnPivot.hpp"
7#include <bitset>
8
9//#############################################################################
10
11
12/** Primal Column Pivot Steepest Edge Algorithm Class
13
14See Forrest-Goldfarb paper for algorithm
15
16*/
17
18class CoinIndexedVector;
19
20class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot {
21 
22public:
23 
24  ///@name Algorithmic methods
25  //@{
26 
27  /** Returns pivot column, -1 if none.
28      updateArray has cost updates (also use pivotRow_ from last iteration).
29      Parts of operation split out into seperate functions for
30      profiling and speed
31  */
32  virtual int pivotColumn(CoinIndexedVector * updates,
33                          CoinIndexedVector * spareRow1,
34                          CoinIndexedVector * spareRow2,
35                          CoinIndexedVector * spareColumn1,
36                          CoinIndexedVector * spareColumn2);
37  /// For quadratic or funny nonlinearities
38  int pivotColumnOldMethod(CoinIndexedVector * updates,
39                          CoinIndexedVector * spareRow1,
40                          CoinIndexedVector * spareRow2,
41                          CoinIndexedVector * spareColumn1,
42                          CoinIndexedVector * spareColumn2);
43  /// Just update djs
44  void justDjs(CoinIndexedVector * updates,
45               CoinIndexedVector * spareRow1,
46               CoinIndexedVector * spareRow2,
47               CoinIndexedVector * spareColumn1,
48               CoinIndexedVector * spareColumn2);
49  /// Update djs, weights for Devex using djs
50  void djsAndDevex(CoinIndexedVector * updates,
51               CoinIndexedVector * spareRow1,
52               CoinIndexedVector * spareRow2,
53               CoinIndexedVector * spareColumn1,
54               CoinIndexedVector * spareColumn2);
55  /// Update djs, weights for Steepest using djs
56  void djsAndSteepest(CoinIndexedVector * updates,
57               CoinIndexedVector * spareRow1,
58               CoinIndexedVector * spareRow2,
59               CoinIndexedVector * spareColumn1,
60               CoinIndexedVector * spareColumn2);
61  /// Update djs, weights for Devex using pivot row
62  void djsAndDevex2(CoinIndexedVector * updates,
63               CoinIndexedVector * spareRow1,
64               CoinIndexedVector * spareRow2,
65               CoinIndexedVector * spareColumn1,
66               CoinIndexedVector * spareColumn2);
67  /// Update djs, weights for Steepest using pivot row
68  void djsAndSteepest2(CoinIndexedVector * updates,
69               CoinIndexedVector * spareRow1,
70               CoinIndexedVector * spareRow2,
71               CoinIndexedVector * spareColumn1,
72               CoinIndexedVector * spareColumn2);
73  /// Update weights for Devex
74  void justDevex(CoinIndexedVector * updates,
75               CoinIndexedVector * spareRow1,
76               CoinIndexedVector * spareRow2,
77               CoinIndexedVector * spareColumn1,
78               CoinIndexedVector * spareColumn2);
79  /// Update weights for Steepest
80  void justSteepest(CoinIndexedVector * updates,
81               CoinIndexedVector * spareRow1,
82               CoinIndexedVector * spareRow2,
83               CoinIndexedVector * spareColumn1,
84               CoinIndexedVector * spareColumn2);
85
86  /// Updates weights - part 1 - also checks accuracy
87  virtual void updateWeights(CoinIndexedVector * input);
88
89  /// Checks accuracy - just for debug
90  void checkAccuracy(int sequence,double relativeTolerance,
91                     CoinIndexedVector * rowArray1,
92                     CoinIndexedVector * rowArray2);
93
94  /// Initialize weights
95  void initializeWeights();
96
97  /// Save weights
98  virtual void saveWeights(ClpSimplex * model,int mode);
99  /// Gets rid of last update
100  virtual void unrollWeights();
101  /// Gets rid of all arrays
102  virtual void clearArrays();
103  /// Returns true if would not find any column
104  virtual bool looksOptimal() const;
105  //@}
106 
107  /**@name gets and sets */
108  //@{
109  /// Mode
110  inline int mode() const
111    { return mode_;};
112 //@}
113
114 
115  ///@name Constructors and destructors
116  //@{
117  /** Default Constructor
118      0 is exact devex, 1 full steepest, 2 is partial exact devex
119      3 switches between 0 and 2 depending on factorization
120      4 starts as partial dantzig/devex but then may switch between 0 and 2.
121      By partial exact devex is meant that the weights are updated as normal
122      but only part of the nonbasic variables are scanned. 
123      This can be faster on very easy problems.
124  */
125  ClpPrimalColumnSteepest(int mode=3); 
126 
127  /// Copy constructor
128  ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest &);
129 
130  /// Assignment operator
131  ClpPrimalColumnSteepest & operator=(const ClpPrimalColumnSteepest& rhs);
132 
133  /// Destructor
134  virtual ~ClpPrimalColumnSteepest ();
135
136  /// Clone
137  virtual ClpPrimalColumnPivot * clone(bool copyData = true) const;
138 
139  //@}
140
141  ///@name Private functions to deal with devex
142  /** reference would be faster using ClpSimplex's status_,
143      but I prefer to keep modularity.
144  */
145  inline bool reference(int i) const {
146    return ((reference_[i>>5]>>(i&31))&1)!=0;
147  }
148  inline void setReference(int i,bool trueFalse) {
149    unsigned int & value = reference_[i>>5];
150    int bit = i&31;
151    if (trueFalse)
152      value |= (1<<bit);
153    else
154      value &= ~(1<<bit);
155  }
156  //@}
157  //---------------------------------------------------------------------------
158 
159private:
160  ///@name Private member data
161  // Update weight
162  double devex_;
163  /// weight array
164  double * weights_;
165  /// square of infeasibility array (just for infeasible columns)
166  CoinIndexedVector * infeasible_;
167  /// alternate weight array (so we can unroll)
168  CoinIndexedVector * alternateWeights_;
169  /// save weight array (so we can use checkpoint)
170  double * savedWeights_;
171  // Array for exact devex to say what is in reference framework
172  unsigned int * reference_;
173  /** Status
174      0) Normal
175      -1) Needs initialization
176      1) Weights are stored by sequence number
177  */
178  int state_;
179  /**
180      0 is exact devex, 1 full steepest, 2 is partial exact devex
181      3 switches between 0 and 2 depending on factorization
182      4 starts as partial dantzig/devex but then may switch between 0 and 2.
183      By partial exact devex is meant that the weights are updated as normal
184      but only part of the nonbasic variables are scanned. 
185      This can be faster on very easy problems.*/
186  int mode_;
187  /// Number of times switched from partial dantzig to 0/2
188  int numberSwitched_;
189  // This is pivot row (or pivot sequence round re-factorization)
190  int pivotSequence_; 
191  // This is saved pivot sequence
192  int savedPivotSequence_; 
193  // This is saved outgoing variable
194  int savedSequenceOut_; 
195  //@}
196};
197
198#endif
Note: See TracBrowser for help on using the repository browser.