source: trunk/Clp/src/ClpGubMatrix.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: 12.4 KB
Line 
1// Copyright (C) 2003, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpGubMatrix_H
4#define ClpGubMatrix_H
5
6
7#include "CoinPragma.hpp"
8
9#include "ClpPackedMatrix.hpp"
10class ClpSimplex;
11/** This implements Gub rows plus a ClpPackedMatrix.
12
13    There will be a version using ClpPlusMinusOne matrix but
14    there is no point doing one with ClpNetworkMatrix (although
15    an embedded network is attractive).
16
17*/
18
19class ClpGubMatrix : public ClpPackedMatrix {
20 
21public:
22  /**@name Main functions provided */
23   //@{
24  /** Returns a new matrix in reverse order without gaps (GUB wants NULL) */
25  virtual ClpMatrixBase * reverseOrderedCopy() const;
26  /// Returns number of elements in column part of basis
27  virtual CoinBigIndex countBasis(ClpSimplex * model,
28                                 const int * whichColumn, 
29                                 int numberRowBasic,
30                                  int & numberColumnBasic);
31  /// Fills in column part of basis
32  virtual void fillBasis(ClpSimplex * model,
33                                 const int * whichColumn, 
34                                 int & numberColumnBasic,
35                                 int * row, int * start,
36                                 int * rowCount, int * columnCount,
37                                 double * element);
38  /** Unpacks a column into an CoinIndexedvector
39   */
40  virtual void unpack(const ClpSimplex * model,CoinIndexedVector * rowArray,
41                   int column) const ;
42  /** Unpacks a column into an CoinIndexedvector
43   ** in packed foramt
44      Note that model is NOT const.  Bounds and objective could
45      be modified if doing column generation (just for this variable) */
46  virtual void unpackPacked(ClpSimplex * model,
47                            CoinIndexedVector * rowArray,
48                            int column) const;
49  /** Adds multiple of a column into an CoinIndexedvector
50      You can use quickAdd to add to vector */
51  virtual void add(const ClpSimplex * model,CoinIndexedVector * rowArray,
52                   int column, double multiplier) const ;
53  /** Adds multiple of a column into an array */
54  virtual void add(const ClpSimplex * model,double * array,
55                   int column, double multiplier) const;
56  /// Partial pricing
57  virtual void partialPricing(ClpSimplex * model, double start, double end,
58                      int & bestSequence, int & numberWanted);
59  /// Returns number of hidden rows e.g. gub
60  virtual int hiddenRows() const;
61   //@}
62
63  /**@name Matrix times vector methods */
64  //@{
65    /** Return <code>x * scalar * A + y</code> in <code>z</code>.
66        Can use y as temporary array (will be empty at end)
67        Note - If x packed mode - then z packed mode
68        Squashes small elements and knows about ClpSimplex */
69  virtual void transposeTimes(const ClpSimplex * model, double scalar,
70                              const CoinIndexedVector * x,
71                              CoinIndexedVector * y,
72                              CoinIndexedVector * z) const;
73    /** Return <code>x * scalar * A + y</code> in <code>z</code>.
74        Can use y as temporary array (will be empty at end)
75        Note - If x packed mode - then z packed mode
76        Squashes small elements and knows about ClpSimplex.
77    This version uses row copy*/
78  virtual void transposeTimesByRow(const ClpSimplex * model, double scalar,
79                              const CoinIndexedVector * x,
80                              CoinIndexedVector * y,
81                              CoinIndexedVector * z) const;
82    /** Return <code>x *A</code> in <code>z</code> but
83        just for indices in y.
84        Note - z always packed mode */
85  virtual void subsetTransposeTimes(const ClpSimplex * model,
86                                    const CoinIndexedVector * x,
87                                    const CoinIndexedVector * y,
88                                    CoinIndexedVector * z) const;
89  /** expands an updated column to allow for extra rows which the main
90      solver does not know about and returns number added if mode 0.
91      If mode 1 deletes extra entries
92
93      This active in Gub
94  */
95  virtual int extendUpdated(ClpSimplex * model,CoinIndexedVector * update,int mode);
96  /**
97     mode=0  - Set up before "update" and "times" for primal solution using extended rows
98     mode=1  - Cleanup primal solution after "times" using extended rows.
99     mode=2  - Check (or report on) primal infeasibilities
100  */
101  virtual void primalExpanded(ClpSimplex * model,int mode);
102  /**
103      mode=0  - Set up before "updateTranspose" and "transposeTimes" for duals using extended
104                updates array (and may use other if dual values pass)
105      mode=1  - Update dual solution after "transposeTimes" using extended rows.
106      mode=2  - Compute all djs and compute key dual infeasibilities
107      mode=3  - Report on key dual infeasibilities
108      mode=4  - Modify before updateTranspose in partial pricing
109  */
110  virtual void dualExpanded(ClpSimplex * model,CoinIndexedVector * array,
111                            double * other,int mode);
112  /**
113      mode=0  - Create list of non-key basics in pivotVariable_ using
114                number as numberBasic in and out
115      mode=1  - Set all key variables as basic
116      mode=2  - return number extra rows needed, number gives maximum number basic
117      mode=3  - before replaceColumn
118      mode=4  - return 1 if can do primal, 2 if dual, 3 if both
119      mode=5  - save any status stuff (when in good state)
120      mode=6  - restore status stuff
121      mode=7  - flag given variable (normally sequenceIn)
122      mode=8  - unflag all variables
123      mode=9  - synchronize costs
124      mode=10  - return 1 if there may be changing bounds on variable (column generation)
125      mode=11  - make sure set is clean (used when a variable rejected - but not flagged)
126      mode=12  - after factorize but before permute stuff
127      mode=13  - at end of simplex to delete stuff
128  */
129  virtual int generalExpanded(ClpSimplex * model,int mode,int & number);
130  /**
131     update information for a pivot (and effective rhs)
132  */
133  virtual int updatePivot(ClpSimplex * model,double oldInValue, double oldOutValue);
134  /// Sets up an effective RHS and does gub crash if needed
135  virtual void useEffectiveRhs(ClpSimplex * model,bool cheapest=true);
136  /** Returns effective RHS offset if it is being used.  This is used for long problems
137      or big gub or anywhere where going through full columns is
138      expensive.  This may re-compute */
139  virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,
140                                bool check=false);
141  /** This is local to Gub to allow synchronization:
142      mode=0 when status of basis is good
143      mode=1 when variable is flagged
144      mode=2 when all variables unflagged (returns number flagged)
145      mode=3 just reset costs (primal)
146      mode=4 correct number of dual infeasibilities
147      mode=5 return 4 if time to re-factorize
148      mode=6  - return 1 if there may be changing bounds on variable (column generation)
149      mode=7  - do extra restores for column generation
150      mode=8  - make sure set is clean
151      mode=9  - adjust lower, upper on set by incoming
152  */
153  virtual int synchronize(ClpSimplex * model,int mode);
154  /// Correct sequence in and out to give true value
155  virtual void correctSequence(int & sequenceIn, int & sequenceOut) const;
156  //@}
157
158
159
160  /**@name Constructors, destructor */
161   //@{
162   /** Default constructor. */
163   ClpGubMatrix();
164   /** Destructor */
165   virtual ~ClpGubMatrix();
166   //@}
167
168   /**@name Copy method */
169   //@{
170   /** The copy constructor. */
171   ClpGubMatrix(const ClpGubMatrix&);
172   /** The copy constructor from an CoinPackedMatrix. */
173   ClpGubMatrix(const CoinPackedMatrix&);
174  /** Subset constructor (without gaps).  Duplicates are allowed
175      and order is as given */
176  ClpGubMatrix (const ClpGubMatrix & wholeModel,
177                    int numberRows, const int * whichRows,
178                    int numberColumns, const int * whichColumns);
179  ClpGubMatrix (const CoinPackedMatrix & wholeModel,
180                    int numberRows, const int * whichRows,
181                    int numberColumns, const int * whichColumns);
182
183  /** This takes over ownership (for space reasons) */
184   ClpGubMatrix(CoinPackedMatrix * matrix);
185
186  /** This takes over ownership (for space reasons) and is the
187      real constructor*/
188   ClpGubMatrix(ClpPackedMatrix * matrix, int numberSets,
189                const int * start, const int * end,
190                const double * lower, const double * upper,
191                const unsigned char * status=NULL);
192
193   ClpGubMatrix& operator=(const ClpGubMatrix&);
194  /// Clone
195  virtual ClpMatrixBase * clone() const ;
196  /** Subset clone (without gaps).  Duplicates are allowed
197      and order is as given */
198  virtual ClpMatrixBase * subsetClone (
199                    int numberRows, const int * whichRows,
200                    int numberColumns, const int * whichColumns) const ;
201  /** redoes next_ for a set.  */
202  void redoSet(ClpSimplex * model,int newKey, int oldKey, int iSet); 
203  //@}
204  /**@name gets and sets */
205  //@{
206  /// Status
207  inline ClpSimplex::Status getStatus(int sequence) const
208  {return static_cast<ClpSimplex::Status> (status_[sequence]&7);};
209  inline void setStatus(int sequence, ClpSimplex::Status status)
210  {
211    unsigned char & st_byte = status_[sequence];
212    st_byte &= ~7;
213    st_byte |= status;
214  };
215  /// To flag a variable
216  inline void setFlagged( int sequence)
217  {
218    status_[sequence] |= 64;
219  };
220  inline void clearFlagged( int sequence)
221  {
222    status_[sequence] &= ~64;
223  };
224  inline bool flagged(int sequence) const
225  {return ((status_[sequence]&64)!=0);};
226  /// To say key is above ub
227  inline void setAbove( int sequence)
228  {
229    unsigned char iStat = status_[sequence];
230    iStat &= ~24;
231    status_[sequence] = iStat|16;
232  };
233  /// To say key is feasible
234  inline void setFeasible( int sequence)
235  {
236    unsigned char iStat = status_[sequence];
237    iStat &= ~24;
238    status_[sequence] = iStat|8;
239  };
240  /// To say key is below lb
241  inline void setBelow( int sequence)
242  {
243    unsigned char iStat = status_[sequence];
244    iStat &= ~24;
245    status_[sequence] = iStat;
246  };
247  inline double weight( int sequence) const
248  {
249    int iStat = status_[sequence]&31;
250    iStat = iStat>>3;
251    return (double) (iStat-1);
252  };
253  /// Starts
254  inline int * start() const
255  { return start_;};
256  /// End
257  inline int * end() const
258  { return end_;};
259  /// Lower bounds on sets
260  inline double * lower() const
261  { return lower_;};
262  /// Upper bounds on sets
263  inline double * upper() const
264  { return upper_;};
265  /// Key variable of set
266  inline int * keyVariable() const
267  { return keyVariable_;};
268  /// Backward pointer to set number
269  inline int * backward() const
270  { return backward_;};
271  /// Number of sets (gub rows)
272  inline int numberSets() const
273  { return numberSets_;};
274  /// Switches off dj checking each factorization (for BIG models)
275  void switchOffCheck();
276   //@}
277   
278   
279protected:
280   /**@name Data members
281      The data members are protected to allow access for derived classes. */
282   //@{
283  /// Sum of dual infeasibilities
284  double sumDualInfeasibilities_;
285  /// Sum of primal infeasibilities
286  double sumPrimalInfeasibilities_;
287  /// Sum of Dual infeasibilities using tolerance based on error in duals
288  double sumOfRelaxedDualInfeasibilities_;
289  /// Sum of Primal infeasibilities using tolerance based on error in primals
290  double sumOfRelaxedPrimalInfeasibilities_;
291  /// Infeasibility weight when last full pass done
292  double infeasibilityWeight_;
293  /// Starts
294  int * start_;
295  /// End
296  int * end_;
297  /// Lower bounds on sets
298  double * lower_;
299  /// Upper bounds on sets
300  double * upper_;
301  /// Status of slacks
302  mutable unsigned char * status_;
303  /// Saved status of slacks
304  unsigned char * saveStatus_;
305  /// Saved key variables
306  int * savedKeyVariable_;
307  /// Backward pointer to set number
308  int * backward_;
309  /// Backward pointer to pivot row !!!
310  int * backToPivotRow_;
311  /// Change in costs for keys
312  double * changeCost_;
313  /// Key variable of set
314  mutable int * keyVariable_;
315  /** Next basic variable in set - starts at key and end with -(set+1).
316      Now changes to -(nonbasic+1).
317      next_ has extra space for 2* longest set */
318  mutable int * next_;
319  /// Backward pointer to index in CoinIndexedVector
320  int * toIndex_;
321  // Reverse pointer from index to set
322  int * fromIndex_; 
323  /// Pointer back to model
324  ClpSimplex * model_;
325  /// Number of dual infeasibilities
326  int numberDualInfeasibilities_;
327  /// Number of primal infeasibilities
328  int numberPrimalInfeasibilities_;
329  /** If pricing will declare victory (i.e. no check every factorization).
330      -1 - always check
331      0  - don't check
332      1  - in don't check mode but looks optimal
333  */
334  int noCheck_;
335  /// Number of sets (gub rows)
336  int numberSets_;
337  /// Number in vector without gub extension
338  int saveNumber_;
339  /// Pivot row of possible next key
340  int possiblePivotKey_;
341  /// Gub slack in (set number or -1)
342  int gubSlackIn_;
343  /// First gub variables (same as start_[0] at present)
344  int firstGub_;
345  /// last gub variable (same as end_[numberSets_-1] at present)
346  int lastGub_;
347  /** type of gub - 0 not contiguous, 1 contiguous
348      add 8 bit to say no ubs on individual variables */
349  int gubType_;
350   //@}
351};
352
353#endif
Note: See TracBrowser for help on using the repository browser.