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

Last change on this file since 223 was 223, checked in by forrest, 17 years ago

Stuff
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.6 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  /** Returns number of extra columns for sprint algorithm - 0 means off.
113      Also number of iterations before recompute
114  */
115  virtual int numberSprintColumns(int & numberIterations) const;
116  /// Switch off sprint idea
117  virtual void switchOffSprint();
118 
119 //@}
120
121 
122  ///@name Constructors and destructors
123  //@{
124  /** Default Constructor
125      0 is exact devex, 1 full steepest, 2 is partial exact devex
126      3 switches between 0 and 2 depending on factorization
127      4 starts as partial dantzig/devex but then may switch between 0 and 2.
128      By partial exact devex is meant that the weights are updated as normal
129      but only part of the nonbasic variables are scanned. 
130      This can be faster on very easy problems.
131  */
132  ClpPrimalColumnSteepest(int mode=3); 
133 
134  /// Copy constructor
135  ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest &);
136 
137  /// Assignment operator
138  ClpPrimalColumnSteepest & operator=(const ClpPrimalColumnSteepest& rhs);
139 
140  /// Destructor
141  virtual ~ClpPrimalColumnSteepest ();
142
143  /// Clone
144  virtual ClpPrimalColumnPivot * clone(bool copyData = true) const;
145 
146  //@}
147
148  ///@name Private functions to deal with devex
149  /** reference would be faster using ClpSimplex's status_,
150      but I prefer to keep modularity.
151  */
152  inline bool reference(int i) const {
153    return ((reference_[i>>5]>>(i&31))&1)!=0;
154  }
155  inline void setReference(int i,bool trueFalse) {
156    unsigned int & value = reference_[i>>5];
157    int bit = i&31;
158    if (trueFalse)
159      value |= (1<<bit);
160    else
161      value &= ~(1<<bit);
162  }
163  //@}
164  //---------------------------------------------------------------------------
165 
166private:
167  ///@name Private member data
168  // Update weight
169  double devex_;
170  /// weight array
171  double * weights_;
172  /// square of infeasibility array (just for infeasible columns)
173  CoinIndexedVector * infeasible_;
174  /// alternate weight array (so we can unroll)
175  CoinIndexedVector * alternateWeights_;
176  /// save weight array (so we can use checkpoint)
177  double * savedWeights_;
178  // Array for exact devex to say what is in reference framework
179  unsigned int * reference_;
180  /** Status
181      0) Normal
182      -1) Needs initialization
183      1) Weights are stored by sequence number
184  */
185  int state_;
186  /**
187      0 is exact devex, 1 full steepest, 2 is partial exact devex
188      3 switches between 0 and 2 depending on factorization
189      4 starts as partial dantzig/devex but then may switch between 0 and 2.
190      By partial exact devex is meant that the weights are updated as normal
191      but only part of the nonbasic variables are scanned. 
192      This can be faster on very easy problems.
193
194      New dubious option is >=10 which does mini-sprint
195  */
196  int mode_;
197  /// Number of times switched from partial dantzig to 0/2
198  int numberSwitched_;
199  // This is pivot row (or pivot sequence round re-factorization)
200  int pivotSequence_; 
201  // This is saved pivot sequence
202  int savedPivotSequence_; 
203  // This is saved outgoing variable
204  int savedSequenceOut_; 
205  //@}
206};
207
208#endif
Note: See TracBrowser for help on using the repository browser.