source: trunk/Clp/src/ClpGubMatrix.hpp @ 1502

Last change on this file since 1502 was 1502, checked in by forrest, 10 years ago

moving sandbox stuff to trunk

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