1/* $Id: ClpDynamicMatrix.hpp 1760 2011-07-02 13:15:55Z stefan $ */
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 /// Writes out model (without names)
98 void writeMps(const char * name);
99 /// Populates initial matrix from dynamic status
100 void initialProblem();
101 /** Adds in a column to gub structure (called from descendant) and returns sequence */
102 int addColumn(int numberEntries, const int * row, const double * element,
103 double cost, double lower, double upper, int iSet,
104 DynamicStatus status);
105 /** If addColumn forces compression then this allows descendant to know what to do.
106 If >=0 then entry stayed in, if -1 then entry went out to lower bound.of zero.
107 Entries at upper bound (really nonzero) never go out (at present).
108 */
109 virtual void packDown(const int * , int ) {}
110 /// Gets lower bound (to simplify coding)
111 inline double columnLower(int sequence) const {
112 if (columnLower_) return columnLower_[sequence];
113 else return 0.0;
114 }
115 /// Gets upper bound (to simplify coding)
116 inline double columnUpper(int sequence) const {
117 if (columnUpper_) return columnUpper_[sequence];
118 else return COIN_DBL_MAX;
119 }
120
121 //@}
122
123
124
125 /**@name Constructors, destructor */
126 //@{
127 /** Default constructor. */
128 ClpDynamicMatrix();
129 /** This is the real constructor.
130 It assumes factorization frequency will not be changed.
131 This resizes model !!!!
132 The contents of original matrix in model will be taken over and original matrix
133 will be sanitized so can be deleted (to avoid a very small memory leak)
134 */
135 ClpDynamicMatrix(ClpSimplex * model, int numberSets,
136 int numberColumns, const int * starts,
137 const double * lower, const double * upper,
138 const CoinBigIndex * startColumn, const int * row,
139 const double * element, const double * cost,
140 const double * columnLower = NULL, const double * columnUpper = NULL,
141 const unsigned char * status = NULL,
142 const unsigned char * dynamicStatus = NULL);
143
144 /** Destructor */
145 virtual ~ClpDynamicMatrix();
146 //@}
147
148 /**@name Copy method */
149 //@{
150 /** The copy constructor. */
151 ClpDynamicMatrix(const ClpDynamicMatrix&);
152 /** The copy constructor from an CoinPackedMatrix. */
153 ClpDynamicMatrix(const CoinPackedMatrix&);
154
155 ClpDynamicMatrix& operator=(const ClpDynamicMatrix&);
156 /// Clone
157 virtual ClpMatrixBase * clone() const ;
158 //@}
159 /**@name gets and sets */
160 //@{
161 /// Status of row slacks
162 inline ClpSimplex::Status getStatus(int sequence) const {
163 return static_cast<ClpSimplex::Status> (status_[sequence] & 7);
164 }
165 inline void setStatus(int sequence, ClpSimplex::Status status) {
166 unsigned char & st_byte = status_[sequence];
167 st_byte = static_cast<unsigned char>(st_byte & ~7);
168 st_byte = static_cast<unsigned char>(st_byte | status);
169 }
170 /// Whether flagged slack
171 inline bool flaggedSlack(int i) const {
172 return (status_[i] & 8) != 0;
173 }
174 inline void setFlaggedSlack(int i) {
175 status_[i] = static_cast<unsigned char>(status_[i] | 8);
176 }
177 inline void unsetFlaggedSlack(int i) {
178 status_[i] = static_cast<unsigned char>(status_[i] & ~8);
179 }
180 /// Number of sets (dynamic rows)
181 inline int numberSets() const {
182 return numberSets_;
183 }
184 /// Number of possible gub variables
185 inline int numberGubEntries() const
186 { return startSet_[numberSets_];}
187 /// Sets
188 inline int * startSets() const
189 { return startSet_;}
190 /// Whether flagged
191 inline bool flagged(int i) const {
192 return (dynamicStatus_[i] & 8) != 0;
193 }
194 inline void setFlagged(int i) {
195 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i] | 8);
196 }
197 inline void unsetFlagged(int i) {
198 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i] & ~8);
199 }
200 inline void setDynamicStatus(int sequence, DynamicStatus status) {
201 unsigned char & st_byte = dynamicStatus_[sequence];
202 st_byte = static_cast<unsigned char>(st_byte & ~7);
203 st_byte = static_cast<unsigned char>(st_byte | status);
204 }
205 inline DynamicStatus getDynamicStatus(int sequence) const {
206 return static_cast<DynamicStatus> (dynamicStatus_[sequence] & 7);
207 }
208 /// Saved value of objective offset
209 inline double objectiveOffset() const {
210 return objectiveOffset_;
211 }
212 /// Starts of each column
213 inline CoinBigIndex * startColumn() const {
214 return startColumn_;
215 }
216 /// rows
217 inline int * row() const {
218 return row_;
219 }
220 /// elements
221 inline double * element() const {
222 return element_;
223 }
224 /// costs
225 inline double * cost() const {
226 return cost_;
227 }
228 /// ids of active columns (just index here)
229 inline int * id() const {
230 return id_;
231 }
232 /// Optional lower bounds on columns
233 inline double * columnLower() const {
234 return columnLower_;
235 }
236 /// Optional upper bounds on columns
237 inline double * columnUpper() const {
238 return columnUpper_;
239 }
240 /// Lower bounds on sets
241 inline double * lowerSet() const {
242 return lowerSet_;
243 }
244 /// Upper bounds on sets
245 inline double * upperSet() const {
246 return upperSet_;
247 }
248 /// size
249 inline int numberGubColumns() const {
250 return numberGubColumns_;
251 }
252 /// first free
253 inline int firstAvailable() const {
254 return firstAvailable_;
255 }
256 /// first dynamic
257 inline int firstDynamic() const {
258 return firstDynamic_;
259 }
260 /// number of columns in dynamic model
261 inline int lastDynamic() const {
262 return lastDynamic_;
263 }
264 /// number of rows in original model
265 inline int numberStaticRows() const {
266 return numberStaticRows_;
267 }
268 /// size of working matrix (max)
269 inline int numberElements() const {
270 return numberElements_;
271 }
272 inline int * keyVariable() const {
273 return keyVariable_;
274 }
275 /// Switches off dj checking each factorization (for BIG models)
276 void switchOffCheck();
277 /// Status region for gub slacks
278 inline unsigned char * gubRowStatus() const {
279 return status_;
280 }
281 /// Status region for gub variables
282 inline unsigned char * dynamicStatus() const {
283 return dynamicStatus_;
284 }
285 /// Returns which set a variable is in
286 int whichSet (int sequence) const;
287 //@}
288
289
290protected:
291 /**@name Data members
292 The data members are protected to allow access for derived classes. */
293 //@{
294 /// Sum of dual infeasibilities
295 double sumDualInfeasibilities_;
296 /// Sum of primal infeasibilities
297 double sumPrimalInfeasibilities_;
298 /// Sum of Dual infeasibilities using tolerance based on error in duals
299 double sumOfRelaxedDualInfeasibilities_;
300 /// Sum of Primal infeasibilities using tolerance based on error in primals
301 double sumOfRelaxedPrimalInfeasibilities_;
302 /// Saved best dual on gub row in pricing
303 double savedBestGubDual_;
304 /// Saved best set in pricing
305 int savedBestSet_;
306 /// Backward pointer to pivot row !!!
307 int * backToPivotRow_;
308 /// Key variable of set (only accurate if none in small problem)
309 mutable int * keyVariable_;
310 /// Backward pointer to extra row
311 int * toIndex_;
312 // Reverse pointer from index to set
313 int * fromIndex_;
314 /// Number of sets (dynamic rows)
315 int numberSets_;
316 /// Number of active sets
317 int numberActiveSets_;
318 /// Saved value of objective offset
319 double objectiveOffset_;
320 /// Lower bounds on sets
321 double * lowerSet_;
322 /// Upper bounds on sets
323 double * upperSet_;
324 /// Status of slack on set
325 unsigned char * status_;
326 /// Pointer back to model
327 ClpSimplex * model_;
328 /// first free
329 int firstAvailable_;
330 /// first free when iteration started
331 int firstAvailableBefore_;
332 /// first dynamic
333 int firstDynamic_;
334 /// number of columns in dynamic model
335 int lastDynamic_;
336 /// number of rows in original model
337 int numberStaticRows_;
338 /// size of working matrix (max)
339 int numberElements_;
340 /// Number of dual infeasibilities
341 int numberDualInfeasibilities_;
342 /// Number of primal infeasibilities
343 int numberPrimalInfeasibilities_;
344 /** If pricing will declare victory (i.e. no check every factorization).
345 -1 - always check
346 0 - don't check
347 1 - in don't check mode but looks optimal
348 */
349 int noCheck_;
350 /// Infeasibility weight when last full pass done
351 double infeasibilityWeight_;
352 /// size
353 int numberGubColumns_;
354 /// current maximum number of columns (then compress)
355 int maximumGubColumns_;
356 /// current maximum number of elemnts (then compress)
357 int maximumElements_;
358 /// Start of each set
359 int * startSet_;
360 /// next in chain
361 int * next_;
362 /// Starts of each column
363 CoinBigIndex * startColumn_;
364 /// rows
365 int * row_;
366 /// elements
367 double * element_;
368 /// costs
369 double * cost_;
370 /// ids of active columns (just index here)
371 int * id_;
372 /// for status and which bound
373 unsigned char * dynamicStatus_;
374 /// Optional lower bounds on columns
375 double * columnLower_;
376 /// Optional upper bounds on columns
377 double * columnUpper_;
378 //@}
379};
380
381#endif
382