source: trunk/Clp/src/ClpDynamicMatrix.hpp @ 1665

Last change on this file since 1665 was 1665, checked in by lou, 9 years ago

Add EPL license notice in src.

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