source: trunk/Clp/src/ClpMatrixBase.hpp @ 2470

Last change on this file since 2470 was 2385, checked in by unxusr, 9 months ago

formatting

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