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

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

formatting

  • Property svn:keywords set to Id
File size: 6.5 KB
Line 
1/* $Id: AbcPrimalColumnSteepest.hpp 2385 2019-01-06 19:43:06Z stefan $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others, Copyright (C) 2012, FasterCoin.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef AbcPrimalColumnSteepest_H
7#define AbcPrimalColumnSteepest_H
8
9#include "AbcPrimalColumnPivot.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 AbcPrimalColumnSteepest : public AbcPrimalColumnPivot {
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(CoinPartitionedVector *updates,
35    CoinPartitionedVector *spareRow2,
36    CoinPartitionedVector *spareColumn1);
37  /// Just update djs
38  void justDjs(CoinIndexedVector *updates,
39    CoinIndexedVector *spareColumn1);
40  /// Update djs doing partial pricing (dantzig)
41  int partialPricing(CoinIndexedVector *updates,
42    int numberWanted,
43    int numberLook);
44  /// Update djs, weights for Devex using djs
45  void djsAndDevex(CoinIndexedVector *updates,
46    CoinIndexedVector *spareRow2,
47    CoinIndexedVector *spareColumn1);
48  /// Update djs, weights for Devex using pivot row
49  void djsAndDevex2(CoinIndexedVector *updates,
50    CoinIndexedVector *spareColumn1);
51  /// Update weights for Devex
52  void justDevex(CoinIndexedVector *updates,
53    CoinIndexedVector *spareColumn1);
54  /** Does steepest work
55      type -
56      0 - just djs
57      1 - just steepest
58      2 - both using scaleFactor
59      3 - both using extra array
60   */
61  int doSteepestWork(CoinPartitionedVector *updates,
62    CoinPartitionedVector *spareRow2,
63    CoinPartitionedVector *spareColumn1,
64    int type);
65
66  /// Updates weights - part 1 - also checks accuracy
67  virtual void updateWeights(CoinIndexedVector *input);
68
69  /// Checks accuracy - just for debug
70  void checkAccuracy(int sequence, double relativeTolerance,
71    CoinIndexedVector *rowArray1);
72
73  /// Initialize weights
74  void initializeWeights();
75
76  /** Save weights - this may initialize weights as well
77         mode is -
78         1) before factorization
79         2) after factorization
80         3) just redo infeasibilities
81         4) restore weights
82         5) at end of values pass (so need initialization)
83     */
84  virtual void saveWeights(AbcSimplex *model, int mode);
85  /// Gets rid of last update
86  virtual void unrollWeights();
87  /// Gets rid of all arrays
88  virtual void clearArrays();
89  /// Returns true if would not find any column
90  virtual bool looksOptimal() const;
91  /// Called when maximum pivots changes
92  virtual void maximumPivotsChanged();
93  //@}
94
95  /**@name gets and sets */
96  //@{
97  /// Mode
98  inline int mode() const
99  {
100    return mode_;
101  }
102  //@}
103
104  /** enums for persistence
105     */
106  enum Persistence {
107    normal = 0x00, // create (if necessary) and destroy
108    keep = 0x01 // create (if necessary) and leave
109  };
110
111  ///@name Constructors and destructors
112  //@{
113  /** Default Constructor
114         0 is exact devex, 1 full steepest, 2 is partial exact devex
115         3 switches between 0 and 2 depending on factorization
116         4 starts as partial dantzig/devex but then may switch between 0 and 2.
117         By partial exact devex is meant that the weights are updated as normal
118         but only part of the nonbasic variables are scanned.
119         This can be faster on very easy problems.
120     */
121  AbcPrimalColumnSteepest(int mode = 3);
122
123  /// Copy constructor
124  AbcPrimalColumnSteepest(const AbcPrimalColumnSteepest &rhs);
125
126  /// Assignment operator
127  AbcPrimalColumnSteepest &operator=(const AbcPrimalColumnSteepest &rhs);
128
129  /// Destructor
130  virtual ~AbcPrimalColumnSteepest();
131
132  /// Clone
133  virtual AbcPrimalColumnPivot *clone(bool copyData = true) const;
134
135  //@}
136
137  ///@name Private functions to deal with devex
138  /** reference would be faster using AbcSimplex's status_,
139         but I prefer to keep modularity.
140     */
141  inline bool reference(int i) const
142  {
143    return ((reference_[i >> 5] >> (i & 31)) & 1) != 0;
144  }
145  inline void setReference(int i, bool trueFalse)
146  {
147    unsigned int &value = reference_[i >> 5];
148    int bit = i & 31;
149    if (trueFalse)
150      value |= (1 << bit);
151    else
152      value &= ~(1 << bit);
153  }
154  /// Set/ get persistence
155  inline void setPersistence(Persistence life)
156  {
157    persistence_ = life;
158  }
159  inline Persistence persistence() const
160  {
161    return persistence_;
162  }
163
164  //@}
165  //---------------------------------------------------------------------------
166
167private:
168  ///@name Private member data
169  // Update weight
170  double devex_;
171  /// weight array
172  double *weights_;
173  /// square of infeasibility array (just for infeasible columns)
174  CoinIndexedVector *infeasible_;
175  /// alternate weight array (so we can unroll)
176  CoinIndexedVector *alternateWeights_;
177  /// save weight array (so we can use checkpoint)
178  double *savedWeights_;
179  // Array for exact devex to say what is in reference framework
180  unsigned int *reference_;
181  /** Status
182         0) Normal
183         -1) Needs initialization
184         1) Weights are stored by sequence number
185     */
186  int state_;
187  /**
188         0 is exact devex, 1 full steepest, 2 is partial exact devex
189         3 switches between 0 and 2 depending on factorization
190         4 starts as partial dantzig/devex but then may switch between 0 and 2.
191         5 is always partial dantzig
192         By partial exact devex is meant that the weights are updated as normal
193         but only part of the nonbasic variables are scanned.
194         This can be faster on very easy problems.
195
196         New dubious option is >=10 which does mini-sprint
197
198     */
199  int mode_;
200  /// Life of weights
201  Persistence persistence_;
202  /// Number of times switched from partial dantzig to 0/2
203  int numberSwitched_;
204  // This is pivot row (or pivot sequence round re-factorization)
205  int pivotSequence_;
206  // This is saved pivot sequence
207  int savedPivotSequence_;
208  // This is saved outgoing variable
209  int savedSequenceOut_;
210  // Iteration when last rectified
211  int lastRectified_;
212  // Size of factorization at invert (used to decide algorithm)
213  int sizeFactorization_;
214  //@}
215};
216
217#endif
218
219/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
220*/
Note: See TracBrowser for help on using the repository browser.