source: trunk/Clp/src/ClpDynamicMatrix.hpp @ 754

Last change on this file since 754 was 754, checked in by andreasw, 14 years ago

first version

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.4 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpDynamicMatrix_H
4#define ClpDynamicMatrix_H
5
6
7#include "CoinPragma.hpp"
8
9#include "ClpPackedMatrix.hpp"
10class ClpSimplex;
11/** This implements  a dynamic matrix when we have a limit on the number of
12    "interesting rows". This version inherits from ClpPackedMatrix and knows that
13    the real matrix is gub.  A later version could use shortest path to generate columns.
14
15*/
16
17class ClpDynamicMatrix : public ClpPackedMatrix {
18 
19public:
20  /// enums for status of various sorts
21  enum DynamicStatus {
22    soloKey = 0x00,
23    inSmall = 0x01,
24    atUpperBound = 0x02,
25    atLowerBound = 0x03
26  };
27  /**@name Main functions provided */
28   //@{
29  /// Partial pricing
30  virtual void partialPricing(ClpSimplex * model, double start, double end,
31                      int & bestSequence, int & numberWanted);
32
33  /**
34     update information for a pivot (and effective rhs)
35  */
36  virtual int updatePivot(ClpSimplex * model,double oldInValue, double oldOutValue);
37  /** Returns effective RHS offset if it is being used.  This is used for long problems
38      or big dynamic or anywhere where going through full columns is
39      expensive.  This may re-compute */
40  virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,
41                                bool check=false);
42    /** Return <code>y + A * scalar *x</code> in <code>y</code>.
43        @pre <code>x</code> must be of size <code>numColumns()</code>
44        @pre <code>y</code> must be of size <code>numRows()</code> */
45  virtual void times(double scalar,
46                       const double * x, double * y) const;
47  /// Modifies rhs offset
48  void modifyOffset(int sequence, double amount);
49  /// Gets key value when none in small
50  double keyValue(int iSet) const;
51  /**
52      mode=0  - Set up before "updateTranspose" and "transposeTimes" for duals using extended
53                updates array (and may use other if dual values pass)
54      mode=1  - Update dual solution after "transposeTimes" using extended rows.
55      mode=2  - Compute all djs and compute key dual infeasibilities
56      mode=3  - Report on key dual infeasibilities
57      mode=4  - Modify before updateTranspose in partial pricing
58  */
59  virtual void dualExpanded(ClpSimplex * model,CoinIndexedVector * array,
60                            double * other,int mode);
61  /**
62      mode=0  - Create list of non-key basics in pivotVariable_ using
63                number as numberBasic in and out
64      mode=1  - Set all key variables as basic
65      mode=2  - return number extra rows needed, number gives maximum number basic
66      mode=3  - before replaceColumn
67      mode=4  - return 1 if can do primal, 2 if dual, 3 if both
68      mode=5  - save any status stuff (when in good state)
69      mode=6  - restore status stuff
70      mode=7  - flag given variable (normally sequenceIn)
71      mode=8  - unflag all variables
72      mode=9  - synchronize costs
73      mode=10  - return 1 if there may be changing bounds on variable (column generation)
74      mode=11  - make sure set is clean (used when a variable rejected - but not flagged)
75      mode=12  - after factorize but before permute stuff
76      mode=13  - at end of simplex to delete stuff
77  */
78  virtual int generalExpanded(ClpSimplex * model,int mode,int & number);
79  /** Purely for column generation and similar ideas.  Allows
80      matrix and any bounds or costs to be updated (sensibly).
81      Returns non-zero if any changes.
82  */
83  virtual int refresh(ClpSimplex * model);
84  /** Creates a variable.  This is called after partial pricing and will modify matrix.
85      Will update bestSequence.
86  */
87  virtual void createVariable(ClpSimplex * model, int & bestSequence);
88  /// Returns reduced cost of a variable
89  virtual double reducedCost( ClpSimplex * model,int sequence) const;
90  /// Does gub crash
91  void gubCrash();
92  /// Populates initial matrix from dynamic status
93  void initialProblem();
94  /** Adds in a column to gub structure (called from descendant) and returns sequence */
95  int addColumn(int numberEntries,const int * row, const float * element,
96                 float cost, float lower, float upper, int iSet,
97                 DynamicStatus status);
98  /** If addColumn forces compression then this allows descendant to know what to do.
99      If >=0 then entry stayed in, if -1 then entry went out to lower bound.of zero.
100      Entries at upper bound (really nonzero) never go out (at present).
101  */
102  virtual void packDown(const int * in, int numberToPack) {};
103  /// Gets lower bound (to simplify coding)
104  inline double columnLower(int sequence) const
105  { if (columnLower_) return columnLower_[sequence]; else return 0.0;};
106  /// Gets upper bound (to simplify coding)
107  inline double columnUpper(int sequence) const
108  { if (columnUpper_) return columnUpper_[sequence]; else return COIN_DBL_MAX;};
109
110  //@}
111
112
113
114  /**@name Constructors, destructor */
115   //@{
116   /** Default constructor. */
117   ClpDynamicMatrix();
118  /** This is the real constructor.
119      It assumes factorization frequency will not be changed.
120      This resizes model !!!!
121      The contents of original matrix in model will be taken over and original matrix
122      will be sanitized so can be deleted (to avoid a very small memory leak)
123   */
124  ClpDynamicMatrix(ClpSimplex * model, int numberSets,
125                   int numberColumns, const int * starts,
126                   const double * lower, const double * upper,
127                   const int * startColumn, const int * row,
128                   const double * element, const double * cost,
129                   const double * columnLower=NULL, const double * columnUpper=NULL,
130                   const unsigned char * status=NULL,
131                   const unsigned char * dynamicStatus=NULL);
132 
133   /** Destructor */
134   virtual ~ClpDynamicMatrix();
135   //@}
136
137   /**@name Copy method */
138   //@{
139   /** The copy constructor. */
140   ClpDynamicMatrix(const ClpDynamicMatrix&);
141   /** The copy constructor from an CoinPackedMatrix. */
142   ClpDynamicMatrix(const CoinPackedMatrix&);
143
144   ClpDynamicMatrix& operator=(const ClpDynamicMatrix&);
145  /// Clone
146  virtual ClpMatrixBase * clone() const ;
147  //@}
148  /**@name gets and sets */
149  //@{
150  /// Status of row slacks
151  inline ClpSimplex::Status getStatus(int sequence) const
152  {return static_cast<ClpSimplex::Status> (status_[sequence]&7);};
153  inline void setStatus(int sequence, ClpSimplex::Status status)
154  {
155    unsigned char & st_byte = status_[sequence];
156    st_byte &= ~7;
157    st_byte |= status;
158  };
159  /// Number of sets (dynamic rows)
160  inline int numberSets() const
161  { return numberSets_;};
162  /// Whether flagged
163  inline bool flagged(int i) const {
164    return (dynamicStatus_[i]&8)!=0;
165  };
166  inline void setFlagged(int i) {
167    dynamicStatus_[i] |= 8;
168  };
169  inline void unsetFlagged(int i) {
170    dynamicStatus_[i]  &= ~8;;
171  };
172  inline void setDynamicStatus(int sequence, DynamicStatus status)
173  {
174    unsigned char & st_byte = dynamicStatus_[sequence];
175    st_byte &= ~7;
176    st_byte |= status;
177  };
178  inline DynamicStatus getDynamicStatus(int sequence) const
179  {return static_cast<DynamicStatus> (dynamicStatus_[sequence]&7);};
180  /// Saved value of objective offset
181  inline double objectiveOffset() const
182  { return objectiveOffset_;};
183  /// Starts of each column
184  inline CoinBigIndex * startColumn() const
185  { return startColumn_;};
186  /// rows
187  inline int * row() const
188  { return row_;};
189  /// elements
190  inline float * element() const
191  { return element_;};
192  /// costs
193  inline float * cost() const
194  { return cost_;};
195  /// ids of active columns (just index here)
196  inline int * id() const
197  { return id_;};
198  /// Optional lower bounds on columns
199  inline float * columnLower() const
200  { return columnLower_;};
201  /// Optional upper bounds on columns
202  inline float * columnUpper() const
203  { return columnUpper_;};
204  /// Lower bounds on sets
205  inline float * lowerSet() const
206  { return lowerSet_;};
207  /// Upper bounds on sets
208  inline float * upperSet() const
209  { return upperSet_;};
210  /// size
211  inline int numberGubColumns() const
212  { return numberGubColumns_;};
213  /// first free
214  inline int firstAvailable() const
215  { return firstAvailable_;};
216  /// first dynamic
217  inline int firstDynamic() const
218  { return firstDynamic_;};
219  /// number of columns in dynamic model
220  inline int lastDynamic() const
221  { return lastDynamic_;};
222  /// number of rows in original model
223  inline int numberStaticRows() const
224  { return numberStaticRows_;};
225  /// size of working matrix (max)
226  inline int numberElements() const
227  { return numberElements_;};
228  inline int * keyVariable() const
229  { return keyVariable_;};
230  /// Switches off dj checking each factorization (for BIG models)
231  void switchOffCheck();
232  /// Status region for gub slacks
233  inline unsigned char * gubRowStatus() const
234  { return status_;};
235  /// Status region for gub variables
236  inline unsigned char * dynamicStatus() const
237  { return dynamicStatus_;};
238  /// Returns which set a variable is in
239  int whichSet (int sequence) const;
240   //@}
241   
242   
243protected:
244   /**@name Data members
245      The data members are protected to allow access for derived classes. */
246   //@{
247  /// Sum of dual infeasibilities
248  double sumDualInfeasibilities_;
249  /// Sum of primal infeasibilities
250  double sumPrimalInfeasibilities_;
251  /// Sum of Dual infeasibilities using tolerance based on error in duals
252  double sumOfRelaxedDualInfeasibilities_;
253  /// Sum of Primal infeasibilities using tolerance based on error in primals
254  double sumOfRelaxedPrimalInfeasibilities_;
255  /// Saved best dual on gub row in pricing
256  double savedBestGubDual_;
257  /// Saved best set in pricing
258  int savedBestSet_;
259  /// Backward pointer to pivot row !!!
260  int * backToPivotRow_;
261  /// Key variable of set (only accurate if none in small problem)
262  mutable int * keyVariable_;
263  /// Backward pointer to extra row
264  int * toIndex_;
265  // Reverse pointer from index to set
266  int * fromIndex_; 
267  /// Number of sets (dynamic rows)
268  int numberSets_;
269  /// Number of active sets
270  int numberActiveSets_;
271  /// Saved value of objective offset
272  double objectiveOffset_;
273  /// Lower bounds on sets
274  float * lowerSet_;
275  /// Upper bounds on sets
276  float * upperSet_;
277  /// Status of slack on set
278  unsigned char * status_;
279  /// Pointer back to model
280  ClpSimplex * model_;
281  /// first free
282  int firstAvailable_;
283  /// first free when iteration started
284  int firstAvailableBefore_;
285  /// first dynamic
286  int firstDynamic_;
287  /// number of columns in dynamic model
288  int lastDynamic_;
289  /// number of rows in original model
290  int numberStaticRows_;
291  /// size of working matrix (max)
292  int numberElements_;
293  /// Number of dual infeasibilities
294  int numberDualInfeasibilities_;
295  /// Number of primal infeasibilities
296  int numberPrimalInfeasibilities_;
297  /** If pricing will declare victory (i.e. no check every factorization).
298      -1 - always check
299      0  - don't check
300      1  - in don't check mode but looks optimal
301  */
302  int noCheck_;
303  /// Infeasibility weight when last full pass done
304  double infeasibilityWeight_;
305  /// size
306  int numberGubColumns_;
307  /// current maximum number of columns (then compress)
308  int maximumGubColumns_;
309  /// current maximum number of elemnts (then compress)
310  int maximumElements_;
311  /// Start of each set
312  int * startSet_;
313  /// next in chain
314  int * next_;
315  /// Starts of each column
316  CoinBigIndex * startColumn_;
317  /// rows
318  int * row_;
319  /// elements
320  float * element_;
321  /// costs
322  float * cost_;
323  /// ids of active columns (just index here)
324  int * id_;
325  /// for status and which bound
326  unsigned char * dynamicStatus_;
327  /// Optional lower bounds on columns
328  float * columnLower_;
329  /// Optional upper bounds on columns
330  float * columnUpper_;
331   //@}
332};
333
334#endif
Note: See TracBrowser for help on using the repository browser.