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 spxlpbase_real.hpp 26 * @brief Saving LPs with R values in a form suitable for SoPlex. 27 */ 28 29 #include <assert.h> 30 #include <stdio.h> 31 #include <ctype.h> 32 #include <iostream> 33 34 #include "soplex/spxdefines.h" 35 #include "soplex/spxout.h" 36 #include "soplex/mpsinput.h" 37 #include "soplex/exceptions.h" 38 #include "soplex/spxscaler.h" 39 40 namespace soplex 41 { 42 /// Is \p c a \c space, \c tab, \c nl or \c cr ? 43 static inline bool LPFisSpace(int c) 44 { 45 return (c == ' ') || (c == '\t') || (c == '\n') || (c == '\r'); 46 } 47 48 /// Is there a number at the beginning of \p s ? 49 static inline bool LPFisValue(const char* s) 50 { 51 return ((*s >= '0') && (*s <= '9')) || (*s == '+') || (*s == '-') || (*s == '.'); 52 } 53 54 55 /// Is there a comparison operator at the beginning of \p s ? 56 static inline bool LPFisSense(const char* s) 57 { 58 return (*s == '<') || (*s == '>') || (*s == '='); 59 } 60 61 template <class R> 62 void SPxLPBase<R>::unscaleLP() 63 { 64 SPX_MSG_INFO3((*this->spxout), (*this->spxout) << "remove persistent scaling of LP" << std::endl;) 65 66 if(lp_scaler) 67 { 68 lp_scaler->unscale(*this); 69 } 70 else 71 { 72 SPX_MSG_INFO3((*this->spxout), (*this->spxout) << "no LP scaler available" << std::endl;) 73 } 74 } 75 76 template <class R> inline 77 void SPxLPBase<R>::computePrimalActivity(const VectorBase<R>& primal, VectorBase<R>& activity, 78 const bool unscaled) const 79 { 80 if(primal.dim() != nCols()) 81 throw SPxInternalCodeException("XSPXLP01 Primal vector for computing row activity has wrong dimension"); 82 83 if(activity.dim() != nRows()) 84 throw SPxInternalCodeException("XSPXLP03 Activity vector computing row activity has wrong dimension"); 85 86 int c; 87 88 for(c = 0; c < nCols() && primal[c] == 0; c++) 89 ; 90 91 if(c >= nCols()) 92 { 93 activity.clear(); 94 return; 95 } 96 97 DSVectorBase<R> tmp(nRows()); 98 99 if(unscaled && _isScaled) 100 { 101 lp_scaler->getColUnscaled(*this, c, tmp); 102 activity = tmp; 103 } 104 else 105 activity = colVector(c); 106 107 activity *= primal[c]; 108 c++; 109 110 for(; c < nCols(); c++) 111 { 112 if(primal[c] != 0) 113 { 114 if(unscaled && _isScaled) 115 { 116 lp_scaler->getColUnscaled(*this, c, tmp); 117 activity.multAdd(primal[c], tmp); 118 } 119 else 120 activity.multAdd(primal[c], colVector(c)); 121 } 122 } 123 } 124 125 template <class R> inline 126 void SPxLPBase<R>::computeDualActivity(const VectorBase<R>& dual, VectorBase<R>& activity, 127 const bool unscaled) const 128 { 129 if(dual.dim() != nRows()) 130 throw SPxInternalCodeException("XSPXLP02 Dual vector for computing dual activity has wrong dimension"); 131 132 if(activity.dim() != nCols()) 133 throw SPxInternalCodeException("XSPXLP04 Activity vector computing dual activity has wrong dimension"); 134 135 int r; 136 137 for(r = 0; r < nRows() && dual[r] == 0; r++) 138 ; 139 140 if(r >= nRows()) 141 { 142 activity.clear(); 143 return; 144 } 145 146 DSVectorBase<R> tmp(nCols()); 147 148 if(unscaled && _isScaled) 149 { 150 lp_scaler->getRowUnscaled(*this, r, tmp); 151 activity = tmp; 152 } 153 else 154 activity = rowVector(r); 155 156 activity *= dual[r]; 157 r++; 158 159 for(; r < nRows(); r++) 160 { 161 if(dual[r] != 0) 162 { 163 if(unscaled && _isScaled) 164 { 165 lp_scaler->getRowUnscaled(*this, r, tmp); 166 activity.multAdd(dual[r], tmp); 167 } 168 else 169 activity.multAdd(dual[r], rowVector(r)); 170 } 171 } 172 } 173 174 template <class R> inline 175 R SPxLPBase<R>::maxAbsNzo(bool unscaled) const 176 { 177 R maxi = 0.0; 178 179 if(unscaled && _isScaled) 180 { 181 assert(lp_scaler != nullptr); 182 183 for(int i = 0; i < nCols(); ++i) 184 { 185 R m = lp_scaler->getColMaxAbsUnscaled(*this, i); 186 187 if(m > maxi) 188 maxi = m; 189 } 190 } 191 else 192 { 193 for(int i = 0; i < nCols(); ++i) 194 { 195 R m = colVector(i).maxAbs(); 196 197 if(m > maxi) 198 maxi = m; 199 } 200 } 201 202 assert(maxi >= 0.0); 203 204 return maxi; 205 } 206 207 template <class R> inline 208 R SPxLPBase<R>::minAbsNzo(bool unscaled) const 209 { 210 R mini = R(infinity); 211 212 if(unscaled && _isScaled) 213 { 214 assert(lp_scaler != nullptr); 215 216 for(int i = 0; i < nCols(); ++i) 217 { 218 R m = lp_scaler->getColMinAbsUnscaled(*this, i); 219 220 if(m < mini) 221 mini = m; 222 } 223 } 224 else 225 { 226 for(int i = 0; i < nCols(); ++i) 227 { 228 R m = colVector(i).minAbs(); 229 230 if(m < mini) 231 mini = m; 232 } 233 } 234 235 assert(mini >= 0.0); 236 237 return mini; 238 } 239 240 /// Gets unscaled objective vector. 241 template <class R> 242 void SPxLPBase<R>::getObjUnscaled(VectorBase<R>& pobj) const 243 { 244 if(_isScaled) 245 { 246 assert(lp_scaler); 247 lp_scaler->getMaxObjUnscaled(*this, pobj); 248 } 249 else 250 { 251 pobj = LPColSetBase<R>::maxObj(); 252 } 253 254 if(spxSense() == MINIMIZE) 255 pobj *= -1.0; 256 } 257 258 /// Gets unscaled row vector of row \p i. 259 template <class R> 260 void SPxLPBase<R>::getRowVectorUnscaled(int i, DSVectorBase<R>& vec) const 261 { 262 assert(i >= 0 && i < nRows()); 263 264 if(_isScaled) 265 lp_scaler->getRowUnscaled(*this, i, vec); 266 else 267 vec = DSVectorBase<R>(LPRowSetBase<R>::rowVector(i)); 268 } 269 270 /// Gets unscaled right hand side vector. 271 template <class R> 272 void SPxLPBase<R>::getRhsUnscaled(VectorBase<R>& vec) const 273 { 274 if(_isScaled) 275 lp_scaler->getRhsUnscaled(*this, vec); 276 else 277 vec = LPRowSetBase<R>::rhs(); 278 } 279 280 /// Returns unscaled right hand side of row number \p i. 281 template <class R> 282 R SPxLPBase<R>::rhsUnscaled(int i) const 283 { 284 assert(i >= 0 && i < nRows()); 285 286 if(_isScaled) 287 return lp_scaler->rhsUnscaled(*this, i); 288 else 289 return LPRowSetBase<R>::rhs(i); 290 } 291 292 /// Returns unscaled right hand side of row with identifier \p id. 293 template <class R> 294 R SPxLPBase<R>::rhsUnscaled(const SPxRowId& id) const 295 { 296 assert(id.isValid()); 297 return rhsUnscaled(number(id)); 298 } 299 300 /// Returns unscaled left hand side vector. 301 template <class R> 302 void SPxLPBase<R>::getLhsUnscaled(VectorBase<R>& vec) const 303 { 304 if(_isScaled) 305 lp_scaler->getLhsUnscaled(*this, vec); 306 else 307 vec = LPRowSetBase<R>::lhs(); 308 } 309 310 /// Returns unscaled left hand side of row number \p i. 311 template <class R> 312 R SPxLPBase<R>::lhsUnscaled(int i) const 313 { 314 assert(i >= 0 && i < nRows()); 315 316 if(_isScaled) 317 return lp_scaler->lhsUnscaled(*this, i); 318 else 319 return LPRowSetBase<R>::lhs(i); 320 } 321 322 /// Returns left hand side of row with identifier \p id. 323 template <class R> 324 R SPxLPBase<R>::lhsUnscaled(const SPxRowId& id) const 325 { 326 assert(id.isValid()); 327 return lhsUnscaled(number(id)); 328 } 329 330 /// Gets column vector of column \p i. 331 template <class R> 332 void SPxLPBase<R>::getColVectorUnscaled(int i, DSVectorBase<R>& vec) const 333 { 334 assert(i >= 0 && i < nCols()); 335 336 if(_isScaled) 337 lp_scaler->getColUnscaled(*this, i, vec); 338 else 339 vec = LPColSetBase<R>::colVector(i); 340 } 341 342 /// Gets column vector of column with identifier \p id. 343 template <class R> 344 void SPxLPBase<R>::getColVectorUnscaled(const SPxColId& id, DSVectorBase<R>& vec) const 345 { 346 assert(id.isValid()); 347 getColVectorUnscaled(number(id), vec); 348 } 349 350 /// Returns unscaled objective value of column \p i. 351 template <class R> 352 R SPxLPBase<R>::objUnscaled(int i) const 353 { 354 assert(i >= 0 && i < nCols()); 355 R res; 356 357 if(_isScaled) 358 { 359 res = lp_scaler->maxObjUnscaled(*this, i); 360 } 361 else 362 { 363 res = maxObj(i); 364 } 365 366 if(spxSense() == MINIMIZE) 367 res *= -1; 368 369 return res; 370 } 371 372 /// Returns unscaled objective value of column with identifier \p id. 373 template <class R> 374 R SPxLPBase<R>::objUnscaled(const SPxColId& id) const 375 { 376 assert(id.isValid()); 377 return objUnscaled(number(id)); 378 } 379 380 /// Returns unscaled objective vector for maximization problem. 381 template <class R> 382 void SPxLPBase<R>::maxObjUnscaled(VectorBase<R>& vec) const 383 { 384 if(_isScaled) 385 lp_scaler->getMaxObjUnscaled(*this, vec); 386 else 387 vec = LPColSetBase<R>::maxObj(); 388 } 389 390 /// Returns unscaled objective value of column \p i for maximization problem. 391 template <class R> 392 R SPxLPBase<R>::maxObjUnscaled(int i) const 393 { 394 assert(i >= 0 && i < nCols()); 395 396 if(_isScaled) 397 return lp_scaler->maxObjUnscaled(*this, i); 398 else 399 return LPColSetBase<R>::maxObj(i); 400 } 401 402 /// Returns unscaled objective value of column with identifier \p id for maximization problem. 403 template <class R> 404 R SPxLPBase<R>::maxObjUnscaled(const SPxColId& id) const 405 { 406 assert(id.isValid()); 407 return maxObjUnscaled(number(id)); 408 } 409 410 /// Returns unscaled upper bound vector 411 template <class R> 412 void SPxLPBase<R>::getUpperUnscaled(VectorBase<R>& vec) const 413 { 414 if(_isScaled) 415 lp_scaler->getUpperUnscaled(*this, vec); 416 else 417 vec = VectorBase<R>(LPColSetBase<R>::upper()); 418 } 419 420 /// Returns unscaled upper bound of column \p i. 421 template <class R> 422 R SPxLPBase<R>::upperUnscaled(int i) const 423 { 424 assert(i >= 0 && i < nCols()); 425 426 if(_isScaled) 427 return lp_scaler->upperUnscaled(*this, i); 428 else 429 return LPColSetBase<R>::upper(i); 430 } 431 432 /// Returns unscaled upper bound of column with identifier \p id. 433 template <class R> 434 R SPxLPBase<R>::upperUnscaled(const SPxColId& id) const 435 { 436 assert(id.isValid()); 437 return upperUnscaled(number(id)); 438 } 439 440 /// Returns unscaled lower bound vector. 441 template <class R> 442 void SPxLPBase<R>::getLowerUnscaled(VectorBase<R>& vec) const 443 { 444 if(_isScaled) 445 lp_scaler->getLowerUnscaled(*this, vec); 446 else 447 vec = VectorBase<R>(LPColSetBase<R>::lower()); 448 } 449 450 /// Returns unscaled lower bound of column \p i. 451 template<class R> 452 R SPxLPBase<R>::lowerUnscaled(int i) const 453 { 454 assert(i >= 0 && i < nCols()); 455 456 if(_isScaled) 457 return lp_scaler->lowerUnscaled(*this, i); 458 else 459 return LPColSetBase<R>::lower(i); 460 } 461 462 /// Returns unscaled lower bound of column with identifier \p id. 463 template <class R> 464 R SPxLPBase<R>::lowerUnscaled(const SPxColId& id) const 465 { 466 assert(id.isValid()); 467 return lowerUnscaled(number(id)); 468 } 469 470 471 472 473 // --------------------------------------------------------------------------------------------------------------------- 474 // Specialization for reading LP format 475 // --------------------------------------------------------------------------------------------------------------------- 476 477 #define SOPLEX_LPF_MAX_LINE_LEN 8192 ///< maximum length of a line (8190 + \\n + \\0) 478 479 480 /// Is there a possible column name at the beginning of \p s ? 481 static inline bool LPFisColName(const char* s) 482 { 483 // strchr() gives a true for the null char. 484 if(*s == '\0') 485 return false; 486 487 return ((*s >= 'A') && (*s <= 'Z')) 488 || ((*s >= 'a') && (*s <= 'z')) 489 || (strchr("!\"#$%&()/,;?@_'`{}|~", *s) != 0); 490 } 491 492 493 static inline bool LPFisInfinity(const char* s) 494 { 495 return ((s[0] == '-') || (s[0] == '+')) 496 && (tolower(s[1]) == 'i') 497 && (tolower(s[2]) == 'n') 498 && (tolower(s[3]) == 'f'); 499 } 500 501 502 503 static inline bool LPFisFree(const char* s) 504 { 505 return (tolower(s[0]) == 'f') 506 && (tolower(s[1]) == 'r') 507 && (tolower(s[2]) == 'e') 508 && (tolower(s[3]) == 'e'); 509 } 510 511 512 513 /// Read the next number and advance \p pos. 514 /** If only a sign is encountered, the number is assumed to be \c sign * 1.0. This routine will not catch malformatted 515 * numbers like .e10 ! 516 */ 517 template <class R> 518 static R LPFreadValue(char*& pos, SPxOut* spxout) 519 { 520 assert(LPFisValue(pos)); 521 522 char tmp[SOPLEX_LPF_MAX_LINE_LEN]; 523 const char* s = pos; 524 char* t; 525 R value = 1.0; 526 bool has_digits = false; 527 bool has_emptyexponent = false; 528 529 // 1. sign 530 if((*s == '+') || (*s == '-')) 531 s++; 532 533 // 2. Digits before the decimal dot 534 while((*s >= '0') && (*s <= '9')) 535 { 536 has_digits = true; 537 s++; 538 } 539 540 // 3. Decimal dot 541 if(*s == '.') 542 { 543 s++; 544 545 // 4. If there was a dot, possible digit behind it 546 while((*s >= '0') && (*s <= '9')) 547 { 548 has_digits = true; 549 s++; 550 } 551 } 552 553 // 5. Exponent 554 if(tolower(*s) == 'e') 555 { 556 has_emptyexponent = true; 557 s++; 558 559 // 6. Exponent sign 560 if((*s == '+') || (*s == '-')) 561 s++; 562 563 // 7. Exponent digits 564 while((*s >= '0') && (*s <= '9')) 565 { 566 has_emptyexponent = false; 567 s++; 568 } 569 } 570 571 assert(s != pos); 572 573 if(has_emptyexponent) 574 { 575 SPX_MSG_WARNING((*spxout), (*spxout) << 576 "WLPFRD01 Warning: found empty exponent in LP file - check for forbidden variable names with initial 'e' or 'E'\n"; 577 ) 578 } 579 580 if(!has_digits) 581 value = (*pos == '-') ? -1.0 : 1.0; 582 else 583 { 584 for(t = tmp; pos != s; pos++) 585 *t++ = *pos; 586 587 *t = '\0'; 588 value = atof(tmp); 589 } 590 591 pos += s - pos; 592 593 assert(pos == s); 594 595 SPxOut::debug(spxout, "DLPFRD01 LPFreadValue = {}\n", value); 596 597 if(LPFisSpace(*pos)) 598 pos++; 599 600 return value; 601 } 602 603 604 605 /// Read the next column name from the input. 606 /** The name read is looked up and if not found \p emptycol 607 * is added to \p colset. \p pos is advanced behind the name. 608 * @return The Index of the named column. 609 */ 610 template <class R> 611 static int LPFreadColName(char*& pos, NameSet* colnames, LPColSetBase<R>& colset, 612 const LPColBase<R>* emptycol, SPxOut* spxout) 613 { 614 assert(LPFisColName(pos)); 615 assert(colnames != 0); 616 617 char name[SOPLEX_LPF_MAX_LINE_LEN]; 618 const char* s = pos; 619 int i; 620 int colidx; 621 622 // These are the characters that are not allowed in a column name. 623 while((strchr("+-.<>= ", *s) == 0) && (*s != '\0')) 624 s++; 625 626 for(i = 0; pos != s; i++, pos++) 627 name[i] = *pos; 628 629 name[i] = '\0'; 630 631 if((colidx = colnames->number(name)) < 0) 632 { 633 // We only add the name if we got an empty column. 634 if(emptycol == nullptr) 635 { 636 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD02 Unknown variable \"" << name << "\" ";) 637 } 638 else 639 { 640 colidx = colnames->num(); 641 colnames->add(name); 642 colset.add(*emptycol); 643 } 644 } 645 646 SPxOut::debug(spxout, "DLPFRD03 LPFreadColName [{}] = {}\n", name, colidx); 647 648 if(LPFisSpace(*pos)) 649 pos++; 650 651 return colidx; 652 } 653 654 655 656 /// Read the next <,>,=,==,<=,=<,>=,=> and advance \p pos. 657 static inline int LPFreadSense(char*& pos) 658 { 659 assert(LPFisSense(pos)); 660 661 int sense = *pos++; 662 663 if((*pos == '<') || (*pos == '>')) 664 sense = *pos++; 665 else if(*pos == '=') 666 pos++; 667 668 if(LPFisSpace(*pos)) 669 pos++; 670 671 return sense; 672 } 673 674 675 676 /// Is the \p keyword present in \p buf ? If yes, advance \p pos. 677 /** \p keyword should be lower case. It can contain optional sections which are enclosed in '[' ']' like "min[imize]". 678 */ 679 static inline bool LPFhasKeyword(char*& pos, const char* keyword) 680 { 681 int i; 682 int k; 683 684 assert(keyword != 0); 685 686 for(i = 0, k = 0; keyword[i] != '\0'; i++, k++) 687 { 688 if(keyword[i] == '[') 689 { 690 i++; 691 692 // Here we assumed that we have a ']' for the '['. 693 while((tolower(pos[k]) == keyword[i]) && (pos[k] != '\0')) 694 { 695 k++; 696 i++; 697 } 698 699 while(keyword[i] != ']') 700 i++; 701 702 --k; 703 } 704 else 705 { 706 if(keyword[i] != tolower(pos[k])) 707 break; 708 } 709 } 710 711 // we have to be at the end of the keyword and the word found on the line also has to end here. Attention: The 712 // LPFisSense is a kludge to allow LPFhasKeyword also to process Inf[inity] keywords in the bounds section. 713 if(keyword[i] == '\0' && (pos[k] == '\0' || LPFisSpace(pos[k]) || LPFisSense(&pos[k]))) 714 { 715 pos += k; 716 717 return true; 718 } 719 720 return false; 721 } 722 723 724 725 /// If \p buf start with "name:" store the name in \p rownames and advance \p pos. 726 static inline bool LPFhasRowName(char*& pos, NameSet* rownames) 727 { 728 const char* s = strchr(pos, ':'); 729 730 if(s == 0) 731 return false; 732 733 int dcolpos = int(s - pos); 734 735 int end; 736 int srt; 737 738 // skip spaces between name and ":" 739 for(end = dcolpos - 1; end >= 0; end--) 740 if(pos[end] != ' ') 741 break; 742 743 // are there only spaces in front of the ":" ? 744 if(end < 0) 745 { 746 pos = &(pos[dcolpos + 1]); 747 return false; 748 } 749 750 // skip spaces in front of name 751 for(srt = end - 1; srt >= 0; srt--) 752 if(pos[srt] == ' ') 753 break; 754 755 // go back to the non-space character 756 srt++; 757 758 assert(srt <= end && pos[srt] != ' '); 759 760 char name[SOPLEX_LPF_MAX_LINE_LEN]; 761 int i; 762 int k = 0; 763 764 for(i = srt; i <= end; i++) 765 name[k++] = pos[i]; 766 767 name[k] = '\0'; 768 769 if(rownames != 0) 770 rownames->add(name); 771 772 pos = &(pos[dcolpos + 1]); 773 774 return true; 775 } 776 777 778 template <class R> 779 static R LPFreadInfinity(char*& pos) 780 { 781 assert(LPFisInfinity(pos)); 782 783 R sense = (*pos == '-') ? -1.0 : 1.0; 784 785 (void) LPFhasKeyword(++pos, "inf[inity]"); 786 787 return sense * R(infinity); 788 } 789 790 791 /// Read LP in "CPLEX LP File Format". 792 /** The specification is taken from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 527. 793 * 794 * This routine should read (most?) valid LP format files. What it will not do, is find all cases where a file is ill 795 * formed. If this happens it may complain and read nothing or read "something". 796 * 797 * Problem: A line ending in '+' or '-' followed by a line starting with a number, will be regarded as an error. 798 * 799 * The reader will accept the keyword INT[egers] as a synonym for GEN[erals] which is an undocumented feature in CPLEX. 800 * 801 * A difference to the CPLEX reader, is that no name for the objective row is required. 802 * 803 * The manual says the maximum allowed line length is 255 characters, but CPLEX does not complain if the lines are 804 * longer. 805 * 806 * @return true if the file was read correctly 807 */ 808 template <class R> inline 809 bool SPxLPBase<R>::readLPF( 810 std::istream& p_input, ///< input stream. 811 NameSet* p_rnames, ///< row names. 812 NameSet* p_cnames, ///< column names. 813 DIdxSet* p_intvars) ///< integer variables. 814 { 815 enum 816 { 817 START, OBJECTIVE, CONSTRAINTS, BOUNDS, INTEGERS, BINARIES 818 } section = START; 819 820 NameSet* rnames; ///< row names. 821 NameSet* cnames; ///< column names. 822 823 LPColSetBase<R> cset; ///< the set of columns read. 824 LPRowSetBase<R> rset; ///< the set of rows read. 825 LPColBase<R> emptycol; ///< reusable empty column. 826 LPRowBase<R> row; ///< last assembled row. 827 DSVectorBase<R> vec; ///< last assembled vector (from row). 828 829 R val = 1.0; 830 int colidx; 831 int sense = 0; 832 833 int lineno = 0; 834 bool unnamed = true; 835 bool finished = false; 836 bool other; 837 bool have_value = true; 838 int i; 839 int k; 840 int buf_size; 841 int buf_pos; 842 char* buf = NULL; 843 char* tmp = NULL; 844 char* line = NULL; 845 char* s; 846 char* pos; 847 char* pos_old = 0; 848 849 if(p_cnames) 850 cnames = p_cnames; 851 else 852 { 853 cnames = 0; 854 spx_alloc(cnames); 855 cnames = new(cnames) NameSet(); 856 } 857 858 cnames->clear(); 859 860 if(p_rnames) 861 rnames = p_rnames; 862 else 863 { 864 try 865 { 866 rnames = 0; 867 spx_alloc(rnames); 868 rnames = new(rnames) NameSet(); 869 } 870 catch(const SPxMemoryException& x) 871 { 872 if(!p_cnames) 873 { 874 cnames->~NameSet(); 875 spx_free(cnames); 876 } 877 878 throw x; 879 } 880 } 881 882 rnames->clear(); 883 884 SPxLPBase<R>::clear(); // clear the LP. 885 886 //-------------------------------------------------------------------------- 887 //--- Main Loop 888 //-------------------------------------------------------------------------- 889 buf_size = SOPLEX_LPF_MAX_LINE_LEN; 890 spx_alloc(buf, buf_size); 891 spx_alloc(tmp, buf_size); 892 spx_alloc(line, buf_size); 893 buf[0] = '\0'; 894 895 for(;;) 896 { 897 // 0. Read a line from the file. 898 buf_pos = 0; 899 900 while(!p_input.getline(buf + buf_pos, buf_size - buf_pos)) 901 { 902 p_input.clear(); 903 904 if(strlen(buf) == (size_t) buf_size - 1) 905 { 906 buf_pos = buf_size - 1; 907 buf_size = buf_size + SOPLEX_LPF_MAX_LINE_LEN; 908 909 if(buf_size >= INT_MAX) 910 { 911 SPX_MSG_ERROR(std::cerr << "ELPFRD16 Line longer than INT_MAX" << std::endl;) 912 finished = true; 913 break; 914 } 915 916 spx_realloc(buf, buf_size); 917 } 918 else 919 { 920 SPX_MSG_ERROR(std::cerr << "ELPFRD07 No 'End' marker found" << std::endl;) 921 finished = true; 922 break; 923 } 924 } 925 926 if((size_t) buf_size > sizeof(tmp)) 927 { 928 spx_realloc(tmp, buf_size); 929 spx_realloc(line, buf_size); 930 } 931 932 lineno++; 933 i = 0; 934 pos = buf; 935 936 SPxOut::debug(spxout, "DLPFRD08 Reading line {} (pos={})\n", lineno, pos); 937 938 // 1. Remove comments. 939 if(0 != (s = strchr(buf, '\\'))) 940 * s = '\0'; 941 942 // 2. Look for keywords. 943 if(section == START) 944 { 945 if(LPFhasKeyword(pos, "max[imize]")) 946 { 947 changeSense(SPxLPBase<R>::MAXIMIZE); 948 section = OBJECTIVE; 949 } 950 else if(LPFhasKeyword(pos, "min[imize]")) 951 { 952 changeSense(SPxLPBase<R>::MINIMIZE); 953 section = OBJECTIVE; 954 } 955 } 956 else if(section == OBJECTIVE) 957 { 958 if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") 959 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 960 || LPFhasKeyword(pos, "s[.][ ]t[.]") 961 || LPFhasKeyword(pos, "lazy con[straints]")) 962 { 963 // store objective vector 964 for(int j = vec.size() - 1; j >= 0; --j) 965 cset.maxObj_w(vec.index(j)) = vec.value(j); 966 967 // multiplication with -1 for minimization is done below 968 vec.clear(); 969 have_value = true; 970 val = 1.0; 971 section = CONSTRAINTS; 972 } 973 } 974 else if(section == CONSTRAINTS && 975 (LPFhasKeyword(pos, "s[ubject][ ]t[o]") 976 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 977 || LPFhasKeyword(pos, "s[.][ ]t[.]"))) 978 { 979 have_value = true; 980 val = 1.0; 981 } 982 else 983 { 984 if(LPFhasKeyword(pos, "lazy con[straints]")) 985 ; 986 else if(LPFhasKeyword(pos, "bound[s]")) 987 section = BOUNDS; 988 else if(LPFhasKeyword(pos, "bin[ary]")) 989 section = BINARIES; 990 else if(LPFhasKeyword(pos, "bin[aries]")) 991 section = BINARIES; 992 else if(LPFhasKeyword(pos, "gen[erals]")) 993 section = INTEGERS; 994 else if(LPFhasKeyword(pos, "int[egers]")) // this is undocumented 995 section = INTEGERS; 996 else if(LPFhasKeyword(pos, "end")) 997 { 998 finished = true; 999 break; 1000 } 1001 else if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") // second time 1002 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 1003 || LPFhasKeyword(pos, "s[.][ ]t[.]") 1004 || LPFhasKeyword(pos, "lazy con[straints]")) 1005 { 1006 // In principle this has to checked for all keywords above, 1007 // otherwise we just ignore any half finished constraint 1008 if(have_value) 1009 goto syntax_error; 1010 1011 have_value = true; 1012 val = 1.0; 1013 } 1014 } 1015 1016 // 3a. Look for row names in objective and drop it. 1017 if(section == OBJECTIVE) 1018 LPFhasRowName(pos, 0); 1019 1020 // 3b. Look for row name in constraint and store it. 1021 if(section == CONSTRAINTS) 1022 if(LPFhasRowName(pos, rnames)) 1023 unnamed = false; 1024 1025 // 4a. Remove initial spaces. 1026 while(LPFisSpace(pos[i])) 1027 i++; 1028 1029 // 4b. remove spaces if they do not appear before the name of a vaiable. 1030 for(k = 0; pos[i] != '\0'; i++) 1031 if(!LPFisSpace(pos[i]) || LPFisColName(&pos[i + 1])) 1032 tmp[k++] = pos[i]; 1033 1034 tmp[k] = '\0'; 1035 1036 // 5. Is this an empty line ? 1037 if(tmp[0] == '\0') 1038 continue; 1039 1040 // 6. Collapse sequences of '+' and '-'. e.g ++---+ => - 1041 for(i = 0, k = 0; tmp[i] != '\0'; i++) 1042 { 1043 while(((tmp[i] == '+') || (tmp[i] == '-')) && ((tmp[i + 1] == '+') || (tmp[i + 1] == '-'))) 1044 { 1045 if(tmp[i++] == '-') 1046 tmp[i] = (tmp[i] == '-') ? '+' : '-'; 1047 } 1048 1049 line[k++] = tmp[i]; 1050 } 1051 1052 line[k] = '\0'; 1053 1054 //----------------------------------------------------------------------- 1055 //--- Line processing loop 1056 //----------------------------------------------------------------------- 1057 pos = line; 1058 1059 SPxOut::debug(spxout, "DLPFRD09 pos={}\n", pos); 1060 1061 // 7. We have something left to process. 1062 while((pos != 0) && (*pos != '\0')) 1063 { 1064 // remember our position, so we are sure we make progress. 1065 pos_old = pos; 1066 1067 // now process the sections 1068 switch(section) 1069 { 1070 case OBJECTIVE: 1071 if(LPFisValue(pos)) 1072 { 1073 R pre_sign = 1.0; 1074 1075 /* Already having here a value could only result from being the first number in a constraint, or a sign 1076 * '+' or '-' as last token on the previous line. 1077 */ 1078 if(have_value) 1079 { 1080 if(NE(spxAbs(val), R(1.0), this->tolerances()->epsilon())) 1081 goto syntax_error; 1082 1083 if(EQ(val, R(-1.0), this->tolerances()->epsilon())) 1084 pre_sign = val; 1085 } 1086 1087 /* non-finite coefficients are not allowed in the objective */ 1088 if(LPFisInfinity(pos)) 1089 goto syntax_error; 1090 1091 have_value = true; 1092 val = LPFreadValue<R>(pos, spxout) * pre_sign; 1093 } 1094 1095 if(*pos == '\0') 1096 continue; 1097 1098 if(!have_value || !LPFisColName(pos)) 1099 goto syntax_error; 1100 1101 have_value = false; 1102 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout); 1103 vec.add(colidx, val); 1104 break; 1105 1106 case CONSTRAINTS: 1107 if(LPFisValue(pos)) 1108 { 1109 R pre_sign = 1.0; 1110 1111 /* Already having here a value could only result from being the first number in a constraint, or a sign 1112 * '+' or '-' as last token on the previous line. 1113 */ 1114 if(have_value) 1115 { 1116 if(NE(spxAbs(val), R(1.0), this->tolerances()->epsilon())) 1117 goto syntax_error; 1118 1119 if(EQ(val, R(-1.0), this->tolerances()->epsilon())) 1120 pre_sign = val; 1121 } 1122 1123 if(LPFisInfinity(pos)) 1124 { 1125 /* non-finite coefficients are not allowed */ 1126 if(sense == 0) 1127 goto syntax_error; 1128 1129 val = LPFreadInfinity<R>(pos) * pre_sign; 1130 } 1131 else 1132 val = LPFreadValue<R>(pos, spxout) * pre_sign; 1133 1134 have_value = true; 1135 1136 if(sense != 0) 1137 { 1138 if(sense == '<') 1139 { 1140 row.setLhs(R(-infinity)); 1141 row.setRhs(val); 1142 } 1143 else if(sense == '>') 1144 { 1145 row.setLhs(val); 1146 row.setRhs(R(infinity)); 1147 } 1148 else 1149 { 1150 assert(sense == '='); 1151 1152 row.setLhs(val); 1153 row.setRhs(val); 1154 } 1155 1156 row.setRowVector(vec); 1157 rset.add(row); 1158 vec.clear(); 1159 1160 if(!unnamed) 1161 unnamed = true; 1162 else 1163 { 1164 char name[16]; 1165 spxSnprintf(name, 16, "C%d", rset.num()); 1166 rnames->add(name); 1167 } 1168 1169 have_value = true; 1170 val = 1.0; 1171 sense = 0; 1172 pos = 0; 1173 // next line 1174 continue; 1175 } 1176 } 1177 1178 if(*pos == '\0') 1179 continue; 1180 1181 if(have_value) 1182 { 1183 if(LPFisColName(pos)) 1184 { 1185 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout); 1186 1187 if(val != 0.0) 1188 { 1189 // Do we have this index already in the row? 1190 int n = vec.pos(colidx); 1191 1192 // if not, add it 1193 if(n < 0) 1194 vec.add(colidx, val); 1195 // if yes, add them up and remove the element if it amounts to zero 1196 else 1197 { 1198 assert(vec.index(n) == colidx); 1199 1200 val += vec.value(n); 1201 1202 if(val == 0.0) 1203 vec.remove(n); 1204 else 1205 vec.value(n) = val; 1206 1207 assert(cnames->has(colidx)); 1208 1209 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD10 Duplicate index " 1210 << (*cnames)[colidx] 1211 << " in line " << lineno 1212 << std::endl;) 1213 } 1214 } 1215 1216 have_value = false; 1217 } 1218 else 1219 { 1220 // We have a row like c1: <= 5 with no variables. We can not handle 10 <= 5; issue a syntax error. 1221 if(val != 1.0) 1222 goto syntax_error; 1223 1224 // If the next thing is not the sense we give up also. 1225 if(!LPFisSense(pos)) 1226 goto syntax_error; 1227 1228 have_value = false; 1229 } 1230 } 1231 1232 assert(!have_value); 1233 1234 if(LPFisSense(pos)) 1235 sense = LPFreadSense(pos); 1236 1237 break; 1238 1239 case BOUNDS: 1240 other = false; 1241 sense = 0; 1242 1243 if(LPFisValue(pos)) 1244 { 1245 val = LPFisInfinity(pos) ? LPFreadInfinity<R>(pos) : LPFreadValue<R>(pos, spxout); 1246 1247 if(!LPFisSense(pos)) 1248 goto syntax_error; 1249 1250 sense = LPFreadSense(pos); 1251 other = true; 1252 } 1253 1254 if(!LPFisColName(pos)) 1255 goto syntax_error; 1256 1257 if((colidx = LPFreadColName<R>(pos, cnames, cset, nullptr, spxout)) < 0) 1258 { 1259 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD11 in Bounds section line " 1260 << lineno << " ignored" << std::endl;) 1261 *pos = '\0'; 1262 continue; 1263 } 1264 1265 if(sense) 1266 { 1267 if(sense == '<') 1268 cset.lower_w(colidx) = val; 1269 else if(sense == '>') 1270 cset.upper_w(colidx) = val; 1271 else 1272 { 1273 assert(sense == '='); 1274 cset.lower_w(colidx) = val; 1275 cset.upper_w(colidx) = val; 1276 } 1277 } 1278 1279 if(LPFisFree(pos)) 1280 { 1281 cset.lower_w(colidx) = R(-infinity); 1282 cset.upper_w(colidx) = R(infinity); 1283 other = true; 1284 pos += 4; // set position after the word "free" 1285 } 1286 else if(LPFisSense(pos)) 1287 { 1288 sense = LPFreadSense(pos); 1289 other = true; 1290 1291 if(!LPFisValue(pos)) 1292 goto syntax_error; 1293 1294 val = LPFisInfinity(pos) ? LPFreadInfinity<R>(pos) : LPFreadValue<R>(pos, spxout); 1295 1296 if(sense == '<') 1297 cset.upper_w(colidx) = val; 1298 else if(sense == '>') 1299 cset.lower_w(colidx) = val; 1300 else 1301 { 1302 assert(sense == '='); 1303 cset.lower_w(colidx) = val; 1304 cset.upper_w(colidx) = val; 1305 } 1306 } 1307 1308 /* Do we have only a single column name in the input line? We could ignore this savely, but it is probably 1309 * a sign of some other error. 1310 */ 1311 if(!other) 1312 goto syntax_error; 1313 1314 break; 1315 1316 case BINARIES: 1317 case INTEGERS: 1318 if((colidx = LPFreadColName<R>(pos, cnames, cset, 0, spxout)) < 0) 1319 { 1320 SPX_MSG_WARNING((*this->spxout), 1321 (*this->spxout) << "WLPFRD12 in Binary/General section line " << lineno 1322 << " ignored" << std::endl;) 1323 } 1324 else 1325 { 1326 if(section == BINARIES) 1327 { 1328 if(cset.lower(colidx) < 0.0) 1329 { 1330 cset.lower_w(colidx) = 0.0; 1331 } 1332 1333 if(cset.upper(colidx) > 1.0) 1334 { 1335 cset.upper_w(colidx) = 1.0; 1336 } 1337 } 1338 1339 if(p_intvars != 0) 1340 p_intvars->addIdx(colidx); 1341 } 1342 1343 break; 1344 1345 case START: 1346 SPX_MSG_ERROR(std::cerr << "ELPFRD13 This seems to be no LP format file" << std::endl;) 1347 goto syntax_error; 1348 1349 default: 1350 throw SPxInternalCodeException("XLPFRD01 This should never happen."); 1351 } 1352 1353 if(pos == pos_old) 1354 goto syntax_error; 1355 } 1356 } 1357 1358 assert(isConsistent()); 1359 1360 addCols(cset); 1361 assert(isConsistent()); 1362 1363 addRows(rset); 1364 assert(isConsistent()); 1365 1366 syntax_error: 1367 1368 if(finished) 1369 { 1370 SPX_MSG_INFO2((*this->spxout), (*this->spxout) << "Finished reading " << lineno << " lines" << 1371 std::endl;) 1372 } 1373 else 1374 SPX_MSG_ERROR(std::cerr << "ELPFRD15 Syntax error in line " << lineno << std::endl;) 1375 1376 if(p_cnames == 0) 1377 spx_free(cnames); 1378 1379 if(p_rnames == 0) 1380 spx_free(rnames); 1381 1382 return finished; 1383 } 1384 1385 1386 1387 // --------------------------------------------------------------------------------------------------------------------- 1388 // Specialization for reading MPS format 1389 // --------------------------------------------------------------------------------------------------------------------- 1390 1391 /// Process NAME section. 1392 static inline void MPSreadName(MPSInput& mps, SPxOut* spxout) 1393 { 1394 do 1395 { 1396 // This has to be the Line with the NAME section. 1397 if(!mps.readLine() || (mps.field0() == 0) || strcmp(mps.field0(), "NAME")) 1398 break; 1399 1400 // Sometimes the name is omitted. 1401 mps.setProbName((mps.field1() == 0) ? "_MPS_" : mps.field1()); 1402 1403 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD01 Problem name : " << mps.probName() << std::endl;) 1404 1405 // This has to be a new section 1406 if(!mps.readLine() || (mps.field0() == 0)) 1407 break; 1408 1409 if(!strcmp(mps.field0(), "ROWS")) 1410 mps.setSection(MPSInput::ROWS); 1411 else if(!strncmp(mps.field0(), "OBJSEN", 6)) 1412 mps.setSection(MPSInput::OBJSEN); 1413 else if(!strcmp(mps.field0(), "OBJNAME")) 1414 mps.setSection(MPSInput::OBJNAME); 1415 else 1416 break; 1417 1418 return; 1419 } 1420 while(false); 1421 1422 mps.syntaxError(); 1423 } 1424 1425 1426 1427 /// Process OBJSEN section. This Section is an ILOG extension. 1428 static inline void MPSreadObjsen(MPSInput& mps) 1429 { 1430 do 1431 { 1432 // This has to be the Line with MIN or MAX. 1433 if(!mps.readLine() || (mps.field1() == 0)) 1434 break; 1435 1436 if(!strcmp(mps.field1(), "MIN")) 1437 mps.setObjSense(MPSInput::MINIMIZE); 1438 else if(!strcmp(mps.field1(), "MAX")) 1439 mps.setObjSense(MPSInput::MAXIMIZE); 1440 else 1441 break; 1442 1443 // Look for ROWS or OBJNAME Section 1444 if(!mps.readLine() || (mps.field0() == 0)) 1445 break; 1446 1447 if(!strcmp(mps.field0(), "ROWS")) 1448 mps.setSection(MPSInput::ROWS); 1449 else if(!strcmp(mps.field0(), "OBJNAME")) 1450 mps.setSection(MPSInput::OBJNAME); 1451 else 1452 break; 1453 1454 return; 1455 } 1456 while(false); 1457 1458 mps.syntaxError(); 1459 } 1460 1461 1462 1463 /// Process OBJNAME section. This Section is an ILOG extension. 1464 static inline void MPSreadObjname(MPSInput& mps) 1465 { 1466 do 1467 { 1468 // This has to be the Line with the name. 1469 if(!mps.readLine() || (mps.field1() == 0)) 1470 break; 1471 1472 mps.setObjName(mps.field1()); 1473 1474 // Look for ROWS Section 1475 if(!mps.readLine() || (mps.field0() == 0)) 1476 break; 1477 1478 if(strcmp(mps.field0(), "ROWS")) 1479 break; 1480 1481 mps.setSection(MPSInput::ROWS); 1482 1483 return; 1484 } 1485 while(false); 1486 1487 mps.syntaxError(); 1488 } 1489 1490 1491 1492 /// Process ROWS section. 1493 template <class R> 1494 static void MPSreadRows(MPSInput& mps, LPRowSetBase<R>& rset, NameSet& rnames, SPxOut* spxout) 1495 { 1496 LPRowBase<R> row; 1497 1498 while(mps.readLine()) 1499 { 1500 if(mps.field0() != 0) 1501 { 1502 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD02 Objective name : " << mps.objName() << std::endl;) 1503 1504 if(strcmp(mps.field0(), "COLUMNS")) 1505 break; 1506 1507 mps.setSection(MPSInput::COLUMNS); 1508 1509 return; 1510 } 1511 1512 if((mps.field1() == 0) || (mps.field2() == 0)) 1513 break; 1514 1515 if(*mps.field1() == 'N') 1516 { 1517 if(*mps.objName() == '\0') 1518 mps.setObjName(mps.field2()); 1519 } 1520 else 1521 { 1522 if(rnames.has(mps.field2())) 1523 break; 1524 1525 rnames.add(mps.field2()); 1526 1527 switch(*mps.field1()) 1528 { 1529 case 'G': 1530 row.setLhs(0.0); 1531 row.setRhs(R(infinity)); 1532 break; 1533 1534 case 'E': 1535 row.setLhs(0.0); 1536 row.setRhs(0.0); 1537 break; 1538 1539 case 'L': 1540 row.setLhs(R(-infinity)); 1541 row.setRhs(0.0); 1542 break; 1543 1544 default: 1545 mps.syntaxError(); 1546 return; 1547 } 1548 1549 rset.add(row); 1550 } 1551 1552 assert((*mps.field1() == 'N') || (rnames.number(mps.field2()) == rset.num() - 1)); 1553 } 1554 1555 mps.syntaxError(); 1556 } 1557 1558 1559 1560 /// Process COLUMNS section. 1561 template <class R> 1562 static void MPSreadCols(MPSInput& mps, const LPRowSetBase<R>& rset, const NameSet& rnames, 1563 LPColSetBase<R>& cset, NameSet& cnames, DIdxSet* intvars) 1564 { 1565 R val; 1566 int idx; 1567 char colname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1568 LPColBase<R> col(rset.num()); 1569 DSVectorBase<R> vec; 1570 1571 col.setObj(0.0); 1572 vec.clear(); 1573 1574 while(mps.readLine()) 1575 { 1576 if(mps.field0() != 0) 1577 { 1578 if(strcmp(mps.field0(), "RHS")) 1579 break; 1580 1581 if(colname[0] != '\0') 1582 { 1583 col.setColVector(vec); 1584 cset.add(col); 1585 } 1586 1587 mps.setSection(MPSInput::RHS); 1588 1589 return; 1590 } 1591 1592 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1593 break; 1594 1595 // new column? 1596 if(strcmp(colname, mps.field1())) 1597 { 1598 // first column? 1599 if(colname[0] != '\0') 1600 { 1601 col.setColVector(vec); 1602 cset.add(col); 1603 } 1604 1605 // save copy of string (make sure string ends with \0) 1606 spxSnprintf(colname, MPSInput::MAX_LINE_LEN - 1, "%s", mps.field1()); 1607 colname[MPSInput::MAX_LINE_LEN - 1] = '\0'; 1608 1609 int ncnames = cnames.size(); 1610 cnames.add(colname); 1611 1612 // check whether the new name is unique wrt previous column names 1613 if(cnames.size() <= ncnames) 1614 { 1615 SPX_MSG_ERROR(std::cerr << "ERROR in COLUMNS: duplicate column name or not column-wise ordering" << 1616 std::endl;) 1617 break; 1618 } 1619 1620 vec.clear(); 1621 col.setObj(0.0); 1622 col.setLower(0.0); 1623 col.setUpper(R(infinity)); 1624 1625 if(mps.isInteger()) 1626 { 1627 assert(cnames.number(colname) == cset.num()); 1628 1629 if(intvars != 0) 1630 intvars->addIdx(cnames.number(colname)); 1631 1632 // for Integer variable the default bounds are 0/1 1633 col.setUpper(1.0); 1634 } 1635 } 1636 1637 val = atof(mps.field3()); 1638 1639 if(!strcmp(mps.field2(), mps.objName())) 1640 col.setObj(val); 1641 else 1642 { 1643 if((idx = rnames.number(mps.field2())) < 0) 1644 mps.entryIgnored("Column", mps.field1(), "row", mps.field2()); 1645 else if(val != 0.0) 1646 vec.add(idx, val); 1647 } 1648 1649 if(mps.field5() != 0) 1650 { 1651 assert(mps.field4() != 0); 1652 1653 val = atof(mps.field5()); 1654 1655 if(!strcmp(mps.field4(), mps.objName())) 1656 col.setObj(val); 1657 else 1658 { 1659 if((idx = rnames.number(mps.field4())) < 0) 1660 mps.entryIgnored("Column", mps.field1(), "row", mps.field4()); 1661 else if(val != 0.0) 1662 vec.add(idx, val); 1663 } 1664 } 1665 } 1666 1667 mps.syntaxError(); 1668 } 1669 1670 1671 1672 /// Process RHS section. 1673 template <class R> 1674 static void MPSreadRhs(MPSInput& mps, LPRowSetBase<R>& rset, const NameSet& rnames, SPxOut* spxout) 1675 { 1676 char rhsname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1677 char addname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1678 int idx; 1679 R val; 1680 1681 while(mps.readLine()) 1682 { 1683 if(mps.field0() != 0) 1684 { 1685 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD03 RHS name : " << rhsname << std::endl;); 1686 1687 if(!strcmp(mps.field0(), "RANGES")) 1688 mps.setSection(MPSInput::RANGES); 1689 else if(!strcmp(mps.field0(), "BOUNDS")) 1690 mps.setSection(MPSInput::BOUNDS); 1691 else if(!strcmp(mps.field0(), "ENDATA")) 1692 mps.setSection(MPSInput::ENDATA); 1693 else 1694 break; 1695 1696 return; 1697 } 1698 1699 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0))) 1700 mps.insertName("_RHS_"); 1701 1702 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1703 break; 1704 1705 if(*rhsname == '\0') 1706 spxSnprintf(rhsname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1707 1708 if(strcmp(rhsname, mps.field1())) 1709 { 1710 if(strcmp(addname, mps.field1())) 1711 { 1712 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN); 1713 spxSnprintf(addname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1714 SPX_MSG_INFO3((*spxout), (*spxout) << "IMPSRD07 RHS ignored : " << addname << std::endl); 1715 } 1716 } 1717 else 1718 { 1719 if((idx = rnames.number(mps.field2())) < 0) 1720 mps.entryIgnored("RHS", mps.field1(), "row", mps.field2()); 1721 else 1722 { 1723 val = atof(mps.field3()); 1724 1725 // LE or EQ 1726 if(rset.rhs(idx) < R(infinity)) 1727 rset.rhs_w(idx) = val; 1728 1729 // GE or EQ 1730 if(rset.lhs(idx) > R(-infinity)) 1731 rset.lhs_w(idx) = val; 1732 } 1733 1734 if(mps.field5() != 0) 1735 { 1736 if((idx = rnames.number(mps.field4())) < 0) 1737 mps.entryIgnored("RHS", mps.field1(), "row", mps.field4()); 1738 else 1739 { 1740 val = atof(mps.field5()); 1741 1742 // LE or EQ 1743 if(rset.rhs(idx) < R(infinity)) 1744 rset.rhs_w(idx) = val; 1745 1746 // GE or EQ 1747 if(rset.lhs(idx) > R(-infinity)) 1748 rset.lhs_w(idx) = val; 1749 } 1750 } 1751 } 1752 } 1753 1754 mps.syntaxError(); 1755 } 1756 1757 1758 1759 /// Process RANGES section. 1760 template <class R> 1761 static void MPSreadRanges(MPSInput& mps, LPRowSetBase<R>& rset, const NameSet& rnames, 1762 SPxOut* spxout) 1763 { 1764 char rngname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1765 int idx; 1766 R val; 1767 1768 while(mps.readLine()) 1769 { 1770 if(mps.field0() != 0) 1771 { 1772 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD04 Range name : " << rngname << std::endl;); 1773 1774 if(!strcmp(mps.field0(), "BOUNDS")) 1775 mps.setSection(MPSInput::BOUNDS); 1776 else if(!strcmp(mps.field0(), "ENDATA")) 1777 mps.setSection(MPSInput::ENDATA); 1778 else 1779 break; 1780 1781 return; 1782 } 1783 1784 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0))) 1785 mps.insertName("_RNG_"); 1786 1787 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1788 break; 1789 1790 if(*rngname == '\0') 1791 { 1792 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN); 1793 spxSnprintf(rngname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1794 } 1795 1796 /* The rules are: 1797 * Row Sign LHS RHS 1798 * ---------------------------------------- 1799 * G +/- rhs rhs + |range| 1800 * L +/- rhs - |range| rhs 1801 * E + rhs rhs + range 1802 * E - rhs + range rhs 1803 * ---------------------------------------- 1804 */ 1805 if(!strcmp(rngname, mps.field1())) 1806 { 1807 if((idx = rnames.number(mps.field2())) < 0) 1808 mps.entryIgnored("Range", mps.field1(), "row", mps.field2()); 1809 else 1810 { 1811 val = atof(mps.field3()); 1812 1813 // EQ 1814 if((rset.lhs(idx) > R(-infinity)) && (rset.rhs_w(idx) < R(infinity))) 1815 { 1816 assert(rset.lhs(idx) == rset.rhs(idx)); 1817 1818 if(val >= 0) 1819 rset.rhs_w(idx) += val; 1820 else 1821 rset.lhs_w(idx) += val; 1822 } 1823 else 1824 { 1825 // GE 1826 if(rset.lhs(idx) > R(-infinity)) 1827 rset.rhs_w(idx) = rset.lhs(idx) + spxAbs(val); 1828 // LE 1829 else 1830 rset.lhs_w(idx) = rset.rhs(idx) - spxAbs(val); 1831 } 1832 } 1833 1834 if(mps.field5() != 0) 1835 { 1836 if((idx = rnames.number(mps.field4())) < 0) 1837 mps.entryIgnored("Range", mps.field1(), "row", mps.field4()); 1838 else 1839 { 1840 val = atof(mps.field5()); 1841 1842 // EQ 1843 if((rset.lhs(idx) > R(-infinity)) && (rset.rhs(idx) < R(infinity))) 1844 { 1845 assert(rset.lhs(idx) == rset.rhs(idx)); 1846 1847 if(val >= 0) 1848 rset.rhs_w(idx) += val; 1849 else 1850 rset.lhs_w(idx) += val; 1851 } 1852 else 1853 { 1854 // GE 1855 if(rset.lhs(idx) > R(-infinity)) 1856 rset.rhs_w(idx) = rset.lhs(idx) + spxAbs(val); 1857 // LE 1858 else 1859 rset.lhs_w(idx) = rset.rhs(idx) - spxAbs(val); 1860 } 1861 } 1862 } 1863 } 1864 } 1865 1866 mps.syntaxError(); 1867 } 1868 1869 1870 1871 /// Process BOUNDS section. 1872 template <class R> 1873 static void MPSreadBounds(MPSInput& mps, LPColSetBase<R>& cset, const NameSet& cnames, 1874 DIdxSet* intvars, SPxOut* spxout) 1875 { 1876 DIdxSet oldbinvars; 1877 char bndname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1878 int idx; 1879 R val; 1880 1881 while(mps.readLine()) 1882 { 1883 if(mps.field0() != 0) 1884 { 1885 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD05 Bound name : " << bndname << std::endl;) 1886 1887 if(strcmp(mps.field0(), "ENDATA")) 1888 break; 1889 1890 mps.setSection(MPSInput::ENDATA); 1891 1892 return; 1893 } 1894 1895 // Is the value field used ? 1896 if((!strcmp(mps.field1(), "LO")) 1897 || (!strcmp(mps.field1(), "UP")) 1898 || (!strcmp(mps.field1(), "FX")) 1899 || (!strcmp(mps.field1(), "LI")) 1900 || (!strcmp(mps.field1(), "UI"))) 1901 { 1902 if((mps.field3() != 0) && (mps.field4() == 0)) 1903 mps.insertName("_BND_", true); 1904 } 1905 else 1906 { 1907 if((mps.field2() != 0) && (mps.field3() == 0)) 1908 mps.insertName("_BND_", true); 1909 } 1910 1911 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1912 break; 1913 1914 if(*bndname == '\0') 1915 { 1916 assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN); 1917 spxSnprintf(bndname, MPSInput::MAX_LINE_LEN, "%s", mps.field2()); 1918 } 1919 1920 // Only read the first Bound in section 1921 if(!strcmp(bndname, mps.field2())) 1922 { 1923 if((idx = cnames.number(mps.field3())) < 0) 1924 mps.entryIgnored("column", mps.field3(), "bound", bndname); 1925 else 1926 { 1927 if(mps.field4() == 0) 1928 val = 0.0; 1929 else if(!strcmp(mps.field4(), "-Inf") || !strcmp(mps.field4(), "-inf")) 1930 val = R(-infinity); 1931 else if(!strcmp(mps.field4(), "Inf") || !strcmp(mps.field4(), "inf") 1932 || !strcmp(mps.field4(), "+Inf") || !strcmp(mps.field4(), "+inf")) 1933 val = R(infinity); 1934 else 1935 val = atof(mps.field4()); 1936 1937 // ILOG extension (Integer Bound) 1938 if(mps.field1()[1] == 'I') 1939 { 1940 if(intvars != 0) 1941 intvars->addIdx(idx); 1942 1943 // if the variable has appeared in the MARKER section of the COLUMNS section then its default bounds were 1944 // set to 0,1; the first time it is declared integer we need to change to default bounds 0,R(infinity) 1945 if(oldbinvars.pos(idx) < 0) 1946 { 1947 cset.upper_w(idx) = R(infinity); 1948 oldbinvars.addIdx(idx); 1949 } 1950 } 1951 1952 switch(*mps.field1()) 1953 { 1954 case 'L': 1955 cset.lower_w(idx) = val; 1956 break; 1957 1958 case 'U': 1959 cset.upper_w(idx) = val; 1960 break; 1961 1962 case 'F': 1963 if(mps.field1()[1] == 'X') 1964 { 1965 cset.lower_w(idx) = val; 1966 cset.upper_w(idx) = val; 1967 } 1968 else 1969 { 1970 cset.lower_w(idx) = R(-infinity); 1971 cset.upper_w(idx) = R(infinity); 1972 } 1973 1974 break; 1975 1976 case 'M': 1977 cset.lower_w(idx) = R(-infinity); 1978 break; 1979 1980 case 'P': 1981 cset.upper_w(idx) = R(infinity); 1982 break; 1983 1984 // Ilog extension (Binary) 1985 case 'B': 1986 cset.lower_w(idx) = 0.0; 1987 cset.upper_w(idx) = 1.0; 1988 1989 if(intvars != 0) 1990 intvars->addIdx(idx); 1991 1992 break; 1993 1994 default: 1995 mps.syntaxError(); 1996 return; 1997 } 1998 } 1999 } 2000 } 2001 2002 mps.syntaxError(); 2003 } 2004 2005 2006 2007 /// Read LP in MPS File Format. 2008 /** 2009 * The specification is taken from the IBM Optimization Library Guide and Reference, online available at 2010 * http://www.software.ibm.com/sos/features/libuser.htm and from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 2011 * 531. 2012 * 2013 * This routine should read all valid MPS format files. What it will not do, is find all cases where a file is ill 2014 * formed. If this happens it may complain and read nothing or read "something". 2015 * 2016 * @return true if the file was read correctly. 2017 */ 2018 const int Init_Cols = 10000; ///< initialy allocated columns. 2019 const int Init_NZos = 100000; ///< initialy allocated non zeros. 2020 template <class R> inline 2021 bool SPxLPBase<R>::readMPS( 2022 std::istream& p_input, ///< input stream. 2023 NameSet* p_rnames, ///< row names. 2024 NameSet* p_cnames, ///< column names. 2025 DIdxSet* p_intvars) ///< integer variables. 2026 { 2027 LPRowSetBase<R>& rset = *this; 2028 LPColSetBase<R>& cset = *this; 2029 NameSet* rnames; 2030 NameSet* cnames; 2031 2032 if(p_cnames) 2033 cnames = p_cnames; 2034 else 2035 { 2036 cnames = 0; 2037 spx_alloc(cnames); 2038 cnames = new(cnames) NameSet(); 2039 } 2040 2041 cnames->clear(); 2042 2043 if(p_rnames) 2044 rnames = p_rnames; 2045 else 2046 { 2047 try 2048 { 2049 rnames = 0; 2050 spx_alloc(rnames); 2051 rnames = new(rnames) NameSet(); 2052 } 2053 catch(const SPxMemoryException& x) 2054 { 2055 if(!p_cnames) 2056 { 2057 cnames->~NameSet(); 2058 spx_free(cnames); 2059 } 2060 2061 throw x; 2062 } 2063 } 2064 2065 rnames->clear(); 2066 2067 SPxLPBase<R>::clear(); // clear the LP. 2068 2069 cset.memRemax(Init_NZos); 2070 cset.reMax(Init_Cols); 2071 2072 MPSInput mps(p_input); 2073 2074 MPSreadName(mps, spxout); 2075 2076 if(mps.section() == MPSInput::OBJSEN) 2077 MPSreadObjsen(mps); 2078 2079 if(mps.section() == MPSInput::OBJNAME) 2080 MPSreadObjname(mps); 2081 2082 if(mps.section() == MPSInput::ROWS) 2083 MPSreadRows(mps, rset, *rnames, spxout); 2084 2085 addedRows(rset.num()); 2086 2087 if(mps.section() == MPSInput::COLUMNS) 2088 MPSreadCols(mps, rset, *rnames, cset, *cnames, p_intvars); 2089 2090 if(mps.section() == MPSInput::RHS) 2091 MPSreadRhs(mps, rset, *rnames, spxout); 2092 2093 if(mps.section() == MPSInput::RANGES) 2094 MPSreadRanges(mps, rset, *rnames, spxout); 2095 2096 if(mps.section() == MPSInput::BOUNDS) 2097 MPSreadBounds(mps, cset, *cnames, p_intvars, spxout); 2098 2099 if(mps.section() != MPSInput::ENDATA) 2100 mps.syntaxError(); 2101 2102 if(mps.hasError()) 2103 clear(); 2104 else 2105 { 2106 changeSense(mps.objSense() == MPSInput::MINIMIZE ? SPxLPBase<R>::MINIMIZE : SPxLPBase<R>::MAXIMIZE); 2107 2108 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD06 Objective sense: " << ((mps.objSense() == 2109 MPSInput::MINIMIZE) ? "Minimize\n" : "Maximize\n")); 2110 2111 added2Set( 2112 *(reinterpret_cast<SVSetBase<R>*>(static_cast<LPRowSetBase<R>*>(this))), 2113 *(reinterpret_cast<SVSetBase<R>*>(static_cast<LPColSetBase<R>*>(this))), 2114 cset.num()); 2115 addedCols(cset.num()); 2116 2117 assert(isConsistent()); 2118 } 2119 2120 if(p_cnames == 0) 2121 { 2122 cnames->~NameSet(); 2123 spx_free(cnames); 2124 } 2125 2126 if(p_rnames == 0) 2127 { 2128 rnames->~NameSet(); 2129 spx_free(rnames); 2130 } 2131 2132 return !mps.hasError(); 2133 } 2134 2135 2136 2137 // --------------------------------------------------------------------------------------------------------------------- 2138 // Specialization for writing LP format 2139 // --------------------------------------------------------------------------------------------------------------------- 2140 2141 // get the name of a row or construct one 2142 template <class R> 2143 static const char* LPFgetRowName( 2144 const SPxLPBase<R>& p_lp, 2145 int p_idx, 2146 const NameSet* p_rnames, 2147 char* p_buf, 2148 int p_num_written_rows 2149 ) 2150 { 2151 assert(p_buf != 0); 2152 assert(p_idx >= 0); 2153 assert(p_idx < p_lp.nRows()); 2154 2155 if(p_rnames != 0) 2156 { 2157 DataKey key = p_lp.rId(p_idx); 2158 2159 if(p_rnames->has(key)) 2160 return (*p_rnames)[key]; 2161 } 2162 2163 spxSnprintf(p_buf, 16, "C%d", p_num_written_rows); 2164 2165 return p_buf; 2166 } 2167 2168 2169 2170 // get the name of a column or construct one 2171 template <class R> 2172 static const char* getColName( 2173 const SPxLPBase<R>& p_lp, 2174 int p_idx, 2175 const NameSet* p_cnames, 2176 char* p_buf 2177 ) 2178 { 2179 assert(p_buf != 0); 2180 assert(p_idx >= 0); 2181 assert(p_idx < p_lp.nCols()); 2182 2183 if(p_cnames != 0) 2184 { 2185 DataKey key = p_lp.cId(p_idx); 2186 2187 if(p_cnames->has(key)) 2188 return (*p_cnames)[key]; 2189 } 2190 2191 spxSnprintf(p_buf, 16, "x%d", p_idx); 2192 2193 return p_buf; 2194 } 2195 2196 2197 2198 // write an SVectorBase<R> 2199 #define SOPLEX_NUM_ENTRIES_PER_LINE 5 2200 template <class R> 2201 static void LPFwriteSVector( 2202 const SPxLPBase<R>& p_lp, ///< the LP 2203 std::ostream& p_output, ///< output stream 2204 const NameSet* p_cnames, ///< column names 2205 const SVectorBase<R>& p_svec) ///< vector to write 2206 { 2207 2208 char name[16]; 2209 int num_coeffs = 0; 2210 2211 for(int j = 0; j < p_lp.nCols(); ++j) 2212 { 2213 const R coeff = p_svec[j]; 2214 2215 if(coeff == 0) 2216 continue; 2217 2218 if(num_coeffs == 0) 2219 p_output << coeff << " " << getColName(p_lp, j, p_cnames, name); 2220 else 2221 { 2222 // insert a line break every SOPLEX_NUM_ENTRIES_PER_LINE columns 2223 if(num_coeffs % SOPLEX_NUM_ENTRIES_PER_LINE == 0) 2224 p_output << "\n\t"; 2225 2226 if(coeff < 0) 2227 p_output << " - " << -coeff; 2228 else 2229 p_output << " + " << coeff; 2230 2231 p_output << " " << getColName(p_lp, j, p_cnames, name); 2232 } 2233 2234 ++num_coeffs; 2235 } 2236 } 2237 2238 2239 2240 // write the objective 2241 template <class R> 2242 static void LPFwriteObjective( 2243 const SPxLPBase<R>& p_lp, ///< the LP 2244 std::ostream& p_output, ///< output stream 2245 const NameSet* p_cnames ///< column names 2246 ) 2247 { 2248 2249 const int sense = p_lp.spxSense(); 2250 2251 p_output << ((sense == SPxLPBase<R>::MINIMIZE) ? "Minimize\n" : "Maximize\n"); 2252 p_output << " obj: "; 2253 2254 const VectorBase<R>& obj = p_lp.maxObj(); 2255 DSVectorBase<R> svec(obj.dim()); 2256 svec.operator = (obj); 2257 svec *= R(sense); 2258 LPFwriteSVector(p_lp, p_output, p_cnames, svec); 2259 p_output << "\n"; 2260 } 2261 2262 2263 2264 // write non-ranged rows 2265 template <class R> 2266 static void LPFwriteRow( 2267 const SPxLPBase<R>& p_lp, ///< the LP 2268 std::ostream& p_output, ///< output stream 2269 const NameSet* p_cnames, ///< column names 2270 const SVectorBase<R>& p_svec, ///< vector of the row 2271 const R& p_lhs, ///< lhs of the row 2272 const R& p_rhs ///< rhs of the row 2273 ) 2274 { 2275 2276 LPFwriteSVector(p_lp, p_output, p_cnames, p_svec); 2277 2278 if(p_lhs == p_rhs) 2279 p_output << " = " << p_rhs; 2280 else if(p_lhs <= R(-infinity)) 2281 p_output << " <= " << p_rhs; 2282 else 2283 { 2284 assert(p_rhs >= R(infinity)); 2285 p_output << " >= " << p_lhs; 2286 } 2287 2288 p_output << "\n"; 2289 } 2290 2291 2292 2293 // write all rows 2294 template <class R> 2295 static void LPFwriteRows( 2296 const SPxLPBase<R>& p_lp, ///< the LP 2297 std::ostream& p_output, ///< output stream 2298 const NameSet* p_rnames, ///< row names 2299 const NameSet* p_cnames ///< column names 2300 ) 2301 { 2302 2303 char name[16]; 2304 2305 p_output << "Subject To\n"; 2306 2307 for(int i = 0; i < p_lp.nRows(); ++i) 2308 { 2309 const R lhs = p_lp.lhs(i); 2310 const R rhs = p_lp.rhs(i); 2311 2312 if(lhs > R(-infinity) && rhs < R(infinity) && lhs != rhs) 2313 { 2314 // ranged row -> write two non-ranged rows 2315 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_1 : "; 2316 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, R(infinity)); 2317 2318 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_2 : "; 2319 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), R(-infinity), rhs); 2320 } 2321 else 2322 { 2323 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << " : "; 2324 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, rhs); 2325 } 2326 } 2327 } 2328 2329 2330 2331 // write the variable bounds 2332 // (the default bounds 0 <= x <= R(infinity) are not written) 2333 template <class R> 2334 static void LPFwriteBounds( 2335 const SPxLPBase<R>& p_lp, ///< the LP to write 2336 std::ostream& p_output, ///< output stream 2337 const NameSet* p_cnames ///< column names 2338 ) 2339 { 2340 2341 char name[16]; 2342 2343 p_output << "Bounds\n"; 2344 2345 for(int j = 0; j < p_lp.nCols(); ++j) 2346 { 2347 const R lower = p_lp.lower(j); 2348 const R upper = p_lp.upper(j); 2349 2350 if(lower == upper) 2351 { 2352 p_output << " " << getColName(p_lp, j, p_cnames, name) << " = " << upper << '\n'; 2353 } 2354 else if(lower > R(-infinity)) 2355 { 2356 if(upper < R(infinity)) 2357 { 2358 // range bound 2359 if(lower != 0) 2360 p_output << " " << lower << " <= " 2361 << getColName(p_lp, j, p_cnames, name) 2362 << " <= " << upper << '\n'; 2363 else 2364 p_output << " " << getColName(p_lp, j, p_cnames, name) 2365 << " <= " << upper << '\n'; 2366 } 2367 else if(lower != 0) 2368 p_output << " " << lower << " <= " 2369 << getColName(p_lp, j, p_cnames, name) 2370 << '\n'; 2371 } 2372 else if(upper < R(infinity)) 2373 p_output << " -Inf <= " 2374 << getColName(p_lp, j, p_cnames, name) 2375 << " <= " << upper << '\n'; 2376 else 2377 p_output << " " << getColName(p_lp, j, p_cnames, name) 2378 << " free\n"; 2379 } 2380 } 2381 2382 2383 2384 // write the generals section 2385 template <class R> 2386 static void LPFwriteGenerals( 2387 const SPxLPBase<R>& p_lp, ///< the LP to write 2388 std::ostream& p_output, ///< output stream 2389 const NameSet* p_cnames, ///< column names 2390 const DIdxSet* p_intvars ///< integer variables 2391 ) 2392 { 2393 2394 char name[16]; 2395 2396 if(p_intvars == NULL || p_intvars->size() <= 0) 2397 return; // no integer variables 2398 2399 p_output << "Generals\n"; 2400 2401 for(int j = 0; j < p_lp.nCols(); ++j) 2402 if(p_intvars->pos(j) >= 0) 2403 p_output << " " << getColName(p_lp, j, p_cnames, name) << "\n"; 2404 } 2405 2406 2407 2408 /// Write LP in LP Format. 2409 template <class R> inline 2410 void SPxLPBase<R>::writeLPF( 2411 std::ostream& p_output, ///< output stream 2412 const NameSet* p_rnames, ///< row names 2413 const NameSet* p_cnames, ///< column names 2414 const DIdxSet* p_intvars ///< integer variables 2415 ) const 2416 { 2417 SPxOut::setScientific(p_output, 16); 2418 2419 LPFwriteObjective(*this, p_output, p_cnames); 2420 LPFwriteRows(*this, p_output, p_rnames, p_cnames); 2421 LPFwriteBounds(*this, p_output, p_cnames); 2422 LPFwriteGenerals(*this, p_output, p_cnames, p_intvars); 2423 2424 p_output << "End" << std::endl; 2425 } 2426 2427 2428 2429 // --------------------------------------------------------------------------------------------------------------------- 2430 // Specialization for writing MPS format 2431 // --------------------------------------------------------------------------------------------------------------------- 2432 2433 template <class R> 2434 static void MPSwriteRecord( 2435 std::ostream& os, 2436 const char* indicator, 2437 const char* name, 2438 const char* name1 = nullptr, 2439 const R value1 = 0.0, 2440 const char* name2 = nullptr, 2441 const R value2 = 0.0 2442 ) 2443 { 2444 char buf[81]; 2445 2446 spxSnprintf(buf, sizeof(buf), " %-2.2s %-8.8s", (indicator == 0) ? "" : indicator, 2447 (name == 0) ? "" : name); 2448 os << buf; 2449 2450 if(name1 != nullptr) 2451 { 2452 spxSnprintf(buf, sizeof(buf), "%-8.8s %.15" SOPLEX_REAL_FORMAT, name1, (Real) value1); 2453 os << buf; 2454 2455 if(name2 != 0) 2456 { 2457 spxSnprintf(buf, sizeof(buf), " %-8.8s %.15" SOPLEX_REAL_FORMAT, name2, (Real) value2); 2458 os << buf; 2459 } 2460 } 2461 2462 os << std::endl; 2463 } 2464 2465 2466 2467 template <class R> 2468 static R MPSgetRHS(R left, R right) 2469 { 2470 R rhsval; 2471 2472 if(left > R(-infinity)) /// This includes ranges 2473 rhsval = left; 2474 else if(right < R(infinity)) 2475 rhsval = right; 2476 else 2477 throw SPxInternalCodeException("XMPSWR01 This should never happen."); 2478 2479 return rhsval; 2480 } 2481 2482 2483 template <class R> 2484 static const char* MPSgetRowName( 2485 const SPxLPBase<R>& lp, 2486 int idx, 2487 const NameSet* rnames, 2488 char* buf 2489 ) 2490 { 2491 assert(buf != 0); 2492 assert(idx >= 0); 2493 assert(idx < lp.nRows()); 2494 2495 if(rnames != 0) 2496 { 2497 DataKey key = lp.rId(idx); 2498 2499 if(rnames->has(key)) 2500 return (*rnames)[key]; 2501 } 2502 2503 spxSnprintf(buf, 16, "C%d", idx); 2504 2505 return buf; 2506 } 2507 2508 2509 2510 /// Write LP in MPS format. 2511 /** @note There will always be a BOUNDS section, even if there are no bounds. 2512 */ 2513 template <class R> inline 2514 void SPxLPBase<R>::writeMPS( 2515 std::ostream& p_output, ///< output stream. 2516 const NameSet* p_rnames, ///< row names. 2517 const NameSet* p_cnames, ///< column names. 2518 const DIdxSet* p_intvars ///< integer variables. 2519 ) const 2520 { 2521 2522 const char* indicator; 2523 char name [16]; 2524 char name1[16]; 2525 char name2[16]; 2526 bool has_ranges = false; 2527 int i; 2528 int k; 2529 2530 SPxOut::setScientific(p_output, 16); 2531 // --- NAME Section --- 2532 p_output << "NAME MPSDATA" << std::endl; 2533 2534 // --- ROWS Section --- 2535 p_output << "ROWS" << std::endl; 2536 2537 for(i = 0; i < nRows(); i++) 2538 { 2539 if(lhs(i) == rhs(i)) 2540 indicator = "E"; 2541 else if((lhs(i) > R(-infinity)) && (rhs(i) < R(infinity))) 2542 { 2543 indicator = "E"; 2544 has_ranges = true; 2545 } 2546 else if(lhs(i) > R(-infinity)) 2547 indicator = "G"; 2548 else if(rhs(i) < R(infinity)) 2549 indicator = "L"; 2550 else 2551 throw SPxInternalCodeException("XMPSWR02 This should never happen."); 2552 2553 MPSwriteRecord<R>(p_output, indicator, MPSgetRowName(*this, i, p_rnames, name)); 2554 } 2555 2556 MPSwriteRecord<R>(p_output, "N", "MINIMIZE"); 2557 2558 // --- COLUMNS Section --- 2559 p_output << "COLUMNS" << std::endl; 2560 2561 bool has_intvars = (p_intvars != 0) && (p_intvars->size() > 0); 2562 2563 for(int j = 0; j < (has_intvars ? 2 : 1); j++) 2564 { 2565 bool is_intrun = has_intvars && (j == 1); 2566 2567 if(is_intrun) 2568 p_output << " MARK0001 'MARKER' 'INTORG'" << std::endl; 2569 2570 for(i = 0; i < nCols(); i++) 2571 { 2572 bool is_intvar = has_intvars && (p_intvars->pos(i) >= 0); 2573 2574 if((is_intrun && !is_intvar) || (!is_intrun && is_intvar)) 2575 continue; 2576 2577 const SVectorBase<R>& col = colVector(i); 2578 int colsize2 = (col.size() / 2) * 2; 2579 2580 assert(colsize2 % 2 == 0); 2581 2582 for(k = 0; k < colsize2; k += 2) 2583 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), 2584 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k), 2585 MPSgetRowName(*this, col.index(k + 1), p_rnames, name2), col.value(k + 1)); 2586 2587 if(colsize2 != col.size()) 2588 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), 2589 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k)); 2590 2591 if(isNotZero(maxObj(i), this->tolerances()->epsilon())) 2592 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), "MINIMIZE", -maxObj(i)); 2593 } 2594 2595 if(is_intrun) 2596 p_output << " MARK0001 'MARKER' 'INTEND'" << std::endl; 2597 } 2598 2599 // --- RHS Section --- 2600 p_output << "RHS" << std::endl; 2601 2602 i = 0; 2603 2604 while(i < nRows()) 2605 { 2606 R rhsval1 = 0.0; 2607 R rhsval2 = 0.0; 2608 2609 for(; i < nRows(); i++) 2610 if((rhsval1 = MPSgetRHS(lhs(i), rhs(i))) != 0.0) 2611 break; 2612 2613 if(i < nRows()) 2614 { 2615 for(k = i + 1; k < nRows(); k++) 2616 { 2617 if((rhsval2 = MPSgetRHS(lhs(k), rhs(k))) != 0.0) 2618 break; 2619 } 2620 2621 if(k < nRows()) 2622 { 2623 MPSwriteRecord(p_output, 0, "RHS", MPSgetRowName(*this, i, p_rnames, name1), rhsval1, 2624 MPSgetRowName(*this, k, p_rnames, name2), rhsval2); 2625 } 2626 else 2627 MPSwriteRecord(p_output, 0, "RHS", MPSgetRowName(*this, i, p_rnames, name1), rhsval1); 2628 2629 i = k + 1; 2630 } 2631 } 2632 2633 // --- RANGES Section --- 2634 if(has_ranges) 2635 { 2636 p_output << "RANGES" << std::endl; 2637 2638 for(i = 0; i < nRows(); i++) 2639 { 2640 if((lhs(i) > R(-infinity)) && (rhs(i) < R(infinity))) 2641 MPSwriteRecord(p_output, "", "RANGE", MPSgetRowName(*this, i, p_rnames, name1), rhs(i) - lhs(i)); 2642 } 2643 } 2644 2645 // --- BOUNDS Section --- 2646 p_output << "BOUNDS" << std::endl; 2647 2648 for(i = 0; i < nCols(); i++) 2649 { 2650 // skip variables that do not appear in the objective function or any constraint 2651 const SVectorBase<R>& col = colVector(i); 2652 2653 if(col.size() == 0 && isZero(maxObj(i), this->tolerances()->epsilon())) 2654 continue; 2655 2656 if(lower(i) == upper(i)) 2657 { 2658 MPSwriteRecord(p_output, "FX", "BOUND", getColName(*this, i, p_cnames, name1), lower(i)); 2659 continue; 2660 } 2661 2662 if((lower(i) <= R(-infinity)) && (upper(i) >= R(infinity))) 2663 { 2664 MPSwriteRecord<R>(p_output, "FR", "BOUND", getColName(*this, i, p_cnames, name1)); 2665 continue; 2666 } 2667 2668 if(lower(i) != 0.0) 2669 { 2670 if(lower(i) > R(-infinity)) 2671 MPSwriteRecord(p_output, "LO", "BOUND", getColName(*this, i, p_cnames, name1), lower(i)); 2672 else 2673 MPSwriteRecord<R>(p_output, "MI", "BOUND", getColName(*this, i, p_cnames, name1)); 2674 } 2675 2676 if(has_intvars && (p_intvars->pos(i) >= 0)) 2677 { 2678 // Integer variables have default upper bound 1.0, but we should write 2679 // it nevertheless since CPLEX seems to assume R(infinity) otherwise. 2680 MPSwriteRecord(p_output, "UP", "BOUND", getColName(*this, i, p_cnames, name1), upper(i)); 2681 } 2682 else 2683 { 2684 // Continous variables have default upper bound R(infinity) 2685 if(upper(i) < R(infinity)) 2686 MPSwriteRecord(p_output, "UP", "BOUND", getColName(*this, i, p_cnames, name1), upper(i)); 2687 } 2688 } 2689 2690 // --- ENDATA Section --- 2691 p_output << "ENDATA" << std::endl; 2692 2693 // Output warning when writing a maximisation problem 2694 if(spxSense() == SPxLPBase<R>::MAXIMIZE) 2695 { 2696 SPX_MSG_WARNING((*spxout), (*spxout) << 2697 "XMPSWR03 Warning: objective function inverted when writing maximization problem in MPS file format\n"); 2698 } 2699 } 2700 2701 2702 2703 /// Building the dual problem from a given LP 2704 /// @note primalRows must be as large as the number of unranged primal rows + 2 * the number of ranged primal rows. 2705 /// dualCols must have the identical size to the primal rows. 2706 template <class R> inline 2707 void SPxLPBase<R>::buildDualProblem(SPxLPBase<R>& dualLP, SPxRowId primalRowIds[], 2708 SPxColId primalColIds[], 2709 SPxRowId dualRowIds[], SPxColId dualColIds[], int* nprimalrows, int* nprimalcols, int* ndualrows, 2710 int* ndualcols) 2711 { 2712 // Setting up the primalrowids and dualcolids arrays if not given as parameters 2713 if(primalRowIds == 0 || primalColIds == 0 || dualRowIds == 0 || dualColIds == 0) 2714 { 2715 DataArray < SPxRowId > primalrowids(2 * nRows()); 2716 DataArray < SPxColId > primalcolids(2 * nCols()); 2717 DataArray < SPxRowId > dualrowids(2 * nCols()); 2718 DataArray < SPxColId > dualcolids(2 * nRows()); 2719 int numprimalrows = 0; 2720 int numprimalcols = 0; 2721 int numdualrows = 0; 2722 int numdualcols = 0; 2723 2724 buildDualProblem(dualLP, primalrowids.get_ptr(), primalcolids.get_ptr(), dualrowids.get_ptr(), 2725 dualcolids.get_ptr(), &numprimalrows, &numprimalcols, &numdualrows, &numdualcols); 2726 2727 if(primalRowIds != 0) 2728 { 2729 primalRowIds = primalrowids.get_ptr(); 2730 (*nprimalrows) = numprimalrows; 2731 } 2732 2733 if(primalColIds != 0) 2734 { 2735 primalColIds = primalcolids.get_ptr(); 2736 (*nprimalcols) = numprimalcols; 2737 } 2738 2739 if(dualRowIds != 0) 2740 { 2741 dualRowIds = dualrowids.get_ptr(); 2742 (*ndualrows) = numdualrows; 2743 } 2744 2745 if(dualColIds != 0) 2746 { 2747 dualColIds = dualcolids.get_ptr(); 2748 (*ndualcols) = numdualcols; 2749 } 2750 2751 return; 2752 } 2753 2754 // setting the sense of the dual LP 2755 if(spxSense() == MINIMIZE) 2756 dualLP.changeSense(MAXIMIZE); 2757 else 2758 dualLP.changeSense(MINIMIZE); 2759 2760 LPRowSetBase<R> dualrows(nCols()); 2761 LPColSetBase<R> dualcols(nRows()); 2762 DSVectorBase<R> col(1); 2763 2764 int numAddedRows = 0; 2765 int numVarBoundCols = 0; 2766 int primalrowsidx = 0; 2767 int primalcolsidx = 0; 2768 2769 for(int i = 0; i < nCols(); ++i) 2770 { 2771 primalColIds[primalcolsidx] = cId(i); 2772 primalcolsidx++; 2773 2774 if(lower(i) <= R(-infinity) && upper(i) >= R(infinity)) // unrestricted variables 2775 { 2776 dualrows.create(0, obj(i), obj(i)); 2777 numAddedRows++; 2778 } 2779 else if(lower(i) <= R(-infinity)) // no lower bound is set, indicating a <= 0 variable 2780 { 2781 if(isZero(upper(i), this->tolerances()->epsilon())) // standard bound variable 2782 { 2783 if(spxSense() == MINIMIZE) 2784 dualrows.create(0, obj(i), R(infinity)); 2785 else 2786 dualrows.create(0, R(-infinity), obj(i)); 2787 } 2788 else // additional upper bound on the variable 2789 { 2790 col.add(numAddedRows, 1.0); 2791 2792 if(spxSense() == MINIMIZE) 2793 { 2794 dualrows.create(0, obj(i), obj(i)); 2795 dualcols.add(upper(i), R(-infinity), col, 0.0); 2796 } 2797 else 2798 { 2799 dualrows.create(0, obj(i), obj(i)); 2800 dualcols.add(upper(i), 0.0, col, R(infinity)); 2801 } 2802 2803 col.clear(); 2804 2805 numVarBoundCols++; 2806 } 2807 2808 numAddedRows++; 2809 } 2810 else if(upper(i) >= R(infinity)) // no upper bound set, indicating a >= 0 variable 2811 { 2812 if(isZero(lower(i), this->tolerances()->epsilon())) // standard bound variable 2813 { 2814 if(spxSense() == MINIMIZE) 2815 dualrows.create(0, R(-infinity), obj(i)); 2816 else 2817 dualrows.create(0, obj(i), R(infinity)); 2818 } 2819 else // additional lower bound on the variable 2820 { 2821 col.add(numAddedRows, 1.0); 2822 2823 if(spxSense() == MINIMIZE) 2824 { 2825 dualrows.create(0, obj(i), obj(i)); 2826 dualcols.add(lower(i), 0.0, col, R(infinity)); 2827 } 2828 else 2829 { 2830 dualrows.create(0, obj(i), obj(i)); 2831 dualcols.add(lower(i), R(-infinity), col, 0.0); 2832 } 2833 2834 col.clear(); 2835 2836 numVarBoundCols++; 2837 } 2838 2839 numAddedRows++; 2840 } 2841 else if(NE(lower(i), upper(i), this->tolerances()->epsilon())) // a boxed variable 2842 { 2843 if(isZero(lower(i), this->tolerances()->epsilon())) // variable bounded between 0 and upper(i) 2844 { 2845 col.add(numAddedRows, 1.0); 2846 2847 if(spxSense() == MINIMIZE) 2848 { 2849 dualrows.create(0, R(-infinity), obj(i)); 2850 dualcols.add(upper(i), R(-infinity), col, 0.0); 2851 } 2852 else 2853 { 2854 dualrows.create(0, obj(i), R(infinity)); 2855 dualcols.add(upper(i), 0.0, col, R(infinity)); 2856 } 2857 2858 col.clear(); 2859 2860 numVarBoundCols++; 2861 } 2862 else if(isZero(upper(i), 2863 this->tolerances()->epsilon())) // variable bounded between lower(i) and 0 2864 { 2865 col.add(numAddedRows, 1.0); 2866 2867 if(spxSense() == MINIMIZE) 2868 { 2869 dualrows.create(0, obj(i), R(infinity)); 2870 dualcols.add(lower(i), 0.0, col, R(infinity)); 2871 } 2872 else 2873 { 2874 dualrows.create(0, R(-infinity), obj(i)); 2875 dualcols.add(lower(i), R(-infinity), col, 0.0); 2876 } 2877 2878 col.clear(); 2879 2880 numVarBoundCols++; 2881 } 2882 else // variable bounded between lower(i) and upper(i) 2883 { 2884 dualrows.create(0, obj(i), obj(i)); 2885 2886 col.add(numAddedRows, 1.0); 2887 2888 if(spxSense() == MINIMIZE) 2889 { 2890 dualcols.add(lower(i), 0.0, col, R(infinity)); 2891 dualcols.add(upper(i), R(-infinity), col, 0.0); 2892 } 2893 else 2894 { 2895 dualcols.add(lower(i), R(-infinity), col, 0.0); 2896 dualcols.add(upper(i), 0.0, col, R(infinity)); 2897 } 2898 2899 col.clear(); 2900 2901 numVarBoundCols += 2; 2902 } 2903 2904 numAddedRows++; 2905 } 2906 else 2907 { 2908 assert(lower(i) == upper(i)); 2909 2910 dualrows.create(0, obj(i), obj(i)); 2911 2912 col.add(numAddedRows, 1.0); 2913 dualcols.add(lower(i), 0, col, R(infinity)); 2914 dualcols.add(lower(i), R(-infinity), col, 0); 2915 col.clear(); 2916 2917 numVarBoundCols += 2; 2918 numAddedRows++; 2919 } 2920 } 2921 2922 // adding the empty rows to the dual LP 2923 dualLP.addRows(dualrows); 2924 2925 // setting the dual row ids for the related primal cols. 2926 // this assumes that the rows are added in sequential order. 2927 for(int i = 0; i < primalcolsidx; i++) 2928 dualRowIds[i] = dualLP.rId(i); 2929 2930 (*nprimalcols) = primalcolsidx; 2931 (*ndualrows) = primalcolsidx; 2932 2933 // iterating over each of the rows to create dual columns 2934 for(int i = 0; i < nRows(); ++i) 2935 { 2936 // checking the type of the row 2937 switch(rowType(i)) 2938 { 2939 case LPRowBase<R>::RANGE: // range constraint, requires the addition of two dual variables 2940 assert(lhs(i) > R(-infinity)); 2941 assert(rhs(i) < R(infinity)); 2942 2943 if(spxSense() == MINIMIZE) 2944 { 2945 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2946 primalrowsidx++; 2947 dualcols.add(lhs(i), 0.0, rowVector(i), R(infinity)); 2948 2949 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2950 primalrowsidx++; 2951 dualcols.add(rhs(i), R(-infinity), rowVector(i), 0.0); 2952 } 2953 else 2954 { 2955 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2956 primalrowsidx++; 2957 dualcols.add(lhs(i), R(-infinity), rowVector(i), 0.0); 2958 2959 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2960 primalrowsidx++; 2961 dualcols.add(rhs(i), 0.0, rowVector(i), R(infinity)); 2962 } 2963 2964 break; 2965 2966 case LPRowBase<R>::GREATER_EQUAL: // >= constraint 2967 assert(lhs(i) > R(-infinity)); 2968 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2969 primalrowsidx++; 2970 2971 if(spxSense() == MINIMIZE) 2972 dualcols.add(lhs(i), 0.0, rowVector(i), R(infinity)); 2973 else 2974 dualcols.add(lhs(i), R(-infinity), rowVector(i), 0.0); 2975 2976 break; 2977 2978 case LPRowBase<R>::LESS_EQUAL: // <= constriant 2979 assert(rhs(i) < R(infinity)); 2980 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2981 primalrowsidx++; 2982 2983 if(spxSense() == MINIMIZE) 2984 dualcols.add(rhs(i), R(-infinity), rowVector(i), 0.0); 2985 else 2986 dualcols.add(rhs(i), 0.0, rowVector(i), R(infinity)); 2987 2988 break; 2989 2990 case LPRowBase<R>::EQUAL: // Equality constraint 2991 assert(EQ(lhs(i), rhs(i), this->tolerances()->epsilon())); 2992 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row 2993 primalrowsidx++; 2994 dualcols.add(rhs(i), R(-infinity), rowVector(i), R(infinity)); 2995 break; 2996 2997 default: 2998 throw SPxInternalCodeException("XLPFRD01 This should never happen."); 2999 } 3000 } 3001 3002 // adding the filled columns to the dual LP 3003 dualLP.addCols(dualcols); 3004 3005 // setting the dual column ids for the related primal rows. 3006 // this assumes that the columns are added in sequential order. 3007 for(int i = 0; i < primalrowsidx; i++) 3008 dualColIds[i] = dualLP.cId(i + numVarBoundCols); 3009 3010 (*nprimalrows) = primalrowsidx; 3011 (*ndualcols) = primalrowsidx; 3012 } 3013 3014 } // namespace soplex 3015