1/* $Id: CoinWarmStartBasis.hpp 1372 2011-01-03 23:31:00Z lou $ */
2/*! \legal
3 Copyright (C) 2000 -- 2003, International Business Machines Corporation
4 and others. All Rights Reserved.
5 This code is licensed under the terms of the Eclipse Public License (EPL).
6*/
7
8/*! \file CoinWarmStart.hpp
9 \brief Declaration of the generic simplex (basis-oriented) warm start
10 class. Also contains a basis diff class.
11*/
12
13#ifndef CoinWarmStartBasis_H
14#define CoinWarmStartBasis_H
15
16#include <vector>
17
18#include "CoinSort.hpp"
19#include "CoinHelperFunctions.hpp"
20#include "CoinWarmStart.hpp"
21
22//#############################################################################
23
24/*! \class CoinWarmStartBasis
25 \brief The default COIN simplex (basis-oriented) warm start class
26
27 CoinWarmStartBasis provides for a warm start object which contains the
28 status of each variable (structural and artificial).
29
30 \todo Modify this class so that the number of status entries per byte
31 and bytes per status vector allocation unit are not hardcoded.
32 At the least, collect this into a couple of macros.
33
34 \todo Consider separate fields for allocated capacity and actual basis
35 size. We could avoid some reallocation, at the price of retaining
36 more space than we need. Perhaps more important, we could do much
37 better sanity checks.
38*/
39
40class CoinWarmStartBasis : public virtual CoinWarmStart {
41public:
42
43 /*! \brief Enum for status of variables
44
45 Matches CoinPrePostsolveMatrix::Status, without superBasic. Most code that
46 converts between CoinPrePostsolveMatrix::Status and
47 CoinWarmStartBasis::Status will break if this correspondence is broken.
48
49 The status vectors are currently packed using two bits per status code,
50 four codes per byte. The location of the status information for
51 variable \c i is in byte <code>i>>2</code> and occupies bits 0:1
52 if <code>i\%4 == 0</code>, bits 2:3 if <code>i\%4 == 1</code>, etc.
53 The non-member functions getStatus(const char*,int) and
54 setStatus(char*,int,CoinWarmStartBasis::Status) are provided to hide
55 details of the packing.
56 */
57 enum Status {
58 isFree = 0x00, ///< Nonbasic free variable
59 basic = 0x01, ///< Basic variable
60 atUpperBound = 0x02, ///< Nonbasic at upper bound
61 atLowerBound = 0x03 ///< Nonbasic at lower bound
62 };
63
64 /** \brief Transfer vector entry for
65 mergeBasis(const CoinWarmStartBasis*,const XferVec*,const XferVec*)
66 */
67 typedef CoinTriple<int,int,int> XferEntry ;
68
69 /** \brief Transfer vector for
70 mergeBasis(const CoinWarmStartBasis*,const XferVec*,const XferVec*)
71 */
72 typedef std::vector<XferEntry> XferVec ;
73
74public:
75
76/*! \name Methods to get and set basis information.
77
78 The status of variables is kept in a pair of arrays, one for structural
79 variables, and one for artificials (aka logicals and slacks). The status
80 is coded using the values of the Status enum.
81
82 \sa CoinWarmStartBasis::Status for a description of the packing used in
83 the status arrays.
84*/
85//@{
86 /// Return the number of structural variables
87 inline int getNumStructural() const { return numStructural_; }
88
89 /// Return the number of artificial variables
90 inline int getNumArtificial() const { return numArtificial_; }
91
92 /** Return the number of basic structurals
93
94 A fast test for an all-slack basis.
95 */
96 int numberBasicStructurals() const ;
97
98 /// Return the status of the specified structural variable.
99 inline Status getStructStatus(int i) const {
100 const int st = (structuralStatus_[i>>2] >> ((i&3)<<1)) & 3;
101 return static_cast<CoinWarmStartBasis::Status>(st);
102 }
103
104 /// Set the status of the specified structural variable.
105 inline void setStructStatus(int i, Status st) {
106 char& st_byte = structuralStatus_[i>>2];
107 st_byte = static_cast<char>(st_byte & ~(3 << ((i&3)<<1))) ;
108 st_byte = static_cast<char>(st_byte | (st << ((i&3)<<1))) ;
109 }
110
111 /** Return the status array for the structural variables
112
113 The status information is stored using the codes defined in the
114 Status enum, 2 bits per variable, packed 4 variables per byte.
115 */
116 inline char * getStructuralStatus() { return structuralStatus_; }
117
118 /** \c const overload for
119 \link CoinWarmStartBasis::getStructuralStatus()
120 getStructuralStatus()
121 \endlink
122 */
123 inline const char * getStructuralStatus() const { return structuralStatus_; }
124
125 /** As for \link getStructuralStatus() getStructuralStatus \endlink,
126 but returns the status array for the artificial variables.
127 */
128 inline char * getArtificialStatus() { return artificialStatus_; }
129
130 /// Return the status of the specified artificial variable.
131 inline Status getArtifStatus(int i) const {
132 const int st = (artificialStatus_[i>>2] >> ((i&3)<<1)) & 3;
133 return static_cast<CoinWarmStartBasis::Status>(st);
134 }
135
136 /// Set the status of the specified artificial variable.
137 inline void setArtifStatus(int i, Status st) {
138 char& st_byte = artificialStatus_[i>>2];
139 st_byte = static_cast<char>(st_byte & ~(3 << ((i&3)<<1))) ;
140 st_byte = static_cast<char>(st_byte | (st << ((i&3)<<1))) ;
141 }
142
143 /** \c const overload for
144 \link CoinWarmStartBasis::getArtificialStatus()
145 getArtificialStatus()
146 \endlink
147 */
148 inline const char * getArtificialStatus() const { return artificialStatus_; }
149
150//@}
151
152/*! \name Basis `diff' methods */
153//@{
154
155 /*! \brief Generate a `diff' that can convert the warm start basis passed as
156 a parameter to the warm start basis specified by \c this.
157
158 The capabilities are limited: the basis passed as a parameter can be no
159 larger than the basis pointed to by \c this.
160 */
161
162 virtual CoinWarmStartDiff*
163 generateDiff (const CoinWarmStart *const oldCWS) const override ;
164
165 /*! \brief Apply \p diff to this basis
166
167 Update this basis by applying \p diff. It's assumed that the allocated
168 capacity of the basis is sufficiently large.
169 */
170
171 virtual void
172 applyDiff (const CoinWarmStartDiff *const cwsdDiff) override ;
173
174//@}
175
176
177/*! \name Methods to modify the warm start object */
178//@{
179
180 /*! \brief Set basis capacity; existing basis is discarded.
181
182 After execution of this routine, the warm start object does not describe
183 a valid basis: all structural and artificial variables have status isFree.
184 */
185 virtual void setSize(int ns, int na) ;
186
187 /*! \brief Set basis capacity; existing basis is maintained.
188
189 After execution of this routine, the warm start object describes a valid
190 basis: the status of new structural variables (added columns) is set to
191 nonbasic at lower bound, and the status of new artificial variables
192 (added rows) is set to basic. (The basis can be invalid if new structural
193 variables do not have a finite lower bound.)
194 */
195 virtual void resize (int newNumberRows, int newNumberColumns);
196
197 /** \brief Delete a set of rows from the basis
198
199 \warning
200 This routine assumes that the set of indices to be deleted is sorted in
201 ascending order and contains no duplicates. Use deleteRows() if this is
202 not the case.
203
204 \warning
205 The resulting basis is guaranteed valid only if all deleted
206 constraints are slack (hence the associated logicals are basic).
207
208 Removal of a tight constraint with a nonbasic logical implies that
209 some basic variable must be made nonbasic. This correction is left to
210 the client.
211 */
212
213 virtual void compressRows (int tgtCnt, const int *tgts) ;
214
215 /** \brief Delete a set of rows from the basis
216
217 \warning
218 The resulting basis is guaranteed valid only if all deleted
219 constraints are slack (hence the associated logicals are basic).
220
221 Removal of a tight constraint with a nonbasic logical implies that
222 some basic variable must be made nonbasic. This correction is left to
223 the client.
224 */
225
226 virtual void deleteRows(int rawTgtCnt, const int *rawTgts) ;
227
228 /** \brief Delete a set of columns from the basis
229
230 \warning
231 The resulting basis is guaranteed valid only if all deleted variables
232 are nonbasic.
233
234 Removal of a basic variable implies that some nonbasic variable must be
235 made basic. This correction is left to the client.
236 */
237
238 virtual void deleteColumns(int number, const int * which);
239
240 /** \brief Merge entries from a source basis into this basis.
241
242 \warning
243 It's the client's responsibility to ensure validity of the merged basis,
244 if that's important to the application.
245
246 The vector xferCols (xferRows) specifies runs of entries to be taken from
247 the source basis and placed in this basis. Each entry is a CoinTriple,
248 with first specifying the starting source index of a run, second
249 specifying the starting destination index, and third specifying the run
250 length.
251 */
252 virtual void mergeBasis(const CoinWarmStartBasis *src,
253 const XferVec *xferRows,
254 const XferVec *xferCols) ;
255
256//@}
257
258/*! \name Constructors, destructors, and related functions */
259
260//@{
261
262 /** Default constructor
263
264 Creates a warm start object representing an empty basis
265 (0 rows, 0 columns).
266 */
267 CoinWarmStartBasis();
268
269 /** Constructs a warm start object with the specified status vectors.
270
271 The parameters are copied.
272 Consider assignBasisStatus(int,int,char*&,char*&) if the object should
273 assume ownership.
274
275 \sa CoinWarmStartBasis::Status for a description of the packing used in
276 the status arrays.
277 */
278 CoinWarmStartBasis(int ns, int na, const char* sStat, const char* aStat) ;
279
280 /** Copy constructor */
281 CoinWarmStartBasis(const CoinWarmStartBasis& ws) ;
282
283 /** `Virtual constructor' */
284 virtual CoinWarmStart *clone() const override
285 {
286 return new CoinWarmStartBasis(*this);
287 }
288
289 /** Destructor */
290 virtual ~CoinWarmStartBasis();
291
292 /** Assignment */
293
294 virtual CoinWarmStartBasis& operator=(const CoinWarmStartBasis& rhs) ;
295
296 /** Assign the status vectors to be the warm start information.
297
298 In this method the CoinWarmStartBasis object assumes ownership of the
299 pointers and upon return the argument pointers will be NULL.
300 If copying is desirable, use the
301 \link CoinWarmStartBasis(int,int,const char*,const char*)
302 array constructor \endlink
303 or the
304 \link operator=(const CoinWarmStartBasis&)
305 assignment operator \endlink.
306
307 \note
308 The pointers passed to this method will be
309 freed using delete[], so they must be created using new[].
310 */
311 virtual void assignBasisStatus(int ns, int na, char*& sStat, char*& aStat) ;
312//@}
313
314/*! \name Miscellaneous methods */
315//@{
316
317 /// Prints in readable format (for debug)
318 virtual void print() const;
319 /// Returns true if full basis (for debug)
320 bool fullBasis() const;
321 /// Returns true if full basis and fixes up (for debug)
322 bool fixFullBasis();
323
324//@}
325
326protected:
327 /** \name Protected data members
328
329 \sa CoinWarmStartBasis::Status for a description of the packing used in
330 the status arrays.
331 */
332 //@{
333 /// The number of structural variables
334 int numStructural_;
335 /// The number of artificial variables
336 int numArtificial_;
337 /// The maximum sise (in ints - actually 4*char) (so resize does not need to do new)
338 int maxSize_;
339 /** The status of the structural variables. */
340 char * structuralStatus_;
341 /** The status of the artificial variables. */
342 char * artificialStatus_;
343 //@}
344};
345
346
347/*! \relates CoinWarmStartBasis
348 \brief Get the status of the specified variable in the given status array.
349*/
350
351inline CoinWarmStartBasis::Status getStatus(const char *array, int i) {
352 const int st = (array[i>>2] >> ((i&3)<<1)) & 3;
353 return static_cast<CoinWarmStartBasis::Status>(st);
354}
355
356/*! \relates CoinWarmStartBasis
357 \brief Set the status of the specified variable in the given status array.
358*/
359
360inline void setStatus(char * array, int i, CoinWarmStartBasis::Status st) {
361 char& st_byte = array[i>>2];
362 st_byte = static_cast<char>(st_byte & ~(3 << ((i&3)<<1))) ;
363 st_byte = static_cast<char>(st_byte | (st << ((i&3)<<1))) ;
364}
365
366
367
368/*! \class CoinWarmStartBasisDiff
369 \brief A `diff' between two CoinWarmStartBasis objects
370
371 This class exists in order to hide from the world the details of
372 calculating and representing a `diff' between two CoinWarmStartBasis
373 objects. For convenience, assignment, cloning, and deletion are visible to
374 the world, and default and copy constructors are made available to derived
375 classes. Knowledge of the rest of this structure, and of generating and
376 applying diffs, is restricted to the friend functions
377 CoinWarmStartBasis::generateDiff() and CoinWarmStartBasis::applyDiff().
378
379 The actual data structure is an unsigned int vector, #difference_ which
380 starts with indices of changed and then has values starting after #sze_
381
382 \todo This is a pretty generic structure, and vector diff is a pretty generic
383 activity. We should be able to convert this to a template.
384
385 \todo Using unsigned int as the data type for the diff vectors might help
386 to contain the damage when this code is inevitably compiled for 64 bit
387 architectures. But the notion of int as 4 bytes is hardwired into
388 CoinWarmStartBasis, so changes are definitely required.
389*/
390
391class CoinWarmStartBasisDiff : public virtual CoinWarmStartDiff
392{ public:
393
394 /*! \brief `Virtual constructor' */
395 virtual CoinWarmStartDiff *clone() const override
396 { CoinWarmStartBasisDiff *cwsbd = new CoinWarmStartBasisDiff(*this) ;
397 return (dynamic_cast<CoinWarmStartDiff *>(cwsbd)) ; }
398
399 /*! \brief Assignment */
400 virtual
401 CoinWarmStartBasisDiff &operator= (const CoinWarmStartBasisDiff &rhs) ;
402
403 /*! \brief Destructor */
404 virtual ~CoinWarmStartBasisDiff();
405
406 protected:
407
408 /*! \brief Default constructor
409
410 This is protected (rather than private) so that derived classes can
411 see it when they make <i>their</i> default constructor protected or
412 private.
413 */
414 CoinWarmStartBasisDiff () : sze_(0), difference_(nullptr) { }
415
416 /*! \brief Copy constructor
417
418 For convenience when copying objects containing CoinWarmStartBasisDiff
419 objects. But consider whether you should be using #clone() to retain
420 polymorphism.
421
422 This is protected (rather than private) so that derived classes can
423 see it when they make <i>their</i> copy constructor protected or
424 private.
425 */
426 CoinWarmStartBasisDiff (const CoinWarmStartBasisDiff &cwsbd) ;
427
428 /*! \brief Standard constructor */
429 CoinWarmStartBasisDiff (int sze, const unsigned int *const diffNdxs,
430 const unsigned int *const diffVals) ;
431
432 /*! \brief Constructor when full is smaller than diff!*/
433 CoinWarmStartBasisDiff (const CoinWarmStartBasis * rhs);
434
435 private:
436
437 friend CoinWarmStartDiff*
438 CoinWarmStartBasis::generateDiff(const CoinWarmStart *const oldCWS) const ;
439 friend void
440 CoinWarmStartBasis::applyDiff(const CoinWarmStartDiff *const diff) ;
441
442 /*! \brief Number of entries (and allocated capacity), in units of \c int. */
443 int sze_ ;
444
445 /*! \brief Array of diff indices and diff values */
446
447 unsigned int *difference_ ;
448
449} ;
450
451
452#endif
453