source: stable/1.6/Clp/src/ClpDynamicMatrix.hpp @ 1609

Last change on this file since 1609 was 1088, checked in by andreasw, 13 years ago

merging changes from Bug Squashing Party Aug 2007 to regular trunk

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