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