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