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