Scippy

SoPlex

Sequential object-oriented simPlex

lprowsetbase.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2015 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file lprowsetbase.h
17  * @brief Set of LP columns.
18  */
19 #ifndef _LPROWSETBASE_H_
20 #define _LPROWSETBASE_H_
21 
22 
23 #include <assert.h>
24 
25 #include "spxdefines.h"
26 #include "basevectors.h"
27 #include "datakey.h"
28 #include "lprowbase.h"
29 
30 namespace soplex
31 {
32 /**@brief Set of LP rows.
33  * @ingroup Algebra
34  *
35  * Class LPRowSetBase implements a set of \ref LPRowBase "LPRowBase%s". Unless for memory limitations, any number of
36  * LPRowBase%s may be #add%ed to an LPRowSetBase. Single or multiple LPRowBase%s may be added to an LPRowSetBase, where
37  * each method add() comes with two different signatures. One with and one without a parameter, used for returning the
38  * Keys assigned to the new LPRowBase%s by the set. See DataKey for a more detailed description of the concept of
39  * keys. For the concept of renumbering LPRowBase%s within an LPRowSetBase after removal of some LPRows see DataSet.
40  *
41  * @see DataSet, DataKey
42 */
43 template < class R >
44 class LPRowSetBase : protected SVSetBase<R>
45 {
46  template < class S > friend class LPRowSetBase;
47 
48 private:
49 
50  // ------------------------------------------------------------------------------------------------------------------
51  /**@name Data */
52  //@{
53 
54  DVectorBase<R> left; ///< vector of left hand sides (lower bounds) of LPRowBase%s.
55  DVectorBase<R> right; ///< vector of right hand sides (upper bounds) of LPRowBase%s.
56  DVectorBase<R> object; ///< vector of objective coefficients.
57 
58  //@}
59 
60 protected:
61 
62  // ------------------------------------------------------------------------------------------------------------------
63  /**@name Helpers */
64  //@{
65 
66  /// Returns the complete SVSet.
67  const SVSetBase<R>* rowSet() const
68  {
69  return this;
70  }
71 
72  //@}
73 
74 public:
75 
76  // ------------------------------------------------------------------------------------------------------------------
77  /**@name Access / modification */
78  //@{
79 
80  /// Returns the number of LPRowBase%s in LPRowSetBase.
81  int num() const
82  {
83  return SVSetBase<R>::num();
84  }
85 
86  /// Returns the maximum number of LPRowBase%s that fit.
87  int max() const
88  {
89  return SVSetBase<R>::max();
90  }
91 
92  /// Returns the vector of lhs values.
93  const VectorBase<R>& lhs() const
94  {
95  return left;
96  }
97 
98  /// Returns the vector of lhs values.
100  {
101  return left;
102  }
103 
104  /// Returns the lhs of the \p i 'th LPRowBase.
105  const R& lhs(int i) const
106  {
107  return left[i];
108  }
109 
110  /// Returns the lhs of the \p i 'th LPRowBase.
111  R& lhs_w(int i)
112  {
113  return left[i];
114  }
115 
116  /// Returns the lhs of the LPRowBase with DataKey \p k in LPRowSetBase.
117  const R& lhs(const DataKey& k) const
118  {
119  return left[number(k)];
120  }
121 
122  /// Returns the lhs of the LPRowBase with DataKey \p k in LPRowSetBase.
123  R& lhs_w(const DataKey& k)
124  {
125  return left[number(k)];
126  }
127 
128  /// Returns the vector of rhs values.
129  const VectorBase<R>& rhs() const
130  {
131  return right;
132  }
133 
134  /// Returns the vector of rhs values (writeable).
136  {
137  return right;
138  }
139 
140  /// Returns the rhs of the \p i 'th LPRowBase.
141  const R& rhs(int i) const
142  {
143  return right[i];
144  }
145 
146  /// Returns the rhs of the \p i 'th LPRowBase (writeable).
147  R& rhs_w(int i)
148  {
149  return right[i];
150  }
151 
152  /// Returns the rhs of the LPRowBase with DataKey \p k in LPRowSetBase.
153  const R& rhs(const DataKey& k) const
154  {
155  return right[number(k)];
156  }
157 
158  /// Returns the rhs of the LPRowBase with DataKey \p k in LPRowSetBase (writeable).
159  R& rhs_w(const DataKey& k)
160  {
161  return right[number(k)];
162  }
163 
164  /// Returns the vector of objective coefficients.
165  const VectorBase<R>& obj() const
166  {
167  return object;
168  }
169 
170  /// Returns the vector of objective coefficients (writeable).
172  {
173  return object;
174  }
175 
176  /// Returns the objective coefficient of the \p i 'th LPRowBase.
177  const R& obj(int i) const
178  {
179  return object[i];
180  }
181 
182  /// Returns the objective coefficient of the \p i 'th LPRowBase (writeable).
183  R& obj_w(int i)
184  {
185  return object[i];
186  }
187 
188  /// Returns the objective coefficient of the LPRowBase with DataKey \p k in LPRowSetBase.
189  const R& obj(const DataKey& k) const
190  {
191  return object[number(k)];
192  }
193 
194  /// Returns the objective coefficient of the LPRowBase with DataKey \p k in LPRowSetBase (writeable).
195  R& obj_w(const DataKey& k)
196  {
197  return object[number(k)];
198  }
199 
200  /// Returns a writable rowVector of the \p i 'th LPRowBase.
202  {
203  return SVSetBase<R>::operator[](i);
204  }
205 
206  /// Returns the rowVector of the \p i 'th LPRowBase.
207  const SVectorBase<R>& rowVector(int i) const
208  {
209  return SVSetBase<R>::operator[](i);
210  }
211 
212  /// Returns a writable rowVector of the LPRowBase with DataKey \p k.
214  {
215  return SVSetBase<R>::operator[](k);
216  }
217 
218  /// Returns the rowVector of the LPRowBase with DataKey \p k.
219  const SVectorBase<R>& rowVector(const DataKey& k) const
220  {
221  return SVSetBase<R>::operator[](k);
222  }
223 
224  /// Returns the inequalitiy type of the \p i 'th LPRowBase.
225  typename LPRowBase<R>::Type type(int i) const
226  {
227  if( rhs(i) >= double(infinity) )
229  if( lhs(i) <= double(-infinity) )
231  if( lhs(i) == rhs(i) )
232  return LPRowBase<R>::EQUAL;
233 
234  return LPRowBase<R>::RANGE;
235  }
236 
237  /// Returns the inequality type of the LPRowBase with DataKey \p k.
238  typename LPRowBase<R>::Type type(const DataKey& k) const
239  {
240  return type(number(k));
241  }
242 
243  /// Changes the inequality type of row \p i to \p type.
244  void setType(int i, typename LPRowBase<R>::Type t)
245  {
246  switch( t )
247  {
249  lhs_w(i) = -infinity;
250  break;
251  case LPRowBase<R>::EQUAL:
252  if( lhs_w(i) > -infinity )
253  rhs_w(i) = lhs(i);
254  else
255  lhs_w(i) = rhs(i);
256  break;
258  rhs_w(i) = infinity;
259  break;
260  case LPRowBase<R>::RANGE:
261  MSG_ERROR( std::cerr << "EROWST01 RANGE not supported in LPRowSet::setType()" << std::endl );
262  throw SPxInternalCodeException("XROWST01 This should never happen.");
263  default:
264  throw SPxInternalCodeException("XROWST02 This should never happen.");
265  }
266  }
267 
268  /// Returns the value of the \p i'th LPRowBase.
269  const R& value(int i) const
270  {
271  if( rhs(i) < infinity )
272  return rhs(i);
273  else
274  {
275  assert(lhs(i) > -infinity);
276  return lhs(i);
277  }
278  }
279 
280  /// Returns the value of the LPRowBase with DataKey \p k.
281  /** The \em value of a row depends on its type: if the inequality is of type "greater or equal", the value is the lhs
282  * of the row. Otherwise, the value is the rhs.
283  */
284  const R& value(const DataKey& k) const
285  {
286  return value(number(k));
287  }
288 
289  /// Returns the DataKey of the \p i 'th LPRowBase in LPRowSetBase.
290  DataKey key(int i) const
291  {
292  return SVSetBase<R>::key(i);
293  }
294 
295  /// Returns the number of the LPRowBase with DataKey \p k in LPRowSetBase.
296  int number(const DataKey& k) const
297  {
298  return SVSetBase<R>::number(k);
299  }
300 
301  /// does DataKey \p k belong to LPRowSetBase ?
302  bool has(const DataKey& k) const
303  {
304  return SVSetBase<R>::has(k);
305  }
306 
307  //@}
308 
309  // ------------------------------------------------------------------------------------------------------------------
310  /**@name Extension
311  *
312  * Extension methods come with two signatures, one of them providing a parameter to return the assigned
313  * DataKey(s). See DataSet for a more detailed description. All extension methods will automatically rearrange or
314  * allocate more memory if required.
315  */
316  //@{
317 
318  ///
319  void add(const LPRowBase<R>& row)
320  {
321  DataKey k;
322  add(k, row);
323  }
324 
325  /// Adds \p row to LPRowSetBase.
326  void add(DataKey& pkey, const LPRowBase<R>& prow)
327  {
328  add(pkey, prow.lhs(), prow.rowVector(), prow.rhs(), prow.obj());
329  }
330 
331  /// Adds LPRowBase consisting of left hand side \p lhs, row vector \p rowVector, and right hand side \p rhs to LPRowSetBase.
332  void add(const R& plhs, const SVectorBase<R>& prowVector, const R& prhs, const R& pobj = 0)
333  {
334  DataKey k;
335  add(k, plhs, prowVector, prhs, pobj);
336  }
337 
338  /// Adds LPRowBase consisting of left hand side \p lhs, row vector \p rowVector, and right hand side \p rhs to LPRowSetBase.
339  template < class S >
340  void add(const S* lhsValue, const S* rowValues, const int* rowIndices, int rowSize, const S* rhsValue, const S* objValue = 0)
341  {
342  assert(lhsValue != 0);
343  assert(rowSize <= 0 || rowValues != 0);
344  assert(rowSize <= 0 || rowIndices != 0);
345  assert(rhsValue != 0);
346 
347  DataKey k;
348  add(k, lhsValue, rowValues, rowIndices, rowSize, rhsValue, objValue);
349  }
350 
351  /// Adds LPRowBase consisting of left hand side \p lhs, row vector \p rowVector, and right hand side \p rhs to
352  /// LPRowSetBase, with DataKey \p key.
353  template < class S >
354  void add(DataKey& newkey, const S* lhsValue, const S* rowValues, const int* rowIndices, int rowSize, const S* rhsValue, const S* objValue = 0)
355  {
356  assert(lhsValue != 0);
357  assert(rowSize <= 0 || rowValues != 0);
358  assert(rowSize <= 0 || rowIndices != 0);
359  assert(rhsValue != 0);
360 
361  SVSetBase<R>::add(newkey, rowValues, rowIndices, rowSize);
362 
363  if( num() > left.dim() )
364  {
365  left.reDim(num());
366  right.reDim(num());
367  object.reDim(num());
368  }
369 
370  left[num() - 1] = *lhsValue;
371  right[num() - 1] = *rhsValue;
372  if( objValue != 0 )
373  object[num() - 1] = *objValue;
374  else
375  object[num() - 1] = 0;
376  }
377 
378  /// Adds LPRowBase consisting of left hand side \p lhs, row vector \p rowVector, and right hand side \p rhs to
379  /// LPRowSetBase, with DataKey \p key.
380  void add(DataKey& newkey, const R& newlhs, const SVectorBase<R>& newrowVector, const R& newrhs, const R& newobj = 0)
381  {
382  SVSetBase<R>::add(newkey, newrowVector);
383 
384  if( num() > left.dim() )
385  {
386  left.reDim(num());
387  right.reDim(num());
388  object.reDim(num());
389  }
390 
391  left[num() - 1] = newlhs;
392  right[num() - 1] = newrhs;
393  object[num() - 1] = newobj;
394  }
395 
396  ///
397  void add(const LPRowSetBase<R>& newset)
398  {
399  int i = num();
400 
401  SVSetBase<R>::add(newset);
402 
403  if( num() > left.dim() )
404  {
405  left.reDim(num());
406  right.reDim(num());
407  object.reDim(num());
408  }
409 
410  for( int j = 0; i < num(); ++i, ++j )
411  {
412  left[i] = newset.lhs(j);
413  right[i] = newset.rhs(j);
414  object[i] = newset.obj(j);
415  }
416  }
417 
418  /// Adds all LPRowBase%s of \p set to LPRowSetBase.
419  void add(DataKey keys[], const LPRowSetBase<R>& set)
420  {
421  int i = num();
422 
423  add(set);
424 
425  for( int j = 0; i < num(); ++i, ++j )
426  keys[j] = key(i);
427  }
428 
429  /// Extends row \p n to fit \p newmax nonzeros.
430  void xtend(int n, int newmax)
431  {
432  SVSetBase<R>::xtend(rowVector_w(n), newmax);
433  }
434 
435  /// Extends row with DataKey \p key to fit \p newmax nonzeros.
436  void xtend(const DataKey& pkey, int pnewmax)
437  {
438  SVSetBase<R>::xtend(rowVector_w(pkey), pnewmax);
439  }
440 
441  /// Adds \p n nonzero (\p idx, \p val)-pairs to rowVector with DataKey \p k.
442  void add2(const DataKey& k, int n, const int idx[], const R val[])
443  {
444  SVSetBase<R>::add2(rowVector_w(k), n, idx, val);
445  }
446 
447  /// Adds \p n nonzero (\p idx, \p val)-pairs to \p i 'th rowVector.
448  void add2(int i, int n, const int idx[], const R val[])
449  {
450  SVSetBase<R>::add2(rowVector_w(i), n, idx, val);
451  }
452 
453  /// Adds \p n nonzero (\p idx, \p val)-pairs to \p i 'th rowVector.
454  template < class S >
455  void add2(int i, int n, const int idx[], const S val[])
456  {
457  SVSetBase<R>::add2(rowVector_w(i), n, idx, val);
458  }
459 
460  /// Creates new LPRowBase with specified parameters and returns a reference to its row vector.
461  SVectorBase<R>& create(int pnonzeros = 0, const R& plhs = 0, const R& prhs = 1, const R& pobj = 0)
462  {
463  DataKey k;
464  return create(k, pnonzeros, plhs, prhs, pobj);
465  }
466 
467  /// Creates new LPRowBase with specified parameters and returns a reference to its row vector.
468  SVectorBase<R>& create(DataKey& newkey, int nonzeros = 0, const R& newlhs = 0, const R& newrhs = 1, const R& newobj = 0)
469  {
470  if( num() + 1 > left.dim() )
471  {
472  left.reDim(num() + 1);
473  right.reDim(num() + 1);
474  object.reDim(num() + 1);
475  }
476 
477  left[num()] = newlhs;
478  right[num()] = newrhs;
479  object[num()] = newobj;
480 
481  return *SVSetBase<R>::create(newkey, nonzeros);
482  }
483 
484  //@}
485 
486  // ------------------------------------------------------------------------------------------------------------------
487  /**@name Shrinking
488  *
489  * See DataSet for a description of the renumbering of the remaining LPRowBase%s in a LPRowSetBase after the call of
490  * a removal method.
491  */
492  //@{
493 
494  /// Removes \p i 'th LPRowBase.
495  void remove(int i)
496  {
498  left[i] = left[num()];
499  right[i] = right[num()];
500  object[i] = object[num()];
501  left.reDim(num());
502  right.reDim(num());
503  object.reDim(num());
504  }
505 
506  /// Removes LPRowBase with DataKey \p k.
507  void remove(const DataKey& k)
508  {
509  remove(number(k));
510  }
511 
512  /// Removes multiple LPRowBase%s.
513  void remove(int perm[])
514  {
515  int j = num();
516 
517  SVSetBase<R>::remove(perm);
518 
519  for( int i = 0; i < j; ++i )
520  {
521  if( perm[i] >= 0 && perm[i] != i )
522  {
523  left[perm[i]] = left[i];
524  right[perm[i]] = right[i];
525  object[perm[i]] = object[i];
526  }
527  }
528 
529  left.reDim (num());
530  right.reDim(num());
531  object.reDim(num());
532  }
533 
534  /// Removes \p n LPRowBase%s with row numbers given by \p nums.
535  void remove(const int nums[], int n)
536  {
537  DataArray<int> perm(num());
538  remove(nums, n, perm.get_ptr());
539  }
540 
541  /// Removes \p n LPRowBase%s with row numbers given by \p nums,
542  /// Stores permutation of row indices in \p perm.
543  void remove(const int nums[], int n, int* perm)
544  {
545  SVSetBase<R>::remove(nums, n, perm);
546 
547  int j = num();
548 
549  for( int i = 0; i < j; ++i )
550  {
551  if( perm[i] >= 0 && perm[i] != i )
552  {
553  left[perm[i]] = left[i];
554  right[perm[i]] = right[i];
555  object[perm[i]] = object[i];
556  }
557  }
558 
559  left.reDim (num());
560  right.reDim(num());
561  object.reDim(num());
562  }
563 
564  /// Removes all LPRowBase%s.
565  void clear()
566  {
568  left.reDim(num());
569  right.reDim(num());
570  object.reDim(num());
571  }
572 
573  //@}
574 
575  // ------------------------------------------------------------------------------------------------------------------
576  /**@name Memory Management
577  *
578  * For a description of the memory management methods, see the documentation of SVSet, which has been used for
579  * implementating LPRowSetBase.
580  */
581  //@{
582 
583  /// Reallocates memory to be able to store \p newmax LPRowBase%s.
584  void reMax(int newmax = 0)
585  {
586  SVSetBase<R>::reMax(newmax);
587  left.reSize (max());
588  right.reSize(max());
589  object.reSize(max());
590  }
591 
592  /// Returns number of used nonzero entries.
593  int memSize() const
594  {
595  return SVSetBase<R>::memSize();
596  }
597 
598  /// Returns length of nonzero memory.
599  int memMax() const
600  {
601  return SVSetBase<R>::memMax();
602  }
603 
604  /// Reallocates memory to be able to store \p newmax nonzeros.
605  void memRemax(int newmax)
606  {
607  SVSetBase<R>::memRemax(newmax);
608  }
609 
610  /// Garbage collection in nonzero memory.
611  void memPack()
612  {
614  }
615 
616  //@}
617 
618  // ------------------------------------------------------------------------------------------------------------------
619  /**@name Consistency check */
620 
621  /// Checks consistency.
622  bool isConsistent() const
623  {
624 #ifdef ENABLE_CONSISTENCY_CHECKS
625  const int ldim = left.dim();
626 
627  if( ldim != right.dim() )
628  return MSGinconsistent("LPRowSetBase");
629  if( ldim != object.dim() )
630  return MSGinconsistent("LPRowSetBase");
631  if( ldim != num() )
632  return MSGinconsistent("LPRowSetBase");
633 
634  return left.isConsistent() && right.isConsistent() && object.isConsistent() && SVSetBase<R>::isConsistent();
635 #else
636  return true;
637 #endif
638  }
639 
640  //@}
641 
642  // ------------------------------------------------------------------------------------------------------------------
643  /**@name Construction / Destruction */
644  //@{
645 
646  /// Default constructor.
647  /** The user can specify the initial maximum number of rows \p max and the initial maximum number of nonzero entries
648  * \p memmax. If these parameters are omitted, a default size is used. However, one can add an arbitrary number of
649  * rows to the LPRowSetBase, which may result in automated memory realllocation.
650  */
651  explicit
652  LPRowSetBase<R>(int pmax = -1, int pmemmax = -1)
653  : SVSetBase<R>(pmax, pmemmax), left(0), right(0), object(0)
654  {
655  assert(isConsistent());
656  }
657 
658  /// Assignment operator.
660  {
661  if( this != &rs )
662  {
664  left = rs.left;
665  right = rs.right;
666  object = rs.object;
667 
668  assert(isConsistent());
669  }
670 
671  return *this;
672  }
673 
674  /// Assignment operator.
675  template < class S >
677  {
678  if( this != (const LPRowSetBase<R>*)(&rs) )
679  {
681  left = rs.left;
682  right = rs.right;
683  object = rs.object;
684 
685  assert(isConsistent());
686  }
687 
688  return *this;
689  }
690 
691  /// Copy constructor.
693  : SVSetBase<R>(rs)
694  , left(rs.left)
695  , right(rs.right)
696  , object(rs.object)
697  {
698  assert(isConsistent());
699  }
700 
701  /// Copy constructor.
702  template < class S >
704  : SVSetBase<R>(rs)
705  , left(rs.left)
706  , right(rs.right)
707  , object(rs.object)
708  {
709  assert(isConsistent());
710  }
711 
712  /// Destructor.
713  virtual ~LPRowSetBase<R>()
714  {}
715 
716  //@}
717 };
718 } // namespace soplex
719 #endif // _LPROWSETBASE_H_