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

Last change on this file since 2470 was 2385, checked in by unxusr, 8 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 8.5 KB
Line 
1/* $Id: ClpPrimalColumnSteepest.hpp 2385 2019-01-06 19:43:06Z stefan $ */
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/** Primal Column Pivot Steepest Edge Algorithm Class
16
17See Forrest-Goldfarb paper for algorithm
18
19*/
20
21class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot {
22
23public:
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 *spareRow2,
48    CoinIndexedVector *spareColumn1,
49    CoinIndexedVector *spareColumn2);
50  /// Update djs doing partial pricing (dantzig)
51  int partialPricing(CoinIndexedVector *updates,
52    CoinIndexedVector *spareRow2,
53    int numberWanted,
54    int numberLook);
55  /// Update djs, weights for Devex using djs
56  void djsAndDevex(CoinIndexedVector *updates,
57    CoinIndexedVector *spareRow2,
58    CoinIndexedVector *spareColumn1,
59    CoinIndexedVector *spareColumn2);
60  /** Update djs, weights for Steepest using djs
61         sets best sequence (possibly) */
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  int 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  /// redo infeasibilities
112  void redoInfeasibilities();
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  {
128    return mode_;
129  }
130  /// Set mode
131  inline void setMode(int mode)
132  {
133    mode_ = mode;
134  }
135  /// square of infeasibility array (just for infeasible columns)
136  inline CoinIndexedVector *infeasible() const
137  {
138    return infeasible_;
139  }
140  /// Weights
141  inline const double *weights() const
142  {
143    return weights_;
144  }
145  /// alternate weight array
146  inline CoinIndexedVector *alternateWeights() const
147  {
148    return alternateWeights_;
149  }
150  /** Returns number of extra columns for sprint algorithm - 0 means off.
151         Also number of iterations before recompute
152     */
153  virtual int numberSprintColumns(int &numberIterations) const;
154  /// Switch off sprint idea
155  virtual void switchOffSprint();
156
157  //@}
158
159  /** enums for persistence
160     */
161  enum Persistence {
162    normal = 0x00, // create (if necessary) and destroy
163    keep = 0x01 // create (if necessary) and leave
164  };
165
166  ///@name Constructors and destructors
167  //@{
168  /** Default Constructor
169         0 is exact devex, 1 full steepest, 2 is partial exact devex
170         3 switches between 0 and 2 depending on factorization
171         4 starts as partial dantzig/devex but then may switch between 0 and 2.
172         By partial exact devex is meant that the weights are updated as normal
173         but only part of the nonbasic variables are scanned.
174         This can be faster on very easy problems.
175     */
176  ClpPrimalColumnSteepest(int mode = 3);
177
178  /// Copy constructor
179  ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest &rhs);
180
181  /// Assignment operator
182  ClpPrimalColumnSteepest &operator=(const ClpPrimalColumnSteepest &rhs);
183
184  /// Destructor
185  virtual ~ClpPrimalColumnSteepest();
186
187  /// Clone
188  virtual ClpPrimalColumnPivot *clone(bool copyData = true) const;
189
190  //@}
191
192  ///@name Private functions to deal with devex
193  /** reference would be faster using ClpSimplex's status_,
194         but I prefer to keep modularity.
195     */
196  inline bool reference(int i) const
197  {
198    return ((reference_[i >> 5] >> (i & 31)) & 1) != 0;
199  }
200  inline void setReference(int i, bool trueFalse)
201  {
202    unsigned int &value = reference_[i >> 5];
203    int bit = i & 31;
204    if (trueFalse)
205      value |= (1 << bit);
206    else
207      value &= ~(1 << bit);
208  }
209  /// Set/ get persistence
210  inline void setPersistence(Persistence life)
211  {
212    persistence_ = life;
213  }
214  inline Persistence persistence() const
215  {
216    return persistence_;
217  }
218
219  //@}
220  //---------------------------------------------------------------------------
221
222protected:
223  ///@name Protected member data
224  // Update weight
225  double devex_;
226  /// weight array
227  double *weights_;
228  /// square of infeasibility array (just for infeasible columns)
229  CoinIndexedVector *infeasible_;
230  /// alternate weight array (so we can unroll)
231  CoinIndexedVector *alternateWeights_;
232  /// save weight array (so we can use checkpoint)
233  double *savedWeights_;
234  // Array for exact devex to say what is in reference framework
235  unsigned int *reference_;
236  /** Status
237         0) Normal
238         -1) Needs initialization
239         1) Weights are stored by sequence number
240     */
241  int state_;
242  /**
243         0 is exact devex, 1 full steepest, 2 is partial exact devex
244         3 switches between 0 and 2 depending on factorization
245         4 starts as partial dantzig/devex but then may switch between 0 and 2.
246         5 is always partial dantzig
247         By partial exact devex is meant that the weights are updated as normal
248         but only part of the nonbasic variables are scanned.
249         This can be faster on very easy problems.
250
251         New dubious option is >=10 which does mini-sprint
252
253     */
254  int mode_;
255  /* Infeasibility state i.e. array of infeasibilities and sequenceIn-
256        0 - correct
257        1 - needs correcting
258        2 - not known but column sequence has been chosen
259     */
260  int infeasibilitiesState_;
261  /// Life of weights
262  Persistence persistence_;
263  /// Number of times switched from partial dantzig to 0/2
264  int numberSwitched_;
265  // This is pivot row (or pivot sequence round re-factorization)
266  int pivotSequence_;
267  // This is saved pivot sequence
268  int savedPivotSequence_;
269  // This is saved outgoing variable
270  int savedSequenceOut_;
271  // Iteration when last rectified
272  int lastRectified_;
273  // Size of factorization at invert (used to decide algorithm)
274  int sizeFactorization_;
275  //@}
276};
277
278#endif
279
280/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
281*/
Note: See TracBrowser for help on using the repository browser.