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_rational.hpp 26 * @brief Saving LPs with Rational 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/rational.h" 39 40 #define SOPLEX_MAX_LINE_WRITE_LEN 65536 ///< maximum length allowed for writing lines 41 42 namespace soplex 43 { 44 template<> inline 45 void SPxLPBase<Rational>::computePrimalActivity(const VectorBase<Rational>& primal, 46 VectorBase<Rational>& activity, const bool unscaled) const 47 { 48 if(primal.dim() != nCols()) 49 { 50 throw SPxInternalCodeException("XSPXLP01 Primal vector for computing row activity has wrong dimension"); 51 } 52 53 if(activity.dim() != nRows()) 54 { 55 throw SPxInternalCodeException("XSPXLP03 Activity vector computing row activity has wrong dimension"); 56 } 57 58 int c; 59 60 for(c = 0; c < nCols() && primal[c] == 0; c++) 61 ; 62 63 if(c >= nCols()) 64 { 65 activity.clear(); 66 return; 67 } 68 69 activity = colVector(c); 70 71 activity *= primal[c]; 72 c++; 73 74 for(; c < nCols(); c++) 75 { 76 if(primal[c] != 0) 77 { 78 activity.multAdd(primal[c], colVector(c)); 79 } 80 } 81 } 82 83 template<> inline 84 void SPxLPBase<Rational>::computeDualActivity(const VectorBase<Rational>& dual, 85 VectorBase<Rational>& activity, const bool unscaled) const 86 { 87 if(dual.dim() != nRows()) 88 { 89 throw SPxInternalCodeException("XSPXLP02 Dual vector for computing dual activity has wrong dimension"); 90 } 91 92 if(activity.dim() != nCols()) 93 { 94 throw SPxInternalCodeException("XSPXLP04 Activity vector computing dual activity has wrong dimension"); 95 } 96 97 int r; 98 99 for(r = 0; r < nRows() && dual[r] == 0; r++) 100 ; 101 102 if(r >= nRows()) 103 { 104 activity.clear(); 105 return; 106 } 107 108 activity = rowVector(r); 109 110 activity *= dual[r]; 111 r++; 112 113 for(; r < nRows(); r++) 114 { 115 if(dual[r] != 0) 116 { 117 activity.multAdd(dual[r], rowVector(r)); 118 } 119 } 120 } 121 122 template<> inline 123 Rational SPxLPBase<Rational>::maxAbsNzo(bool /* unscaled */) const 124 { 125 Rational maxi = Rational(0); 126 127 for(int i = 0; i < nCols(); ++i) 128 { 129 Rational m = colVector(i).maxAbs(); 130 131 if(m > maxi) 132 maxi = m; 133 } 134 135 assert(maxi >= Rational(0)); 136 137 return maxi; 138 } 139 140 template<> inline 141 Rational SPxLPBase<Rational>::minAbsNzo(bool /* unscaled */) const 142 { 143 Rational mini = infinity; 144 145 for(int i = 0; i < nCols(); ++i) 146 { 147 Rational m = colVector(i).minAbs(); 148 149 if(m < mini) 150 mini = m; 151 } 152 153 assert(mini >= Rational(0)); 154 155 return mini; 156 } 157 158 // --------------------------------------------------------------------------------------------------------------------- 159 // Specialization for reading LP format 160 // --------------------------------------------------------------------------------------------------------------------- 161 162 #define SOPLEX_LPF_MAX_LINE_LEN 8192 ///< maximum length of a line (8190 + \\n + \\0) 163 164 /// Read the next number and advance \p pos. 165 /** If only a sign is encountered, the number is assumed to be \c sign * 1. This routine will not catch malformatted 166 * numbers like .e10 ! 167 */ 168 static Rational LPFreadValue(char*& pos, SPxOut* spxout, const int lineno = -1) 169 { 170 assert(LPFisValue(pos)); 171 172 char tmp[SOPLEX_LPF_MAX_LINE_LEN]; 173 const char* s = pos; 174 char* t; 175 Rational value = 1; 176 bool has_digits = false; 177 bool has_emptyexponent = false; 178 bool has_dot = false; 179 bool has_exponent = false; 180 bool has_emptydivisor = false; 181 182 // 1. sign 183 if((*s == '+') || (*s == '-')) 184 s++; 185 186 // 2. Digits before the decimal dot 187 while((*s >= '0') && (*s <= '9')) 188 { 189 has_digits = true; 190 s++; 191 } 192 193 // 3. Decimal dot 194 if(*s == '.') 195 { 196 has_dot = true; 197 s++; 198 199 // 4. If there was a dot, possible digit behind it 200 while((*s >= '0') && (*s <= '9')) 201 { 202 has_digits = true; 203 s++; 204 } 205 } 206 207 // 5. Exponent 208 if(tolower(*s) == 'e') 209 { 210 has_exponent = true; 211 has_emptyexponent = true; 212 s++; 213 214 // 6. Exponent sign 215 if((*s == '+') || (*s == '-')) 216 s++; 217 218 // 7. Exponent digits 219 while((*s >= '0') && (*s <= '9')) 220 { 221 has_emptyexponent = false; 222 s++; 223 } 224 } 225 226 // 8. Division 227 if(*s == '/') 228 { 229 s++; 230 has_emptydivisor = true; 231 232 while((*s >= '0') && (*s <= '9')) 233 { 234 has_emptydivisor = false; 235 s++; 236 } 237 238 if(has_dot || has_exponent || has_emptydivisor || 239 (*s == '.') || (*s == '+') || (*s == '-') || (tolower(*s) == 'e')) 240 { 241 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD03 Warning: In line " << lineno << 242 ": malformed rational value in LP file\n";) 243 } 244 } 245 246 247 assert(s != pos); 248 249 if(has_emptyexponent) 250 { 251 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD01 Warning: In line " << lineno << 252 ": found empty exponent in LP file - check for forbidden variable names with initial 'e' or 'E'\n"); 253 } 254 255 if(!has_digits) 256 value = (*pos == '-') ? -1 : 1; 257 else 258 { 259 for(t = tmp; pos != s; pos++) 260 *t++ = *pos; 261 262 *t = '\0'; 263 264 try 265 { 266 value = ratFromString(tmp); 267 } 268 catch(const std::exception& e) 269 { 270 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD04 Warning: In line " << lineno << 271 ": malformed rational value in LP file\n"); 272 std::cerr << e.what() << '\n'; 273 } 274 } 275 276 pos += s - pos; 277 278 assert(pos == s); 279 280 SPxOut::debug(spxout, "DLPFRD01 LPFreadValue = {}\n", value); 281 282 if(LPFisSpace(*pos)) 283 pos++; 284 285 return value; 286 } 287 288 289 290 /// Read the next column name from the input. 291 /** The name read is looked up and if not found \p emptycol 292 * is added to \p colset. \p pos is advanced behind the name. 293 * @return The Index of the named column. 294 */ 295 static int LPFreadColName(char*& pos, NameSet* colnames, LPColSetBase<Rational>& colset, 296 const LPColBase<Rational>* emptycol, SPxOut* spxout) 297 { 298 assert(LPFisColName(pos)); 299 assert(colnames != 0); 300 301 char name[SOPLEX_LPF_MAX_LINE_LEN]; 302 const char* s = pos; 303 int i; 304 int colidx; 305 306 // These are the characters that are not allowed in a column name. 307 while((strchr("+-.<>= ", *s) == 0) && (*s != '\0')) 308 s++; 309 310 for(i = 0; pos != s; i++, pos++) 311 name[i] = *pos; 312 313 name[i] = '\0'; 314 315 if((colidx = colnames->number(name)) < 0) 316 { 317 // We only add the name if we got an empty column. 318 if(emptycol == 0) 319 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD02 Unknown variable \"" << name << "\" ";) 320 else 321 { 322 colidx = colnames->num(); 323 colnames->add(name); 324 colset.add(*emptycol); 325 } 326 } 327 328 SPxOut::debug(spxout, "DLPFRD03 LPFreadColName [{}] = {}\n", name, colidx); 329 330 if(LPFisSpace(*pos)) 331 pos++; 332 333 return colidx; 334 } 335 336 static Rational LPFreadInfinity(char*& pos) 337 { 338 assert(LPFisInfinity(pos)); 339 340 Rational sense = (*pos == '-') ? -1 : 1; 341 342 (void) LPFhasKeyword(++pos, "inf[inity]"); 343 344 sense *= Rational(infinity); 345 return sense; 346 } 347 348 /// Read LP in "CPLEX LP File Format". 349 /** The specification is taken from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 527. 350 * 351 * This routine should read (most?) valid LP format files. What it will not do, is find all cases where a file is ill 352 * formed. If this happens it may complain and read nothing or read "something". 353 * 354 * Problem: A line ending in '+' or '-' followed by a line starting with a number, will be regarded as an error. 355 * 356 * The reader will accept the keyword INT[egers] as a synonym for GEN[erals] which is an undocumented feature in CPLEX. 357 * 358 * A difference to the CPLEX reader, is that no name for the objective row is required. 359 * 360 * The manual says the maximum allowed line length is 255 characters, but CPLEX does not complain if the lines are 361 * longer. 362 * 363 * @return true if the file was read correctly 364 */ 365 template <> inline 366 bool SPxLPBase<Rational>::readLPF( 367 std::istream& p_input, ///< input stream. 368 NameSet* p_rnames, ///< row names. 369 NameSet* p_cnames, ///< column names. 370 DIdxSet* p_intvars) ///< integer variables. 371 { 372 enum 373 { 374 START, OBJECTIVE, CONSTRAINTS, BOUNDS, INTEGERS, BINARIES 375 } section = START; 376 377 NameSet* rnames; ///< row names. 378 NameSet* cnames; ///< column names. 379 380 LPColSetBase<Rational> cset; ///< the set of columns read. 381 LPRowSetBase<Rational> rset; ///< the set of rows read. 382 LPColBase<Rational> emptycol; ///< reusable empty column. 383 LPRowBase<Rational> row; ///< last assembled row. 384 DSVectorBase<Rational> vec; ///< last assembled vector (from row). 385 386 Rational val = 1; 387 int colidx; 388 int sense = 0; 389 390 int lineno = 0; 391 bool unnamed = true; 392 bool finished = false; 393 bool other; 394 bool have_value = true; 395 int i; 396 int k; 397 int buf_size; 398 int buf_pos; 399 char* buf; 400 char* tmp; 401 char* line; 402 char* s; 403 char* pos; 404 char* pos_old = 0; 405 406 if(p_cnames) 407 cnames = p_cnames; 408 else 409 { 410 cnames = 0; 411 spx_alloc(cnames); 412 cnames = new(cnames) NameSet(); 413 } 414 415 cnames->clear(); 416 417 if(p_rnames) 418 rnames = p_rnames; 419 else 420 { 421 try 422 { 423 rnames = 0; 424 spx_alloc(rnames); 425 rnames = new(rnames) NameSet(); 426 } 427 catch(const SPxMemoryException& x) 428 { 429 if(!p_cnames) 430 { 431 cnames->~NameSet(); 432 spx_free(cnames); 433 } 434 435 throw x; 436 } 437 } 438 439 rnames->clear(); 440 441 SPxLPBase<Rational>::clear(); // clear the LP. 442 443 //-------------------------------------------------------------------------- 444 //--- Main Loop 445 //-------------------------------------------------------------------------- 446 buf_size = SOPLEX_LPF_MAX_LINE_LEN; 447 spx_alloc(buf, buf_size); 448 spx_alloc(tmp, buf_size); 449 spx_alloc(line, buf_size); 450 451 for(;;) 452 { 453 buf_pos = 0; 454 455 while(!p_input.getline(buf + buf_pos, buf_size - buf_pos)) 456 { 457 p_input.clear(); 458 459 if(strlen(buf) == (size_t) buf_size - 1) 460 { 461 buf_pos = buf_size - 1; 462 buf_size = buf_size + SOPLEX_LPF_MAX_LINE_LEN; 463 464 if(buf_size >= INT_MAX) 465 { 466 SPX_MSG_ERROR(std::cerr << "ELPFRD16 Line longer than INT_MAX" << std::endl;) 467 finished = true; 468 break; 469 } 470 471 spx_realloc(buf, buf_size); 472 } 473 else 474 { 475 SPX_MSG_ERROR(std::cerr << "ELPFRD07 No 'End' marker found" << std::endl;) 476 finished = true; 477 break; 478 } 479 } 480 481 if((size_t) buf_size > sizeof(tmp)) 482 { 483 spx_realloc(tmp, buf_size); 484 spx_realloc(line, buf_size); 485 } 486 487 lineno++; 488 i = 0; 489 pos = buf; 490 491 SPxOut::debug(spxout, "DLPFRD08 Reading line {} (pos={})\n", lineno, pos); 492 493 // 1. Remove comments. 494 if(0 != (s = strchr(buf, '\\'))) 495 * s = '\0'; 496 497 // 2. Look for keywords. 498 if(section == START) 499 { 500 if(LPFhasKeyword(pos, "max[imize]")) 501 { 502 changeSense(SPxLPBase<Rational>::MAXIMIZE); 503 section = OBJECTIVE; 504 } 505 else if(LPFhasKeyword(pos, "min[imize]")) 506 { 507 changeSense(SPxLPBase<Rational>::MINIMIZE); 508 section = OBJECTIVE; 509 } 510 } 511 else if(section == OBJECTIVE) 512 { 513 if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") 514 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 515 || LPFhasKeyword(pos, "s[.][ ]t[.]") 516 || LPFhasKeyword(pos, "lazy con[straints]")) 517 { 518 // store objective vector 519 for(int j = vec.size() - 1; j >= 0; --j) 520 cset.maxObj_w(vec.index(j)) = vec.value(j); 521 522 // multiplication with -1 for minimization is done below 523 vec.clear(); 524 have_value = true; 525 val = 1; 526 section = CONSTRAINTS; 527 } 528 } 529 else if(section == CONSTRAINTS && 530 (LPFhasKeyword(pos, "s[ubject][ ]t[o]") 531 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 532 || LPFhasKeyword(pos, "s[.][ ]t[.]"))) 533 { 534 have_value = true; 535 val = 1; 536 } 537 else 538 { 539 if(LPFhasKeyword(pos, "lazy con[straints]")) 540 ; 541 else if(LPFhasKeyword(pos, "bound[s]")) 542 section = BOUNDS; 543 else if(LPFhasKeyword(pos, "bin[ary]")) 544 section = BINARIES; 545 else if(LPFhasKeyword(pos, "bin[aries]")) 546 section = BINARIES; 547 else if(LPFhasKeyword(pos, "gen[erals]")) 548 section = INTEGERS; 549 else if(LPFhasKeyword(pos, "int[egers]")) // this is undocumented 550 section = INTEGERS; 551 else if(LPFhasKeyword(pos, "end")) 552 { 553 finished = true; 554 break; 555 } 556 else if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") // second time 557 || LPFhasKeyword(pos, "s[uch][ ]t[hat]") 558 || LPFhasKeyword(pos, "s[.][ ]t[.]") 559 || LPFhasKeyword(pos, "lazy con[straints]")) 560 { 561 // In principle this has to checked for all keywords above, 562 // otherwise we just ignore any half finished constraint 563 if(have_value) 564 goto syntax_error; 565 566 have_value = true; 567 val = 1; 568 } 569 } 570 571 // 3a. Look for row names in objective and drop it. 572 if(section == OBJECTIVE) 573 LPFhasRowName(pos, 0); 574 575 // 3b. Look for row name in constraint and store it. 576 if(section == CONSTRAINTS) 577 if(LPFhasRowName(pos, rnames)) 578 unnamed = false; 579 580 // 4a. Remove initial spaces. 581 while(LPFisSpace(pos[i])) 582 i++; 583 584 // 4b. remove spaces if they do not appear before the name of a vaiable. 585 for(k = 0; pos[i] != '\0'; i++) 586 if(!LPFisSpace(pos[i]) || LPFisColName(&pos[i + 1])) 587 tmp[k++] = pos[i]; 588 589 tmp[k] = '\0'; 590 591 // 5. Is this an empty line ? 592 if(tmp[0] == '\0') 593 continue; 594 595 // 6. Collapse sequences of '+' and '-'. e.g ++---+ => - 596 for(i = 0, k = 0; tmp[i] != '\0'; i++) 597 { 598 while(((tmp[i] == '+') || (tmp[i] == '-')) && ((tmp[i + 1] == '+') || (tmp[i + 1] == '-'))) 599 { 600 if(tmp[i++] == '-') 601 tmp[i] = (tmp[i] == '-') ? '+' : '-'; 602 } 603 604 line[k++] = tmp[i]; 605 } 606 607 line[k] = '\0'; 608 609 //----------------------------------------------------------------------- 610 //--- Line processing loop 611 //----------------------------------------------------------------------- 612 pos = line; 613 614 SPxOut::debug(spxout, "DLPFRD09 pos= {}\n", pos); 615 616 // 7. We have something left to process. 617 while((pos != 0) && (*pos != '\0')) 618 { 619 // remember our position, so we are sure we make progress. 620 pos_old = pos; 621 622 // now process the sections 623 switch(section) 624 { 625 case OBJECTIVE: 626 if(LPFisValue(pos)) 627 { 628 Rational pre_sign = 1; 629 630 /* Already having here a value could only result from being the first number in a constraint, or a sign 631 * '+' or '-' as last token on the previous line. 632 */ 633 if(have_value) 634 { 635 if(spxAbs(val) != 1) 636 goto syntax_error; 637 638 if(val == -1) 639 pre_sign = val; 640 } 641 642 have_value = true; 643 val = LPFreadValue(pos, spxout, lineno); 644 val *= pre_sign; 645 } 646 647 if(*pos == '\0') 648 continue; 649 650 if(!have_value || !LPFisColName(pos)) 651 goto syntax_error; 652 653 have_value = false; 654 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout); 655 vec.add(colidx, val); 656 break; 657 658 case CONSTRAINTS: 659 if(LPFisValue(pos)) 660 { 661 Rational pre_sign = 1; 662 663 /* Already having here a value could only result from being the first number in a constraint, or a sign 664 * '+' or '-' as last token on the previous line. 665 */ 666 if(have_value) 667 { 668 if(spxAbs(val) != 1) 669 goto syntax_error; 670 671 if(val == -1) 672 pre_sign = val; 673 } 674 675 have_value = true; 676 val = LPFreadValue(pos, spxout, lineno); 677 val *= pre_sign; 678 679 if(sense != 0) 680 { 681 if(sense == '<') 682 { 683 row.setLhs(-infinity); 684 row.setRhs(val); 685 } 686 else if(sense == '>') 687 { 688 row.setLhs(val); 689 row.setRhs(infinity); 690 } 691 else 692 { 693 assert(sense == '='); 694 695 row.setLhs(val); 696 row.setRhs(val); 697 } 698 699 row.setRowVector(vec); 700 rset.add(row); 701 vec.clear(); 702 703 if(!unnamed) 704 unnamed = true; 705 else 706 { 707 char name[16]; 708 spxSnprintf(name, 16, "C%d", rset.num()); 709 rnames->add(name); 710 } 711 712 have_value = true; 713 val = 1; 714 sense = 0; 715 pos = 0; 716 // next line 717 continue; 718 } 719 } 720 721 if(*pos == '\0') 722 continue; 723 724 if(have_value) 725 { 726 if(LPFisColName(pos)) 727 { 728 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout); 729 730 if(val != 0) 731 { 732 // Do we have this index already in the row? 733 int n = vec.pos(colidx); 734 735 // if not, add it 736 if(n < 0) 737 vec.add(colidx, val); 738 // if yes, add them up and remove the element if it amounts to zero 739 else 740 { 741 assert(vec.index(n) == colidx); 742 743 val += vec.value(n); 744 745 if(val == 0) 746 vec.remove(n); 747 else 748 vec.value(n) = val; 749 750 assert(cnames->has(colidx)); 751 752 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD10 Duplicate index " 753 << (*cnames)[colidx] 754 << " in line " << lineno 755 << std::endl;) 756 } 757 } 758 759 have_value = false; 760 } 761 else 762 { 763 // We have a row like c1: <= 5 with no variables. We can not handle 10 <= 5; issue a syntax error. 764 if(val != 1) 765 goto syntax_error; 766 767 // If the next thing is not the sense we give up also. 768 if(!LPFisSense(pos)) 769 goto syntax_error; 770 771 have_value = false; 772 } 773 } 774 775 assert(!have_value); 776 777 if(LPFisSense(pos)) 778 sense = LPFreadSense(pos); 779 780 break; 781 782 case BOUNDS: 783 other = false; 784 sense = 0; 785 786 if(LPFisValue(pos)) 787 { 788 val = LPFisInfinity(pos) ? LPFreadInfinity(pos) : LPFreadValue(pos, spxout, lineno); 789 790 if(!LPFisSense(pos)) 791 goto syntax_error; 792 793 sense = LPFreadSense(pos); 794 other = true; 795 } 796 797 if(!LPFisColName(pos)) 798 goto syntax_error; 799 800 if((colidx = LPFreadColName(pos, cnames, cset, 0, spxout)) < 0) 801 { 802 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD11 in Bounds section line " 803 << lineno << " ignored" << std::endl;) 804 *pos = '\0'; 805 continue; 806 } 807 808 if(sense) 809 { 810 if(sense == '<') 811 cset.lower_w(colidx) = val; 812 else if(sense == '>') 813 cset.upper_w(colidx) = val; 814 else 815 { 816 assert(sense == '='); 817 cset.lower_w(colidx) = val; 818 cset.upper_w(colidx) = val; 819 } 820 } 821 822 if(LPFisFree(pos)) 823 { 824 cset.lower_w(colidx) = -infinity; 825 cset.upper_w(colidx) = infinity; 826 other = true; 827 pos += 4; // set position after the word "free" 828 } 829 else if(LPFisSense(pos)) 830 { 831 sense = LPFreadSense(pos); 832 other = true; 833 834 if(!LPFisValue(pos)) 835 goto syntax_error; 836 837 val = LPFisInfinity(pos) ? LPFreadInfinity(pos) : LPFreadValue(pos, spxout, lineno); 838 839 if(sense == '<') 840 cset.upper_w(colidx) = val; 841 else if(sense == '>') 842 cset.lower_w(colidx) = val; 843 else 844 { 845 assert(sense == '='); 846 cset.lower_w(colidx) = val; 847 cset.upper_w(colidx) = val; 848 } 849 } 850 851 /* Do we have only a single column name in the input line? We could ignore this savely, but it is probably 852 * a sign of some other error. 853 */ 854 if(!other) 855 goto syntax_error; 856 857 break; 858 859 case BINARIES: 860 case INTEGERS: 861 if((colidx = LPFreadColName(pos, cnames, cset, 0, spxout)) < 0) 862 { 863 SPX_MSG_WARNING((*this->spxout), 864 (*this->spxout) << "WLPFRD12 in Binary/General section line " << lineno 865 << " ignored" << std::endl;) 866 } 867 else 868 { 869 if(section == BINARIES) 870 { 871 if(cset.lower(colidx) < 0) 872 { 873 cset.lower_w(colidx) = 0; 874 } 875 876 if(cset.upper(colidx) > 1) 877 { 878 cset.upper_w(colidx) = 1; 879 } 880 } 881 882 if(p_intvars != 0) 883 p_intvars->addIdx(colidx); 884 } 885 886 break; 887 888 case START: 889 SPX_MSG_ERROR(std::cerr << "ELPFRD13 This seems to be no LP format file" << std::endl;) 890 goto syntax_error; 891 892 default: 893 throw SPxInternalCodeException("XLPFRD01 This should never happen."); 894 } 895 896 if(pos == pos_old) 897 goto syntax_error; 898 } 899 } 900 901 assert(isConsistent()); 902 903 addCols(cset); 904 assert(isConsistent()); 905 906 addRows(rset); 907 assert(isConsistent()); 908 909 syntax_error: 910 911 if(finished) 912 { 913 SPX_MSG_INFO2((*this->spxout), (*this->spxout) << "Finished reading " << lineno << " lines" << 914 std::endl;) 915 } 916 else 917 SPX_MSG_ERROR(std::cerr << "ELPFRD15 Syntax error in line " << lineno << std::endl;) 918 919 if(p_cnames == 0) 920 spx_free(cnames); 921 922 if(p_rnames == 0) 923 spx_free(rnames); 924 925 return finished; 926 } 927 928 /// Process ROWS section. 929 static void MPSreadRows(MPSInput& mps, LPRowSetBase<Rational>& rset, NameSet& rnames, 930 SPxOut* spxout) 931 { 932 LPRowBase<Rational> row; 933 934 while(mps.readLine()) 935 { 936 if(mps.field0() != 0) 937 { 938 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD02 Objective name : " << mps.objName() << std::endl;) 939 940 if(strcmp(mps.field0(), "COLUMNS")) 941 break; 942 943 mps.setSection(MPSInput::COLUMNS); 944 945 return; 946 } 947 948 if(*mps.field1() == 'N') 949 { 950 if(*mps.objName() == '\0') 951 mps.setObjName(mps.field2()); 952 } 953 else 954 { 955 if(rnames.has(mps.field2())) 956 break; 957 958 rnames.add(mps.field2()); 959 960 switch(*mps.field1()) 961 { 962 case 'G': 963 row.setLhs(0); 964 row.setRhs(infinity); 965 break; 966 967 case 'E': 968 row.setLhs(0); 969 row.setRhs(0); 970 break; 971 972 case 'L': 973 row.setLhs(-infinity); 974 row.setRhs(0); 975 break; 976 977 default: 978 mps.syntaxError(); 979 return; 980 } 981 982 rset.add(row); 983 } 984 985 assert((*mps.field1() == 'N') || (rnames.number(mps.field2()) == rset.num() - 1)); 986 } 987 988 mps.syntaxError(); 989 } 990 991 992 993 /// Process COLUMNS section. 994 static void MPSreadCols(MPSInput& mps, const LPRowSetBase<Rational>& rset, const NameSet& rnames, 995 LPColSetBase<Rational>& cset, NameSet& cnames, DIdxSet* intvars, SPxOut* spxout) 996 { 997 Rational val; 998 int idx; 999 char colname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1000 LPColBase<Rational> col(rset.num()); 1001 DSVectorBase<Rational> vec; 1002 1003 col.setObj(0); 1004 vec.clear(); 1005 1006 while(mps.readLine()) 1007 { 1008 if(mps.field0() != 0) 1009 { 1010 if(strcmp(mps.field0(), "RHS")) 1011 break; 1012 1013 if(colname[0] != '\0') 1014 { 1015 col.setColVector(vec); 1016 cset.add(col); 1017 } 1018 1019 mps.setSection(MPSInput::RHS); 1020 1021 return; 1022 } 1023 1024 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1025 break; 1026 1027 // new column? 1028 if(strcmp(colname, mps.field1())) 1029 { 1030 // first column? 1031 if(colname[0] != '\0') 1032 { 1033 col.setColVector(vec); 1034 cset.add(col); 1035 } 1036 1037 // save copy of string (make sure string ends with \0) 1038 spxSnprintf(colname, MPSInput::MAX_LINE_LEN - 1, "%s", mps.field1()); 1039 colname[MPSInput::MAX_LINE_LEN - 1] = '\0'; 1040 1041 int ncnames = cnames.size(); 1042 cnames.add(colname); 1043 1044 // check whether the new name is unique wrt previous column names 1045 if(cnames.size() <= ncnames) 1046 { 1047 SPX_MSG_ERROR(std::cerr << "ERROR in COLUMNS: duplicate column name or not column-wise ordering" << 1048 std::endl;) 1049 break; 1050 } 1051 1052 vec.clear(); 1053 col.setObj(0); 1054 col.setLower(0); 1055 col.setUpper(infinity); 1056 1057 if(mps.isInteger()) 1058 { 1059 assert(cnames.number(colname) == cset.num()); 1060 1061 if(intvars != 0) 1062 intvars->addIdx(cnames.number(colname)); 1063 1064 // for Integer variable the default bounds are 0/1 1065 col.setUpper(1); 1066 } 1067 } 1068 1069 try 1070 { 1071 val = ratFromString(mps.field3()); 1072 } 1073 catch(const std::exception& e) 1074 { 1075 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD01 Warning: malformed rational value in MPS file\n"); 1076 std::cerr << e.what() << '\n'; 1077 } 1078 1079 if(!strcmp(mps.field2(), mps.objName())) 1080 col.setObj(val); 1081 else 1082 { 1083 if((idx = rnames.number(mps.field2())) < 0) 1084 mps.entryIgnored("Column", mps.field1(), "row", mps.field2()); 1085 else if(val != 0) 1086 vec.add(idx, val); 1087 } 1088 1089 if(mps.field5() != 0) 1090 { 1091 assert(mps.field4() != 0); 1092 1093 try 1094 { 1095 val = ratFromString(mps.field5()); 1096 } 1097 catch(const std::exception& e) 1098 { 1099 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD02 Warning: malformed rational value in MPS file\n"); 1100 std::cerr << e.what() << '\n'; 1101 } 1102 1103 if(!strcmp(mps.field4(), mps.objName())) 1104 col.setObj(val); 1105 else 1106 { 1107 if((idx = rnames.number(mps.field4())) < 0) 1108 mps.entryIgnored("Column", mps.field1(), "row", mps.field4()); 1109 else if(val != 0) 1110 vec.add(idx, val); 1111 } 1112 } 1113 } 1114 1115 mps.syntaxError(); 1116 } 1117 1118 1119 1120 /// Process RHS section. 1121 static void MPSreadRhs(MPSInput& mps, LPRowSetBase<Rational>& rset, const NameSet& rnames, 1122 SPxOut* spxout) 1123 { 1124 char rhsname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1125 char addname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1126 int idx; 1127 Rational val; 1128 1129 while(mps.readLine()) 1130 { 1131 if(mps.field0() != 0) 1132 { 1133 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD03 RHS name : " << rhsname << std::endl;); 1134 1135 if(!strcmp(mps.field0(), "RANGES")) 1136 mps.setSection(MPSInput::RANGES); 1137 else if(!strcmp(mps.field0(), "BOUNDS")) 1138 mps.setSection(MPSInput::BOUNDS); 1139 else if(!strcmp(mps.field0(), "ENDATA")) 1140 mps.setSection(MPSInput::ENDATA); 1141 else 1142 break; 1143 1144 return; 1145 } 1146 1147 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0))) 1148 mps.insertName("_RHS_"); 1149 1150 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1151 break; 1152 1153 if(*rhsname == '\0') 1154 spxSnprintf(rhsname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1155 1156 if(strcmp(rhsname, mps.field1())) 1157 { 1158 if(strcmp(addname, mps.field1())) 1159 { 1160 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN); 1161 spxSnprintf(addname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1162 SPX_MSG_INFO3((*spxout), (*spxout) << "IMPSRD07 RHS ignored : " << addname << std::endl); 1163 } 1164 } 1165 else 1166 { 1167 if((idx = rnames.number(mps.field2())) < 0) 1168 mps.entryIgnored("RHS", mps.field1(), "row", mps.field2()); 1169 else 1170 { 1171 try 1172 { 1173 val = ratFromString(mps.field3()); 1174 } 1175 catch(const std::exception& e) 1176 { 1177 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD03 Warning: malformed rational value in MPS file\n"); 1178 std::cerr << e.what() << '\n'; 1179 } 1180 1181 // LE or EQ 1182 if(double(rset.rhs(idx)) < double(infinity)) 1183 rset.rhs_w(idx) = val; 1184 1185 // GE or EQ 1186 if(double(rset.lhs(idx)) > double(-infinity)) 1187 rset.lhs_w(idx) = val; 1188 } 1189 1190 if(mps.field5() != 0) 1191 { 1192 if((idx = rnames.number(mps.field4())) < 0) 1193 mps.entryIgnored("RHS", mps.field1(), "row", mps.field4()); 1194 else 1195 { 1196 try 1197 { 1198 val = ratFromString(mps.field5()); 1199 } 1200 catch(const std::exception& e) 1201 { 1202 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD04 Warning: malformed rational value in MPS file\n"); 1203 std::cerr << e.what() << '\n'; 1204 } 1205 1206 // LE or EQ 1207 if(double(rset.rhs(idx)) < double(infinity)) 1208 rset.rhs_w(idx) = val; 1209 1210 // GE or EQ 1211 if(double(rset.lhs(idx)) > double(-infinity)) 1212 rset.lhs_w(idx) = val; 1213 } 1214 } 1215 } 1216 } 1217 1218 mps.syntaxError(); 1219 } 1220 1221 1222 1223 /// Process RANGES section. 1224 static void MPSreadRanges(MPSInput& mps, LPRowSetBase<Rational>& rset, const NameSet& rnames, 1225 SPxOut* spxout) 1226 { 1227 char rngname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1228 int idx; 1229 Rational val; 1230 1231 while(mps.readLine()) 1232 { 1233 if(mps.field0() != 0) 1234 { 1235 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD04 Range name : " << rngname << std::endl;); 1236 1237 if(!strcmp(mps.field0(), "BOUNDS")) 1238 mps.setSection(MPSInput::BOUNDS); 1239 else if(!strcmp(mps.field0(), "ENDATA")) 1240 mps.setSection(MPSInput::ENDATA); 1241 else 1242 break; 1243 1244 return; 1245 } 1246 1247 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0))) 1248 mps.insertName("_RNG_"); 1249 1250 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1251 break; 1252 1253 if(*rngname == '\0') 1254 { 1255 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN); 1256 spxSnprintf(rngname, MPSInput::MAX_LINE_LEN, "%s", mps.field1()); 1257 } 1258 1259 /* The rules are: 1260 * Row Sign LHS RHS 1261 * ---------------------------------------- 1262 * G +/- rhs rhs + |range| 1263 * L +/- rhs - |range| rhs 1264 * E + rhs rhs + range 1265 * E - rhs + range rhs 1266 * ---------------------------------------- 1267 */ 1268 if(!strcmp(rngname, mps.field1())) 1269 { 1270 if((idx = rnames.number(mps.field2())) < 0) 1271 mps.entryIgnored("Range", mps.field1(), "row", mps.field2()); 1272 else 1273 { 1274 try 1275 { 1276 val = ratFromString(mps.field3()); 1277 } 1278 catch(const std::exception& e) 1279 { 1280 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD05 Warning: malformed rational value in MPS file\n"); 1281 std::cerr << e.what() << '\n'; 1282 } 1283 1284 // EQ 1285 if((double(rset.lhs(idx)) > -double(infinity)) && (double(rset.rhs_w(idx)) < double(infinity))) 1286 { 1287 assert(rset.lhs(idx) == rset.rhs(idx)); 1288 1289 if(double(val) >= 0) 1290 rset.rhs_w(idx) += val; 1291 else 1292 rset.lhs_w(idx) += val; 1293 } 1294 else 1295 { 1296 // GE 1297 if(double(rset.lhs(idx)) > -double(infinity)) 1298 { 1299 rset.rhs_w(idx) = rset.lhs(idx); 1300 rset.rhs_w(idx) += spxAbs(val); 1301 } 1302 // LE 1303 else 1304 { 1305 rset.lhs_w(idx) = rset.rhs(idx); 1306 rset.lhs_w(idx) -= spxAbs(val); 1307 } 1308 } 1309 } 1310 1311 if(mps.field5() != 0) 1312 { 1313 if((idx = rnames.number(mps.field4())) < 0) 1314 mps.entryIgnored("Range", mps.field1(), "row", mps.field4()); 1315 else 1316 { 1317 try 1318 { 1319 val = ratFromString(mps.field5()); 1320 } 1321 catch(const std::exception& e) 1322 { 1323 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD06 Warning: malformed rational value in MPS file\n"); 1324 std::cerr << e.what() << '\n'; 1325 } 1326 1327 // EQ 1328 if((double(rset.lhs(idx)) > -double(infinity)) && (double(rset.rhs(idx)) < double(infinity))) 1329 { 1330 assert(rset.lhs(idx) == rset.rhs(idx)); 1331 1332 if(double(val) >= 0) 1333 rset.rhs_w(idx) += val; 1334 else 1335 rset.lhs_w(idx) += val; 1336 } 1337 else 1338 { 1339 // GE 1340 if(double(rset.lhs(idx)) > -double(infinity)) 1341 { 1342 rset.rhs_w(idx) = rset.lhs(idx); 1343 rset.rhs_w(idx) += spxAbs(val); 1344 } 1345 // LE 1346 else 1347 { 1348 rset.lhs_w(idx) = rset.rhs(idx); 1349 rset.lhs_w(idx) -= spxAbs(val); 1350 } 1351 } 1352 } 1353 } 1354 } 1355 } 1356 1357 mps.syntaxError(); 1358 } 1359 1360 1361 1362 /// Process BOUNDS section. 1363 static void MPSreadBounds(MPSInput& mps, LPColSetBase<Rational>& cset, const NameSet& cnames, 1364 DIdxSet* intvars, SPxOut* spxout) 1365 { 1366 DIdxSet oldbinvars; 1367 char bndname[MPSInput::MAX_LINE_LEN] = { '\0' }; 1368 int idx; 1369 Rational val; 1370 1371 while(mps.readLine()) 1372 { 1373 if(mps.field0() != 0) 1374 { 1375 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD05 Bound name : " << bndname << std::endl;) 1376 1377 if(strcmp(mps.field0(), "ENDATA")) 1378 break; 1379 1380 mps.setSection(MPSInput::ENDATA); 1381 1382 return; 1383 } 1384 1385 // Is the value field used ? 1386 if((!strcmp(mps.field1(), "LO")) 1387 || (!strcmp(mps.field1(), "UP")) 1388 || (!strcmp(mps.field1(), "FX")) 1389 || (!strcmp(mps.field1(), "LI")) 1390 || (!strcmp(mps.field1(), "UI"))) 1391 { 1392 if((mps.field3() != 0) && (mps.field4() == 0)) 1393 mps.insertName("_BND_", true); 1394 } 1395 else 1396 { 1397 if((mps.field2() != 0) && (mps.field3() == 0)) 1398 mps.insertName("_BND_", true); 1399 } 1400 1401 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0)) 1402 break; 1403 1404 if(*bndname == '\0') 1405 { 1406 assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN); 1407 spxSnprintf(bndname, MPSInput::MAX_LINE_LEN, "%s", mps.field2()); 1408 } 1409 1410 // Only read the first Bound in section 1411 if(!strcmp(bndname, mps.field2())) 1412 { 1413 if((idx = cnames.number(mps.field3())) < 0) 1414 mps.entryIgnored("column", mps.field3(), "bound", bndname); 1415 else 1416 { 1417 if(mps.field4() == 0) 1418 val = 0; 1419 else if(!strcmp(mps.field4(), "-Inf") || !strcmp(mps.field4(), "-inf")) 1420 val = -infinity; 1421 else if(!strcmp(mps.field4(), "Inf") || !strcmp(mps.field4(), "inf") 1422 || !strcmp(mps.field4(), "+Inf") || !strcmp(mps.field4(), "+inf")) 1423 val = infinity; 1424 else 1425 try 1426 { 1427 val = ratFromString(mps.field4()); 1428 } 1429 catch(const std::exception& e) 1430 { 1431 SPX_MSG_WARNING((*spxout), (*spxout) << "WMPSRD07 Warning: malformed rational value in MPS file\n"); 1432 std::cerr << e.what() << '\n'; 1433 } 1434 1435 // ILOG extension (Integer Bound) 1436 if(mps.field1()[1] == 'I') 1437 { 1438 if(intvars != 0) 1439 intvars->addIdx(idx); 1440 1441 // if the variable has appeared in the MARKER section of the COLUMNS section then its default bounds were 1442 // set to 0,1; the first time it is declared integer we need to change to default bounds 0,infinity 1443 if(oldbinvars.pos(idx) < 0) 1444 { 1445 cset.upper_w(idx) = infinity; 1446 oldbinvars.addIdx(idx); 1447 } 1448 } 1449 1450 switch(*mps.field1()) 1451 { 1452 case 'L': 1453 cset.lower_w(idx) = val; 1454 break; 1455 1456 case 'U': 1457 cset.upper_w(idx) = val; 1458 break; 1459 1460 case 'F': 1461 if(mps.field1()[1] == 'X') 1462 { 1463 cset.lower_w(idx) = val; 1464 cset.upper_w(idx) = val; 1465 } 1466 else 1467 { 1468 cset.lower_w(idx) = -infinity; 1469 cset.upper_w(idx) = infinity; 1470 } 1471 1472 break; 1473 1474 case 'M': 1475 cset.lower_w(idx) = -infinity; 1476 break; 1477 1478 case 'P': 1479 cset.upper_w(idx) = infinity; 1480 break; 1481 1482 // Ilog extension (Binary) 1483 case 'B': 1484 cset.lower_w(idx) = 0; 1485 cset.upper_w(idx) = 1; 1486 1487 if(intvars != 0) 1488 intvars->addIdx(idx); 1489 1490 break; 1491 1492 default: 1493 mps.syntaxError(); 1494 return; 1495 } 1496 } 1497 } 1498 } 1499 1500 mps.syntaxError(); 1501 } 1502 1503 /// Read LP in MPS File Format. 1504 /** 1505 * The specification is taken from the IBM Optimization Library Guide and Reference, online available at 1506 * http://www.software.ibm.com/sos/features/libuser.htm and from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 1507 * 531. 1508 * 1509 * This routine should read all valid MPS format files. What it will not do, is find all cases where a file is ill 1510 * formed. If this happens it may complain and read nothing or read "something". 1511 * 1512 * @return true if the file was read correctly. 1513 */ 1514 #define SOPLEX_INIT_COLS 1000 ///< initialy allocated columns. 1515 #define SOPLEX_INIT_NZOS 5000 ///< initialy allocated non zeros. 1516 template <> inline 1517 bool SPxLPBase<Rational>::readMPS( 1518 std::istream& p_input, ///< input stream. 1519 NameSet* p_rnames, ///< row names. 1520 NameSet* p_cnames, ///< column names. 1521 DIdxSet* p_intvars) ///< integer variables. 1522 { 1523 LPRowSetBase<Rational>& rset = *this; 1524 LPColSetBase<Rational>& cset = *this; 1525 NameSet* rnames; 1526 NameSet* cnames; 1527 1528 if(p_cnames) 1529 cnames = p_cnames; 1530 else 1531 { 1532 cnames = 0; 1533 spx_alloc(cnames); 1534 cnames = new(cnames) NameSet(); 1535 } 1536 1537 cnames->clear(); 1538 1539 if(p_rnames) 1540 rnames = p_rnames; 1541 else 1542 { 1543 try 1544 { 1545 rnames = 0; 1546 spx_alloc(rnames); 1547 rnames = new(rnames) NameSet(); 1548 } 1549 catch(const SPxMemoryException& x) 1550 { 1551 if(!p_cnames) 1552 { 1553 cnames->~NameSet(); 1554 spx_free(cnames); 1555 } 1556 1557 throw x; 1558 } 1559 } 1560 1561 rnames->clear(); 1562 1563 SPxLPBase<Rational>::clear(); // clear the LP. 1564 1565 cset.memRemax(SOPLEX_INIT_NZOS); 1566 cset.reMax(SOPLEX_INIT_COLS); 1567 1568 MPSInput mps(p_input); 1569 1570 MPSreadName(mps, spxout); 1571 1572 if(mps.section() == MPSInput::OBJSEN) 1573 MPSreadObjsen(mps); 1574 1575 if(mps.section() == MPSInput::OBJNAME) 1576 MPSreadObjname(mps); 1577 1578 if(mps.section() == MPSInput::ROWS) 1579 MPSreadRows(mps, rset, *rnames, spxout); 1580 1581 addedRows(rset.num()); 1582 1583 if(mps.section() == MPSInput::COLUMNS) 1584 MPSreadCols(mps, rset, *rnames, cset, *cnames, p_intvars, spxout); 1585 1586 if(mps.section() == MPSInput::RHS) 1587 MPSreadRhs(mps, rset, *rnames, spxout); 1588 1589 if(mps.section() == MPSInput::RANGES) 1590 MPSreadRanges(mps, rset, *rnames, spxout); 1591 1592 if(mps.section() == MPSInput::BOUNDS) 1593 MPSreadBounds(mps, cset, *cnames, p_intvars, spxout); 1594 1595 if(mps.section() != MPSInput::ENDATA) 1596 mps.syntaxError(); 1597 1598 if(mps.hasError()) 1599 clear(); 1600 else 1601 { 1602 changeSense(mps.objSense() == MPSInput::MINIMIZE ? SPxLPBase<Rational>::MINIMIZE : 1603 SPxLPBase<Rational>::MAXIMIZE); 1604 1605 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD06 Objective sense: " << ((mps.objSense() == 1606 MPSInput::MINIMIZE) ? "Minimize\n" : "Maximize\n")); 1607 1608 added2Set( 1609 *(reinterpret_cast<SVSetBase<Rational>*>(static_cast<LPRowSetBase<Rational>*>(this))), 1610 *(reinterpret_cast<SVSetBase<Rational>*>(static_cast<LPColSetBase<Rational>*>(this))), 1611 cset.num()); 1612 addedCols(cset.num()); 1613 1614 assert(isConsistent()); 1615 } 1616 1617 if(p_cnames == 0) 1618 { 1619 cnames->~NameSet(); 1620 spx_free(cnames); 1621 } 1622 1623 if(p_rnames == 0) 1624 { 1625 rnames->~NameSet(); 1626 spx_free(rnames); 1627 } 1628 1629 return !mps.hasError(); 1630 } 1631 1632 1633 1634 // --------------------------------------------------------------------------------------------------------------------- 1635 // Specialization for writing LP format 1636 // --------------------------------------------------------------------------------------------------------------------- 1637 1638 // get the name of a row or construct one 1639 static const char* LPFgetRowName( 1640 const SPxLPBase<Rational>& p_lp, 1641 int p_idx, 1642 const NameSet* p_rnames, 1643 char* p_buf, 1644 int p_num_written_rows 1645 ) 1646 { 1647 assert(p_buf != 0); 1648 assert(p_idx >= 0); 1649 assert(p_idx < p_lp.nRows()); 1650 1651 if(p_rnames != 0) 1652 { 1653 DataKey key = p_lp.rId(p_idx); 1654 1655 if(p_rnames->has(key)) 1656 return (*p_rnames)[key]; 1657 } 1658 1659 spxSnprintf(p_buf, 16, "C%d", p_num_written_rows); 1660 1661 return p_buf; 1662 } 1663 1664 1665 1666 // get the name of a column or construct one 1667 static const char* getColName( 1668 const SPxLPBase<Rational>& p_lp, 1669 int p_idx, 1670 const NameSet* p_cnames, 1671 char* p_buf 1672 ) 1673 { 1674 assert(p_buf != 0); 1675 assert(p_idx >= 0); 1676 assert(p_idx < p_lp.nCols()); 1677 1678 if(p_cnames != 0) 1679 { 1680 DataKey key = p_lp.cId(p_idx); 1681 1682 if(p_cnames->has(key)) 1683 return (*p_cnames)[key]; 1684 } 1685 1686 spxSnprintf(p_buf, 16, "x%d", p_idx); 1687 1688 return p_buf; 1689 } 1690 1691 1692 1693 // write an SVector 1694 #define SOPLEX_NUM_ENTRIES_PER_LINE 5 1695 static void LPFwriteSVector( 1696 const SPxLPBase<Rational>& p_lp, ///< the LP 1697 std::ostream& p_output, ///< output stream 1698 const NameSet* p_cnames, ///< column names 1699 const SVectorBase<Rational>& p_svec, ///< vector to write 1700 SPxOut* spxout ///< out stream 1701 ) 1702 { 1703 1704 char name[16]; 1705 int num_coeffs = 0; 1706 long long pos; 1707 1708 pos = p_output.tellp(); 1709 1710 for(int j = 0; j < p_lp.nCols(); ++j) 1711 { 1712 const Rational coeff = p_svec[j]; 1713 1714 if(coeff == 0) 1715 continue; 1716 1717 if(num_coeffs == 0) 1718 p_output << coeff << " " << getColName(p_lp, j, p_cnames, name); 1719 else 1720 { 1721 // insert a line break every SOPLEX_NUM_ENTRIES_PER_LINE columns or whenever max line length is nearly exceeded 1722 if(num_coeffs == SOPLEX_NUM_ENTRIES_PER_LINE || 1723 (long long)(p_output.tellp()) - pos + (long long)(coeff.str().length() + 100) > 1724 SOPLEX_MAX_LINE_WRITE_LEN) 1725 { 1726 num_coeffs = 0; 1727 p_output << "\n\t"; 1728 1729 if((long long)(p_output.tellp()) - pos > SOPLEX_MAX_LINE_WRITE_LEN) 1730 { 1731 SPX_MSG_WARNING((*spxout), (*spxout) << 1732 "XLPSWR01 Warning: SOPLEX_MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n"); 1733 } 1734 1735 pos = p_output.tellp(); 1736 } 1737 1738 if(coeff < 0) 1739 p_output << " - " << -coeff; 1740 else 1741 p_output << " + " << coeff; 1742 1743 p_output << " " << getColName(p_lp, j, p_cnames, name); 1744 } 1745 1746 ++num_coeffs; 1747 } 1748 } 1749 1750 1751 1752 // write the objective 1753 static void LPFwriteObjective( 1754 const SPxLPBase<Rational>& p_lp, ///< the LP 1755 std::ostream& p_output, ///< output stream 1756 const NameSet* p_cnames, ///< column names 1757 SPxOut* spxout ///< out stream 1758 ) 1759 { 1760 1761 const int sense = p_lp.spxSense(); 1762 1763 p_output << ((sense == SPxLPBase<Rational>::MINIMIZE) ? "Minimize\n" : "Maximize\n"); 1764 p_output << " obj: "; 1765 1766 const VectorBase<Rational>& obj = p_lp.maxObj(); 1767 DSVectorBase<Rational> svec(obj.dim()); 1768 svec.operator = (obj); 1769 svec *= Rational(sense); 1770 LPFwriteSVector(p_lp, p_output, p_cnames, svec, spxout); 1771 p_output << "\n"; 1772 } 1773 1774 1775 1776 // write non-ranged rows 1777 static void LPFwriteRow( 1778 const SPxLPBase<Rational>& p_lp, ///< the LP 1779 std::ostream& p_output, ///< output stream 1780 const NameSet* p_cnames, ///< column names 1781 const SVectorBase<Rational>& p_svec, ///< vector of the row 1782 const Rational& p_lhs, ///< lhs of the row 1783 const Rational& p_rhs, ///< rhs of the row 1784 SPxOut* spxout ///< out stream 1785 ) 1786 { 1787 1788 long long pos; 1789 pos = p_output.tellp(); 1790 1791 LPFwriteSVector(p_lp, p_output, p_cnames, p_svec, spxout); 1792 1793 long long sidelen; 1794 sidelen = (p_lhs == p_rhs 1795 || double(p_lhs) <= double(-infinity)) ? (long long)p_rhs.str().length() 1796 : (long long)p_lhs.str().length(); 1797 1798 // insert a line break if max line length is in danger of being exceeded 1799 if((long long)(p_output.tellp()) - pos + sidelen + (long long)100 > SOPLEX_MAX_LINE_WRITE_LEN) 1800 { 1801 p_output << "\n\t"; 1802 1803 if((long long)(p_output.tellp()) - pos > SOPLEX_MAX_LINE_WRITE_LEN) 1804 { 1805 SPX_MSG_WARNING((*spxout), (*spxout) << 1806 "XLPSWR02 Warning: SOPLEX_MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n"); 1807 } 1808 1809 pos = p_output.tellp(); 1810 } 1811 1812 // write bound value 1813 if(p_lhs == p_rhs) 1814 p_output << " = " << p_rhs; 1815 else if(double(p_lhs) <= double(-infinity)) 1816 p_output << " <= " << p_rhs; 1817 else 1818 { 1819 assert(double(p_rhs) >= double(infinity)); 1820 p_output << " >= " << p_lhs; 1821 } 1822 1823 p_output << "\n"; 1824 1825 if((long long)(p_output.tellp()) - pos > SOPLEX_MAX_LINE_WRITE_LEN) 1826 { 1827 SPX_MSG_WARNING((*spxout), (*spxout) << 1828 "XLPSWR03 Warning: SOPLEX_MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n"); 1829 } 1830 } 1831 1832 1833 1834 // write all rows 1835 static void LPFwriteRows( 1836 const SPxLPBase<Rational>& p_lp, ///< the LP 1837 std::ostream& p_output, ///< output stream 1838 const NameSet* p_rnames, ///< row names 1839 const NameSet* p_cnames, ///< column names 1840 SPxOut* spxout ///< out stream 1841 ) 1842 { 1843 1844 char name[16]; 1845 1846 p_output << "Subject To\n"; 1847 1848 for(int i = 0; i < p_lp.nRows(); ++i) 1849 { 1850 const Rational lhs = p_lp.lhs(i); 1851 const Rational rhs = p_lp.rhs(i); 1852 1853 if(double(lhs) > -double(infinity) && double(rhs) < double(infinity) && lhs != rhs) 1854 { 1855 // ranged row -> write two non-ranged rows 1856 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_1 : "; 1857 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, infinity, spxout); 1858 1859 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_2 : "; 1860 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), -infinity, rhs, spxout); 1861 } 1862 else 1863 { 1864 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << " : "; 1865 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, rhs, spxout); 1866 } 1867 } 1868 } 1869 1870 1871 1872 // write the variable bounds 1873 // (the default bounds 0 <= x <= infinity are not written) 1874 static void LPFwriteBounds( 1875 const SPxLPBase<Rational>& p_lp, ///< the LP to write 1876 std::ostream& p_output, ///< output stream 1877 const NameSet* p_cnames, ///< column names 1878 SPxOut* spxout ///< out stream 1879 ) 1880 { 1881 1882 char name[16]; 1883 long long pos; 1884 1885 pos = p_output.tellp(); 1886 1887 p_output << "Bounds\n"; 1888 1889 for(int j = 0; j < p_lp.nCols(); ++j) 1890 { 1891 const Rational lower = p_lp.lower(j); 1892 const Rational upper = p_lp.upper(j); 1893 1894 if(lower == upper) 1895 { 1896 p_output << " " << getColName(p_lp, j, p_cnames, name) << " = " << upper << '\n'; 1897 } 1898 else if(double(lower) > -double(infinity)) 1899 { 1900 if(double(upper) < double(infinity)) 1901 { 1902 // range bound 1903 if(lower != 0) 1904 p_output << " " << lower << " <= " 1905 << getColName(p_lp, j, p_cnames, name) 1906 << " <= " << upper << '\n'; 1907 else 1908 p_output << " " << getColName(p_lp, j, p_cnames, name) 1909 << " <= " << upper << '\n'; 1910 } 1911 else if(lower != 0) 1912 p_output << " " << lower << " <= " 1913 << getColName(p_lp, j, p_cnames, name) 1914 << '\n'; 1915 } 1916 else if(double(upper) < double(infinity)) 1917 p_output << " -Inf <= " 1918 << getColName(p_lp, j, p_cnames, name) 1919 << " <= " << upper << '\n'; 1920 else 1921 p_output << " " << getColName(p_lp, j, p_cnames, name) 1922 << " free\n"; 1923 1924 // check if max line length exceeded 1925 if((long long)(p_output.tellp()) - pos > SOPLEX_MAX_LINE_WRITE_LEN) 1926 { 1927 SPX_MSG_WARNING((*spxout), (*spxout) << 1928 "XLPSWR04 Warning: SOPLEX_MAX_LINE_WRITE_LEN exceeded when writing LP file\n"); 1929 } 1930 1931 pos = p_output.tellp(); 1932 } 1933 } 1934 1935 1936 1937 // write the generals section 1938 static void LPFwriteGenerals( 1939 const SPxLPBase<Rational>& p_lp, ///< the LP to write 1940 std::ostream& p_output, ///< output stream 1941 const NameSet* p_cnames, ///< column names 1942 const DIdxSet* p_intvars ///< integer variables 1943 ) 1944 { 1945 1946 char name[16]; 1947 1948 if(p_intvars == NULL || p_intvars->size() <= 0) 1949 return; // no integer variables 1950 1951 p_output << "Generals\n"; 1952 1953 for(int j = 0; j < p_lp.nCols(); ++j) 1954 if(p_intvars->pos(j) >= 0) 1955 p_output << " " << getColName(p_lp, j, p_cnames, name) << "\n"; 1956 } 1957 1958 1959 /// Write LP in LP Format. 1960 template <> inline 1961 void SPxLPBase<Rational>::writeLPF( 1962 std::ostream& p_output, ///< output stream 1963 const NameSet* p_rnames, ///< row names 1964 const NameSet* p_cnames, ///< column names 1965 const DIdxSet* p_intvars ///< integer variables 1966 ) const 1967 { 1968 LPFwriteObjective(*this, p_output, p_cnames, spxout); 1969 LPFwriteRows(*this, p_output, p_rnames, p_cnames, spxout); 1970 LPFwriteBounds(*this, p_output, p_cnames, spxout); 1971 LPFwriteGenerals(*this, p_output, p_cnames, p_intvars); 1972 1973 p_output << "End" << std::endl; 1974 } 1975 1976 1977 1978 // --------------------------------------------------------------------------------------------------------------------- 1979 // Specialization for writing MPS format 1980 // --------------------------------------------------------------------------------------------------------------------- 1981 1982 // A problem here. 1983 static void MPSwriteRecord( 1984 std::ostream& os, 1985 const char* indicator, 1986 const char* name, 1987 SPxOut* spxout, 1988 const char* name1 = nullptr, 1989 const Rational value1 = 0, 1990 const char* name2 = nullptr, 1991 const Rational value2 = 0 1992 ) 1993 { 1994 char buf[81]; 1995 long long pos; 1996 pos = os.tellp(); 1997 1998 spxSnprintf(buf, sizeof(buf), " %-2.2s %-8.8s", (indicator == 0) ? "" : indicator, 1999 (name == 0) ? "" : name); 2000 os << buf; 2001 2002 if(name1 != nullptr) 2003 { 2004 spxSnprintf(buf, sizeof(buf), " %-8.8s ", name1); 2005 os << buf << value1; 2006 2007 if(name2 != 0) 2008 { 2009 spxSnprintf(buf, sizeof(buf), " %-8.8s ", name2); 2010 os << buf << value2; 2011 } 2012 } 2013 2014 os << std::endl; 2015 2016 // Warning if line is too long 2017 if((long long)(os.tellp()) - pos > SOPLEX_MAX_LINE_WRITE_LEN) 2018 { 2019 SPX_MSG_WARNING((*spxout), (*spxout) << 2020 "XMPSWR04 Warning: SOPLEX_MAX_LINE_WRITE_LEN exceeded when writing MPS file\n"); 2021 } 2022 } 2023 2024 2025 2026 static Rational MPSgetRHS(Rational left, Rational right) 2027 { 2028 Rational rhsval; 2029 2030 if(double(left) > -double(infinity)) /// This includes ranges 2031 rhsval = left; 2032 else if(double(right) < double(infinity)) 2033 rhsval = right; 2034 else 2035 throw SPxInternalCodeException("XMPSWR01 This should never happen."); 2036 2037 return rhsval; 2038 } 2039 2040 2041 2042 static const char* MPSgetRowName( 2043 const SPxLPBase<Rational>& lp, 2044 int idx, 2045 const NameSet* rnames, 2046 char* buf 2047 ) 2048 { 2049 assert(buf != 0); 2050 assert(idx >= 0); 2051 assert(idx < lp.nRows()); 2052 2053 if(rnames != 0) 2054 { 2055 DataKey key = lp.rId(idx); 2056 2057 if(rnames->has(key)) 2058 return (*rnames)[key]; 2059 } 2060 2061 spxSnprintf(buf, 16, "C%d", idx); 2062 2063 return buf; 2064 } 2065 2066 2067 2068 /// Write LP in MPS format. 2069 /** @note There will always be a BOUNDS section, even if there are no bounds. 2070 */ 2071 template <> inline 2072 void SPxLPBase<Rational>::writeMPS( 2073 std::ostream& p_output, ///< output stream. 2074 const NameSet* p_rnames, ///< row names. 2075 const NameSet* p_cnames, ///< column names. 2076 const DIdxSet* p_intvars ///< integer variables. 2077 ) const 2078 { 2079 2080 const char* indicator; 2081 char name [16]; 2082 char name1[16]; 2083 char name2[16]; 2084 bool has_ranges = false; 2085 int i; 2086 int k; 2087 2088 // --- NAME Section --- 2089 p_output << "NAME MPSDATA" << std::endl; 2090 2091 // --- ROWS Section --- 2092 p_output << "ROWS" << std::endl; 2093 2094 for(i = 0; i < nRows(); i++) 2095 { 2096 if(lhs(i) == rhs(i)) 2097 indicator = "E"; 2098 else if((double(lhs(i)) > -double(infinity)) && (double(rhs(i)) < double(infinity))) 2099 { 2100 indicator = "E"; 2101 has_ranges = true; 2102 } 2103 else if(double(lhs(i)) > -double(infinity)) 2104 indicator = "G"; 2105 else if(double(rhs(i)) < double(infinity)) 2106 indicator = "L"; 2107 else 2108 throw SPxInternalCodeException("XMPSWR02 This should never happen."); 2109 2110 MPSwriteRecord(p_output, indicator, MPSgetRowName(*this, i, p_rnames, name), spxout); 2111 } 2112 2113 MPSwriteRecord(p_output, "N", "MINIMIZE", spxout); 2114 2115 // --- COLUMNS Section --- 2116 p_output << "COLUMNS" << std::endl; 2117 2118 bool has_intvars = (p_intvars != 0) && (p_intvars->size() > 0); 2119 2120 for(int j = 0; j < (has_intvars ? 2 : 1); j++) 2121 { 2122 bool is_intrun = has_intvars && (j == 1); 2123 2124 if(is_intrun) 2125 p_output << " MARK0001 'MARKER' 'INTORG'" << std::endl; 2126 2127 for(i = 0; i < nCols(); i++) 2128 { 2129 bool is_intvar = has_intvars && (p_intvars->pos(i) >= 0); 2130 2131 if((is_intrun && !is_intvar) || (!is_intrun && is_intvar)) 2132 continue; 2133 2134 const SVectorBase<Rational>& col = colVector(i); 2135 int colsize2 = (col.size() / 2) * 2; 2136 2137 assert(colsize2 % 2 == 0); 2138 2139 for(k = 0; k < colsize2; k += 2) 2140 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout, 2141 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k), 2142 MPSgetRowName(*this, col.index(k + 1), p_rnames, name2), col.value(k + 1)); 2143 2144 if(colsize2 != col.size()) 2145 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout, 2146 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k)); 2147 2148 if(maxObj(i) != 0) 2149 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout, "MINIMIZE", -maxObj(i)); 2150 } 2151 2152 if(is_intrun) 2153 p_output << " MARK0001 'MARKER' 'INTEND'" << std::endl; 2154 } 2155 2156 // --- RHS Section --- 2157 p_output << "RHS" << std::endl; 2158 2159 i = 0; 2160 2161 while(i < nRows()) 2162 { 2163 Rational rhsval1 = 0; 2164 Rational rhsval2 = 0; 2165 2166 for(; i < nRows(); i++) 2167 if((rhsval1 = MPSgetRHS(lhs(i), rhs(i))) != 0) 2168 break; 2169 2170 if(i < nRows()) 2171 { 2172 for(k = i + 1; k < nRows(); k++) 2173 { 2174 if((rhsval2 = MPSgetRHS(lhs(k), rhs(k))) != 0) 2175 break; 2176 } 2177 2178 if(k < nRows()) 2179 { 2180 MPSwriteRecord(p_output, 0, "RHS", spxout, MPSgetRowName(*this, i, p_rnames, name1), rhsval1, 2181 MPSgetRowName(*this, k, p_rnames, name2), rhsval2); 2182 } 2183 else 2184 MPSwriteRecord(p_output, 0, "RHS", spxout, MPSgetRowName(*this, i, p_rnames, name1), rhsval1); 2185 2186 i = k + 1; 2187 } 2188 } 2189 2190 // --- RANGES Section --- 2191 if(has_ranges) 2192 { 2193 p_output << "RANGES" << std::endl; 2194 2195 for(i = 0; i < nRows(); i++) 2196 { 2197 if((double(lhs(i)) > -double(infinity)) && (double(rhs(i)) < double(infinity))) 2198 { 2199 Rational range = rhs(i); 2200 range -= lhs(i); 2201 MPSwriteRecord(p_output, "", "RANGE", spxout, MPSgetRowName(*this, i, p_rnames, name1), range); 2202 } 2203 } 2204 } 2205 2206 // --- BOUNDS Section --- 2207 p_output << "BOUNDS" << std::endl; 2208 2209 for(i = 0; i < nCols(); i++) 2210 { 2211 // skip variables that do not appear in the objective function or any constraint 2212 const SVectorBase<Rational>& col = colVector(i); 2213 2214 if(col.size() == 0 && maxObj(i) == 0) 2215 continue; 2216 2217 if(lower(i) == upper(i)) 2218 { 2219 MPSwriteRecord(p_output, "FX", "BOUND", spxout, getColName(*this, i, p_cnames, name1), lower(i)); 2220 continue; 2221 } 2222 2223 if((double(lower(i)) <= double(-infinity)) && (double(upper(i)) >= double(infinity))) 2224 { 2225 MPSwriteRecord(p_output, "FR", "BOUND", spxout, getColName(*this, i, p_cnames, name1)); 2226 continue; 2227 } 2228 2229 if(lower(i) != 0) 2230 { 2231 if(double(lower(i)) > -double(infinity)) 2232 MPSwriteRecord(p_output, "LO", "BOUND", spxout, getColName(*this, i, p_cnames, name1), lower(i)); 2233 else 2234 MPSwriteRecord(p_output, "MI", "BOUND", spxout, getColName(*this, i, p_cnames, name1)); 2235 } 2236 2237 if(has_intvars && (p_intvars->pos(i) >= 0)) 2238 { 2239 // Integer variables have default upper bound 1, but we should write 2240 // it nevertheless since CPLEX seems to assume infinity otherwise. 2241 MPSwriteRecord(p_output, "UP", "BOUND", spxout, getColName(*this, i, p_cnames, name1), upper(i)); 2242 } 2243 else 2244 { 2245 // Continous variables have default upper bound infinity 2246 if(double(upper(i)) < double(infinity)) 2247 MPSwriteRecord(p_output, "UP", "BOUND", spxout, getColName(*this, i, p_cnames, name1), upper(i)); 2248 } 2249 } 2250 2251 // --- ENDATA Section --- 2252 p_output << "ENDATA" << std::endl; 2253 2254 // Output warning when writing a maximisation problem 2255 if(spxSense() == SPxLPBase<Rational>::MAXIMIZE) 2256 { 2257 SPX_MSG_WARNING((*spxout), (*spxout) << 2258 "XMPSWR03 Warning: objective function inverted when writing maximization problem in MPS file format\n"); 2259 } 2260 } 2261 2262 2263 2264 /// Building the dual problem from a given LP 2265 /// @note primalRows must be as large as the number of unranged primal rows + 2 * the number of ranged primal rows. 2266 /// dualCols must have the identical size to the primal rows. 2267 template <> inline 2268 void SPxLPBase<Rational>::buildDualProblem(SPxLPBase<Rational>& dualLP, SPxRowId primalRowIds[], 2269 SPxColId primalColIds[], 2270 SPxRowId dualRowIds[], SPxColId dualColIds[], int* nprimalrows, int* nprimalcols, int* ndualrows, 2271 int* ndualcols) 2272 { 2273 assert(false); 2274 SPX_MSG_ERROR(std::cerr << "Method buildDualProblem() not implemented for Rational\n"); 2275 } 2276 2277 2278 // --------------------------------------------------------------------------------------------------------------------- 2279 // Explicit instantiation 2280 // --------------------------------------------------------------------------------------------------------------------- 2281 template class SPxLPBase < Rational >; 2282 } // namespace soplex 2283