1/* $Id: ClpGubMatrix.hpp 1665 2011-01-04 17:55:54Z lou $ */
2// Copyright (C) 2003, 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 ClpGubMatrix_H
7#define ClpGubMatrix_H
8
9
10#include "CoinPragma.hpp"
11
12#include "ClpPackedMatrix.hpp"
13class ClpSimplex;
14/** This implements Gub rows plus a ClpPackedMatrix.
15
16 There will be a version using ClpPlusMinusOne matrix but
17 there is no point doing one with ClpNetworkMatrix (although
18 an embedded network is attractive).
19
20*/
21
22class ClpGubMatrix : public ClpPackedMatrix {
23
24public:
25 /**@name Main functions provided */
26 //@{
27 /** Returns a new matrix in reverse order without gaps (GUB wants NULL) */
28 virtual ClpMatrixBase * reverseOrderedCopy() const;
29 /// Returns number of elements in column part of basis
30 virtual CoinBigIndex countBasis(const int * whichColumn,
31 int & numberColumnBasic);
32 /// Fills in column part of basis
33 virtual void fillBasis(ClpSimplex * model,
34 const int * whichColumn,
35 int & numberColumnBasic,
36 int * row, int * start,
37 int * rowCount, int * columnCount,
38 CoinFactorizationDouble * element);
39 /** Unpacks a column into an CoinIndexedvector
40 */
41 virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray,
42 int column) const ;
43 /** Unpacks a column into an CoinIndexedvector
44 ** in packed foramt
45 Note that model is NOT const. Bounds and objective could
46 be modified if doing column generation (just for this variable) */
47 virtual void unpackPacked(ClpSimplex * model,
48 CoinIndexedVector * rowArray,
49 int column) const;
50 /** Adds multiple of a column into an CoinIndexedvector
51 You can use quickAdd to add to vector */
52 virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray,
53 int column, double multiplier) const ;
54 /** Adds multiple of a column into an array */
55 virtual void add(const ClpSimplex * model, double * array,
56 int column, double multiplier) const;
57 /// Partial pricing
58 virtual void partialPricing(ClpSimplex * model, double start, double end,
59 int & bestSequence, int & numberWanted);
60 /// Returns number of hidden rows e.g. gub
61 virtual int hiddenRows() const;
62 //@}
63
64 /**@name Matrix times vector methods */
65 //@{
66
67 using ClpPackedMatrix::transposeTimes ;
68 /** Return <code>x * scalar * A + y</code> in <code>z</code>.
69 Can use y as temporary array (will be empty at end)
70 Note - If x packed mode - then z packed mode
71 Squashes small elements and knows about ClpSimplex */
72 virtual void transposeTimes(const ClpSimplex * model, double scalar,
73 const CoinIndexedVector * x,
74 CoinIndexedVector * y,
75 CoinIndexedVector * z) const;
76 /** Return <code>x * scalar * A + y</code> in <code>z</code>.
77 Can use y as temporary array (will be empty at end)
78 Note - If x packed mode - then z packed mode
79 Squashes small elements and knows about ClpSimplex.
80 This version uses row copy*/
81 virtual void transposeTimesByRow(const ClpSimplex * model, double scalar,
82 const CoinIndexedVector * x,
83 CoinIndexedVector * y,
84 CoinIndexedVector * z) const;
85 /** Return <code>x *A</code> in <code>z</code> but
86 just for indices in y.
87 Note - z always packed mode */
88 virtual void subsetTransposeTimes(const ClpSimplex * model,
89 const CoinIndexedVector * x,
90 const CoinIndexedVector * y,
91 CoinIndexedVector * z) const;
92 /** expands an updated column to allow for extra rows which the main
93 solver does not know about and returns number added if mode 0.
94 If mode 1 deletes extra entries
95
96 This active in Gub
97 */
98 virtual int extendUpdated(ClpSimplex * model, CoinIndexedVector * update, int mode);
99 /**
100 mode=0 - Set up before "update" and "times" for primal solution using extended rows
101 mode=1 - Cleanup primal solution after "times" using extended rows.
102 mode=2 - Check (or report on) primal infeasibilities
103 */
104 virtual void primalExpanded(ClpSimplex * model, int mode);
105 /**
106 mode=0 - Set up before "updateTranspose" and "transposeTimes" for duals using extended
107 updates array (and may use other if dual values pass)
108 mode=1 - Update dual solution after "transposeTimes" using extended rows.
109 mode=2 - Compute all djs and compute key dual infeasibilities
110 mode=3 - Report on key dual infeasibilities
111 mode=4 - Modify before updateTranspose in partial pricing
112 */
113 virtual void dualExpanded(ClpSimplex * model, CoinIndexedVector * array,
114 double * other, int mode);
115 /**
116 mode=0 - Create list of non-key basics in pivotVariable_ using
117 number as numberBasic in and out
118 mode=1 - Set all key variables as basic
119 mode=2 - return number extra rows needed, number gives maximum number basic
120 mode=3 - before replaceColumn
121 mode=4 - return 1 if can do primal, 2 if dual, 3 if both
122 mode=5 - save any status stuff (when in good state)
123 mode=6 - restore status stuff
124 mode=7 - flag given variable (normally sequenceIn)
125 mode=8 - unflag all variables
126 mode=9 - synchronize costs
127 mode=10 - return 1 if there may be changing bounds on variable (column generation)
128 mode=11 - make sure set is clean (used when a variable rejected - but not flagged)
129 mode=12 - after factorize but before permute stuff
130 mode=13 - at end of simplex to delete stuff
131 */
132 virtual int generalExpanded(ClpSimplex * model, int mode, int & number);
133 /**
134 update information for a pivot (and effective rhs)
135 */
136 virtual int updatePivot(ClpSimplex * model, double oldInValue, double oldOutValue);
137 /// Sets up an effective RHS and does gub crash if needed
138 virtual void useEffectiveRhs(ClpSimplex * model, bool cheapest = true);
139 /** Returns effective RHS offset if it is being used. This is used for long problems
140 or big gub or anywhere where going through full columns is
141 expensive. This may re-compute */
142 virtual double * rhsOffset(ClpSimplex * model, bool forceRefresh = false,
143 bool check = false);
144 /** This is local to Gub to allow synchronization:
145 mode=0 when status of basis is good
146 mode=1 when variable is flagged
147 mode=2 when all variables unflagged (returns number flagged)
148 mode=3 just reset costs (primal)
149 mode=4 correct number of dual infeasibilities
150 mode=5 return 4 if time to re-factorize
151 mode=6 - return 1 if there may be changing bounds on variable (column generation)
152 mode=7 - do extra restores for column generation
153 mode=8 - make sure set is clean
154 mode=9 - adjust lower, upper on set by incoming
155 */
156 virtual int synchronize(ClpSimplex * model, int mode);
157 /// Correct sequence in and out to give true value
158 virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ;
159 //@}
160
161
162
163 /**@name Constructors, destructor */
164 //@{
165 /** Default constructor. */
166 ClpGubMatrix();
167 /** Destructor */
168 virtual ~ClpGubMatrix();
169 //@}
170
171 /**@name Copy method */
172 //@{
173 /** The copy constructor. */
174 ClpGubMatrix(const ClpGubMatrix&);
175 /** The copy constructor from an CoinPackedMatrix. */
176 ClpGubMatrix(const CoinPackedMatrix&);
177 /** Subset constructor (without gaps). Duplicates are allowed
178 and order is as given */
179 ClpGubMatrix (const ClpGubMatrix & wholeModel,
180 int numberRows, const int * whichRows,
181 int numberColumns, const int * whichColumns);
182 ClpGubMatrix (const CoinPackedMatrix & wholeModel,
183 int numberRows, const int * whichRows,
184 int numberColumns, const int * whichColumns);
185
186 /** This takes over ownership (for space reasons) */
187 ClpGubMatrix(CoinPackedMatrix * matrix);
188
189 /** This takes over ownership (for space reasons) and is the
190 real constructor*/
191 ClpGubMatrix(ClpPackedMatrix * matrix, int numberSets,
192 const int * start, const int * end,
193 const double * lower, const double * upper,
194 const unsigned char * status = NULL);
195
196 ClpGubMatrix& operator=(const ClpGubMatrix&);
197 /// Clone
198 virtual ClpMatrixBase * clone() const ;
199 /** Subset clone (without gaps). Duplicates are allowed
200 and order is as given */
201 virtual ClpMatrixBase * subsetClone (
202 int numberRows, const int * whichRows,
203 int numberColumns, const int * whichColumns) const ;
204 /** redoes next_ for a set. */
205 void redoSet(ClpSimplex * model, int newKey, int oldKey, int iSet);
206 //@}
207 /**@name gets and sets */
208 //@{
209 /// Status
210 inline ClpSimplex::Status getStatus(int sequence) const {
211 return static_cast<ClpSimplex::Status> (status_[sequence] & 7);
212 }
213 inline void setStatus(int sequence, ClpSimplex::Status status) {
214 unsigned char & st_byte = status_[sequence];
215 st_byte = static_cast<unsigned char>(st_byte & ~7);
216 st_byte = static_cast<unsigned char>(st_byte | status);
217 }
218 /// To flag a variable
219 inline void setFlagged( int sequence) {
220 status_[sequence] = static_cast<unsigned char>(status_[sequence] | 64);
221 }
222 inline void clearFlagged( int sequence) {
223 status_[sequence] = static_cast<unsigned char>(status_[sequence] & ~64);
224 }
225 inline bool flagged(int sequence) const {
226 return ((status_[sequence] & 64) != 0);
227 }
228 /// To say key is above ub
229 inline void setAbove( int sequence) {
230 unsigned char iStat = status_[sequence];
231 iStat = static_cast<unsigned char>(iStat & ~24);
232 status_[sequence] = static_cast<unsigned char>(iStat | 16);
233 }
234 /// To say key is feasible
235 inline void setFeasible( int sequence) {
236 unsigned char iStat = status_[sequence];
237 iStat = static_cast<unsigned char>(iStat & ~24);
238 status_[sequence] = static_cast<unsigned char>(iStat | 8);
239 }
240 /// To say key is below lb
241 inline void setBelow( int sequence) {
242 unsigned char iStat = status_[sequence];
243 iStat = static_cast<unsigned char>(iStat & ~24);
244 status_[sequence] = iStat;
245 }
246 inline double weight( int sequence) const {
247 int iStat = status_[sequence] & 31;
248 iStat = iStat >> 3;
249 return static_cast<double> (iStat - 1);
250 }
251 /// Starts
252 inline int * start() const {
253 return start_;
254 }
255 /// End
256 inline int * end() const {
257 return end_;
258 }
259 /// Lower bounds on sets
260 inline double * lower() const {
261 return lower_;
262 }
263 /// Upper bounds on sets
264 inline double * upper() const {
265 return upper_;
266 }
267 /// Key variable of set
268 inline int * keyVariable() const {
269 return keyVariable_;
270 }
271 /// Backward pointer to set number
272 inline int * backward() const {
273 return backward_;
274 }
275 /// Number of sets (gub rows)
276 inline int numberSets() const {
277 return numberSets_;
278 }
279 /// Switches off dj checking each factorization (for BIG models)
280 void switchOffCheck();
281 //@}
282
283
284protected:
285 /**@name Data members
286 The data members are protected to allow access for derived classes. */
287 //@{
288 /// Sum of dual infeasibilities
289 double sumDualInfeasibilities_;
290 /// Sum of primal infeasibilities
291 double sumPrimalInfeasibilities_;
292 /// Sum of Dual infeasibilities using tolerance based on error in duals
293 double sumOfRelaxedDualInfeasibilities_;
294 /// Sum of Primal infeasibilities using tolerance based on error in primals
295 double sumOfRelaxedPrimalInfeasibilities_;
296 /// Infeasibility weight when last full pass done
297 double infeasibilityWeight_;
298 /// Starts
299 int * start_;
300 /// End
301 int * end_;
302 /// Lower bounds on sets
303 double * lower_;
304 /// Upper bounds on sets
305 double * upper_;
306 /// Status of slacks
307 mutable unsigned char * status_;
308 /// Saved status of slacks
309 unsigned char * saveStatus_;
310 /// Saved key variables
311 int * savedKeyVariable_;
312 /// Backward pointer to set number
313 int * backward_;
314 /// Backward pointer to pivot row !!!
315 int * backToPivotRow_;
316 /// Change in costs for keys
317 double * changeCost_;
318 /// Key variable of set
319 mutable int * keyVariable_;
320 /** Next basic variable in set - starts at key and end with -(set+1).
321 Now changes to -(nonbasic+1).
322 next_ has extra space for 2* longest set */
323 mutable int * next_;
324 /// Backward pointer to index in CoinIndexedVector
325 int * toIndex_;
326 // Reverse pointer from index to set
327 int * fromIndex_;
328 /// Pointer back to model
329 ClpSimplex * model_;
330 /// Number of dual infeasibilities
331 int numberDualInfeasibilities_;
332 /// Number of primal infeasibilities
333 int numberPrimalInfeasibilities_;
334 /** If pricing will declare victory (i.e. no check every factorization).
335 -1 - always check
336 0 - don't check
337 1 - in don't check mode but looks optimal
338 */
339 int noCheck_;
340 /// Number of sets (gub rows)
341 int numberSets_;
342 /// Number in vector without gub extension
343 int saveNumber_;
344 /// Pivot row of possible next key
345 int possiblePivotKey_;
346 /// Gub slack in (set number or -1)
347 int gubSlackIn_;
348 /// First gub variables (same as start_[0] at present)
349 int firstGub_;
350 /// last gub variable (same as end_[numberSets_-1] at present)
351 int lastGub_;
352 /** type of gub - 0 not contiguous, 1 contiguous
353 add 8 bit to say no ubs on individual variables */
354 int gubType_;
355 //@}
356};
357
358#endif
359