source: stable/1.15/Clp/src/AbcPrimalColumnSteepest.hpp @ 1995

Last change on this file since 1995 was 1910, checked in by stefan, 7 years ago
  • add configure option --enable-aboca={1,2,3,4,yes,no}
  • compile Aboca source only if --enable-aboca set (instead of compiling empty source files)
  • fix svn properties
  • Property svn:keywords set to Id
File size: 7.0 KB
Line 
1/* $Id: AbcPrimalColumnSteepest.hpp 1910 2013-01-27 02:00:13Z 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
16/** Primal Column Pivot Steepest Edge Algorithm Class
17
18See Forrest-Goldfarb paper for algorithm
19
20*/
21
22
23class AbcPrimalColumnSteepest : public AbcPrimalColumnPivot {
24
25public:
26
27     ///@name Algorithmic methods
28     //@{
29
30     /** Returns pivot column, -1 if none.
31         The Packed CoinIndexedVector updates has cost updates - for normal LP
32         that is just +-weight where a feasibility changed.  It also has
33         reduced cost from last iteration in pivot row
34         Parts of operation split out into separate functions for
35         profiling and speed
36     */
37     virtual int pivotColumn(CoinPartitionedVector * updates,
38                             CoinPartitionedVector * spareRow2,
39                             CoinPartitionedVector * spareColumn1);
40     /// Just update djs
41     void justDjs(CoinIndexedVector * updates,
42                  CoinIndexedVector * spareColumn1);
43     /// Update djs doing partial pricing (dantzig)
44     int partialPricing(CoinIndexedVector * updates,
45                        int numberWanted,
46                        int numberLook);
47     /// Update djs, weights for Devex using djs
48     void djsAndDevex(CoinIndexedVector * updates,
49                      CoinIndexedVector * spareRow2,
50                      CoinIndexedVector * spareColumn1);
51     /// Update djs, weights for Devex using pivot row
52     void djsAndDevex2(CoinIndexedVector * updates,
53                       CoinIndexedVector * spareColumn1);
54     /// Update weights for Devex
55     void justDevex(CoinIndexedVector * updates,
56                    CoinIndexedVector * spareColumn1);
57  /** Does steepest work
58      type -
59      0 - just djs
60      1 - just steepest
61      2 - both using scaleFactor
62      3 - both using extra array
63   */
64     int doSteepestWork(CoinPartitionedVector * updates,
65                        CoinPartitionedVector * spareRow2,
66                        CoinPartitionedVector * spareColumn1,
67                        int type);
68
69     /// Updates weights - part 1 - also checks accuracy
70     virtual void updateWeights(CoinIndexedVector * input);
71
72     /// Checks accuracy - just for debug
73     void checkAccuracy(int sequence, double relativeTolerance,
74                        CoinIndexedVector * rowArray1);
75
76     /// Initialize weights
77     void initializeWeights();
78
79     /** Save weights - this may initialize weights as well
80         mode is -
81         1) before factorization
82         2) after factorization
83         3) just redo infeasibilities
84         4) restore weights
85         5) at end of values pass (so need initialization)
86     */
87     virtual void saveWeights(AbcSimplex * model, int mode);
88     /// Gets rid of last update
89     virtual void unrollWeights();
90     /// Gets rid of all arrays
91     virtual void clearArrays();
92     /// Returns true if would not find any column
93     virtual bool looksOptimal() const;
94     /// Called when maximum pivots changes
95     virtual void maximumPivotsChanged();
96     //@}
97
98     /**@name gets and sets */
99     //@{
100     /// Mode
101     inline int mode() const {
102          return mode_;
103     }
104//@}
105
106     /** enums for persistence
107     */
108     enum Persistence {
109          normal = 0x00, // create (if necessary) and destroy
110          keep = 0x01 // create (if necessary) and leave
111     };
112
113     ///@name Constructors and destructors
114     //@{
115     /** Default Constructor
116         0 is exact devex, 1 full steepest, 2 is partial exact devex
117         3 switches between 0 and 2 depending on factorization
118         4 starts as partial dantzig/devex but then may switch between 0 and 2.
119         By partial exact devex is meant that the weights are updated as normal
120         but only part of the nonbasic variables are scanned.
121         This can be faster on very easy problems.
122     */
123     AbcPrimalColumnSteepest(int mode = 3);
124
125     /// Copy constructor
126     AbcPrimalColumnSteepest(const AbcPrimalColumnSteepest & rhs);
127
128     /// Assignment operator
129     AbcPrimalColumnSteepest & operator=(const AbcPrimalColumnSteepest& rhs);
130
131     /// Destructor
132     virtual ~AbcPrimalColumnSteepest ();
133
134     /// Clone
135     virtual AbcPrimalColumnPivot * clone(bool copyData = true) const;
136
137     //@}
138
139     ///@name Private functions to deal with devex
140     /** reference would be faster using AbcSimplex's status_,
141         but I prefer to keep modularity.
142     */
143     inline bool reference(int i) const {
144          return ((reference_[i>>5] >> (i & 31)) & 1) != 0;
145     }
146     inline void setReference(int i, bool trueFalse) {
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          persistence_ = life;
157     }
158     inline Persistence persistence() const {
159          return persistence_ ;
160     }
161
162     //@}
163     //---------------------------------------------------------------------------
164
165private:
166     ///@name Private member data
167     // Update weight
168     double devex_;
169     /// weight array
170     double * weights_;
171     /// square of infeasibility array (just for infeasible columns)
172     CoinIndexedVector * infeasible_;
173     /// alternate weight array (so we can unroll)
174     CoinIndexedVector * alternateWeights_;
175     /// save weight array (so we can use checkpoint)
176     double * savedWeights_;
177     // Array for exact devex to say what is in reference framework
178     unsigned int * reference_;
179     /** Status
180         0) Normal
181         -1) Needs initialization
182         1) Weights are stored by sequence number
183     */
184     int state_;
185     /**
186         0 is exact devex, 1 full steepest, 2 is partial exact devex
187         3 switches between 0 and 2 depending on factorization
188         4 starts as partial dantzig/devex but then may switch between 0 and 2.
189         5 is always partial dantzig
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     */
197     int mode_;
198     /// Life of weights
199     Persistence persistence_;
200     /// Number of times switched from partial dantzig to 0/2
201     int numberSwitched_;
202     // This is pivot row (or pivot sequence round re-factorization)
203     int pivotSequence_;
204     // This is saved pivot sequence
205     int savedPivotSequence_;
206     // This is saved outgoing variable
207     int savedSequenceOut_;
208     // Iteration when last rectified
209     int lastRectified_;
210     // Size of factorization at invert (used to decide algorithm)
211     int sizeFactorization_;
212     //@}
213};
214
215#endif
Note: See TracBrowser for help on using the repository browser.