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