source: releases/1.8.0/Clp/src/ClpPrimalColumnSteepest.hpp @ 2257

Last change on this file since 2257 was 1055, checked in by forrest, 13 years ago

out };

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