1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the class library                   */
4    	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SoPlex; see the file LICENSE. If not email to soplex@zib.de.  */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file  lpcolsetbase.h
26   	 * @brief Set of LP columns.
27   	 */
28   	#ifndef _LPCOLSETBASE_H_
29   	#define _LPCOLSETBASE_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/spxdefines.h"
34   	#include "soplex/basevectors.h"
35   	#include "soplex/datakey.h"
36   	#include "soplex/lpcolbase.h"
37   	
38   	namespace soplex
39   	{
40   	/**@brief   Set of LP columns.
41   	 * @ingroup Algebra
42   	 *
43   	 *  Class LPColSetBase implements a set of \ref LPColBase "LPColBase%s". Unless for memory limitations, any number of LPColBase%s may be
44   	 *  #add%ed to an LPColSetBase. Single or multiple LPColBase%s may be #add%ed to an LPColSetBase, where each method add() comes with
45   	 *  two different signatures. One with and one without a parameter, used for returning the \ref DataKey "DataKeys"
46   	 *  assigned to the new LPColBase%s by the set. See DataKey for a more detailed description of the concept of keys. For the
47   	 *  concept of renumbering LPColBase%s within an LPColSetBase after removal of some LPColBase%s, see DataSet.
48   	 *
49   	 * @see        DataSet, DataKey
50   	 */
51   	template < class R >
52   	class LPColSetBase : protected SVSetBase<R>
53   	{
54   	   template < class S > friend class LPColSetBase;
55   	
56   	private:
57   	
58   	   // ------------------------------------------------------------------------------------------------------------------
59   	   /**@name Data */
60   	   ///@{
61   	
62   	   VectorBase<R> low;     ///< vector of lower bounds.
63   	   VectorBase<R> up;      ///< vector of upper bounds.
64   	   VectorBase<R> object;  ///< vector of objective coefficients.
65   	
66   	   ///@}
67   	
68   	protected:
69   	
70   	   DataArray < int > scaleExp;   ///< column scaling factors (stored as bitshift)
71   	
72   	   // ------------------------------------------------------------------------------------------------------------------
73   	   /**@name Protected helpers */
74   	   ///@{
75   	
76   	   /// Returns the complete SVSetBase.
77   	   const SVSetBase<R>* colSet() const
78   	   {
79   	      return this;
80   	   }
81   	
82   	   ///@}
83   	
84   	public:
85   	
86   	   // ------------------------------------------------------------------------------------------------------------------
87   	   /**@name Inquiry */
88   	   ///@{
89   	
90   	   /// Returns the number of LPColBase%s currently in LPColSetBase.
91   	   int num() const
92   	   {
93   	      return SVSetBase<R>::num();
94   	   }
95   	
96   	   /// Returns maximum number of LPColBase%s currently fitting into LPColSetBase.
97   	   int max() const
98   	   {
99   	      return SVSetBase<R>::max();
100  	   }
101  	
102  	   ///
103  	   const VectorBase<R>& maxObj() const
104  	   {
105  	      return object;
106  	   }
107  	
108  	   /// Returns vector of objective values w.r.t. maximization.
109  	   VectorBase<R>& maxObj_w()
110  	   {
111  	      return object;
112  	   }
113  	
114  	   ///
115  	   const R& maxObj(int i) const
116  	   {
117  	      return object[i];
118  	   }
119  	
120  	   /// Returns objective value (w.r.t. maximization) of \p i 'th LPColBase in LPColSetBase.
121  	   R& maxObj_w(int i)
122  	   {
123  	      return object[i];
124  	   }
125  	
126  	   ///
127  	   const R& maxObj(const DataKey& k) const
128  	   {
129  	      return object[number(k)];
130  	   }
131  	
132  	   /// Returns objective value (w.r.t. maximization) of LPColBase with DataKey \p k in LPColSetBase.
133  	   R& maxObj_w(const DataKey& k)
134  	   {
135  	      return object[number(k)];
136  	   }
137  	
138  	   ///
139  	   const VectorBase<R>& lower() const
140  	   {
141  	      return low;
142  	   }
143  	
144  	   /// Returns vector of lower bound values.
145  	   VectorBase<R>& lower_w()
146  	   {
147  	      return low;
148  	   }
149  	
150  	   ///
151  	   const R& lower(int i) const
152  	   {
153  	      return low[i];
154  	   }
155  	
156  	   /// Returns lower bound of \p i 'th LPColBase in LPColSetBase.
157  	   R& lower_w(int i)
158  	   {
159  	      return low[i];
160  	   }
161  	
162  	   ///
163  	   const R& lower(const DataKey& k) const
164  	   {
165  	      return low[number(k)];
166  	   }
167  	
168  	   /// Returns lower bound of LPColBase with DataKey \p k in LPColSetBase.
169  	   R& lower_w(const DataKey& k)
170  	   {
171  	      return low[number(k)];
172  	   }
173  	
174  	   ///
175  	   const VectorBase<R>& upper() const
176  	   {
177  	      return up;
178  	   }
179  	
180  	   /// Returns vector of upper bound values.
181  	   VectorBase<R>& upper_w()
182  	   {
183  	      return up;
184  	   }
185  	
186  	   ///
187  	   const R& upper(int i) const
188  	   {
189  	      return up[i];
190  	   }
191  	
192  	   /// Returns upper bound of \p i 'th LPColBase in LPColSetBase.
193  	   R& upper_w(int i)
194  	   {
195  	      return up[i];
196  	   }
197  	
198  	   ///
199  	   const R& upper(const DataKey& k) const
200  	   {
201  	      return up[number(k)];
202  	   }
203  	
204  	   /// Returns upper bound of LPColBase with DataKey \p k in LPColSetBase.
205  	   R& upper_w(const DataKey& k)
206  	   {
207  	      return up[number(k)];
208  	   }
209  	
210  	   ///
211  	   SVectorBase<R>& colVector_w(int i)
212  	   {
213  	      return SVSetBase<R>::operator[](i);
214  	   }
215  	
216  	   /// Returns colVector of \p i 'th LPColBase in LPColSetBase.
217  	   const SVectorBase<R>& colVector(int i) const
218  	   {
219  	      return SVSetBase<R>::operator[](i);
220  	   }
221  	
222  	   /// Returns writeable colVector of LPColBase with DataKey \p k in LPColSetBase.
223  	   SVectorBase<R>& colVector_w(const DataKey& k)
224  	   {
225  	      return SVSetBase<R>::operator[](k);
226  	   }
227  	
228  	   /// Returns colVector of LPColBase with DataKey \p k in LPColSetBase.
229  	   const SVectorBase<R>& colVector(const DataKey& k) const
230  	   {
231  	      return SVSetBase<R>::operator[](k);
232  	   }
233  	
234  	   /// Returns DataKey of \p i 'th LPColBase in LPColSetBase.
235  	   DataKey key(int i) const
236  	   {
237  	      return SVSetBase<R>::key(i);
238  	   }
239  	
240  	   /// Returns number of LPColBase with DataKey \p k in LPColSetBase.
241  	   int number(const DataKey& k) const
242  	   {
243  	      return SVSetBase<R>::number(k);
244  	   }
245  	
246  	   /// Does DataKey \p k belong to LPColSetBase ?
247  	   bool has(const DataKey& k) const
248  	   {
249  	      return SVSetBase<R>::has(k);
250  	   }
251  	
252  	   ///@}
253  	
254  	   // ------------------------------------------------------------------------------------------------------------------
255  	   /**@name Extension
256  	    *
257  	    *  All extension methods come with two signatures, one of which providing a parameter to return the assigned
258  	    *  DataKey(s). See DataSet for a more detailed description. All extension methods are designed to automatically
259  	    *  reallocate memory if required.
260  	    */
261  	   ///@{
262  	
263  	   ///
264  	   void add(const LPColBase<R>& pcol)
265  	   {
266  	      DataKey k;
267  	      add(k, pcol);
268  	   }
269  	
270  	   /// Adds p pcol to LPColSetBase.
271  	   void add(DataKey& pkey, const LPColBase<R>& pcol)
272  	   {
273  	      add(pkey, pcol.obj(), pcol.lower(), pcol.colVector(), pcol.upper());
274  	   }
275  	
276  	   ///
277  	   void add(const R& pobj, const R& plower, const SVectorBase<R>& pcolVector, const R& pupper,
278  	            const int& pscaleExp = 0)
279  	   {
280  	      DataKey k;
281  	      add(k, pobj, plower, pcolVector, pupper, pscaleExp);
282  	   }
283  	
284  	   /// Adds LPColBase consisting of objective value \p obj, lower bound \p lower, column vector \p colVector and upper bound \p upper to LPColSetBase.
285  	   void add(DataKey& newkey, const R& obj, const R& newlower, const SVectorBase<R>& newcolVector,
286  	            const R& newupper, const int& newscaleExp = 0)
287  	   {
288  	      SVSetBase<R>::add(newkey, newcolVector);
289  	
290  	      if(num() > low.dim())
291  	      {
292  	         low.reDim(num());
293  	         up.reDim(num());
294  	         object.reDim(num());
295  	         scaleExp.reSize(num());
296  	      }
297  	
298  	      low[num() - 1] = newlower;
299  	      up[num() - 1] = newupper;
300  	      object[num() - 1] = obj;
301  	      scaleExp[num() - 1] = newscaleExp;
302  	   }
303  	
304  	   /// Adds LPColBase consisting of left hand side \p lhs, column vector \p colVector, and right hand side \p rhs to LPColSetBase.
305  	   template < class S >
306  	   void add(const S* obj, const S* lowerValue, const S* colValues, const int* colIndices, int colSize,
307  	            const S* upperValue)
308  	   {
309  	      DataKey k;
310  	      add(k, obj, lowerValue, colValues, colIndices, colSize, upperValue);
311  	   }
312  	
313  	   /// Adds LPColBase consisting of left hand side \p lhs, column vector \p colVector, and right hand side \p rhs to
314  	   /// LPColSetBase, with DataKey \p key.
315  	   template < class S >
316  	   void add(DataKey& newkey, const S* objValue, const S* lowerValue, const S* colValues,
317  	            const int* colIndices, int colSize, const S* upperValue)
318  	   {
319  	      SVSetBase<R>::add(newkey, colValues, colIndices, colSize);
320  	
321  	      if(num() > low.dim())
322  	      {
323  	         low.reDim(num());
324  	         up.reDim(num());
325  	         object.reDim(num());
326  	      }
327  	
328  	      low[num() - 1] = *lowerValue;
329  	      up[num() - 1] = *upperValue;
330  	      object[num() - 1] = *objValue;
331  	   }
332  	
333  	   ///
334  	   void add(const LPColSetBase<R>& newset)
335  	   {
336  	      int i = num();
337  	
338  	      SVSetBase<R>::add(newset);
339  	
340  	      if(num() > low.dim())
341  	      {
342  	         low.reDim(num());
343  	         up.reDim(num());
344  	         object.reDim(num());
345  	         scaleExp.reSize(num());
346  	      }
347  	
348  	      for(int j = 0; i < num(); ++i, ++j)
349  	      {
350  	         low[i] = newset.lower(j);
351  	         up[i] = newset.upper(j);
352  	         object[i] = newset.maxObj(j);
353  	         scaleExp[i] = newset.scaleExp[j];
354  	      }
355  	   }
356  	
357  	   /// Adds all LPColBase%s of \p set to LPColSetBase.
358  	   void add(DataKey keys[], const LPColSetBase<R>& newset)
359  	   {
360  	      int i = num();
361  	
362  	      add(newset);
363  	
364  	      for(int j = 0; i < num(); ++i, ++j)
365  	         keys[j] = key(i);
366  	   }
367  	
368  	   /// Extends column \p n to fit \p newmax nonzeros.
369  	   void xtend(int n, int newmax)
370  	   {
371  	      SVSetBase<R>::xtend(colVector_w(n), newmax);
372  	   }
373  	
374  	   /// Extends column with DataKey \p key to fit \p newmax nonzeros.
375  	   void xtend(const DataKey& pkey, int pnewmax)
376  	   {
377  	      SVSetBase<R>::xtend(colVector_w(pkey), pnewmax);
378  	   }
379  	
380  	   ///
381  	   void add2(const DataKey& k, int n, const int idx[], const R val[])
382  	   {
383  	      SVSetBase<R>::add2(colVector_w(k), n, idx, val);
384  	   }
385  	
386  	   /// Adds \p n nonzero (\p idx, \p val)-pairs to \p i 'th colVector.
387  	   void add2(int i, int n, const int idx[], const R val[])
388  	   {
389  	      SVSetBase<R>::add2(colVector_w(i), n, idx, val);
390  	   }
391  	
392  	   /// Adds \p n nonzero (\p idx, \p val)-pairs to \p i 'th colVector.
393  	   template < class S >
394  	   void add2(int i, int n, const int idx[], const S val[])
395  	   {
396  	      SVSetBase<R>::add2(colVector_w(i), n, idx, val);
397  	   }
398  	
399  	   ///
400  	   SVectorBase<R>& create(int pnonzeros = 0, const R& pobj = 1, const R& plw = 0, const R& pupp = 1,
401  	                          const int& pscaleExp = 0)
402  	   {
403  	      DataKey k;
404  	      return create(k, pnonzeros, pobj, plw, pupp, pscaleExp);
405  	   }
406  	
407  	   /// Creates new LPColBase with specified arguments and returns a reference to its column vector.
408  	   SVectorBase<R>& create(DataKey& newkey, int nonzeros = 0, const R& obj = 1, const R& newlow = 0,
409  	                          const R& newup = 1, const int& newscaleExp = 0)
410  	   {
411  	      if(num() + 1 > low.dim())
412  	      {
413  	         low.reDim(num() + 1);
414  	         up.reDim(num() + 1);
415  	         object.reDim(num() + 1);
416  	         scaleExp.reSize(num() + 1);
417  	      }
418  	
419  	      low[num()] = newlow;
420  	      up[num()] = newup;
421  	      object[num()] = obj;
422  	      scaleExp[num()] = newscaleExp;
423  	
424  	      return *SVSetBase<R>::create(newkey, nonzeros);
425  	   }
426  	
427  	   ///@}
428  	
429  	
430  	   // ------------------------------------------------------------------------------------------------------------------
431  	   /**@name Shrinking
432  	    *
433  	    *  See DataSet for a description of the renumbering of the remaining LPColBase%s in a LPColSetBase after the call of
434  	    *  a removal method.
435  	    */
436  	   ///@{
437  	
438  	   /// Removes \p i 'th LPColBase.
439  	   void remove(int i)
440  	   {
441  	      SVSetBase<R>::remove(i);
442  	      low[i] = low[num()];
443  	      up[i] = up[num()];
444  	      object[i] = object[num()];
445  	      scaleExp[i] = scaleExp[num()];
446  	      low.reDim(num());
447  	      up.reDim(num());
448  	      object.reDim(num());
449  	      scaleExp.reSize(num());
450  	   }
451  	
452  	   /// Removes LPColBase with DataKey \p k.
453  	   void remove(const DataKey& k)
454  	   {
455  	      remove(number(k));
456  	   }
457  	
458  	   /// Removes multiple elements.
459  	   void remove(int perm[])
460  	   {
461  	      int n = num();
462  	
463  	      SVSetBase<R>::remove(perm);
464  	
465  	      for(int i = 0; i < n; ++i)
466  	      {
467  	         if(perm[i] >= 0 && perm[i] != i)
468  	         {
469  	            low[perm[i]] = low[i];
470  	            up[perm[i]] = up[i];
471  	            object[perm[i]] = object[i];
472  	            scaleExp[perm[i]] = scaleExp[i];
473  	         }
474  	      }
475  	
476  	      low.reDim(num());
477  	      up.reDim(num());
478  	      object.reDim(num());
479  	      scaleExp.reSize(num());
480  	   }
481  	
482  	   /// Removes LPColBase%s with numbers \p nums, where \p n is the length of the array \p nums
483  	   void remove(const int nums[], int n)
484  	   {
485  	      DataArray < int > perm(num());
486  	      remove(nums, n, perm.get_ptr());
487  	   }
488  	
489  	   /// Removes LPColBase%s with numbers \p nums, where \p n is the length of the array \p nums, and stores the index permutation in array \p perm.
490  	   void remove(const int nums[], int n, int* perm)
491  	   {
492  	      SVSetBase<R>::remove(nums, n, perm);
493  	
494  	      int j = num();
495  	
496  	      for(int i = 0; i < j; ++i)
497  	      {
498  	         if(perm[i] >= 0 && perm[i] != i)
499  	         {
500  	            low[perm[i]] = low[i];
501  	            up[perm[i]] = up[i];
502  	            object[perm[i]] = object[i];
503  	            scaleExp[perm[i]] = scaleExp[i];
504  	         }
505  	      }
506  	
507  	      low.reDim(num());
508  	      up.reDim(num());
509  	      object.reDim(num());
510  	      scaleExp.reSize(num());
511  	   }
512  	
513  	   /// Removes all LPColBase%s from the set.
514  	   void clear()
515  	   {
516  	      SVSetBase<R>::clear();
517  	      low.reDim(num());
518  	      up.reDim(num());
519  	      object.reDim(num());
520  	      scaleExp.clear();
521  	   }
522  	
523  	   ///@}
524  	
525  	   // ------------------------------------------------------------------------------------------------------------------
526  	   /**@name Memory Management
527  	    *  See SVSet for a description of the memory management methods.
528  	   */
529  	   ///@{
530  	
531  	   /// Reallocates memory to be able to store \p newmax LPColBase%s.
532  	   void reMax(int newmax = 0)
533  	   {
534  	      SVSetBase<R>::reMax(newmax);
535  	      up.reSize(max());
536  	      low.reSize(max());
537  	      object.reSize(max());
538  	      scaleExp.reSize(max());
539  	   }
540  	
541  	   /// Returns used nonzero memory.
542  	   int memSize() const
543  	   {
544  	      return SVSetBase<R>::memSize();
545  	   }
546  	
547  	   /// Returns length of nonzero memory.
548  	   int memMax() const
549  	   {
550  	      return SVSetBase<R>::memMax();
551  	   }
552  	
553  	   /// Resets length of nonzero memory.
554  	   void memRemax(int newmax)
555  	   {
556  	      SVSetBase<R>::memRemax(newmax);
557  	   }
558  	
559  	   /// Garbage collection in nonzero memory.
560  	   void memPack()
561  	   {
562  	      SVSetBase<R>::memPack();
563  	   }
564  	
565  	   ///@}
566  	
567  	   // ------------------------------------------------------------------------------------------------------------------
568  	   /**@name Miscellaneous */
569  	   ///@{
570  	
571  	   /// Checks consistency.
572  	   bool isConsistent() const
573  	   {
574  	#ifdef ENABLE_CONSISTENCY_CHECKS
575  	
576  	      if(low.dim() != object.dim())
577  	         return SPX_MSG_INCONSISTENT("LPColSetBase");
578  	
579  	      if(low.dim() != up.dim())
580  	         return SPX_MSG_INCONSISTENT("LPColSetBase");
581  	
582  	      if(low.dim() != num())
583  	         return SPX_MSG_INCONSISTENT("LPColSetBase");
584  	
585  	      return low.isConsistent() && up.isConsistent() && SVSetBase<R>::isConsistent();
586  	#else
587  	      return true;
588  	#endif
589  	   }
590  	
591  	   ///@}
592  	
593  	   // ------------------------------------------------------------------------------------------------------------------
594  	   /**@name Constructors / Destructors */
595  	   ///@{
596  	
597  	   /// Default constructor.
598  	   /** The user can specify the initial maximum number of columns \p max and the initial maximum number of nonzero
599  	    *  entries \p memmax. If these parameters are omitted, a default size is used. However, one can add an arbitrary
600  	    *  number of columns to the LPColSetBase, which may result in automated memory realllocation.
601  	   */
602  	   explicit
603  	   LPColSetBase(int pmax = -1, int pmemmax = -1)
604  	      : SVSetBase<R>(pmax, pmemmax), low(0), up(0), object(0), scaleExp(0)
605  	   {
606  	      assert(isConsistent());
607  	   }
608  	
609  	   /// Assignment operator.
610  	   LPColSetBase<R>& operator=(const LPColSetBase<R>& rs)
611  	   {
612  	      if(this != &rs)
613  	      {
614  	         SVSetBase<R>::operator=(rs);
615  	         low = rs.low;
616  	         up = rs.up;
617  	         object = rs.object;
618  	         scaleExp = rs.scaleExp;
619  	
620  	         assert(isConsistent());
621  	      }
622  	
623  	      return *this;
624  	   }
625  	
626  	   /// Assignment operator.
627  	   template < class S >
628  	   LPColSetBase<R>& operator=(const LPColSetBase<S>& rs)
629  	   {
630  	      if(this != (const LPColSetBase<R>*)(&rs))
631  	      {
632  	         SVSetBase<R>::operator=(rs);
633  	         low = rs.low;
634  	         up = rs.up;
635  	         object = rs.object;
636  	         scaleExp = rs.scaleExp;
637  	
638  	         assert(isConsistent());
639  	      }
640  	
641  	      return *this;
642  	   }
643  	
644  	   /// Copy constructor.
645  	   LPColSetBase(const LPColSetBase<R>& rs)
646  	      : SVSetBase<R>(rs)
647  	      , low(rs.low)
648  	      , up(rs.up)
649  	      , object(rs.object)
650  	      , scaleExp(rs.scaleExp)
651  	   {
652  	      assert(isConsistent());
653  	   }
654  	
655  	   /// Copy constructor.
656  	   template < class S >
657  	   LPColSetBase(const LPColSetBase<S>& rs)
658  	      : SVSetBase<R>(rs)
659  	      , low(rs.low)
660  	      , up(rs.up)
661  	      , object(rs.object)
662  	      , scaleExp(rs.scaleExp)
663  	   {
664  	      assert(isConsistent());
665  	   }
666  	
667  	   /// Destructor.
668  	   virtual ~LPColSetBase()
669  	   {}
670  	
671  	   ///@}
672  	};
673  	
674  	} // namespace soplex
675  	#endif // _LPCOLSETBASE_H_
676