source: trunk/Clp/src/ClpMatrixBase.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: 22.2 KB
Line 
1/* $Id: ClpMatrixBase.hpp 1502 2010-01-29 14:25:07Z forrest $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef ClpMatrixBase_H
5#define ClpMatrixBase_H
6
7#include "CoinPragma.hpp"
8#include "CoinFinite.hpp"
9
10#include "CoinPackedMatrix.hpp"
11class CoinIndexedVector;
12class ClpSimplex;
13class ClpModel;
14
15/** Abstract base class for Clp Matrices
16
17Since this class is abstract, no object of this type can be created.
18
19If a derived class provides all methods then all Clp algorithms
20should work.  Some can be very inefficient e.g. getElements etc is
21only used for tightening bounds for dual and the copies are
22deleted.  Many methods can just be dummy i.e. abort(); if not
23all features are being used.  So if column generation was being done
24then it makes no sense to do steepest edge so there would be
25no point providing subsetTransposeTimes.
26*/
27
28class ClpMatrixBase  {
29
30public:
31    /**@name Virtual methods that the derived classes must provide */
32    //@{
33    /// Return a complete CoinPackedMatrix
34    virtual CoinPackedMatrix * getPackedMatrix() const = 0;
35    /** Whether the packed matrix is column major ordered or not. */
36    virtual bool isColOrdered() const = 0;
37    /** Number of entries in the packed matrix. */
38    virtual CoinBigIndex getNumElements() const = 0;
39    /** Number of columns. */
40    virtual int getNumCols() const = 0;
41    /** Number of rows. */
42    virtual int getNumRows() const = 0;
43
44    /** A vector containing the elements in the packed matrix. Note that there
45        might be gaps in this list, entries that do not belong to any
46        major-dimension vector. To get the actual elements one should look at
47        this vector together with vectorStarts and vectorLengths. */
48    virtual const double * getElements() const = 0;
49    /** A vector containing the minor indices of the elements in the packed
50        matrix. Note that there might be gaps in this list, entries that do not
51        belong to any major-dimension vector. To get the actual elements one
52        should look at this vector together with vectorStarts and
53        vectorLengths. */
54    virtual const int * getIndices() const = 0;
55
56    virtual const CoinBigIndex * getVectorStarts() const = 0;
57    /** The lengths of the major-dimension vectors. */
58    virtual const int * getVectorLengths() const = 0 ;
59    /** The length of a single major-dimension vector. */
60    virtual int getVectorLength(int index) const ;
61    /** Delete the columns whose indices are listed in <code>indDel</code>. */
62    virtual void deleteCols(const int numDel, const int * indDel) = 0;
63    /** Delete the rows whose indices are listed in <code>indDel</code>. */
64    virtual void deleteRows(const int numDel, const int * indDel) = 0;
65#ifndef CLP_NO_VECTOR
66    /// Append Columns
67    virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
68    /// Append Rows
69    virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
70#endif
71    /** Modify one element of packed matrix.  An element may be added.
72        This works for either ordering If the new element is zero it will be
73        deleted unless keepZero true */
74    virtual void modifyCoefficient(int row, int column, double newElement,
75                                   bool keepZero = false);
76    /** Append a set of rows/columns to the end of the matrix. Returns number of errors
77        i.e. if any of the new rows/columns contain an index that's larger than the
78        number of columns-1/rows-1 (if numberOther>0) or duplicates
79        If 0 then rows, 1 if columns */
80    virtual int appendMatrix(int number, int type,
81                             const CoinBigIndex * starts, const int * index,
82                             const double * element, int numberOther = -1);
83
84    /** Returns a new matrix in reverse order without gaps
85        Is allowed to return NULL if doesn't want to have row copy */
86    virtual ClpMatrixBase * reverseOrderedCopy() const {
87        return NULL;
88    }
89
90    /// Returns number of elements in column part of basis
91    virtual CoinBigIndex countBasis(const int * whichColumn,
92                                    int & numberColumnBasic) = 0;
93    /// Fills in column part of basis
94    virtual void fillBasis(ClpSimplex * model,
95                           const int * whichColumn,
96                           int & numberColumnBasic,
97                           int * row, int * start,
98                           int * rowCount, int * columnCount,
99                           CoinFactorizationDouble * element) = 0;
100    /** Creates scales for column copy (rowCopy in model may be modified)
101        default does not allow scaling
102        returns non-zero if no scaling done */
103    virtual int scale(ClpModel * , const ClpSimplex * = NULL) const {
104        return 1;
105    }
106    /** Scales rowCopy if column copy scaled
107        Only called if scales already exist */
108    virtual void scaleRowCopy(ClpModel * ) const { }
109    /// Returns true if can create row copy
110    virtual bool canGetRowCopy() const {
111        return true;
112    }
113    /** Realy really scales column copy
114        Only called if scales already exist.
115        Up to user to delete */
116    inline virtual ClpMatrixBase * scaledColumnCopy(ClpModel * ) const {
117        return this->clone();
118    }
119
120    /** Checks if all elements are in valid range.  Can just
121        return true if you are not paranoid.  For Clp I will
122        probably expect no zeros.  Code can modify matrix to get rid of
123        small elements.
124        check bits (can be turned off to save time) :
125        1 - check if matrix has gaps
126        2 - check if zero elements
127        4 - check and compress duplicates
128        8 - report on large and small
129    */
130    virtual bool allElementsInRange(ClpModel * ,
131                                    double , double ,
132                                    int = 15) {
133        return true;
134    }
135    /** Set the dimensions of the matrix. In effect, append new empty
136        columns/rows to the matrix. A negative number for either dimension
137        means that that dimension doesn't change. Otherwise the new dimensions
138        MUST be at least as large as the current ones otherwise an exception
139        is thrown. */
140    virtual void setDimensions(int numrows, int numcols);
141    /** Returns largest and smallest elements of both signs.
142        Largest refers to largest absolute value.
143        If returns zeros then can't tell anything */
144    virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
145                                 double & smallestPositive, double & largestPositive);
146
147    /** Unpacks a column into an CoinIndexedvector
148     */
149    virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray,
150                        int column) const = 0;
151    /** Unpacks a column into an CoinIndexedvector
152     ** in packed format
153     Note that model is NOT const.  Bounds and objective could
154     be modified if doing column generation (just for this variable) */
155    virtual void unpackPacked(ClpSimplex * model,
156                              CoinIndexedVector * rowArray,
157                              int column) const = 0;
158    /** Purely for column generation and similar ideas.  Allows
159        matrix and any bounds or costs to be updated (sensibly).
160        Returns non-zero if any changes.
161    */
162    virtual int refresh(ClpSimplex * ) {
163        return 0;
164    }
165
166    // Really scale matrix
167    virtual void reallyScale(const double * rowScale, const double * columnScale);
168    /** Given positive integer weights for each row fills in sum of weights
169        for each column (and slack).
170        Returns weights vector
171        Default returns vector of ones
172    */
173    virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model, int * inputWeights) const;
174    /** Adds multiple of a column into an CoinIndexedvector
175        You can use quickAdd to add to vector */
176    virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray,
177                     int column, double multiplier) const = 0;
178    /** Adds multiple of a column into an array */
179    virtual void add(const ClpSimplex * model, double * array,
180                     int column, double multiplier) const = 0;
181    /// Allow any parts of a created CoinPackedMatrix to be deleted
182    virtual void releasePackedMatrix() const = 0;
183    /// Says whether it can do partial pricing
184    virtual bool canDoPartialPricing() const;
185    /// Returns number of hidden rows e.g. gub
186    virtual int hiddenRows() const;
187    /// Partial pricing
188    virtual void partialPricing(ClpSimplex * model, double start, double end,
189                                int & bestSequence, int & numberWanted);
190    /** expands an updated column to allow for extra rows which the main
191        solver does not know about and returns number added.
192
193        This will normally be a no-op - it is in for GUB but may get extended to
194        general non-overlapping and embedded networks.
195
196        mode 0 - extend
197        mode 1 - delete etc
198    */
199    virtual int extendUpdated(ClpSimplex * model, CoinIndexedVector * update, int mode);
200    /**
201       utility primal function for dealing with dynamic constraints
202       mode=0  - Set up before "update" and "times" for primal solution using extended rows
203       mode=1  - Cleanup primal solution after "times" using extended rows.
204       mode=2  - Check (or report on) primal infeasibilities
205    */
206    virtual void primalExpanded(ClpSimplex * model, int mode);
207    /**
208        utility dual function for dealing with dynamic constraints
209        mode=0  - Set up before "updateTranspose" and "transposeTimes" for duals using extended
210                  updates array (and may use other if dual values pass)
211        mode=1  - Update dual solution after "transposeTimes" using extended rows.
212        mode=2  - Compute all djs and compute key dual infeasibilities
213        mode=3  - Report on key dual infeasibilities
214        mode=4  - Modify before updateTranspose in partial pricing
215    */
216    virtual void dualExpanded(ClpSimplex * model, CoinIndexedVector * array,
217                              double * other, int mode);
218    /**
219        general utility function for dealing with dynamic constraints
220        mode=0  - Create list of non-key basics in pivotVariable_ using
221                  number as numberBasic in and out
222        mode=1  - Set all key variables as basic
223        mode=2  - return number extra rows needed, number gives maximum number basic
224        mode=3  - before replaceColumn
225        mode=4  - return 1 if can do primal, 2 if dual, 3 if both
226        mode=5  - save any status stuff (when in good state)
227        mode=6  - restore status stuff
228        mode=7  - flag given variable (normally sequenceIn)
229        mode=8  - unflag all variables
230        mode=9  - synchronize costs and bounds
231        mode=10  - return 1 if there may be changing bounds on variable (column generation)
232        mode=11  - make sure set is clean (used when a variable rejected - but not flagged)
233        mode=12  - after factorize but before permute stuff
234        mode=13  - at end of simplex to delete stuff
235
236    */
237    virtual int generalExpanded(ClpSimplex * model, int mode, int & number);
238    /**
239       update information for a pivot (and effective rhs)
240    */
241    virtual int updatePivot(ClpSimplex * model, double oldInValue, double oldOutValue);
242    /** Creates a variable.  This is called after partial pricing and may modify matrix.
243        May update bestSequence.
244    */
245    virtual void createVariable(ClpSimplex * model, int & bestSequence);
246    /** Just for debug if odd type matrix.
247        Returns number of primal infeasibilities. */
248    virtual int checkFeasible(ClpSimplex * model, double & sum) const ;
249    /// Returns reduced cost of a variable
250    double reducedCost(ClpSimplex * model, int sequence) const;
251    /// Correct sequence in and out to give true value (if both -1 maybe do whole matrix)
252    virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ;
253    //@}
254
255    //---------------------------------------------------------------------------
256    /**@name Matrix times vector methods
257       They can be faster if scalar is +- 1
258       Also for simplex I am not using basic/non-basic split */
259    //@{
260    /** Return <code>y + A * x * scalar</code> in <code>y</code>.
261        @pre <code>x</code> must be of size <code>numColumns()</code>
262        @pre <code>y</code> must be of size <code>numRows()</code> */
263    virtual void times(double scalar,
264                       const double * x, double * y) const = 0;
265    /** And for scaling - default aborts for when scaling not supported
266        (unless pointers NULL when as normal)
267    */
268    virtual void times(double scalar,
269                       const double * x, double * y,
270                       const double * rowScale,
271                       const double * columnScale) const;
272    /** Return <code>y + x * scalar * A</code> in <code>y</code>.
273        @pre <code>x</code> must be of size <code>numRows()</code>
274        @pre <code>y</code> must be of size <code>numColumns()</code> */
275    virtual void transposeTimes(double scalar,
276                                const double * x, double * y) const = 0;
277    /** And for scaling - default aborts for when scaling not supported
278        (unless pointers NULL when as normal)
279    */
280    virtual void transposeTimes(double scalar,
281                                const double * x, double * y,
282                                const double * rowScale,
283                                const double * columnScale,
284                                double * spare = NULL) const;
285#if COIN_LONG_WORK
286    // For long double versions (aborts if not supported)
287    virtual void times(CoinWorkDouble scalar,
288                       const CoinWorkDouble * x, CoinWorkDouble * y) const ;
289    virtual void transposeTimes(CoinWorkDouble scalar,
290                                const CoinWorkDouble * x, CoinWorkDouble * y) const ;
291#endif
292    /** Return <code>x * scalar *A + y</code> in <code>z</code>.
293        Can use y as temporary array (will be empty at end)
294        Note - If x packed mode - then z packed mode
295        Squashes small elements and knows about ClpSimplex */
296    virtual void transposeTimes(const ClpSimplex * model, double scalar,
297                                const CoinIndexedVector * x,
298                                CoinIndexedVector * y,
299                                CoinIndexedVector * z) const = 0;
300    /** Return <code>x *A</code> in <code>z</code> but
301        just for indices in y.
302        This is only needed for primal steepest edge.
303        Note - z always packed mode */
304    virtual void subsetTransposeTimes(const ClpSimplex * model,
305                                      const CoinIndexedVector * x,
306                                      const CoinIndexedVector * y,
307                                      CoinIndexedVector * z) const = 0;
308    /** Returns true if can combine transposeTimes and subsetTransposeTimes
309        and if it would be faster */
310    virtual bool canCombine(const ClpSimplex * ,
311                            const CoinIndexedVector * ) const {
312        return false;
313    }
314    /// Updates two arrays for steepest and does devex weights (need not be coded)
315    virtual void transposeTimes2(const ClpSimplex * model,
316                                 const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
317                                 const CoinIndexedVector * pi2,
318                                 CoinIndexedVector * spare,
319                                 double referenceIn, double devex,
320                                 // Array for exact devex to say what is in reference framework
321                                 unsigned int * reference,
322                                 double * weights, double scaleFactor);
323    /// Updates second array for steepest and does devex weights (need not be coded)
324    virtual void subsetTimes2(const ClpSimplex * model,
325                              CoinIndexedVector * dj1,
326                              const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
327                              double referenceIn, double devex,
328                              // Array for exact devex to say what is in reference framework
329                              unsigned int * reference,
330                              double * weights, double scaleFactor);
331    /** Return <code>x *A</code> in <code>z</code> but
332        just for number indices in y.
333        Default cheats with fake CoinIndexedVector and
334        then calls subsetTransposeTimes */
335    virtual void listTransposeTimes(const ClpSimplex * model,
336                                    double * x,
337                                    int * y,
338                                    int number,
339                                    double * z) const;
340    //@}
341    //@{
342    ///@name Other
343    /// Clone
344    virtual ClpMatrixBase * clone() const = 0;
345    /** Subset clone (without gaps).  Duplicates are allowed
346        and order is as given.
347        Derived classes need not provide this as it may not always make
348        sense */
349    virtual ClpMatrixBase * subsetClone (
350        int numberRows, const int * whichRows,
351        int numberColumns, const int * whichColumns) const;
352    /// Gets rid of any mutable by products
353    virtual void backToBasics() {}
354    /** Returns type.
355        The types which code may need to know about are:
356        1  - ClpPackedMatrix
357        11 - ClpNetworkMatrix
358        12 - ClpPlusMinusOneMatrix
359    */
360    inline int type() const {
361        return type_;
362    }
363    /// Sets type
364    void setType(int newtype) {
365        type_ = newtype;
366    }
367    /// Sets up an effective RHS
368    void useEffectiveRhs(ClpSimplex * model);
369    /** Returns effective RHS offset if it is being used.  This is used for long problems
370        or big gub or anywhere where going through full columns is
371        expensive.  This may re-compute */
372    virtual double * rhsOffset(ClpSimplex * model, bool forceRefresh = false,
373                               bool check = false);
374    /// If rhsOffset used this is iteration last refreshed
375    inline int lastRefresh() const {
376        return lastRefresh_;
377    }
378    /// If rhsOffset used this is refresh frequency (0==off)
379    inline int refreshFrequency() const {
380        return refreshFrequency_;
381    }
382    inline void setRefreshFrequency(int value) {
383        refreshFrequency_ = value;
384    }
385    /// whether to skip dual checks most of time
386    inline bool skipDualCheck() const {
387        return skipDualCheck_;
388    }
389    inline void setSkipDualCheck(bool yes) {
390        skipDualCheck_ = yes;
391    }
392    /** Partial pricing tuning parameter - minimum number of "objects" to scan.
393        e.g. number of Gub sets but could be number of variables */
394    inline int minimumObjectsScan() const {
395        return minimumObjectsScan_;
396    }
397    inline void setMinimumObjectsScan(int value) {
398        minimumObjectsScan_ = value;
399    }
400    /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
401    inline int minimumGoodReducedCosts() const {
402        return minimumGoodReducedCosts_;
403    }
404    inline void setMinimumGoodReducedCosts(int value) {
405        minimumGoodReducedCosts_ = value;
406    }
407    /// Current start of search space in matrix (as fraction)
408    inline double startFraction() const {
409        return startFraction_;
410    }
411    inline void setStartFraction(double value) {
412        startFraction_ = value;
413    }
414    /// Current end of search space in matrix (as fraction)
415    inline double endFraction() const {
416        return endFraction_;
417    }
418    inline void setEndFraction(double value) {
419        endFraction_ = value;
420    }
421    /// Current best reduced cost
422    inline double savedBestDj() const {
423        return savedBestDj_;
424    }
425    inline void setSavedBestDj(double value) {
426        savedBestDj_ = value;
427    }
428    /// Initial number of negative reduced costs wanted
429    inline int originalWanted() const {
430        return originalWanted_;
431    }
432    inline void setOriginalWanted(int value) {
433        originalWanted_ = value;
434    }
435    /// Current number of negative reduced costs which we still need
436    inline int currentWanted() const {
437        return currentWanted_;
438    }
439    inline void setCurrentWanted(int value) {
440        currentWanted_ = value;
441    }
442    /// Current best sequence
443    inline int savedBestSequence() const {
444        return savedBestSequence_;
445    }
446    inline void setSavedBestSequence(int value) {
447        savedBestSequence_ = value;
448    }
449    //@}
450
451
452protected:
453
454    /**@name Constructors, destructor<br>
455       <strong>NOTE</strong>: All constructors are protected. There's no need
456       to expose them, after all, this is an abstract class. */
457    //@{
458    /** Default constructor. */
459    ClpMatrixBase();
460    /** Destructor (has to be public) */
461public:
462    virtual ~ClpMatrixBase();
463protected:
464    // Copy
465    ClpMatrixBase(const ClpMatrixBase&);
466    // Assignment
467    ClpMatrixBase& operator=(const ClpMatrixBase&);
468    //@}
469
470
471protected:
472    /**@name Data members
473       The data members are protected to allow access for derived classes. */
474    //@{
475    /** Effective RHS offset if it is being used.  This is used for long problems
476        or big gub or anywhere where going through full columns is
477        expensive */
478    double * rhsOffset_;
479    /// Current start of search space in matrix (as fraction)
480    double startFraction_;
481    /// Current end of search space in matrix (as fraction)
482    double endFraction_;
483    /// Best reduced cost so far
484    double savedBestDj_;
485    /// Initial number of negative reduced costs wanted
486    int originalWanted_;
487    /// Current number of negative reduced costs which we still need
488    int currentWanted_;
489    /// Saved best sequence in pricing
490    int savedBestSequence_;
491    /// type (may be useful)
492    int type_;
493    /// If rhsOffset used this is iteration last refreshed
494    int lastRefresh_;
495    /// If rhsOffset used this is refresh frequency (0==off)
496    int refreshFrequency_;
497    /// Partial pricing tuning parameter - minimum number of "objects" to scan
498    int minimumObjectsScan_;
499    /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
500    int minimumGoodReducedCosts_;
501    /// True sequence in (i.e. from larger problem)
502    int trueSequenceIn_;
503    /// True sequence out (i.e. from larger problem)
504    int trueSequenceOut_;
505    /// whether to skip dual checks most of time
506    bool skipDualCheck_;
507    //@}
508};
509// bias for free variables
510#define FREE_BIAS 1.0e1
511// Acceptance criteria for free variables
512#define FREE_ACCEPT 1.0e2
513
514#endif
Note: See TracBrowser for help on using the repository browser.