1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-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 SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file reader_lp.c 26 * @ingroup DEFPLUGINS_READER 27 * @brief LP file reader 28 * @author Tobias Achterberg 29 * @author Marc Pfetsch 30 * @author Stefan Heinz 31 * @author Stefan Vigerske 32 * @author Michael Winkler 33 * @author Lars Schewe 34 * 35 * @todo write fixed (non-active) variables, e.g., for transformed problem 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #include "blockmemshell/memory.h" 41 #include <ctype.h> 42 #include "scip/cons_and.h" 43 #include "scip/cons_bounddisjunction.h" 44 #include "scip/cons_nonlinear.h" 45 #include "scip/cons_indicator.h" 46 #include "scip/cons_knapsack.h" 47 #include "scip/cons_linear.h" 48 #include "scip/cons_logicor.h" 49 #include "scip/cons_setppc.h" 50 #include "scip/cons_sos1.h" 51 #include "scip/cons_sos2.h" 52 #include "scip/cons_varbound.h" 53 #include "scip/pub_cons.h" 54 #include "scip/pub_fileio.h" 55 #include "scip/pub_message.h" 56 #include "scip/pub_misc.h" 57 #include "scip/pub_reader.h" 58 #include "scip/pub_var.h" 59 #include "scip/reader_lp.h" 60 #include "scip/scip_cons.h" 61 #include "scip/scip_mem.h" 62 #include "scip/scip_message.h" 63 #include "scip/scip_numerics.h" 64 #include "scip/scip_param.h" 65 #include "scip/scip_prob.h" 66 #include "scip/scip_reader.h" 67 #include "scip/scip_var.h" 68 #include <stdlib.h> 69 #include <string.h> 70 71 #if !defined(_WIN32) && !defined(_WIN64) 72 #include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */ 73 #endif 74 75 76 #define READER_NAME "lpreader" 77 #define READER_DESC "file reader for MIPs in IBM CPLEX's LP file format" 78 #define READER_EXTENSION "lp" 79 80 #define DEFAULT_LINEARIZE_ANDS TRUE /**< Should possible \"and\"-constraints be linearized when writing the lp file? */ 81 #define DEFAULT_AGGRLINEARIZATION_ANDS TRUE /**< Should an aggregated linearization for and constraints be used? */ 82 83 /* 84 * Data structures 85 */ 86 87 #define LP_MAX_LINELEN 65536 88 #define LP_MAX_PUSHEDTOKENS 2 89 #define LP_INIT_COEFSSIZE 8192 90 #define LP_INIT_QUADCOEFSSIZE 16 91 #define LP_MAX_PRINTLEN 561 /**< the maximum length of any line is 560 + '\\0' = 561*/ 92 #define LP_MAX_NAMELEN 256 /**< the maximum length for any name is 255 + '\\0' = 256 */ 93 #define LP_PRINTLEN 100 94 95 96 /** LP reading data */ 97 struct SCIP_ReaderData 98 { 99 SCIP_Bool linearizeands; 100 SCIP_Bool aggrlinearizationands; 101 }; 102 103 104 /** Section in LP File */ 105 enum LpSection 106 { 107 LP_START, LP_OBJECTIVE, LP_CONSTRAINTS, LP_BOUNDS, LP_GENERALS, LP_BINARIES, LP_SEMICONTINUOUS, LP_SOS, LP_END 108 }; 109 typedef enum LpSection LPSECTION; 110 111 enum LpExpType 112 { 113 LP_EXP_NONE, LP_EXP_UNSIGNED, LP_EXP_SIGNED 114 }; 115 typedef enum LpExpType LPEXPTYPE; 116 117 enum LpSense 118 { 119 LP_SENSE_NOTHING, LP_SENSE_LE, LP_SENSE_GE, LP_SENSE_EQ 120 }; 121 typedef enum LpSense LPSENSE; 122 123 /** LP reading data */ 124 struct LpInput 125 { 126 SCIP_FILE* file; 127 char* linebuf; 128 char probname[LP_MAX_LINELEN]; 129 char objname[LP_MAX_LINELEN]; 130 char* token; 131 char* tokenbuf; 132 char* pushedtokens[LP_MAX_PUSHEDTOKENS]; 133 int npushedtokens; 134 int linenumber; 135 int linepos; 136 int linebufsize; 137 LPSECTION section; 138 SCIP_OBJSENSE objsense; 139 SCIP_Bool inlazyconstraints; /**< whether we are currently reading the section for lazy constraints */ 140 SCIP_Bool inusercuts; /**< whether we are currently reading the section for user cuts */ 141 SCIP_Bool initialconss; /**< should model constraints be marked as initial? */ 142 SCIP_Bool dynamicconss; /**< should model constraints be subject to aging? */ 143 SCIP_Bool dynamiccols; /**< should columns be added and removed dynamically to the LP? */ 144 SCIP_Bool dynamicrows; /**< should rows be added and removed dynamically to the LP? */ 145 SCIP_Bool haserror; 146 }; 147 typedef struct LpInput LPINPUT; 148 149 static const char commentchars[] = "\\"; 150 151 152 /* 153 * Local methods (for reading) 154 */ 155 156 /** issues an error message and marks the LP data to have errors */ 157 static 158 void syntaxError( 159 SCIP* scip, /**< SCIP data structure */ 160 LPINPUT* lpinput, /**< LP reading data */ 161 const char* msg /**< error message */ 162 ) 163 { 164 char formatstr[256]; 165 166 assert(lpinput != NULL); 167 168 SCIPerrorMessage("Syntax error in line %d ('%s'): %s \n", lpinput->linenumber, lpinput->token, msg); 169 if( lpinput->linebuf[lpinput->linebufsize - 1] == '\n' ) 170 { 171 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s", lpinput->linebuf); 172 } 173 else 174 { 175 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " input: %s\n", lpinput->linebuf); 176 } 177 (void) SCIPsnprintf(formatstr, 256, " %%%ds\n", lpinput->linepos); 178 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, (const char*)formatstr, "^"); 179 lpinput->section = LP_END; 180 lpinput->haserror = TRUE; 181 } 182 183 /** returns whether a syntax error was detected */ 184 static 185 SCIP_Bool hasError( 186 LPINPUT* lpinput /**< LP reading data */ 187 ) 188 { 189 assert(lpinput != NULL); 190 191 return lpinput->haserror; 192 } 193 194 /** returns whether the given character is a token delimiter */ 195 static 196 SCIP_Bool isDelimChar( 197 char c /**< input character */ 198 ) 199 { 200 switch (c) 201 { 202 case ' ': 203 case '\f': 204 case '\n': 205 case '\r': 206 case '\t': 207 case '\v': 208 case '\0': 209 return TRUE; 210 default: 211 return FALSE; 212 } 213 } 214 215 /** returns whether the given character is a single token */ 216 static 217 SCIP_Bool isTokenChar( 218 char c /**< input character */ 219 ) 220 { 221 switch (c) 222 { 223 case '-': 224 case '+': 225 case ':': 226 case '<': 227 case '>': 228 case '=': 229 case '[': 230 case ']': 231 case '*': 232 case '^': 233 return TRUE; 234 default: 235 return FALSE; 236 } 237 } 238 239 /** returns whether the current character is member of a value string */ 240 static 241 SCIP_Bool isValueChar( 242 char c, /**< input character */ 243 char nextc, /**< next input character */ 244 SCIP_Bool firstchar, /**< is the given character the first char of the token? */ 245 SCIP_Bool* hasdot, /**< pointer to update the dot flag */ 246 LPEXPTYPE* exptype /**< pointer to update the exponent type */ 247 ) 248 { 249 assert(hasdot != NULL); 250 assert(exptype != NULL); 251 252 if( isdigit((unsigned char)c) ) 253 return TRUE; 254 else if( (*exptype == LP_EXP_NONE) && !(*hasdot) && (c == '.') && ( isdigit((unsigned char)nextc) || isspace((unsigned char)nextc) || nextc == 'e' || nextc == 'E') ) 255 { /* note: we allow for numbers like "24311." for which the next character should be a space or exponent sign */ 256 *hasdot = TRUE; 257 return TRUE; 258 } 259 else if( !firstchar && (*exptype == LP_EXP_NONE) && (c == 'e' || c == 'E') ) 260 { 261 if( nextc == '+' || nextc == '-' ) 262 { 263 *exptype = LP_EXP_SIGNED; 264 return TRUE; 265 } 266 else if( isdigit((unsigned char)nextc) ) 267 { 268 *exptype = LP_EXP_UNSIGNED; 269 return TRUE; 270 } 271 } 272 else if( (*exptype == LP_EXP_SIGNED) && (c == '+' || c == '-') ) 273 { 274 *exptype = LP_EXP_UNSIGNED; 275 return TRUE; 276 } 277 278 return FALSE; 279 } 280 281 /** reads the next line from the input file into the line buffer; skips comments; 282 * returns whether a line could be read 283 */ 284 static 285 SCIP_Bool getNextLine( 286 SCIP* scip, /**< SCIP data structure */ 287 LPINPUT* lpinput /**< LP reading data */ 288 ) 289 { 290 int i; 291 292 assert(lpinput != NULL); 293 294 /* read next line */ 295 lpinput->linepos = 0; 296 lpinput->linebuf[lpinput->linebufsize - 2] = '\0'; 297 298 if( SCIPfgets(lpinput->linebuf, lpinput->linebufsize, lpinput->file) == NULL ) 299 { 300 /* clear the line, this is really necessary here! */ 301 BMSclearMemoryArray(lpinput->linebuf, lpinput->linebufsize); 302 303 return FALSE; 304 } 305 306 lpinput->linenumber++; 307 308 /* if line is too long for our buffer reallocate buffer */ 309 while( lpinput->linebuf[lpinput->linebufsize - 2] != '\0' ) 310 { 311 int newsize; 312 313 newsize = SCIPcalcMemGrowSize(scip, lpinput->linebufsize + 1); 314 SCIP_CALL_ABORT( SCIPreallocBlockMemoryArray(scip, &lpinput->linebuf, lpinput->linebufsize, newsize) ); 315 316 lpinput->linebuf[newsize-2] = '\0'; 317 if ( SCIPfgets(lpinput->linebuf + lpinput->linebufsize - 1, newsize - lpinput->linebufsize + 1, lpinput->file) == NULL ) 318 return FALSE; 319 lpinput->linebufsize = newsize; 320 } 321 lpinput->linebuf[lpinput->linebufsize - 1] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */ 322 323 /* skip characters after comment symbol */ 324 for( i = 0; commentchars[i] != '\0'; ++i ) 325 { 326 char* commentstart; 327 328 commentstart = strchr(lpinput->linebuf, commentchars[i]); 329 if( commentstart != NULL ) 330 { 331 *commentstart = '\0'; 332 *(commentstart+1) = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */ 333 334 break; 335 } 336 } 337 338 return TRUE; 339 } 340 341 /** swaps the addresses of two pointers */ 342 static 343 void swapPointers( 344 char** pointer1, /**< first pointer */ 345 char** pointer2 /**< second pointer */ 346 ) 347 { 348 char* tmp; 349 350 tmp = *pointer1; 351 *pointer1 = *pointer2; 352 *pointer2 = tmp; 353 } 354 355 /** reads the next token from the input file into the token buffer; returns whether a token was read */ 356 static 357 SCIP_Bool getNextToken( 358 SCIP* scip, /**< SCIP data structure */ 359 LPINPUT* lpinput /**< LP reading data */ 360 ) 361 { 362 SCIP_Bool hasdot; 363 LPEXPTYPE exptype; 364 char* buf; 365 int tokenlen; 366 367 assert(lpinput != NULL); 368 assert(lpinput->linepos < lpinput->linebufsize); 369 370 /* check the token stack */ 371 if( lpinput->npushedtokens > 0 ) 372 { 373 swapPointers(&lpinput->token, &lpinput->pushedtokens[lpinput->npushedtokens-1]); 374 lpinput->npushedtokens--; 375 376 SCIPdebugMsg(scip, "(line %d) read token again: '%s'\n", lpinput->linenumber, lpinput->token); 377 return TRUE; 378 } 379 380 /* skip delimiters */ 381 buf = lpinput->linebuf; 382 while( isDelimChar(buf[lpinput->linepos]) ) 383 { 384 if( buf[lpinput->linepos] == '\0' ) 385 { 386 if( !getNextLine(scip, lpinput) ) 387 { 388 lpinput->section = LP_END; 389 SCIPdebugMsg(scip, "(line %d) end of file\n", lpinput->linenumber); 390 return FALSE; 391 } 392 assert(lpinput->linepos == 0); 393 /* update buf, because the linebuffer may have been reallocated */ 394 buf = lpinput->linebuf; 395 } 396 else 397 lpinput->linepos++; 398 } 399 assert(lpinput->linepos < lpinput->linebufsize); 400 assert(!isDelimChar(buf[lpinput->linepos])); 401 402 /* check if the token is a value */ 403 hasdot = FALSE; 404 exptype = LP_EXP_NONE; 405 if( isValueChar(buf[lpinput->linepos], buf[lpinput->linepos+1], TRUE, &hasdot, &exptype) ) 406 { 407 /* read value token */ 408 tokenlen = 0; 409 do 410 { 411 assert(tokenlen < LP_MAX_LINELEN); 412 assert(!isDelimChar(buf[lpinput->linepos])); 413 lpinput->token[tokenlen] = buf[lpinput->linepos]; 414 tokenlen++; 415 lpinput->linepos++; 416 } 417 while( isValueChar(buf[lpinput->linepos], buf[lpinput->linepos+1], FALSE, &hasdot, &exptype) ); 418 } 419 else 420 { 421 /* read non-value token */ 422 tokenlen = 0; 423 do 424 { 425 assert(tokenlen < LP_MAX_LINELEN); 426 lpinput->token[tokenlen] = buf[lpinput->linepos]; 427 tokenlen++; 428 lpinput->linepos++; 429 if( tokenlen == 1 && isTokenChar(lpinput->token[0]) ) 430 break; 431 } 432 while( !isDelimChar(buf[lpinput->linepos]) && !isTokenChar(buf[lpinput->linepos]) ); 433 434 /* if the token is a power sign '^', skip a following '2' 435 * if the token is an equation sense '<', '>', or '=', skip a following '=' 436 * if the token is an equality token '=' and the next character is a '<' or '>', replace the token by the inequality sense 437 */ 438 if( tokenlen >= 1 && lpinput->token[tokenlen-1] == '^' && buf[lpinput->linepos] == '2' ) 439 { 440 lpinput->linepos++; 441 } 442 if( tokenlen >= 1 443 && (lpinput->token[tokenlen-1] == '<' || lpinput->token[tokenlen-1] == '>' || lpinput->token[tokenlen-1] == '=') 444 && buf[lpinput->linepos] == '=' ) 445 { 446 lpinput->linepos++; 447 } 448 else if( lpinput->token[tokenlen-1] == '=' && (buf[lpinput->linepos] == '<' || buf[lpinput->linepos] == '>') ) 449 { 450 lpinput->token[tokenlen-1] = buf[lpinput->linepos]; 451 lpinput->linepos++; 452 } 453 } 454 assert(tokenlen < LP_MAX_LINELEN); 455 lpinput->token[tokenlen] = '\0'; 456 457 SCIPdebugMsg(scip, "(line %d) read token: '%s'\n", lpinput->linenumber, lpinput->token); 458 459 return TRUE; 460 } 461 462 /** puts the current token on the token stack, such that it is read at the next call to getNextToken() */ 463 static 464 void pushToken( 465 LPINPUT* lpinput /**< LP reading data */ 466 ) 467 { 468 assert(lpinput != NULL); 469 assert(lpinput->npushedtokens < LP_MAX_PUSHEDTOKENS); 470 471 swapPointers(&lpinput->pushedtokens[lpinput->npushedtokens], &lpinput->token); 472 lpinput->npushedtokens++; 473 } 474 475 /** puts the buffered token on the token stack, such that it is read at the next call to getNextToken() */ 476 static 477 void pushBufferToken( 478 LPINPUT* lpinput /**< LP reading data */ 479 ) 480 { 481 assert(lpinput != NULL); 482 assert(lpinput->npushedtokens < LP_MAX_PUSHEDTOKENS); 483 484 swapPointers(&lpinput->pushedtokens[lpinput->npushedtokens], &lpinput->tokenbuf); 485 lpinput->npushedtokens++; 486 } 487 488 /** swaps the current token with the token buffer */ 489 static 490 void swapTokenBuffer( 491 LPINPUT* lpinput /**< LP reading data */ 492 ) 493 { 494 assert(lpinput != NULL); 495 496 swapPointers(&lpinput->token, &lpinput->tokenbuf); 497 } 498 499 /** checks whether the current token is a section identifier, and if yes, switches to the corresponding section */ 500 static 501 SCIP_Bool isNewSection( 502 SCIP* scip, /**< SCIP data structure */ 503 LPINPUT* lpinput /**< LP reading data */ 504 ) 505 { 506 SCIP_Bool iscolon; 507 size_t len; 508 509 assert(lpinput != NULL); 510 511 /* remember first token by swapping the token buffer */ 512 swapTokenBuffer(lpinput); 513 514 /* look at next token: if this is a ':', the first token is a name and no section keyword */ 515 iscolon = FALSE; 516 if( getNextToken(scip, lpinput) ) 517 { 518 iscolon = (*lpinput->token == ':'); 519 pushToken(lpinput); 520 } 521 522 /* reinstall the previous token by swapping back the token buffer */ 523 swapTokenBuffer(lpinput); 524 525 /* check for ':' */ 526 if( iscolon ) 527 return FALSE; 528 529 len = strlen(lpinput->token); 530 assert(len < LP_MAX_LINELEN); 531 532 /* the section keywords are at least 2 characters up to 8 or exactly 15 characters long */ 533 if( len > 1 && (len < 9 || len == 15) ) 534 { 535 char token[16]; 536 int c = 0; 537 538 while( lpinput->token[c] != '\0' ) 539 { 540 token[c] = toupper(lpinput->token[c]); /*lint !e734*/ 541 ++c; 542 assert(c < 16); 543 } 544 token[c] = '\0'; 545 546 if( (len == 3 && strcmp(token, "MIN") == 0) 547 || (len == 7 && strcmp(token, "MINIMUM") == 0) 548 || (len == 8 && strcmp(token, "MINIMIZE") == 0) ) 549 { 550 SCIPdebugMsg(scip, "(line %d) new section: OBJECTIVE\n", lpinput->linenumber); 551 lpinput->section = LP_OBJECTIVE; 552 lpinput->objsense = SCIP_OBJSENSE_MINIMIZE; 553 return TRUE; 554 } 555 556 if( (len == 3 && strcmp(token, "MAX") == 0) 557 || (len == 7 && strcmp(token, "MAXIMUM") == 0) 558 || (len == 8 && strcmp(token, "MAXIMIZE") == 0) ) 559 { 560 SCIPdebugMsg(scip, "(line %d) new section: OBJECTIVE\n", lpinput->linenumber); 561 lpinput->section = LP_OBJECTIVE; 562 lpinput->objsense = SCIP_OBJSENSE_MAXIMIZE; 563 return TRUE; 564 } 565 566 if( len == 7 && strcmp(token, "SUBJECT") == 0 ) 567 { 568 /* check if the next token is 'TO' */ 569 swapTokenBuffer(lpinput); 570 if( getNextToken(scip, lpinput) ) 571 { 572 if( strcasecmp(lpinput->token, "TO") == 0 ) 573 { 574 SCIPdebugMsg(scip, "(line %d) new section: CONSTRAINTS\n", lpinput->linenumber); 575 lpinput->section = LP_CONSTRAINTS; 576 lpinput->inlazyconstraints = FALSE; 577 lpinput->inusercuts = FALSE; 578 return TRUE; 579 } 580 else 581 pushToken(lpinput); 582 } 583 swapTokenBuffer(lpinput); 584 } 585 586 if( len == 4 && strcmp(token, "SUCH") == 0 ) 587 { 588 /* check if the next token is 'THAT' */ 589 swapTokenBuffer(lpinput); 590 if( getNextToken(scip, lpinput) ) 591 { 592 if( strcasecmp(lpinput->token, "THAT") == 0 ) 593 { 594 SCIPdebugMsg(scip, "(line %d) new section: CONSTRAINTS\n", lpinput->linenumber); 595 lpinput->section = LP_CONSTRAINTS; 596 lpinput->inlazyconstraints = FALSE; 597 lpinput->inusercuts = FALSE; 598 return TRUE; 599 } 600 else 601 pushToken(lpinput); 602 } 603 swapTokenBuffer(lpinput); 604 } 605 606 if( (len == 2 && strcmp(token, "ST") == 0) 607 || (len == 3 && strcmp(token, "ST.") == 0) 608 || (len == 4 && strcmp(token, "S.T.") == 0) ) 609 { 610 SCIPdebugMsg(scip, "(line %d) new section: CONSTRAINTS\n", lpinput->linenumber); 611 lpinput->section = LP_CONSTRAINTS; 612 lpinput->inlazyconstraints = FALSE; 613 lpinput->inusercuts = FALSE; 614 return TRUE; 615 } 616 617 if( len == 4 && strcmp(token, "LAZY") == 0 ) 618 { 619 /* check if the next token is 'CONSTRAINTS' */ 620 swapTokenBuffer(lpinput); 621 if( getNextToken(scip, lpinput) ) 622 { 623 if( strcasecmp(lpinput->token, "CONSTRAINTS") == 0 ) 624 { 625 SCIPdebugMsg(scip, "(line %d) new section: CONSTRAINTS (lazy)\n", lpinput->linenumber); 626 lpinput->section = LP_CONSTRAINTS; 627 lpinput->inlazyconstraints = TRUE; 628 lpinput->inusercuts = FALSE; 629 return TRUE; 630 } 631 else 632 pushToken(lpinput); 633 } 634 swapTokenBuffer(lpinput); 635 } 636 637 if( len == 4 && strcmp(token, "USER") == 0 ) 638 { 639 /* check if the next token is 'CUTS' */ 640 swapTokenBuffer(lpinput); 641 if( getNextToken(scip, lpinput) ) 642 { 643 if( strcasecmp(lpinput->token, "CUTS") == 0 ) 644 { 645 SCIPdebugMsg(scip, "(line %d) new section: CONSTRAINTS (user cuts)\n", lpinput->linenumber); 646 lpinput->section = LP_CONSTRAINTS; 647 lpinput->inlazyconstraints = FALSE; 648 lpinput->inusercuts = TRUE; 649 return TRUE; 650 } 651 else 652 pushToken(lpinput); 653 } 654 swapTokenBuffer(lpinput); 655 } 656 657 if( (len == 5 && strcmp(token, "BOUND") == 0) 658 || (len == 6 && strcmp(token, "BOUNDS") == 0) ) 659 { 660 SCIPdebugMsg(scip, "(line %d) new section: BOUNDS\n", lpinput->linenumber); 661 lpinput->section = LP_BOUNDS; 662 return TRUE; 663 } 664 665 if( (len == 3 && (strcmp(token, "GEN") == 0 || strcmp(token, "INT") == 0)) 666 || (len == 7 && (strcmp(token, "GENERAL") == 0 || strcmp(token, "INTEGER") == 0)) 667 || (len == 8 && (strcmp(token, "GENERALS") == 0 || strcmp(token, "INTEGERS") == 0)) ) 668 { 669 SCIPdebugMsg(scip, "(line %d) new section: GENERALS\n", lpinput->linenumber); 670 lpinput->section = LP_GENERALS; 671 return TRUE; 672 } 673 674 if( (len == 3 && strcmp(token, "BIN") == 0) 675 || (len == 6 && strcmp(token, "BINARY") == 0) 676 || (len == 8 && strcmp(token, "BINARIES") == 0) ) 677 { 678 SCIPdebugMsg(scip, "(line %d) new section: BINARIES\n", lpinput->linenumber); 679 lpinput->section = LP_BINARIES; 680 return TRUE; 681 } 682 683 if( (len == 4 && strcmp(token, "SEMI") == 0) 684 || (len == 5 && strcmp(token, "SEMIS") == 0) 685 || (len == 15 && strcmp(token, "SEMI-CONTINUOUS") == 0) ) 686 { 687 SCIPdebugMsg(scip, "(line %d) new section: SEMICONTINUOUS\n", lpinput->linenumber); 688 lpinput->section = LP_SEMICONTINUOUS; 689 return TRUE; 690 } 691 692 if( len == 3 && strcmp(token, "SOS") == 0 ) 693 { 694 SCIPdebugMsg(scip, "(line %d) new section: SOS\n", lpinput->linenumber); 695 lpinput->section = LP_SOS; 696 return TRUE; 697 } 698 699 if( len == 3 && strcmp(token, "END") == 0 ) 700 { 701 SCIPdebugMsg(scip, "(line %d) new section: END\n", lpinput->linenumber); 702 lpinput->section = LP_END; 703 return TRUE; 704 } 705 } 706 707 return FALSE; 708 } 709 710 /** returns whether the current token is a sign */ 711 static 712 SCIP_Bool isSign( 713 LPINPUT* lpinput, /**< LP reading data */ 714 int* sign /**< pointer to update the sign */ 715 ) 716 { 717 assert(lpinput != NULL); 718 assert(sign != NULL); 719 assert(*sign == +1 || *sign == -1); 720 721 if( lpinput->token[1] == '\0' ) 722 { 723 if( *lpinput->token == '+' ) 724 return TRUE; 725 else if( *lpinput->token == '-' ) 726 { 727 *sign *= -1; 728 return TRUE; 729 } 730 } 731 732 return FALSE; 733 } 734 735 /** returns whether the current token is a value */ 736 static 737 SCIP_Bool isValue( 738 SCIP* scip, /**< SCIP data structure */ 739 LPINPUT* lpinput, /**< LP reading data */ 740 SCIP_Real* value /**< pointer to store the value (unchanged, if token is no value) */ 741 ) 742 { 743 assert(lpinput != NULL); 744 assert(value != NULL); 745 746 if( strcasecmp(lpinput->token, "INFINITY") == 0 || strcasecmp(lpinput->token, "INF") == 0 ) 747 { 748 *value = SCIPinfinity(scip); 749 return TRUE; 750 } 751 else 752 { 753 double val; 754 char* endptr; 755 756 val = strtod(lpinput->token, &endptr); 757 if( endptr != lpinput->token && *endptr == '\0' ) 758 { 759 *value = val; 760 return TRUE; 761 } 762 } 763 764 return FALSE; 765 } 766 767 /** returns whether the current token is an equation sense */ 768 static 769 SCIP_Bool isSense( 770 LPINPUT* lpinput, /**< LP reading data */ 771 LPSENSE* sense /**< pointer to store the equation sense, or NULL */ 772 ) 773 { 774 assert(lpinput != NULL); 775 776 if( strcmp(lpinput->token, "<") == 0 ) 777 { 778 if( sense != NULL ) 779 *sense = LP_SENSE_LE; 780 return TRUE; 781 } 782 else if( strcmp(lpinput->token, ">") == 0 ) 783 { 784 if( sense != NULL ) 785 *sense = LP_SENSE_GE; 786 return TRUE; 787 } 788 else if( strcmp(lpinput->token, "=") == 0 ) 789 { 790 if( sense != NULL ) 791 *sense = LP_SENSE_EQ; 792 return TRUE; 793 } 794 795 return FALSE; 796 } 797 798 /** returns the variable with the given name, or creates a new variable if it does not exist */ 799 static 800 SCIP_RETCODE getVariable( 801 SCIP* scip, /**< SCIP data structure */ 802 char* name, /**< name of the variable */ 803 SCIP_VAR** var, /**< pointer to store the variable */ 804 SCIP_Bool* created /**< pointer to store whether a new variable was created, or NULL */ 805 ) 806 { 807 assert(name != NULL); 808 assert(var != NULL); 809 810 *var = SCIPfindVar(scip, name); 811 if( *var == NULL ) 812 { 813 SCIP_VAR* newvar; 814 SCIP_Bool dynamiccols; 815 SCIP_Bool initial; 816 SCIP_Bool removable; 817 818 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &dynamiccols) ); 819 initial = !dynamiccols; 820 removable = dynamiccols; 821 822 /* create new variable of the given name */ 823 SCIPdebugMsg(scip, "creating new variable: <%s>\n", name); 824 SCIP_CALL( SCIPcreateVar(scip, &newvar, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS, 825 initial, removable, NULL, NULL, NULL, NULL, NULL) ); 826 SCIP_CALL( SCIPaddVar(scip, newvar) ); 827 *var = newvar; 828 829 /* because the variable was added to the problem, it is captured by SCIP and we can safely release it right now 830 * without making the returned *var invalid 831 */ 832 SCIP_CALL( SCIPreleaseVar(scip, &newvar) ); 833 834 if( created != NULL ) 835 *created = TRUE; 836 } 837 else if( created != NULL ) 838 *created = FALSE; 839 840 return SCIP_OKAY; 841 } 842 843 /** reads the header of the file */ 844 static 845 SCIP_RETCODE readStart( 846 SCIP* scip, /**< SCIP data structure */ 847 LPINPUT* lpinput /**< LP reading data */ 848 ) 849 { 850 assert(lpinput != NULL); 851 852 /* everything before first section is treated as comment */ 853 do 854 { 855 /* get token */ 856 if( !getNextToken(scip, lpinput) ) 857 return SCIP_OKAY; 858 } 859 while( !isNewSection(scip, lpinput) ); 860 861 return SCIP_OKAY; 862 } 863 864 /** reads an objective or constraint with name and coefficients */ 865 static 866 SCIP_RETCODE readCoefficients( 867 SCIP* scip, /**< SCIP data structure */ 868 LPINPUT* lpinput, /**< LP reading data */ 869 SCIP_Bool isobjective, /**< indicates whether we are currently reading the coefficients of the objective */ 870 char* name, /**< pointer to store the name of the line; must be at least of size 871 * LP_MAX_LINELEN */ 872 int* coefssize, /**< size of vars and coefs arrays */ 873 SCIP_VAR*** vars, /**< pointer to store the array with variables (must be freed by caller) */ 874 SCIP_Real** coefs, /**< pointer to store the array with coefficients (must be freed by caller) */ 875 int* ncoefs, /**< pointer to store the number of coefficients */ 876 int* quadcoefssize, /**< size of quadvars1, quadvars2, quadcoefs arrays */ 877 SCIP_VAR*** quadvars1, /**< pointer to store the array with first variables in quadratic terms (must be freed by caller) */ 878 SCIP_VAR*** quadvars2, /**< pointer to store the array with second variables in quadratic terms (must be freed by caller) */ 879 SCIP_Real** quadcoefs, /**< pointer to store the array with coefficients in quadratic terms (must be freed by caller) */ 880 int* nquadcoefs, /**< pointer to store the number of quadratic coefficients */ 881 SCIP_Real* objoffset, /**< pointer to store an objective offset (or NULL if ! isobjective) */ 882 SCIP_Bool* newsection /**< pointer to store whether a new section was encountered */ 883 ) 884 { 885 SCIP_VAR* var = NULL; 886 SCIP_Bool havesign; 887 SCIP_Bool havevalue; 888 SCIP_Bool haveobjoffset = FALSE; 889 SCIP_Real coef; 890 int coefsign; 891 SCIP_Bool inquadpart; 892 SCIP_VAR* firstquadvar; 893 894 assert(lpinput != NULL); 895 assert(name != NULL); 896 assert(coefssize != NULL); 897 assert(vars != NULL); 898 assert(coefs != NULL); 899 assert(ncoefs != NULL); 900 assert(quadcoefssize != NULL); 901 assert(quadvars1 != NULL); 902 assert(quadvars2 != NULL); 903 assert(quadcoefs != NULL); 904 assert(nquadcoefs != NULL); 905 assert(!isobjective || objoffset != NULL); 906 assert(newsection != NULL); 907 908 *coefssize = 0; 909 *vars = NULL; 910 *coefs = NULL; 911 *quadvars1 = NULL; 912 *quadvars2 = NULL; 913 *quadcoefs = NULL; 914 *name = '\0'; 915 *ncoefs = 0; 916 *quadcoefssize = 0; 917 *nquadcoefs = 0; 918 *newsection = FALSE; 919 inquadpart = FALSE; 920 921 if( isobjective ) 922 { 923 assert(objoffset != NULL); 924 *objoffset = 0.0; 925 } 926 927 /* read the first token, which may be the name of the line */ 928 if( getNextToken(scip, lpinput) ) 929 { 930 /* check if we reached a new section */ 931 if( isNewSection(scip, lpinput) ) 932 { 933 *newsection = TRUE; 934 return SCIP_OKAY; 935 } 936 937 /* remember the token in the token buffer */ 938 swapTokenBuffer(lpinput); 939 940 /* get the next token and check, whether it is a colon */ 941 if( getNextToken(scip, lpinput) ) 942 { 943 if( strcmp(lpinput->token, ":") == 0 ) 944 { 945 /* the second token was a colon: the first token is the line name */ 946 (void)SCIPmemccpy(name, lpinput->tokenbuf, '\0', LP_MAX_LINELEN); 947 948 name[LP_MAX_LINELEN - 1] = '\0'; 949 SCIPdebugMsg(scip, "(line %d) read constraint name: '%s'\n", lpinput->linenumber, name); 950 } 951 else 952 { 953 /* the second token was no colon: push the tokens back onto the token stack and parse them as coefficients */ 954 pushToken(lpinput); 955 pushBufferToken(lpinput); 956 } 957 } 958 else 959 { 960 /* there was only one token left: push it back onto the token stack and parse it as coefficient */ 961 pushBufferToken(lpinput); 962 } 963 } 964 965 /* initialize buffers for storing the coefficients */ 966 *coefssize = LP_INIT_COEFSSIZE; 967 SCIP_CALL( SCIPallocBlockMemoryArray(scip, vars, *coefssize) ); 968 SCIP_CALL( SCIPallocBlockMemoryArray(scip, coefs, *coefssize) ); 969 970 *quadcoefssize = LP_INIT_QUADCOEFSSIZE; 971 SCIP_CALL( SCIPallocBlockMemoryArray(scip, quadvars1, *quadcoefssize) ); 972 SCIP_CALL( SCIPallocBlockMemoryArray(scip, quadvars2, *quadcoefssize) ); 973 SCIP_CALL( SCIPallocBlockMemoryArray(scip, quadcoefs, *quadcoefssize) ); 974 975 /* read the coefficients */ 976 coefsign = +1; 977 coef = 1.0; 978 havesign = FALSE; 979 havevalue = FALSE; 980 firstquadvar = NULL; 981 *ncoefs = 0; 982 *nquadcoefs = 0; 983 while( getNextToken(scip, lpinput) ) 984 { 985 /* check whether we reached a new sign token */ 986 if( lpinput->token[1] == '\0' && ( *lpinput->token == '+' || *lpinput->token == '-' ) ) 987 { 988 /* check whether we found an objective offset */ 989 if( isobjective && havevalue && var == NULL ) 990 { 991 assert( objoffset != NULL ); 992 if( haveobjoffset ) 993 { 994 syntaxError(scip, lpinput, "two objective offsets."); 995 return SCIP_OKAY; 996 } 997 SCIPdebugMsg(scip, "(line %d) read objective offset %g\n", lpinput->linenumber, coefsign * coef); 998 haveobjoffset = TRUE; 999 *objoffset = coefsign * coef; 1000 } 1001 } 1002 1003 /* check if we read a sign */ 1004 if( isSign(lpinput, &coefsign) ) 1005 { 1006 if( havevalue ) 1007 { 1008 syntaxError(scip, lpinput, "sign after value without variable."); 1009 return SCIP_OKAY; 1010 } 1011 1012 SCIPdebugMsg(scip, "(line %d) read coefficient sign: %+d\n", lpinput->linenumber, coefsign); 1013 havesign = TRUE; 1014 continue; 1015 } 1016 1017 /* check if we read a value */ 1018 if( isValue(scip, lpinput, &coef) ) 1019 { 1020 SCIPdebugMsg(scip, "(line %d) read coefficient value: %g with sign %+d\n", lpinput->linenumber, coef, coefsign); 1021 if( havevalue ) 1022 { 1023 syntaxError(scip, lpinput, "two consecutive values."); 1024 return SCIP_OKAY; 1025 } 1026 havevalue = TRUE; 1027 continue; 1028 } 1029 1030 /* check if we reached an equation sense */ 1031 if( isSense(lpinput, NULL) ) 1032 { 1033 if( isobjective ) 1034 { 1035 syntaxError(scip, lpinput, "no sense allowed in objective"); 1036 return SCIP_OKAY; 1037 } 1038 1039 if( havevalue ) 1040 { 1041 syntaxError(scip, lpinput, "no constant values allowed for constraints in lp file format"); 1042 return SCIP_OKAY; 1043 } 1044 1045 if( havesign ) 1046 { 1047 syntaxError(scip, lpinput, "constaint has sign without a variable"); 1048 return SCIP_OKAY; 1049 } 1050 1051 /* put the sense back onto the token stack */ 1052 pushToken(lpinput); 1053 break; 1054 } 1055 1056 /* check if we reached a new section, that will be only allowed when having no current sign and value and if we 1057 * are not in the qudratic part 1058 */ 1059 if( (isobjective || (!havevalue && !havesign)) && !inquadpart && isNewSection(scip, lpinput) ) 1060 { 1061 if( havesign && !havevalue ) 1062 { 1063 SCIPwarningMessage(scip, "skipped single sign %c without value or variable in objective\n", coefsign == 1 ? '+' : '-'); 1064 } 1065 else if( isobjective && havevalue && !SCIPisZero(scip, coef) ) 1066 { 1067 assert( objoffset != NULL ); 1068 /* check whether we found an objective offset */ 1069 if( haveobjoffset ) 1070 { 1071 syntaxError(scip, lpinput, "two objective offsets."); 1072 return SCIP_OKAY; 1073 } 1074 SCIPdebugMsg(scip, "(line %d) read objective offset %g\n", lpinput->linenumber, coefsign * coef); 1075 *objoffset = coefsign * coef; 1076 } 1077 1078 *newsection = TRUE; 1079 return SCIP_OKAY; 1080 } 1081 1082 /* check if we start a quadratic part */ 1083 if( *lpinput->token == '[' ) 1084 { 1085 if( inquadpart ) 1086 { 1087 syntaxError(scip, lpinput, "cannot start quadratic part while already in quadratic part."); 1088 return SCIP_OKAY; 1089 } 1090 if( havesign && coefsign != +1 ) 1091 { 1092 syntaxError(scip, lpinput, "cannot have '-' in front of quadratic part."); 1093 return SCIP_OKAY; 1094 } 1095 if( havevalue ) 1096 { 1097 syntaxError(scip, lpinput, "cannot have value in front of quadratic part."); 1098 return SCIP_OKAY; 1099 } 1100 1101 SCIPdebugMsg(scip, "(line %d) start quadratic part\n", lpinput->linenumber); 1102 inquadpart = TRUE; 1103 continue; 1104 } 1105 1106 /* check if we end a quadratic part */ 1107 if( *lpinput->token == ']' ) 1108 { 1109 if( !inquadpart ) 1110 { 1111 syntaxError(scip, lpinput, "cannot end quadratic part before starting one."); 1112 return SCIP_OKAY; 1113 } 1114 if( havesign || havevalue || firstquadvar != NULL ) 1115 { 1116 if( firstquadvar == NULL ) 1117 { 1118 syntaxError(scip, lpinput, "expected value or first quadratic variable."); 1119 } 1120 else 1121 { 1122 syntaxError(scip, lpinput, "expected second quadratic variable."); 1123 } 1124 return SCIP_OKAY; 1125 } 1126 1127 SCIPdebugMsg(scip, "(line %d) end quadratic part\n", lpinput->linenumber); 1128 inquadpart = FALSE; 1129 1130 if( isobjective ) 1131 { 1132 /* quadratic part in objective has to end with '/2' */ 1133 if( !getNextToken(scip, lpinput) ) 1134 { 1135 syntaxError(scip, lpinput, "expected '/2' or '/ 2' after end of quadratic part in objective."); 1136 return SCIP_OKAY; 1137 } 1138 if( strcmp(lpinput->token, "/2") == 0 ) 1139 { 1140 SCIPdebugMsg(scip, "(line %d) saw '/2' or '/ 2' after quadratic part in objective\n", lpinput->linenumber); 1141 } 1142 else if( *lpinput->token == '/' ) 1143 { 1144 /* maybe it says '/ 2' */ 1145 if( !getNextToken(scip, lpinput) || *lpinput->token != '2' ) 1146 { 1147 syntaxError(scip, lpinput, "expected '/2' or '/ 2' after end of quadratic part in objective."); 1148 return SCIP_OKAY; 1149 } 1150 SCIPdebugMsg(scip, "(line %d) saw '/ 2' after quadratic part in objective\n", lpinput->linenumber); 1151 } 1152 else 1153 { 1154 syntaxError(scip, lpinput, "expected '/2' or '/ 2' after end of quadratic part in objective."); 1155 return SCIP_OKAY; 1156 } 1157 } 1158 1159 continue; 1160 } 1161 1162 /* check if we are in between two quadratic variables */ 1163 if( *lpinput->token == '*' ) 1164 { 1165 if( !inquadpart ) 1166 { 1167 syntaxError(scip, lpinput, "cannot have '*' outside of quadratic part."); 1168 return SCIP_OKAY; 1169 } 1170 if( firstquadvar == NULL ) 1171 { 1172 syntaxError(scip, lpinput, "cannot have '*' before first variable in quadratic term."); 1173 return SCIP_OKAY; 1174 } 1175 1176 continue; 1177 } 1178 1179 /* all but the first coefficient need a sign */ 1180 if( !inquadpart && *ncoefs > 0 && !havesign ) 1181 { 1182 syntaxError(scip, lpinput, "expected sign ('+' or '-') or sense ('<' or '>')."); 1183 return SCIP_OKAY; 1184 } 1185 if( inquadpart && *nquadcoefs > 0 && !havesign ) 1186 { 1187 syntaxError(scip, lpinput, "expected sign ('+' or '-')."); 1188 return SCIP_OKAY; 1189 } 1190 1191 /* check if the last variable should be squared */ 1192 var = NULL; 1193 if( *lpinput->token == '^' ) 1194 { 1195 if( !inquadpart ) 1196 { 1197 syntaxError(scip, lpinput, "cannot have squares ('^2') outside of quadratic part."); 1198 return SCIP_OKAY; 1199 } 1200 if( firstquadvar == NULL ) 1201 { 1202 syntaxError(scip, lpinput, "cannot have square '^2' before variable."); 1203 return SCIP_OKAY; 1204 } 1205 1206 var = firstquadvar; 1207 } 1208 else 1209 { 1210 /* the token is a variable name: get the corresponding variable (or create a new one) */ 1211 SCIP_CALL( getVariable(scip, lpinput->token, &var, NULL) ); 1212 } 1213 1214 if( !inquadpart ) 1215 { 1216 /* insert the linear coefficient */ 1217 SCIPdebugMsg(scip, "(line %d) read linear coefficient: %+g<%s>\n", lpinput->linenumber, coefsign * coef, SCIPvarGetName(var)); 1218 if( !SCIPisZero(scip, coef) ) 1219 { 1220 /* resize the vars and coefs array if needed */ 1221 if( *ncoefs >= *coefssize ) 1222 { 1223 int oldcoefssize; 1224 oldcoefssize = *coefssize; 1225 *coefssize *= 2; 1226 *coefssize = MAX(*coefssize, (*ncoefs)+1); 1227 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, vars, oldcoefssize, *coefssize) ); 1228 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, coefs, oldcoefssize, *coefssize) ); 1229 } 1230 assert(*ncoefs < *coefssize); 1231 1232 /* add coefficient */ 1233 (*vars)[*ncoefs] = var; 1234 (*coefs)[*ncoefs] = coefsign * coef; 1235 (*ncoefs)++; 1236 } 1237 } 1238 else 1239 { 1240 if( firstquadvar == NULL ) 1241 { 1242 /* if first quadratic variable read, store it and continue; expect second one in next round */ 1243 firstquadvar = var; 1244 continue; 1245 } 1246 1247 /* insert the quadratic coefficient */ 1248 SCIPdebugMsg(scip, "(line %d) read quadratic coefficient: %+g<%s><%s>\n", lpinput->linenumber, (isobjective ? 0.5 : 1) * coefsign * coef, SCIPvarGetName(firstquadvar), SCIPvarGetName(var)); 1249 if( !SCIPisZero(scip, coef) ) 1250 { 1251 /* resize the vars and coefs array if needed */ 1252 if( *nquadcoefs >= *quadcoefssize ) 1253 { 1254 int oldquadcoefssize; 1255 oldquadcoefssize = *quadcoefssize; 1256 *quadcoefssize *= 2; 1257 *quadcoefssize = MAX(*quadcoefssize, (*nquadcoefs)+1); 1258 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, quadcoefs, oldquadcoefssize, *quadcoefssize) ); 1259 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, quadvars2, oldquadcoefssize, *quadcoefssize) ); 1260 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, quadvars1, oldquadcoefssize, *quadcoefssize) ); 1261 } 1262 assert(*nquadcoefs < *quadcoefssize); 1263 1264 /* add coefficient */ 1265 (*quadvars1)[*nquadcoefs] = firstquadvar; 1266 (*quadvars2)[*nquadcoefs] = var; 1267 (*quadcoefs)[*nquadcoefs] = coefsign * coef; 1268 if( isobjective ) 1269 (*quadcoefs)[*nquadcoefs] /= 2.0; 1270 (*nquadcoefs)++; 1271 } 1272 } 1273 1274 /* reset the flags and coefficient value for the next coefficient */ 1275 coefsign = +1; 1276 coef = 1.0; 1277 havesign = FALSE; 1278 havevalue = FALSE; 1279 firstquadvar = NULL; 1280 } 1281 1282 return SCIP_OKAY; 1283 } 1284 1285 /** reads the objective section */ 1286 static 1287 SCIP_RETCODE readObjective( 1288 SCIP* scip, /**< SCIP data structure */ 1289 LPINPUT* lpinput /**< LP reading data */ 1290 ) 1291 { 1292 char name[LP_MAX_LINELEN]; 1293 SCIP_VAR** vars; 1294 SCIP_Real* coefs; 1295 SCIP_VAR** quadvars1; 1296 SCIP_VAR** quadvars2; 1297 SCIP_Real* quadcoefs; 1298 SCIP_Bool newsection; 1299 SCIP_Real objoffset; 1300 int ncoefs; 1301 int coefssize; 1302 int quadcoefssize; 1303 int nquadcoefs; 1304 1305 assert(lpinput != NULL); 1306 1307 /* read the objective coefficients */ 1308 SCIP_CALL( readCoefficients(scip, lpinput, TRUE, name, &coefssize, &vars, &coefs, &ncoefs, 1309 &quadcoefssize, &quadvars1, &quadvars2, &quadcoefs, &nquadcoefs, &objoffset, &newsection) ); 1310 1311 if( ! SCIPisZero(scip, objoffset) ) 1312 { 1313 SCIP_CALL( SCIPaddOrigObjoffset(scip, objoffset) ); 1314 } 1315 1316 if( !hasError(lpinput) ) 1317 { 1318 int i; 1319 1320 /* set the linear objective values */ 1321 for( i = 0; i < ncoefs; ++i ) 1322 { 1323 assert(vars != NULL); /* for lint */ 1324 assert(coefs != NULL); 1325 SCIP_CALL( SCIPchgVarObj(scip, vars[i], SCIPvarGetObj(vars[i]) + coefs[i]) ); 1326 } 1327 1328 /* insert dummy variable and constraint to represent quadratic part of objective; note that 1329 * reading/{initialconss,dynamicconss,dynamicrows,dynamiccols} apply only to model constraints and variables, not 1330 * to an auxiliary objective constraint (otherwise it can happen that an auxiliary objective variable is loose 1331 * with infinite best bound, triggering the problem that an LP that is unbounded because of loose variables with 1332 * infinite best bound cannot be solved) 1333 */ 1334 if( nquadcoefs > 0 ) 1335 { 1336 SCIP_VAR* quadobjvar; 1337 SCIP_CONS* quadobjcons; 1338 SCIP_Real lhs; 1339 SCIP_Real rhs; 1340 SCIP_Real minusone; 1341 1342 SCIP_CALL( SCIPcreateVar(scip, &quadobjvar, "quadobjvar", -SCIPinfinity(scip), SCIPinfinity(scip), 1.0, 1343 SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1344 SCIP_CALL( SCIPaddVar(scip, quadobjvar) ); 1345 1346 if( lpinput->objsense == SCIP_OBJSENSE_MINIMIZE ) 1347 { 1348 lhs = -SCIPinfinity(scip); 1349 rhs = 0.0; 1350 } 1351 else 1352 { 1353 lhs = 0.0; 1354 rhs = SCIPinfinity(scip); 1355 } 1356 1357 minusone = -1.0; 1358 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &quadobjcons, "quadobj", 1, &quadobjvar, &minusone, nquadcoefs, quadvars1, quadvars2, quadcoefs, lhs, rhs, 1359 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1360 1361 SCIP_CALL( SCIPaddCons(scip, quadobjcons) ); 1362 SCIPdebugMsg(scip, "(line %d) added constraint <%s> to represent quadratic objective: ", lpinput->linenumber, SCIPconsGetName(quadobjcons)); 1363 SCIPdebugPrintCons(scip, quadobjcons, NULL); 1364 1365 SCIP_CALL( SCIPreleaseCons(scip, &quadobjcons) ); 1366 SCIP_CALL( SCIPreleaseVar(scip, &quadobjvar) ); 1367 } 1368 } 1369 1370 /* free memory */ 1371 SCIPfreeBlockMemoryArrayNull(scip, &quadcoefs, quadcoefssize); 1372 SCIPfreeBlockMemoryArrayNull(scip, &quadvars2, quadcoefssize); 1373 SCIPfreeBlockMemoryArrayNull(scip, &quadvars1, quadcoefssize); 1374 SCIPfreeBlockMemoryArrayNull(scip, &vars, coefssize); 1375 SCIPfreeBlockMemoryArrayNull(scip, &coefs, coefssize); 1376 1377 return SCIP_OKAY; /*lint !e438*/ 1378 } 1379 1380 /** create indicator constraint */ 1381 static 1382 SCIP_RETCODE createIndicatorConstraint( 1383 SCIP* scip, /**< SCIP data structure */ 1384 LPINPUT* lpinput, /**< LP reading data */ 1385 const char* name, /**< name of indicator constraint */ 1386 SCIP_VAR* binvar, /**< binary indicator variable */ 1387 SCIP_Real binvalue /**< value of indicator part (0/1) */ 1388 ) 1389 { 1390 char name2[LP_MAX_LINELEN]; 1391 SCIP_VAR** linvars; 1392 SCIP_Real* lincoefs; 1393 SCIP_VAR** quadvars1; 1394 SCIP_VAR** quadvars2; 1395 SCIP_Real* quadcoefs; 1396 SCIP_CONS* cons; 1397 SCIP_RETCODE retcode; 1398 LPSENSE linsense; 1399 SCIP_Real linsidevalue; 1400 SCIP_Real linrhs; 1401 SCIP_Bool newsection; 1402 SCIP_Bool linConsEQ; 1403 SCIP_Bool initial; 1404 SCIP_Bool separate; 1405 SCIP_Bool enforce; 1406 SCIP_Bool check; 1407 SCIP_Bool propagate; 1408 SCIP_Bool local; 1409 SCIP_Bool dynamic; 1410 SCIP_Bool removable; 1411 int lincoefssize; 1412 int quadcoefssize; 1413 int nlincoefs; 1414 int nquadcoefs; 1415 int linsidesign; 1416 int j; 1417 1418 assert( lpinput != NULL ); 1419 assert( binvar != NULL ); 1420 1421 retcode = SCIP_OKAY; 1422 1423 /* check that binvalue is 0 or 1 */ 1424 if( !SCIPisFeasEQ(scip, binvalue, 0.0) && !SCIPisFeasEQ(scip, binvalue, 1.0) ) 1425 { 1426 syntaxError(scip, lpinput, "value for binary variable must be '0' or '1'."); 1427 return SCIP_OKAY; 1428 } 1429 1430 if( SCIPisFeasEQ(scip, binvalue, 0.0) ) 1431 { 1432 SCIP_VAR* negbinvar; 1433 SCIP_Bool infeasible; 1434 1435 /* At this point we force the variable binvar to be binary, since we need the negated variable. We have to check 1436 * later whether the type of the variable specified in the file agrees with this specification. 1437 */ 1438 /* check whether bounds are correct - might already been set if variable is used in another indicator constraint */ 1439 if( SCIPvarGetLbGlobal(binvar) < 0.0 ) 1440 SCIP_CALL( SCIPchgVarLb(scip, binvar, 0.0) ); 1441 if( SCIPvarGetUbGlobal(binvar) > 1.0 ) 1442 SCIP_CALL( SCIPchgVarUb(scip, binvar, 1.0) ); 1443 SCIP_CALL( SCIPchgVarType(scip, binvar, SCIP_VARTYPE_BINARY, &infeasible) ); 1444 /* don't assert feasibility here because the presolver will and should detect a infeasibility */ 1445 1446 SCIP_CALL( SCIPgetNegatedVar(scip, binvar, &negbinvar) ); 1447 binvar = negbinvar; 1448 assert( binvar != NULL ); 1449 } 1450 1451 /* read linear constraint */ 1452 SCIP_CALL( readCoefficients(scip, lpinput, FALSE, name2, &lincoefssize, &linvars, &lincoefs, &nlincoefs, 1453 &quadcoefssize, &quadvars1, &quadvars2, &quadcoefs, &nquadcoefs, NULL, &newsection) ); 1454 1455 if( hasError(lpinput) ) 1456 goto TERMINATE; 1457 if( newsection ) 1458 { 1459 syntaxError(scip, lpinput, "expected constraint."); 1460 goto TERMINATE; 1461 } 1462 if( nquadcoefs > 0 ) 1463 { 1464 /* @todo could introduce auxiliary variable and move quadratic part into quadratic constraint? */ 1465 syntaxError(scip, lpinput, "quadratic indicator constraints not supported."); 1466 goto TERMINATE; 1467 } 1468 if( name2[0] != '\0' ) 1469 { 1470 syntaxError(scip, lpinput, "did not expect name for linear constraint."); 1471 goto TERMINATE; 1472 } 1473 1474 /* read the constraint sense */ 1475 if( !getNextToken(scip, lpinput) ) 1476 { 1477 syntaxError(scip, lpinput, "missing constraint sense."); 1478 goto TERMINATE; 1479 } 1480 if( !isSense(lpinput, &linsense) ) 1481 { 1482 syntaxError(scip, lpinput, "expected constraint sense '<=', '=', or '>='."); 1483 goto TERMINATE; 1484 } 1485 assert(linsense == LP_SENSE_GE || linsense == LP_SENSE_LE || linsense == LP_SENSE_EQ); /*lint !e530*/ 1486 1487 /* read the right hand side */ 1488 linsidesign = +1; 1489 if( !getNextToken(scip, lpinput) ) 1490 { 1491 syntaxError(scip, lpinput, "missing right hand side."); 1492 goto TERMINATE; 1493 } 1494 if( isSign(lpinput, &linsidesign) ) 1495 { 1496 if( !getNextToken(scip, lpinput) ) 1497 { 1498 syntaxError(scip, lpinput, "missing value of right hand side."); 1499 goto TERMINATE; 1500 } 1501 } 1502 if( !isValue(scip, lpinput, &linsidevalue) ) 1503 { 1504 syntaxError(scip, lpinput, "expected value for right hand side."); 1505 goto TERMINATE; 1506 } 1507 linsidevalue *= linsidesign; 1508 1509 /* assign the left and right hand side, depending on the constraint sense */ 1510 linConsEQ = FALSE; 1511 switch( linsense ) /*lint !e530*/ 1512 { 1513 case LP_SENSE_GE: 1514 linrhs = -linsidevalue; 1515 for( j = 0; j < nlincoefs; ++j ) 1516 lincoefs[j] *= -1; 1517 break; 1518 case LP_SENSE_LE: 1519 linrhs = linsidevalue; 1520 break; 1521 case LP_SENSE_EQ: 1522 linConsEQ = TRUE; 1523 linrhs = linsidevalue; 1524 break; 1525 case LP_SENSE_NOTHING: 1526 default: 1527 /* this case cannot occur because it is caught by the syntax check method isSense() above */ 1528 SCIPerrorMessage("invalid constraint sense <%d>\n", linsense); 1529 return SCIP_INVALIDDATA; 1530 } 1531 assert(lincoefs != NULL); 1532 1533 /* create and add the indicator constraint */ 1534 initial = lpinput->initialconss && !lpinput->inlazyconstraints && !lpinput->inusercuts; 1535 separate = TRUE; 1536 enforce = !lpinput->inusercuts; 1537 check = !lpinput->inusercuts; 1538 propagate = TRUE; 1539 local = FALSE; 1540 dynamic = lpinput->dynamicconss; 1541 removable = lpinput->dynamicrows || lpinput->inusercuts; 1542 1543 retcode = SCIPcreateConsIndicator(scip, &cons, name, binvar, nlincoefs, linvars, lincoefs, linrhs, 1544 initial, separate, enforce, check, propagate, local, dynamic, removable, FALSE); 1545 1546 if( retcode != SCIP_OKAY ) 1547 goto TERMINATE; 1548 1549 SCIP_CALL( SCIPaddCons(scip, cons) ); 1550 SCIPdebugMsg(scip, "(line %d) created constraint%s: ", lpinput->linenumber, 1551 lpinput->inlazyconstraints ? " (lazy)" : (lpinput->inusercuts ? " (user cut)" : "")); 1552 SCIPdebugPrintCons(scip, cons, NULL); 1553 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1554 1555 /* create second constraint if it was an equation */ 1556 if( linConsEQ ) 1557 { 1558 char newname[SCIP_MAXSTRLEN]; 1559 1560 (void) SCIPsnprintf(newname, SCIP_MAXSTRLEN, "%s_eqneg", name); 1561 1562 for( j = 0; j < nlincoefs; ++j ) 1563 lincoefs[j] *= -1; 1564 linrhs *= -1; 1565 retcode = SCIPcreateConsIndicator(scip, &cons, newname, binvar, nlincoefs, linvars, lincoefs, linrhs, 1566 initial, separate, enforce, check, propagate, local, dynamic, removable, FALSE); 1567 1568 if( retcode != SCIP_OKAY ) 1569 goto TERMINATE; 1570 1571 SCIP_CALL( SCIPaddCons(scip, cons) ); 1572 SCIPdebugMsg(scip, "(line %d) created constraint%s: ", lpinput->linenumber, 1573 lpinput->inlazyconstraints ? " (lazy)" : (lpinput->inusercuts ? " (user cut)" : "")); 1574 SCIPdebugPrintCons(scip, cons, NULL); 1575 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1576 } 1577 1578 TERMINATE: 1579 /* free memory */ 1580 SCIPfreeBlockMemoryArrayNull(scip, &quadvars1, quadcoefssize); 1581 SCIPfreeBlockMemoryArrayNull(scip, &quadvars2, quadcoefssize); 1582 SCIPfreeBlockMemoryArrayNull(scip, &quadcoefs, quadcoefssize); 1583 SCIPfreeBlockMemoryArrayNull(scip, &lincoefs, lincoefssize); 1584 SCIPfreeBlockMemoryArrayNull(scip, &linvars, lincoefssize); 1585 1586 SCIP_CALL( retcode ); 1587 1588 return SCIP_OKAY; 1589 } 1590 1591 /** reads the constraints section 1592 * 1593 * Read linear and indicator constraints. 1594 * 1595 * The CPLEX manual says that indicator constraints are of the following form: 1596 * 1597 * [constraintname:] binaryvariable = value -> linear constraint 1598 * 1599 * We also accept "<->". 1600 */ 1601 static 1602 SCIP_RETCODE readConstraints( 1603 SCIP* scip, /**< SCIP data structure */ 1604 LPINPUT* lpinput /**< LP reading data */ 1605 ) 1606 { 1607 char name[LP_MAX_LINELEN]; 1608 SCIP_CONS* cons; 1609 SCIP_VAR** vars; 1610 SCIP_Real* coefs; 1611 SCIP_VAR** quadvars1; 1612 SCIP_VAR** quadvars2; 1613 SCIP_Real* quadcoefs; 1614 LPSENSE sense; 1615 SCIP_RETCODE retcode; 1616 SCIP_Real sidevalue; 1617 SCIP_Real lhs; 1618 SCIP_Real rhs; 1619 SCIP_Bool newsection; 1620 SCIP_Bool initial; 1621 SCIP_Bool separate; 1622 SCIP_Bool enforce; 1623 SCIP_Bool check; 1624 SCIP_Bool propagate; 1625 SCIP_Bool local; 1626 SCIP_Bool modifiable; 1627 SCIP_Bool dynamic; 1628 SCIP_Bool removable; 1629 SCIP_Bool isIndicatorCons; 1630 int ncoefs; 1631 int nquadcoefs; 1632 int sidesign; 1633 int quadcoefssize; 1634 int coefssize; 1635 1636 assert(lpinput != NULL); 1637 1638 retcode = SCIP_OKAY; 1639 1640 /* read coefficients */ 1641 SCIP_CALL( readCoefficients(scip, lpinput, FALSE, name, &coefssize, &vars, &coefs, &ncoefs, 1642 &quadcoefssize, &quadvars1, &quadvars2, &quadcoefs, &nquadcoefs, NULL, &newsection) ); 1643 1644 if( hasError(lpinput) ) 1645 goto TERMINATE; 1646 if( newsection ) 1647 { 1648 if( ncoefs > 0 || nquadcoefs > 0 ) 1649 syntaxError(scip, lpinput, "expected constraint sense '<=', '=', or '>='."); 1650 goto TERMINATE; 1651 } 1652 1653 /* read the constraint sense */ 1654 if( !getNextToken(scip, lpinput) ) 1655 { 1656 syntaxError(scip, lpinput, "missing constraint sense."); 1657 goto TERMINATE; 1658 } 1659 if( !isSense(lpinput, &sense) ) 1660 { 1661 syntaxError(scip, lpinput, "expected constraint sense '<=', '=', or '>='."); 1662 goto TERMINATE; 1663 } 1664 assert(sense == LP_SENSE_GE || sense == LP_SENSE_LE || sense == LP_SENSE_EQ); /*lint !e530*/ 1665 1666 /* read the right hand side */ 1667 sidesign = +1; 1668 if( !getNextToken(scip, lpinput) ) 1669 { 1670 syntaxError(scip, lpinput, "missing right hand side."); 1671 goto TERMINATE; 1672 } 1673 if( isSign(lpinput, &sidesign) ) 1674 { 1675 if( !getNextToken(scip, lpinput) ) 1676 { 1677 syntaxError(scip, lpinput, "missing value of right hand side."); 1678 goto TERMINATE; 1679 } 1680 } 1681 if( !isValue(scip, lpinput, &sidevalue) ) 1682 { 1683 syntaxError(scip, lpinput, "expected value as right hand side."); 1684 goto TERMINATE; 1685 } 1686 sidevalue *= sidesign; 1687 1688 /* assign the left and right hand side, depending on the constraint sense */ 1689 switch( sense ) /*lint !e530*/ 1690 { 1691 case LP_SENSE_GE: 1692 lhs = sidevalue; 1693 rhs = SCIPinfinity(scip); 1694 break; 1695 case LP_SENSE_LE: 1696 lhs = -SCIPinfinity(scip); 1697 rhs = sidevalue; 1698 break; 1699 case LP_SENSE_EQ: 1700 lhs = sidevalue; 1701 rhs = sidevalue; 1702 break; 1703 case LP_SENSE_NOTHING: 1704 default: 1705 /* this case cannot occur because it is caught by the syntax check method isSense() above */ 1706 SCIPerrorMessage("invalid constraint sense <%d>.\n", sense); 1707 return SCIP_INVALIDDATA; 1708 } 1709 1710 /* check whether we read the first part of an indicator constraint */ 1711 isIndicatorCons = FALSE; 1712 if ( getNextToken(scip, lpinput) && !isNewSection(scip, lpinput) ) 1713 { 1714 /* check whether we have '<' from a "<->" string */ 1715 if ( *lpinput->token == '<' ) 1716 { 1717 int linepos = lpinput->linepos-1; 1718 1719 /* check next token - cannot be a new section */ 1720 if ( getNextToken(scip, lpinput) ) 1721 { 1722 /* check for "<-" */ 1723 if ( *lpinput->token == '-' ) 1724 { 1725 /* check next token - cannot be a new section */ 1726 if ( getNextToken(scip, lpinput) ) 1727 { 1728 /* check for "<->" */ 1729 if ( *lpinput->token == '>' ) 1730 { 1731 lpinput->linepos = linepos; 1732 (void) SCIPsnprintf(lpinput->token, 2, "<"); 1733 syntaxError(scip, lpinput, 1734 "SCIP does not support equivalence (<->) indicator constraints; consider using the \"->\" form."); 1735 goto TERMINATE; 1736 } 1737 } 1738 } 1739 } 1740 /* reset the lpinput for further usage as we have no indicator constraint */ 1741 lpinput->linepos = linepos; 1742 (void) SCIPsnprintf(lpinput->token, 2, "<"); 1743 } 1744 1745 /* check for "->" */ 1746 if ( *lpinput->token == '-' ) 1747 { 1748 /* remember '-' in token buffer */ 1749 swapTokenBuffer(lpinput); 1750 1751 /* check next token - cannot be a new section */ 1752 if( getNextToken(scip, lpinput) ) 1753 { 1754 /* check for "->" */ 1755 if ( *lpinput->token == '>' ) 1756 isIndicatorCons = TRUE; 1757 else 1758 { 1759 /* push back last token and '-' */ 1760 pushToken(lpinput); 1761 pushBufferToken(lpinput); 1762 } 1763 } 1764 else 1765 pushBufferToken(lpinput); 1766 } 1767 else 1768 pushToken(lpinput); 1769 } 1770 1771 if( !isIndicatorCons ) 1772 { 1773 /* create and add the linear constraint */ 1774 initial = lpinput->initialconss && !lpinput->inlazyconstraints && !lpinput->inusercuts; 1775 separate = TRUE; 1776 enforce = !lpinput->inusercuts; 1777 check = !lpinput->inusercuts; 1778 propagate = TRUE; 1779 local = FALSE; 1780 modifiable = FALSE; 1781 dynamic = lpinput->dynamicconss; 1782 removable = lpinput->dynamicrows || lpinput->inusercuts; 1783 if( nquadcoefs == 0 ) 1784 { 1785 retcode = SCIPcreateConsLinear(scip, &cons, name, ncoefs, vars, coefs, lhs, rhs, 1786 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE); 1787 } 1788 else 1789 { 1790 retcode = SCIPcreateConsQuadraticNonlinear(scip, &cons, name, ncoefs, vars, coefs, 1791 nquadcoefs, quadvars1, quadvars2, quadcoefs, lhs, rhs, 1792 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable); 1793 } 1794 1795 if( retcode != SCIP_OKAY ) 1796 goto TERMINATE; 1797 1798 SCIP_CALL( SCIPaddCons(scip, cons) ); 1799 SCIPdebugMsg(scip, "(line %d) created constraint%s: ", lpinput->linenumber, 1800 lpinput->inlazyconstraints ? " (lazy)" : (lpinput->inusercuts ? " (user cut)" : "")); 1801 SCIPdebugPrintCons(scip, cons, NULL); 1802 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1803 } 1804 else 1805 { 1806 /* now we should have an indicator constraint */ 1807 if( ncoefs != 1 || nquadcoefs > 0 ) 1808 { 1809 syntaxError(scip, lpinput, "Indicator part can only consist of one binary variable."); 1810 goto TERMINATE; 1811 } 1812 assert(coefs != NULL); 1813 if( !SCIPisEQ(scip, coefs[0], 1.0) ) 1814 { 1815 syntaxError(scip, lpinput, "There cannot be a coefficient before the binary indicator variable."); 1816 goto TERMINATE; 1817 } 1818 if( sense != LP_SENSE_EQ ) 1819 { 1820 syntaxError(scip, lpinput, "Indicator part cannot handle equations."); 1821 goto TERMINATE; 1822 } 1823 assert(vars != NULL); 1824 retcode = createIndicatorConstraint(scip, lpinput, name, vars[0], lhs); 1825 } 1826 1827 TERMINATE: 1828 /* free memory */ 1829 SCIPfreeBlockMemoryArrayNull(scip, &quadcoefs, quadcoefssize); 1830 SCIPfreeBlockMemoryArrayNull(scip, &quadvars2, quadcoefssize); 1831 SCIPfreeBlockMemoryArrayNull(scip, &quadvars1, quadcoefssize); 1832 SCIPfreeBlockMemoryArrayNull(scip, &coefs, coefssize); 1833 SCIPfreeBlockMemoryArrayNull(scip, &vars, coefssize); 1834 1835 SCIP_CALL( retcode ); 1836 1837 return SCIP_OKAY; 1838 } 1839 1840 /** reads the bounds section */ 1841 static 1842 SCIP_RETCODE readBounds( 1843 SCIP* scip, /**< SCIP data structure */ 1844 LPINPUT* lpinput /**< LP reading data */ 1845 ) 1846 { 1847 assert(lpinput != NULL); 1848 1849 while( getNextToken(scip, lpinput) ) 1850 { 1851 SCIP_VAR* var; 1852 SCIP_Real value; 1853 SCIP_Real lb; 1854 SCIP_Real ub; 1855 int sign; 1856 SCIP_Bool hassign; 1857 LPSENSE leftsense; 1858 1859 /* check if we reached a new section */ 1860 if( isNewSection(scip, lpinput) ) 1861 return SCIP_OKAY; 1862 1863 /* default bounds are [0,+inf] */ 1864 lb = 0.0; 1865 ub = SCIPinfinity(scip); 1866 leftsense = LP_SENSE_NOTHING; 1867 1868 /* check if the first token is a sign */ 1869 sign = +1; 1870 hassign = isSign(lpinput, &sign); 1871 if( hassign && !getNextToken(scip, lpinput) ) 1872 { 1873 syntaxError(scip, lpinput, "expected value."); 1874 return SCIP_OKAY; 1875 } 1876 1877 /* the first token must be either a value or a variable name */ 1878 if( isValue(scip, lpinput, &value) ) 1879 { 1880 /* first token is a value: the second token must be a sense */ 1881 if( !getNextToken(scip, lpinput) || !isSense(lpinput, &leftsense) ) 1882 { 1883 syntaxError(scip, lpinput, "expected bound sense '<=', '=', or '>='."); 1884 return SCIP_OKAY; 1885 } 1886 1887 /* update the bound corresponding to the sense */ 1888 switch( leftsense ) 1889 { 1890 case LP_SENSE_GE: 1891 ub = sign * value; 1892 break; 1893 case LP_SENSE_LE: 1894 lb = sign * value; 1895 break; 1896 case LP_SENSE_EQ: 1897 lb = sign * value; 1898 ub = sign * value; 1899 break; 1900 case LP_SENSE_NOTHING: 1901 default: 1902 SCIPerrorMessage("invalid bound sense <%d>\n", leftsense); 1903 return SCIP_INVALIDDATA; 1904 } 1905 } 1906 else if( hassign ) 1907 { 1908 syntaxError(scip, lpinput, "expected value."); 1909 return SCIP_OKAY; 1910 } 1911 else 1912 pushToken(lpinput); 1913 1914 /* the next token must be a variable name */ 1915 if( !getNextToken(scip, lpinput) ) 1916 { 1917 syntaxError(scip, lpinput, "expected variable name."); 1918 return SCIP_OKAY; 1919 } 1920 SCIP_CALL( getVariable(scip, lpinput->token, &var, NULL) ); 1921 1922 /* the next token might be another sense, or the word "free" */ 1923 if( getNextToken(scip, lpinput) ) 1924 { 1925 LPSENSE rightsense; 1926 1927 if( isSense(lpinput, &rightsense) ) 1928 { 1929 /* check, if the senses fit */ 1930 if( leftsense == LP_SENSE_NOTHING 1931 || (leftsense == LP_SENSE_LE && rightsense == LP_SENSE_LE) 1932 || (leftsense == LP_SENSE_GE && rightsense == LP_SENSE_GE) ) 1933 { 1934 if( !getNextToken(scip, lpinput) ) 1935 { 1936 syntaxError(scip, lpinput, "expected value or sign."); 1937 return SCIP_OKAY; 1938 } 1939 1940 /* check if the next token is a sign */ 1941 sign = +1; 1942 hassign = isSign(lpinput, &sign); 1943 if( hassign && !getNextToken(scip, lpinput) ) 1944 { 1945 syntaxError(scip, lpinput, "expected value."); 1946 return SCIP_OKAY; 1947 } 1948 1949 /* the next token must be a value */ 1950 if( !isValue(scip, lpinput, &value) ) 1951 { 1952 syntaxError(scip, lpinput, "expected value."); 1953 return SCIP_OKAY; 1954 } 1955 1956 /* update the bound corresponding to the sense */ 1957 switch( rightsense ) 1958 { 1959 case LP_SENSE_GE: 1960 lb = sign * value; 1961 break; 1962 case LP_SENSE_LE: 1963 ub = sign * value; 1964 break; 1965 case LP_SENSE_EQ: 1966 lb = sign * value; 1967 ub = sign * value; 1968 break; 1969 case LP_SENSE_NOTHING: 1970 default: 1971 SCIPerrorMessage("invalid bound sense <%d>\n", leftsense); 1972 return SCIP_INVALIDDATA; 1973 } 1974 } 1975 else 1976 { 1977 syntaxError(scip, lpinput, "the two bound senses do not fit."); 1978 return SCIP_OKAY; 1979 } 1980 } 1981 else if( strcasecmp(lpinput->token, "FREE") == 0 ) 1982 { 1983 if( leftsense != LP_SENSE_NOTHING ) 1984 { 1985 syntaxError(scip, lpinput, "variable with bound is marked as 'free'."); 1986 return SCIP_OKAY; 1987 } 1988 lb = -SCIPinfinity(scip); 1989 ub = SCIPinfinity(scip); 1990 } 1991 else 1992 { 1993 /* the token was no sense: push it back to the token stack */ 1994 pushToken(lpinput); 1995 } 1996 } 1997 1998 /* change the bounds of the variable if bounds have been given (do not destroy earlier specification of bounds) */ 1999 if( lb != 0.0 ) 2000 SCIP_CALL( SCIPchgVarLb(scip, var, lb) ); 2001 /*lint --e{777}*/ 2002 if( ub != SCIPinfinity(scip) ) 2003 SCIP_CALL( SCIPchgVarUb(scip, var, ub) ); 2004 SCIPdebugMsg(scip, "(line %d) new bounds: <%s>[%g,%g]\n", lpinput->linenumber, SCIPvarGetName(var), 2005 SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)); 2006 } 2007 2008 return SCIP_OKAY; 2009 } 2010 2011 /** reads the generals section */ 2012 static 2013 SCIP_RETCODE readGenerals( 2014 SCIP* scip, /**< SCIP data structure */ 2015 LPINPUT* lpinput /**< LP reading data */ 2016 ) 2017 { 2018 assert(lpinput != NULL); 2019 2020 while( getNextToken(scip, lpinput) ) 2021 { 2022 SCIP_VAR* var; 2023 SCIP_Real lb; 2024 SCIP_Real ub; 2025 SCIP_Bool created; 2026 SCIP_Bool infeasible; 2027 2028 /* check if we reached a new section */ 2029 if( isNewSection(scip, lpinput) ) 2030 return SCIP_OKAY; 2031 2032 /* the token must be the name of an existing variable */ 2033 SCIP_CALL( getVariable(scip, lpinput->token, &var, &created) ); 2034 if( created ) 2035 { 2036 syntaxError(scip, lpinput, "unknown variable in generals section."); 2037 return SCIP_OKAY; 2038 } 2039 2040 lb = SCIPvarGetLbGlobal(var); 2041 ub = SCIPvarGetUbGlobal(var); 2042 2043 if( !SCIPisFeasIntegral(scip, lb) || !SCIPisFeasIntegral(scip, ub) ) 2044 { 2045 SCIPwarningMessage(scip, "variable <%s> declared as integer has non-integral bounds[%.14g, %.14g] -> if feasible, bounds will be adjusted\n", SCIPvarGetName(var), lb, ub); 2046 } 2047 2048 /* mark the variable to be integral */ 2049 SCIP_CALL( SCIPchgVarType(scip, var, SCIP_VARTYPE_INTEGER, &infeasible) ); 2050 /* don't assert feasibility here because the presolver will and should detect a infeasibility */ 2051 } 2052 2053 return SCIP_OKAY; 2054 } 2055 2056 /** reads the binaries section */ 2057 static 2058 SCIP_RETCODE readBinaries( 2059 SCIP* scip, /**< SCIP data structure */ 2060 LPINPUT* lpinput /**< LP reading data */ 2061 ) 2062 { 2063 assert(lpinput != NULL); 2064 2065 while( getNextToken(scip, lpinput) ) 2066 { 2067 SCIP_VAR* var; 2068 SCIP_Real lb; 2069 SCIP_Real ub; 2070 SCIP_Bool created; 2071 SCIP_Bool infeasible; 2072 2073 /* check if we reached a new section */ 2074 if( isNewSection(scip, lpinput) ) 2075 return SCIP_OKAY; 2076 2077 /* the token must be the name of an existing variable */ 2078 SCIP_CALL( getVariable(scip, lpinput->token, &var, &created) ); 2079 if( created ) 2080 { 2081 syntaxError(scip, lpinput, "unknown variable in binaries section."); 2082 return SCIP_OKAY; 2083 } 2084 2085 lb = SCIPvarGetLbGlobal(var); 2086 ub = SCIPvarGetUbGlobal(var); 2087 2088 if( (!SCIPisFeasZero(scip, lb) && !SCIPisFeasEQ(scip, lb, 1.0)) || 2089 (!SCIPisFeasZero(scip, ub) && !SCIPisFeasEQ(scip, ub, 1.0) && !SCIPisInfinity(scip, ub)) ) 2090 { 2091 SCIPwarningMessage(scip, "variable <%s> declared as binary has non-binary bounds[%.14g, %.14g] -> if feasible, bounds will be adjusted\n", SCIPvarGetName(var), lb, ub); 2092 } 2093 2094 /* mark the variable to be binary and change its bounds appropriately */ 2095 if( SCIPvarGetLbGlobal(var) < 0.0 ) 2096 { 2097 SCIP_CALL( SCIPchgVarLb(scip, var, 0.0) ); 2098 } 2099 if( SCIPvarGetUbGlobal(var) > 1.0 ) 2100 { 2101 SCIP_CALL( SCIPchgVarUb(scip, var, 1.0) ); 2102 } 2103 SCIP_CALL( SCIPchgVarType(scip, var, SCIP_VARTYPE_BINARY, &infeasible) ); 2104 /* don't assert feasibility here because the presolver will and should detect a infeasibility */ 2105 } 2106 2107 return SCIP_OKAY; 2108 } 2109 2110 /** reads the semi-continuous section */ 2111 static 2112 SCIP_RETCODE readSemicontinuous( 2113 SCIP* scip, /**< SCIP data structure */ 2114 LPINPUT* lpinput /**< LP reading data */ 2115 ) 2116 { 2117 SCIP_Real oldlb; 2118 char name[SCIP_MAXSTRLEN]; 2119 SCIP_CONS* cons; 2120 SCIP_VAR* var; 2121 SCIP_Bool created; 2122 2123 SCIP_VAR* vars[2]; 2124 SCIP_BOUNDTYPE boundtypes[2]; 2125 SCIP_Real bounds[2]; 2126 2127 assert(lpinput != NULL); 2128 2129 /* if section is titles "semi-continuous", then the parser breaks this into parts */ 2130 if( strcasecmp(lpinput->token, "SEMI") == 0 ) 2131 { 2132 if( !getNextToken(scip, lpinput) ) 2133 { 2134 syntaxError(scip, lpinput, "unexpected end."); 2135 return SCIP_OKAY; 2136 } 2137 2138 if( strcasecmp(lpinput->token, "-") == 0 ) 2139 { 2140 if( !getNextToken(scip, lpinput) || strcasecmp(lpinput->token, "CONTINUOUS") != 0 ) 2141 { 2142 syntaxError(scip, lpinput, "expected 'CONTINUOUS' after 'SEMI-'."); 2143 return SCIP_OKAY; 2144 } 2145 } 2146 else 2147 { 2148 pushToken(lpinput); 2149 } 2150 } 2151 2152 while( getNextToken(scip, lpinput) ) 2153 { 2154 /* check if we reached a new section */ 2155 if( isNewSection(scip, lpinput) ) 2156 return SCIP_OKAY; 2157 2158 /* the token must be the name of an existing variable */ 2159 SCIP_CALL( getVariable(scip, lpinput->token, &var, &created) ); 2160 if( created ) 2161 { 2162 syntaxError(scip, lpinput, "unknown variable in semi-continuous section."); 2163 return SCIP_OKAY; 2164 } 2165 2166 if( SCIPvarGetLbGlobal(var) <= 0.0 ) 2167 { 2168 SCIPdebugMsg(scip, "ignore semi-continuity of variable <%s> with negative lower bound %g\n", SCIPvarGetName(var), SCIPvarGetLbGlobal(var)); 2169 continue; 2170 } 2171 2172 oldlb = SCIPvarGetLbGlobal(var); 2173 2174 /* change the lower bound to 0.0 */ 2175 SCIP_CALL( SCIPchgVarLb(scip, var, 0.0) ); 2176 2177 /* add a bound disjunction constraint to say var <= 0.0 or var >= oldlb */ 2178 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "semicont_%s", SCIPvarGetName(var)); 2179 2180 vars[0] = var; 2181 vars[1] = var; 2182 boundtypes[0] = SCIP_BOUNDTYPE_UPPER; 2183 boundtypes[1] = SCIP_BOUNDTYPE_LOWER; 2184 bounds[0] = 0.0; 2185 bounds[1] = oldlb; 2186 2187 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, 2, vars, boundtypes, bounds, 2188 !(lpinput->dynamiccols), TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, lpinput->dynamicconss, lpinput->dynamiccols, FALSE) ); 2189 SCIP_CALL( SCIPaddCons(scip, cons) ); 2190 2191 SCIPdebugMsg(scip, "add bound disjunction constraint for semi-continuity of <%s>:\n\t", SCIPvarGetName(var)); 2192 SCIPdebugPrintCons(scip, cons, NULL); 2193 2194 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 2195 } 2196 2197 return SCIP_OKAY; 2198 } 2199 2200 /** reads the sos section 2201 * 2202 * The format is as follows: 2203 * 2204 * SOS 2205 * \<constraint name\>: [S1|S2]:: {\<variable name\>:\<weight\>} 2206 * ... 2207 * \<constraint name\>: [S1|S2]:: {\<variable name\>:\<weight\>} 2208 * */ 2209 static 2210 SCIP_RETCODE readSos( 2211 SCIP* scip, /**< SCIP data structure */ 2212 LPINPUT* lpinput /**< LP reading data */ 2213 ) 2214 { 2215 SCIP_Bool initial, separate, enforce, check, propagate; 2216 SCIP_Bool local, dynamic, removable; 2217 char name[SCIP_MAXSTRLEN]; 2218 int cnt = 0; 2219 2220 assert(lpinput != NULL); 2221 2222 /* standard settings for SOS constraints: */ 2223 initial = lpinput->initialconss; 2224 separate = TRUE; 2225 enforce = TRUE; 2226 check = TRUE; 2227 propagate = TRUE; 2228 local = FALSE; 2229 dynamic = lpinput->dynamicconss; 2230 removable = lpinput->dynamicrows; 2231 2232 while( getNextToken(scip, lpinput) ) 2233 { 2234 int type = -1; 2235 SCIP_CONS* cons; 2236 2237 /* check if we reached a new section */ 2238 if( isNewSection(scip, lpinput) ) 2239 return SCIP_OKAY; 2240 2241 /* check for an SOS constraint name */ 2242 *name = '\0'; 2243 2244 /* remember the token in the token buffer */ 2245 swapTokenBuffer(lpinput); 2246 2247 /* get the next token and check, whether it is a colon */ 2248 if( getNextToken(scip, lpinput) ) 2249 { 2250 if( strcmp(lpinput->token, ":") == 0 ) 2251 { 2252 /* the second token was a colon: the first token is the constraint name */ 2253 (void)SCIPmemccpy(name, lpinput->tokenbuf, '\0', SCIP_MAXSTRLEN); 2254 2255 name[SCIP_MAXSTRLEN-1] = '\0'; 2256 } 2257 else 2258 { 2259 /* the second token was no colon: push the tokens back onto the token stack and parse it next */ 2260 pushToken(lpinput); 2261 pushBufferToken(lpinput); 2262 } 2263 } 2264 else 2265 { 2266 /* there was only one token left: push it back onto the token stack and parse it next */ 2267 pushBufferToken(lpinput); 2268 } 2269 2270 /* get type */ 2271 if( !getNextToken(scip, lpinput) ) 2272 { 2273 syntaxError(scip, lpinput, "expected SOS type: 'S1::' or 'S2::'."); 2274 return SCIP_OKAY; 2275 } 2276 /* check whether constraint name was left out */ 2277 if( strcmp(lpinput->token, ":") == 0 ) 2278 { 2279 /* we have to push twice ':' and once the type: */ 2280 pushToken(lpinput); 2281 lpinput->token[0] = ':'; 2282 lpinput->token[1] = '\0'; 2283 pushToken(lpinput); 2284 swapTokenBuffer(lpinput); 2285 2286 /* set artificial name */ 2287 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "SOS%d", ++cnt); 2288 } 2289 2290 /* check whether it is type 1 or type 2 */ 2291 if( strcmp(lpinput->token, "S1") == 0 ) 2292 { 2293 type = 1; 2294 SCIP_CALL( SCIPcreateConsSOS1(scip, &cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, 2295 local, dynamic, removable, FALSE) ); 2296 } 2297 else if( strcmp(lpinput->token, "S2") == 0 ) 2298 { 2299 type = 2; 2300 SCIP_CALL( SCIPcreateConsSOS2(scip, &cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, 2301 local, dynamic, removable, FALSE) ); 2302 } 2303 else 2304 { 2305 syntaxError(scip, lpinput, "SOS constraint type other than 1 or 2 appeared."); 2306 return SCIP_OKAY; 2307 } 2308 assert( type == 1 || type == 2 ); 2309 2310 SCIPdebugMsg(scip, "created SOS%d constraint <%s>\n", type, name); 2311 2312 /* make sure that a colons follows */ 2313 if( !getNextToken(scip, lpinput) || strcmp(lpinput->token, ":") != 0 ) 2314 { 2315 syntaxError(scip, lpinput, "SOS constraint type has to be followed by two colons."); 2316 return SCIP_OKAY; 2317 } 2318 2319 /* make sure that another colons follows */ 2320 if( !getNextToken(scip, lpinput) || strcmp(lpinput->token, ":") != 0 ) 2321 { 2322 syntaxError(scip, lpinput, "SOS constraint type has to be followed by two colons."); 2323 return SCIP_OKAY; 2324 } 2325 2326 /* parse elements of SOS constraint */ 2327 while( getNextToken(scip, lpinput) ) 2328 { 2329 SCIP_VAR* var; 2330 SCIP_Real weight; 2331 2332 /* check if we reached a new section */ 2333 if( isNewSection(scip, lpinput) ) 2334 break; 2335 2336 /* remember the token in the token buffer */ 2337 swapTokenBuffer(lpinput); 2338 2339 /* get variable and colon */ 2340 var = SCIPfindVar(scip, lpinput->tokenbuf); 2341 2342 /* if token is a variable name */ 2343 if( var == NULL ) 2344 { 2345 pushBufferToken(lpinput); 2346 break; 2347 } 2348 else 2349 { 2350 SCIPdebugMsg(scip, "found variable <%s>\n", SCIPvarGetName(var)); 2351 if( !getNextToken(scip, lpinput) || strcmp(lpinput->token, ":") != 0 ) 2352 { 2353 syntaxError(scip, lpinput, "expected colon and weight."); 2354 return SCIP_OKAY; 2355 } 2356 /* check next token */ 2357 if( !getNextToken(scip, lpinput) ) 2358 { 2359 /* push back token, since it could be the name of a new constraint */ 2360 pushToken(lpinput); 2361 pushBufferToken(lpinput); 2362 break; 2363 } 2364 else 2365 { 2366 int sign = +1; 2367 2368 /* get sign */ 2369 if( isSign(lpinput, &sign) ) 2370 { 2371 (void) getNextToken(scip, lpinput); 2372 } 2373 2374 /* get weight */ 2375 if( !isValue(scip, lpinput, &weight) ) 2376 { 2377 /* push back token, since it could be the name of a new constraint */ 2378 pushToken(lpinput); 2379 pushBufferToken(lpinput); 2380 break; 2381 } 2382 else 2383 { 2384 /* we now know that we have a variable/weight pair -> add variable*/ 2385 switch( type ) 2386 { 2387 case 1: 2388 SCIP_CALL( SCIPaddVarSOS1(scip, cons, var, sign * weight) ); 2389 break; 2390 case 2: 2391 SCIP_CALL( SCIPaddVarSOS2(scip, cons, var, sign * weight) ); 2392 break; 2393 default: 2394 SCIPerrorMessage("unknown SOS type: <%d>\n", type); /* should not happen */ 2395 SCIPABORT(); 2396 return SCIP_INVALIDDATA; /*lint !e527*/ 2397 } 2398 SCIPdebugMsg(scip, "added variable <%s> with weight %g.\n", SCIPvarGetName(var), weight); 2399 } 2400 } 2401 } 2402 } 2403 2404 /* add the SOS constraint */ 2405 SCIP_CALL( SCIPaddCons(scip, cons) ); 2406 SCIPdebugMsg(scip, "(line %d) added constraint <%s>: ", lpinput->linenumber, SCIPconsGetName(cons)); 2407 SCIPdebugPrintCons(scip, cons, NULL); 2408 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 2409 } 2410 2411 return SCIP_OKAY; 2412 } 2413 2414 /** reads an LP file 2415 * 2416 * @todo check whether variables forced to be binary for the creation of indicator constraints are 2417 * really specified to be binary (or general with 0/1 bounds) in the file. 2418 */ 2419 static 2420 SCIP_RETCODE readLPFile( 2421 SCIP* scip, /**< SCIP data structure */ 2422 LPINPUT* lpinput, /**< LP reading data */ 2423 const char* filename /**< name of the input file */ 2424 ) 2425 { 2426 assert(lpinput != NULL); 2427 2428 /* open file */ 2429 lpinput->file = SCIPfopen(filename, "r"); 2430 if( lpinput->file == NULL ) 2431 { 2432 SCIPerrorMessage("cannot open file <%s> for reading\n", filename); 2433 SCIPprintSysError(filename); 2434 return SCIP_NOFILE; 2435 } 2436 2437 /* create problem */ 2438 SCIP_CALL( SCIPcreateProb(scip, filename, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 2439 2440 /* parse the file */ 2441 lpinput->section = LP_START; 2442 while( lpinput->section != LP_END && !hasError(lpinput) ) 2443 { 2444 switch( lpinput->section ) 2445 { 2446 case LP_START: 2447 SCIP_CALL( readStart(scip, lpinput) ); 2448 break; 2449 2450 case LP_OBJECTIVE: 2451 SCIP_CALL( readObjective(scip, lpinput) ); 2452 break; 2453 2454 case LP_CONSTRAINTS: 2455 SCIP_CALL( readConstraints(scip, lpinput) ); 2456 break; 2457 2458 case LP_BOUNDS: 2459 SCIP_CALL( readBounds(scip, lpinput) ); 2460 break; 2461 2462 case LP_GENERALS: 2463 SCIP_CALL( readGenerals(scip, lpinput) ); 2464 break; 2465 2466 case LP_BINARIES: 2467 SCIP_CALL( readBinaries(scip, lpinput) ); 2468 break; 2469 2470 case LP_SEMICONTINUOUS: 2471 SCIP_CALL( readSemicontinuous(scip, lpinput) ); 2472 break; 2473 2474 case LP_SOS: 2475 SCIP_CALL( readSos(scip, lpinput) ); 2476 break; 2477 2478 case LP_END: /* this is already handled in the while() loop */ 2479 default: 2480 SCIPerrorMessage("invalid LP file section <%d>\n", lpinput->section); 2481 return SCIP_INVALIDDATA; 2482 } 2483 } 2484 2485 /* close file */ 2486 SCIPfclose(lpinput->file); 2487 2488 return SCIP_OKAY; 2489 } 2490 2491 2492 /* 2493 * Local methods (for writing) 2494 */ 2495 2496 /** hash key retrieval function for variables */ 2497 static 2498 SCIP_DECL_HASHGETKEY(hashGetKeyVar) 2499 { /*lint --e{715}*/ 2500 return elem; 2501 } 2502 2503 /** returns TRUE iff the indices of both variables are equal */ 2504 static 2505 SCIP_DECL_HASHKEYEQ(hashKeyEqVar) 2506 { /*lint --e{715}*/ 2507 if( key1 == key2 ) 2508 return TRUE; 2509 return FALSE; 2510 } 2511 2512 /** returns the hash value of the key */ 2513 static 2514 SCIP_DECL_HASHKEYVAL(hashKeyValVar) 2515 { /*lint --e{715}*/ 2516 assert( SCIPvarGetIndex((SCIP_VAR*) key) >= 0 ); 2517 return (unsigned int) SCIPvarGetIndex((SCIP_VAR*) key); 2518 } 2519 2520 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */ 2521 static 2522 SCIP_RETCODE getActiveVariables( 2523 SCIP* scip, /**< SCIP data structure */ 2524 SCIP_VAR*** vars, /**< pointer to vars array to get active variables for */ 2525 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */ 2526 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 2527 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 2528 SCIP_Bool transformed /**< transformed constraint? */ 2529 ) 2530 { 2531 int requiredsize; 2532 int v; 2533 2534 assert(scip != NULL); 2535 assert(vars != NULL); 2536 assert(scalars != NULL); 2537 assert(nvars != NULL); 2538 assert(*vars != NULL || *nvars == 0); 2539 assert(*scalars != NULL || *nvars == 0); 2540 assert(constant != NULL); 2541 2542 if( transformed ) 2543 { 2544 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) ); 2545 2546 if( requiredsize > *nvars ) 2547 { 2548 SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) ); 2549 SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) ); 2550 2551 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) ); 2552 assert( requiredsize <= *nvars ); 2553 } 2554 } 2555 else 2556 { 2557 if( *nvars > 0 && ( *vars == NULL || *scalars == NULL ) ) /*lint !e774 !e845*/ 2558 { 2559 SCIPerrorMessage("Null pointer in LP reader\n"); /* should not happen */ 2560 SCIPABORT(); 2561 return SCIP_INVALIDDATA; /*lint !e527*/ 2562 } 2563 2564 for( v = 0; v < *nvars; ++v ) 2565 { 2566 SCIP_CALL( SCIPvarGetOrigvarSum(&(*vars)[v], &(*scalars)[v], constant) ); 2567 2568 /* negated variables with an original counterpart may also be returned by SCIPvarGetOrigvarSum(); 2569 * make sure we get the original variable in that case 2570 */ 2571 if( SCIPvarGetStatus((*vars)[v]) == SCIP_VARSTATUS_NEGATED ) 2572 { 2573 (*vars)[v] = SCIPvarGetNegatedVar((*vars)[v]); 2574 *constant += (*scalars)[v]; 2575 (*scalars)[v] *= -1.0; 2576 } 2577 } 2578 } 2579 return SCIP_OKAY; 2580 } 2581 2582 /** clears the given line buffer */ 2583 static 2584 void clearLine( 2585 char* linebuffer, /**< line */ 2586 int* linecnt /**< number of characters in line */ 2587 ) 2588 { 2589 assert( linebuffer != NULL ); 2590 assert( linecnt != NULL ); 2591 2592 (*linecnt) = 0; 2593 linebuffer[0] = '\0'; 2594 } 2595 2596 /** ends the given line with '\\0' and prints it to the given file stream */ 2597 static 2598 void endLine( 2599 SCIP* scip, /**< SCIP data structure */ 2600 FILE* file, /**< output file (or NULL for standard output) */ 2601 char* linebuffer, /**< line */ 2602 int* linecnt /**< number of characters in line */ 2603 ) 2604 { 2605 assert( scip != NULL ); 2606 assert( linebuffer != NULL ); 2607 assert( linecnt != NULL ); 2608 assert( 0 <= *linecnt && *linecnt < LP_MAX_PRINTLEN ); 2609 2610 if( (*linecnt) > 0 ) 2611 { 2612 linebuffer[(*linecnt)] = '\0'; 2613 SCIPinfoMessage(scip, file, "%s\n", linebuffer); 2614 clearLine(linebuffer, linecnt); 2615 } 2616 } 2617 2618 /** appends extension to line and prints it to the give file stream if the 2619 * line exceeded the length given in the define LP_PRINTLEN */ 2620 static 2621 void appendLine( 2622 SCIP* scip, /**< SCIP data structure */ 2623 FILE* file, /**< output file (or NULL for standard output) */ 2624 char* linebuffer, /**< line */ 2625 int* linecnt, /**< number of characters in line */ 2626 const char* extension /**< string to extent the line */ 2627 ) 2628 { 2629 assert( scip != NULL ); 2630 assert( linebuffer != NULL ); 2631 assert( linecnt != NULL ); 2632 assert( extension != NULL ); 2633 assert( strlen(linebuffer) + strlen(extension) < LP_MAX_PRINTLEN ); 2634 2635 /* NOTE: avoid 2636 * sprintf(linebuffer, "%s%s", linebuffer, extension); 2637 * because of overlapping memory areas in memcpy used in sprintf. 2638 */ 2639 (void) strncat(linebuffer, extension, LP_MAX_PRINTLEN - strlen(linebuffer)); 2640 2641 (*linecnt) += (int) strlen(extension); 2642 2643 SCIPdebugMsg(scip, "linebuffer <%s>, length = %lu\n", linebuffer, (unsigned long)strlen(linebuffer)); 2644 2645 if( (*linecnt) > LP_PRINTLEN ) 2646 endLine(scip, file, linebuffer, linecnt); 2647 } 2648 2649 2650 /* print row in LP format to file stream */ 2651 static 2652 SCIP_RETCODE printRow( 2653 SCIP* scip, /**< SCIP data structure */ 2654 FILE* file, /**< output file (or NULL for standard output) */ 2655 const char* rowname, /**< row name */ 2656 const char* rownameextension, /**< row name extension */ 2657 const char* type, /**< row type ("=", "<=", or ">=") */ 2658 SCIP_VAR** linvars, /**< array of linear variables */ 2659 SCIP_Real* linvals, /**< array of linear coefficient values */ 2660 int nlinvars, /**< number of linear variables */ 2661 SCIP_EXPR* quadexpr, /**< quadratic expression */ 2662 SCIP_Real rhs, /**< right hand side */ 2663 SCIP_Bool transformed /**< transformed constraint? */ 2664 ) 2665 { 2666 int v; 2667 char linebuffer[LP_MAX_PRINTLEN+1] = { '\0' }; 2668 int linecnt; 2669 2670 char varname[LP_MAX_NAMELEN]; 2671 char varname2[LP_MAX_NAMELEN]; 2672 char consname[LP_MAX_NAMELEN + 1]; /* an extra character for ':' */ 2673 char buffer[LP_MAX_PRINTLEN]; 2674 2675 assert( scip != NULL ); 2676 assert( strcmp(type, "=") == 0 || strcmp(type, "<=") == 0 || strcmp(type, ">=") == 0 ); 2677 assert( nlinvars == 0 || (linvars != NULL && linvals != NULL) ); 2678 2679 clearLine(linebuffer, &linecnt); 2680 2681 /* start each line with a space */ 2682 appendLine(scip, file, linebuffer, &linecnt, " "); 2683 2684 /* print row name */ 2685 if( strlen(rowname) > 0 || strlen(rownameextension) > 0 ) 2686 { 2687 (void) SCIPsnprintf(consname, LP_MAX_NAMELEN + 1, "%s%s:", rowname, rownameextension); 2688 appendLine(scip, file, linebuffer, &linecnt, consname); 2689 } 2690 2691 /* print coefficients */ 2692 for( v = 0; v < nlinvars; ++v ) 2693 { 2694 SCIP_VAR* var; 2695 2696 assert(linvars != NULL); /* for lint */ 2697 assert(linvals != NULL); 2698 2699 var = linvars[v]; 2700 assert( var != NULL ); 2701 2702 /* we start a new line; therefore we tab this line */ 2703 if( linecnt == 0 ) 2704 appendLine(scip, file, linebuffer, &linecnt, " "); 2705 2706 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var)); 2707 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s", linvals[v], varname); 2708 2709 appendLine(scip, file, linebuffer, &linecnt, buffer); 2710 } 2711 2712 /* print quadratic part */ 2713 if( quadexpr != NULL ) 2714 { 2715 SCIP_EXPR** linexprs; 2716 SCIP_VAR** activevars; 2717 SCIP_Real* activevals; 2718 SCIP_Real* lincoefs; 2719 SCIP_Real constant; 2720 SCIP_Real activeconstant = 0.0; 2721 int nbilinexprterms; 2722 int nactivevars; 2723 int nquadexprs; 2724 int nlinexprs; 2725 2726 /* get data from the quadratic expression */ 2727 SCIPexprGetQuadraticData(quadexpr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprterms, 2728 NULL, NULL); 2729 2730 /* allocate memory to store active linear variables */ 2731 SCIP_CALL( SCIPallocBufferArray(scip, &activevars, nlinexprs) ); 2732 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, lincoefs, nlinexprs) ); 2733 nactivevars = nlinexprs; 2734 2735 for( v = 0; v < nlinexprs; ++v ) 2736 { 2737 assert(linexprs != NULL && linexprs[v] != NULL); 2738 assert(SCIPisExprVar(scip, linexprs[v])); 2739 2740 activevars[v] = SCIPgetVarExprVar(linexprs[v]); 2741 assert(activevars[v] != NULL); 2742 } 2743 2744 /* get active variables */ 2745 SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant, transformed) ); 2746 constant += activeconstant; 2747 2748 /* print linear coefficients of linear variables */ 2749 for( v = 0; v < nactivevars; ++v ) 2750 { 2751 SCIP_VAR* var; 2752 2753 assert(activevars != NULL); /* for lint */ 2754 assert(activevals != NULL); 2755 2756 var = activevars[v]; 2757 assert( var != NULL ); 2758 2759 /* we start a new line; therefore we tab this line */ 2760 if( linecnt == 0 ) 2761 appendLine(scip, file, linebuffer, &linecnt, " "); 2762 2763 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var)); 2764 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s", activevals[v], varname); 2765 2766 appendLine(scip, file, linebuffer, &linecnt, buffer); 2767 } 2768 2769 /* free memory for active linear variables */ 2770 SCIPfreeBufferArray(scip, &activevals); 2771 SCIPfreeBufferArray(scip, &activevars); 2772 2773 /* adjust rhs if there is a constant */ 2774 if( constant != 0.0 && !SCIPisInfinity(scip, rhs) ) 2775 rhs -= constant; 2776 2777 /* print linear coefficients of quadratic variables */ 2778 for( v = 0; v < nquadexprs; ++v ) 2779 { 2780 SCIP_EXPR* expr; 2781 SCIP_VAR* var; 2782 SCIP_Real lincoef; 2783 2784 /* get linear coefficient and variable of quadratic term */ 2785 SCIPexprGetQuadraticQuadTerm(quadexpr, v, &expr, &lincoef, NULL, NULL, NULL, NULL); 2786 assert(expr != NULL); 2787 assert(SCIPisExprVar(scip, expr)); 2788 2789 var = SCIPgetVarExprVar(expr); 2790 assert(var != NULL); 2791 2792 if( lincoef == 0.0 ) 2793 continue; 2794 2795 /* we start a new line; therefore we tab this line */ 2796 if( linecnt == 0 ) 2797 appendLine(scip, file, linebuffer, &linecnt, " "); 2798 2799 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var)); 2800 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s", lincoef, varname); 2801 2802 appendLine(scip, file, linebuffer, &linecnt, buffer); 2803 } 2804 2805 /* start quadratic part */ 2806 appendLine(scip, file, linebuffer, &linecnt, " + ["); 2807 2808 /* print square terms */ 2809 for( v = 0; v < nquadexprs; ++v ) 2810 { 2811 SCIP_EXPR* expr; 2812 SCIP_VAR* var; 2813 SCIP_Real sqrcoef; 2814 2815 /* get square coefficient and variable of quadratic term */ 2816 SCIPexprGetQuadraticQuadTerm(quadexpr, v, &expr, NULL, &sqrcoef, NULL, NULL, NULL); 2817 assert(expr != NULL); 2818 assert(SCIPisExprVar(scip, expr)); 2819 2820 var = SCIPgetVarExprVar(expr); 2821 assert(var != NULL); 2822 2823 if( sqrcoef == 0.0 ) 2824 continue; 2825 2826 /* we start a new line; therefore we tab this line */ 2827 if( linecnt == 0 ) 2828 appendLine(scip, file, linebuffer, &linecnt, " "); 2829 2830 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var)); 2831 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s^2", sqrcoef, varname); 2832 2833 appendLine(scip, file, linebuffer, &linecnt, buffer); 2834 } 2835 2836 /* print bilinear terms */ 2837 for( v = 0; v < nbilinexprterms; ++v ) 2838 { 2839 SCIP_EXPR* expr1; 2840 SCIP_EXPR* expr2; 2841 SCIP_VAR* var1; 2842 SCIP_VAR* var2; 2843 SCIP_Real bilincoef; 2844 2845 /* get coefficient and variables of bilinear */ 2846 SCIPexprGetQuadraticBilinTerm(quadexpr, v, &expr1, &expr2, &bilincoef, NULL, NULL); 2847 assert(expr1 != NULL); 2848 assert(SCIPisExprVar(scip, expr1)); 2849 assert(expr2 != NULL); 2850 assert(SCIPisExprVar(scip, expr2)); 2851 2852 var1 = SCIPgetVarExprVar(expr1); 2853 assert(var1 != NULL); 2854 var2 = SCIPgetVarExprVar(expr2); 2855 assert(var2 != NULL); 2856 2857 /* we start a new line; therefore we tab this line */ 2858 if( linecnt == 0 ) 2859 appendLine(scip, file, linebuffer, &linecnt, " "); 2860 2861 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var1)); 2862 (void) SCIPsnprintf(varname2, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var2)); 2863 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s * %s", bilincoef, varname, varname2); 2864 2865 appendLine(scip, file, linebuffer, &linecnt, buffer); 2866 } 2867 2868 /* end quadratic part */ 2869 appendLine(scip, file, linebuffer, &linecnt, " ]"); 2870 } 2871 2872 /* print left hand side */ 2873 if( SCIPisZero(scip, rhs) ) 2874 rhs = 0.0; 2875 2876 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s %+.15g", type, rhs); 2877 2878 /* we start a new line; therefore we tab this line */ 2879 if( linecnt == 0 ) 2880 appendLine(scip, file, linebuffer, &linecnt, " "); 2881 appendLine(scip, file, linebuffer, &linecnt, buffer); 2882 2883 endLine(scip, file, linebuffer, &linecnt); 2884 2885 return SCIP_OKAY; 2886 } 2887 2888 /** prints given (linear or) quadratic constraint information in LP format to file stream */ 2889 static 2890 SCIP_RETCODE printQuadraticCons( 2891 SCIP* scip, /**< SCIP data structure */ 2892 FILE* file, /**< output file (or NULL for standard output) */ 2893 const char* rowname, /**< name of the row */ 2894 SCIP_VAR** linvars, /**< array of linear variables */ 2895 SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */ 2896 int nlinvars, /**< number of linear variables */ 2897 SCIP_EXPR* quadexpr, /**< quadratic expression (or NULL if nlinvars > 0) */ 2898 SCIP_Real lhs, /**< left hand side */ 2899 SCIP_Real rhs, /**< right hand side */ 2900 SCIP_Bool transformed /**< transformed constraint? */ 2901 ) 2902 { 2903 int v; 2904 SCIP_VAR** activevars = NULL; 2905 SCIP_Real* activevals = NULL; 2906 int nactivevars; 2907 SCIP_Real activeconstant = 0.0; 2908 2909 assert( scip != NULL ); 2910 assert( rowname != NULL ); 2911 assert( quadexpr == NULL || nlinvars == 0); 2912 2913 /* The LP format does not forbid that the variable array is empty */ 2914 assert( nlinvars == 0 || linvars != NULL ); 2915 assert( lhs <= rhs ); 2916 2917 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 2918 return SCIP_OKAY; 2919 2920 nactivevars = nlinvars; 2921 if( nlinvars > 0 ) 2922 { 2923 /* duplicate variable and value array */ 2924 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, linvars, nactivevars ) ); 2925 if( linvals != NULL ) 2926 { 2927 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, linvals, nactivevars ) ); 2928 } 2929 else 2930 { 2931 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) ); 2932 2933 for( v = 0; v < nactivevars; ++v ) 2934 activevals[v] = 1.0; 2935 } 2936 2937 /* retransform given variables to active variables */ 2938 SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant, transformed) ); 2939 } 2940 2941 /* print row(s) in LP format */ 2942 if( SCIPisEQ(scip, lhs, rhs) ) 2943 { 2944 assert( !SCIPisInfinity(scip, rhs) ); 2945 2946 /* equal constraint */ 2947 SCIP_CALL( printRow(scip, file, rowname, "", "=", activevars, activevals, nactivevars, quadexpr, 2948 rhs - activeconstant, transformed) ); 2949 } 2950 else 2951 { 2952 if( !SCIPisInfinity(scip, -lhs) ) 2953 { 2954 /* print inequality ">=" */ 2955 SCIP_CALL( printRow(scip, file, rowname, SCIPisInfinity(scip, rhs) ? "" : "_lhs", ">=", activevars, activevals, 2956 nactivevars, quadexpr, lhs - activeconstant, transformed) ); 2957 } 2958 if( !SCIPisInfinity(scip, rhs) ) 2959 { 2960 /* print inequality "<=" */ 2961 SCIP_CALL( printRow(scip, file, rowname, SCIPisInfinity(scip, -lhs) ? "" : "_rhs", "<=", activevars, activevals, 2962 nactivevars, quadexpr, rhs - activeconstant, transformed) ); 2963 } 2964 } 2965 2966 if( nlinvars > 0 ) 2967 { 2968 /* free buffer arrays */ 2969 SCIPfreeBufferArray(scip, &activevals); 2970 SCIPfreeBufferArray(scip, &activevars); 2971 } 2972 2973 return SCIP_OKAY; 2974 } 2975 2976 /** prints given SOS constraint information in LP format to file stream */ 2977 static 2978 void printSosCons( 2979 SCIP* scip, /**< SCIP data structure */ 2980 FILE* file, /**< output file (or NULL for standard output) */ 2981 const char* rowname, /**< name of the row */ 2982 SCIP_VAR** vars, /**< array of variables */ 2983 SCIP_Real* weights, /**< array of weight values (or NULL) */ 2984 int nvars, /**< number of variables */ 2985 int type /**< SOS type (SOS1 or SOS2) */ 2986 ) 2987 { 2988 int v; 2989 2990 char linebuffer[LP_MAX_PRINTLEN+1]; 2991 int linecnt; 2992 char buffer[LP_MAX_PRINTLEN]; 2993 char varname[LP_MAX_NAMELEN]; 2994 2995 assert( scip != NULL ); 2996 assert( file != NULL ); 2997 assert( type == 1 || type == 2 ); 2998 2999 clearLine(linebuffer, &linecnt); 3000 3001 /* start each line with a space */ 3002 appendLine(scip, file, linebuffer, &linecnt, " "); 3003 assert( strlen(rowname) < LP_MAX_NAMELEN ); 3004 3005 if( strlen(rowname) > 0 ) 3006 { 3007 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, "%s:", rowname); 3008 appendLine(scip, file, linebuffer, &linecnt, buffer); 3009 } 3010 3011 /* SOS type */ 3012 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " S%d::", type); 3013 appendLine(scip, file, linebuffer, &linecnt, buffer); 3014 3015 for( v = 0; v < nvars; ++v ) 3016 { 3017 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(vars[v])); 3018 3019 if( weights != NULL ) 3020 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s:%.15g", varname, weights[v]); 3021 else 3022 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s:%d", varname, v); 3023 3024 if(linecnt == 0 ) 3025 { 3026 /* we start a new line; therefore we tab this line */ 3027 appendLine(scip, file, linebuffer, &linecnt, " "); 3028 } 3029 appendLine(scip, file, linebuffer, &linecnt, buffer); 3030 } 3031 3032 endLine(scip, file, linebuffer, &linecnt); 3033 } 3034 3035 /** prints a linearization of an and-constraint into the given file */ 3036 static 3037 SCIP_RETCODE printAndCons( 3038 SCIP* scip, /**< SCIP data structure */ 3039 FILE* file, /**< output file (or NULL for standard output) */ 3040 const char* consname, /**< name of the constraint */ 3041 SCIP_CONS* cons, /**< and constraint */ 3042 SCIP_Bool aggrlinearizationands,/**< print weak or strong realaxation */ 3043 SCIP_Bool transformed /**< transformed constraint? */ 3044 ) 3045 { 3046 SCIP_VAR** vars; 3047 SCIP_VAR** operands; 3048 SCIP_VAR* resultant; 3049 SCIP_Real* vals; 3050 char rowname[LP_MAX_NAMELEN]; 3051 int nvars; 3052 int v; 3053 3054 assert(scip != NULL); 3055 assert(consname != NULL); 3056 assert(cons != NULL); 3057 3058 nvars = SCIPgetNVarsAnd(scip, cons); 3059 operands = SCIPgetVarsAnd(scip, cons); 3060 resultant = SCIPgetResultantAnd(scip, cons); 3061 3062 /* allocate buffer array */ 3063 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars + 1) ); 3064 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars + 1) ); 3065 3066 /* the tight relaxtion, number of and-constraint operands rows */ 3067 if( !aggrlinearizationands ) 3068 { 3069 vars[0] = resultant; 3070 vals[0] = 1.0; 3071 vals[1] = -1.0; 3072 3073 /* print operator rows */ 3074 for( v = 0; v < nvars; ++v ) 3075 { 3076 (void) SCIPsnprintf(rowname, LP_MAX_NAMELEN, "%s_%d", consname, v); 3077 vars[1] = operands[v]; 3078 3079 /* print for each operator a row */ 3080 SCIP_CALL( printQuadraticCons(scip, file, rowname, vars, vals, 2, NULL, -SCIPinfinity(scip), 0.0, 3081 transformed) ); 3082 } 3083 } 3084 3085 /* prepare for next row */ 3086 for( v = nvars - 1; v >= 0; --v ) 3087 { 3088 vars[v] = operands[v]; 3089 vals[v] = -1.0; 3090 } 3091 3092 vars[nvars] = resultant; 3093 3094 /* the weak relaxtion, only one constraint */ 3095 if( aggrlinearizationands ) 3096 { 3097 /* adjust rowname of constraint */ 3098 (void) SCIPsnprintf(rowname, LP_MAX_NAMELEN, "%s_operators", consname); 3099 3100 vals[nvars] = (SCIP_Real) nvars; 3101 3102 /* print aggregated operator row */ 3103 SCIP_CALL( printQuadraticCons(scip, file, rowname, vars, vals, nvars + 1, NULL, -SCIPinfinity(scip), 0.0, 3104 transformed) ); 3105 } 3106 3107 /* create additional linear constraint */ 3108 (void) SCIPsnprintf(rowname, LP_MAX_NAMELEN, "%s_add", consname); 3109 3110 vals[nvars] = 1.0; 3111 3112 SCIP_CALL( printQuadraticCons(scip, file, rowname, vars, vals, nvars + 1, NULL, -nvars + 1.0, SCIPinfinity(scip), 3113 transformed) ); 3114 3115 /* free buffer array */ 3116 SCIPfreeBufferArray(scip, &vals); 3117 SCIPfreeBufferArray(scip, &vars); 3118 3119 return SCIP_OKAY; 3120 } 3121 3122 /** check whether given variables are aggregated and put them into an array without duplication */ 3123 static 3124 SCIP_RETCODE collectAggregatedVars( 3125 SCIP* scip, /**< SCIP data structure */ 3126 SCIP_VAR** vars, /**< variable array */ 3127 int nvars, /**< number of active variables in the problem */ 3128 SCIP_VAR*** aggvars, /**< pointer to array storing the aggregated variables on output */ 3129 int* naggvars, /**< pointer to number of aggregated variables on output */ 3130 int* saggvars, /**< pointer to number of slots in aggvars array */ 3131 SCIP_HASHTABLE* varAggregated /**< hashtable for checking duplicates */ 3132 ) 3133 { 3134 int v; 3135 3136 assert( scip != NULL ); 3137 assert( aggvars != NULL ); 3138 assert( naggvars != NULL ); 3139 assert( saggvars != NULL ); 3140 3141 /* check variables */ 3142 for( v = 0; v < nvars; ++v ) 3143 { 3144 SCIP_VARSTATUS status; 3145 SCIP_VAR* var; 3146 3147 var = vars[v]; 3148 status = SCIPvarGetStatus(var); 3149 3150 /* collect aggregated variables in a list */ 3151 if( status >= SCIP_VARSTATUS_AGGREGATED ) 3152 { 3153 assert( status == SCIP_VARSTATUS_AGGREGATED || status == SCIP_VARSTATUS_MULTAGGR || status == SCIP_VARSTATUS_NEGATED ); 3154 assert( varAggregated != NULL ); 3155 3156 if( ! SCIPhashtableExists(varAggregated, (void*) var) ) 3157 { 3158 /* possibly enlarge array */ 3159 if ( *saggvars <= *naggvars ) 3160 { 3161 int newsize; 3162 newsize = SCIPcalcMemGrowSize(scip, *naggvars + 1); 3163 assert( newsize > *saggvars ); 3164 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &aggvars, *saggvars, newsize) ); 3165 *saggvars = newsize; 3166 } 3167 3168 (*aggvars)[*naggvars] = var; 3169 (*naggvars)++; 3170 SCIP_CALL( SCIPhashtableInsert(varAggregated, (void*) var) ); 3171 assert( *naggvars <= *saggvars ); 3172 } 3173 } 3174 } 3175 return SCIP_OKAY; 3176 } 3177 3178 /** print aggregated variable-constraints */ 3179 static 3180 SCIP_RETCODE printAggregatedCons( 3181 SCIP* scip, /**< SCIP data structure */ 3182 FILE* file, /**< output file (or NULL for standard output) */ 3183 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */ 3184 int nvars, /**< number of active variables in the problem */ 3185 int nAggregatedVars, /**< number of aggregated variables */ 3186 SCIP_VAR** aggregatedVars /**< array storing the aggregated variables */ 3187 ) 3188 { 3189 int j; 3190 3191 SCIP_VAR** activevars; 3192 SCIP_Real* activevals; 3193 int nactivevars; 3194 SCIP_Real activeconstant = 0.0; 3195 char consname[LP_MAX_NAMELEN]; 3196 3197 assert( scip != NULL ); 3198 3199 /* write aggregation constraints */ 3200 SCIP_CALL( SCIPallocBufferArray(scip, &activevars, nvars) ); 3201 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nvars) ); 3202 3203 for( j = 0; j < nAggregatedVars; ++j ) 3204 { 3205 /* set up list to obtain substitution variables */ 3206 nactivevars = 1; 3207 3208 activevars[0] = aggregatedVars[j]; 3209 activevals[0] = 1.0; 3210 activeconstant = 0.0; 3211 3212 /* retransform given variables to active variables */ 3213 SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant, transformed) ); 3214 3215 activevals[nactivevars] = -1.0; 3216 activevars[nactivevars] = aggregatedVars[j]; 3217 ++nactivevars; 3218 3219 /* output constraint */ 3220 (void) SCIPsnprintf(consname, LP_MAX_NAMELEN, "aggr_%s", SCIPvarGetName(aggregatedVars[j])); 3221 SCIP_CALL( printRow(scip, file, consname, "", "=", activevars, activevals, nactivevars, NULL, - activeconstant, 3222 transformed) ); 3223 } 3224 3225 /* free buffer arrays */ 3226 SCIPfreeBufferArray(scip, &activevals); 3227 SCIPfreeBufferArray(scip, &activevars); 3228 3229 return SCIP_OKAY; 3230 } 3231 3232 /** method check if the variable names are not longer than LP_MAX_NAMELEN */ 3233 static 3234 void checkVarnames( 3235 SCIP* scip, /**< SCIP data structure */ 3236 SCIP_VAR** vars, /**< array of variables */ 3237 int nvars /**< number of variables */ 3238 ) 3239 { 3240 SCIP_Bool printwarning; 3241 int v; 3242 3243 assert(scip != NULL); 3244 assert(vars != NULL || nvars == 0); 3245 3246 printwarning = TRUE; 3247 3248 /* check if the variable names are not to long */ 3249 for( v = 0; v < nvars; ++v ) 3250 { 3251 if( strlen(SCIPvarGetName(vars[v])) > LP_MAX_NAMELEN ) /*lint !e613*/ 3252 { 3253 SCIPwarningMessage(scip, "there is a variable name which has to be cut down to %d characters; LP might be corrupted\n", 3254 LP_MAX_NAMELEN - 1); 3255 return; 3256 } 3257 3258 /* check if variable name starts with a digit */ 3259 if( printwarning && isdigit((unsigned char)SCIPvarGetName(vars[v])[0]) ) /*lint !e613*/ 3260 { 3261 SCIPwarningMessage(scip, "violation of LP format - a variable name starts with a digit; " \ 3262 "it is not possible to read the generated LP file with SCIP; " \ 3263 "use write/genproblem or write/gentransproblem for generic variable names\n"); 3264 printwarning = FALSE; 3265 } 3266 } 3267 } 3268 3269 /** method check if the constraint names are not longer than LP_MAX_NAMELEN */ 3270 static 3271 void checkConsnames( 3272 SCIP* scip, /**< SCIP data structure */ 3273 SCIP_CONS** conss, /**< array of constraints */ 3274 int nconss, /**< number of constraints */ 3275 SCIP_Bool transformed /**< TRUE iff problem is the transformed problem */ 3276 ) 3277 { 3278 int c; 3279 SCIP_CONS* cons; 3280 SCIP_CONSHDLR* conshdlr; 3281 const char* conshdlrname; 3282 SCIP_Bool printwarning = TRUE; 3283 3284 assert( scip != NULL ); 3285 assert( conss != NULL || nconss == 0 ); 3286 3287 for( c = 0; c < nconss; ++c ) 3288 { 3289 int len; 3290 3291 assert(conss != NULL); /* for lint */ 3292 cons = conss[c]; 3293 assert(cons != NULL ); 3294 3295 /* in case the transformed is written only constraints are posted which are enabled in the current node */ 3296 assert(!transformed || SCIPconsIsEnabled(cons)); 3297 3298 conshdlr = SCIPconsGetHdlr(cons); 3299 assert( conshdlr != NULL ); 3300 3301 conshdlrname = SCIPconshdlrGetName(conshdlr); 3302 assert( transformed == SCIPconsIsTransformed(cons) ); 3303 3304 len = (int) strlen(SCIPconsGetName(cons)); 3305 3306 if( strcmp(conshdlrname, "linear") == 0 ) 3307 { 3308 SCIP_Real lhs = SCIPgetLhsLinear(scip, cons); 3309 SCIP_Real rhs = SCIPgetRhsLinear(scip, cons); 3310 3311 if( (SCIPisEQ(scip, lhs, rhs) && len > LP_MAX_NAMELEN) || ( !SCIPisEQ(scip, lhs, rhs) && len > LP_MAX_NAMELEN - 4) ) 3312 { 3313 SCIPwarningMessage(scip, "there is a constraint name which has to be cut down to %d characters;\n", LP_MAX_NAMELEN - 1); 3314 return; 3315 } 3316 } 3317 else if( len > LP_MAX_NAMELEN ) 3318 { 3319 SCIPwarningMessage(scip, "there is a constraint name which has to be cut down to %d characters;\n", LP_MAX_NAMELEN - 1); 3320 return; 3321 } 3322 3323 /* check if constraint name starts with a digit */ 3324 if( printwarning && isdigit((unsigned char)SCIPconsGetName(cons)[0]) ) 3325 { 3326 SCIPwarningMessage(scip, "violation of LP format - a constraint name starts with a digit; " \ 3327 "it is not possible to read the generated LP file with SCIP; " \ 3328 "use write/genproblem or write/gentransproblem for generic variable names\n"); 3329 printwarning = FALSE; 3330 } 3331 } 3332 } 3333 3334 /* 3335 * Callback methods of reader 3336 */ 3337 3338 /** copy method for reader plugins (called when SCIP copies plugins) */ 3339 static 3340 SCIP_DECL_READERCOPY(readerCopyLp) 3341 { /*lint --e{715}*/ 3342 assert(scip != NULL); 3343 assert(reader != NULL); 3344 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 3345 3346 /* call inclusion method of reader */ 3347 SCIP_CALL( SCIPincludeReaderLp(scip) ); 3348 3349 return SCIP_OKAY; 3350 } 3351 3352 /** destructor of reader to free user data (called when SCIP is exiting) */ 3353 static 3354 SCIP_DECL_READERFREE(readerFreeLp) 3355 { 3356 SCIP_READERDATA* readerdata; 3357 3358 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 3359 readerdata = SCIPreaderGetData(reader); 3360 assert(readerdata != NULL); 3361 SCIPfreeBlockMemory(scip, &readerdata); 3362 3363 return SCIP_OKAY; 3364 } 3365 3366 /** problem reading method of reader */ 3367 static 3368 SCIP_DECL_READERREAD(readerReadLp) 3369 { /*lint --e{715}*/ 3370 3371 SCIP_CALL( SCIPreadLp(scip, reader, filename, result) ); 3372 3373 return SCIP_OKAY; 3374 } 3375 3376 3377 /** problem writing method of reader */ 3378 static 3379 SCIP_DECL_READERWRITE(readerWriteLp) 3380 { /*lint --e{715}*/ 3381 assert(reader != NULL); 3382 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 3383 3384 SCIP_CALL( SCIPwriteLp(scip, file, name, transformed, objsense, objscale, objoffset, vars, 3385 nvars, nbinvars, nintvars, nimplvars, ncontvars, conss, nconss, result) ); 3386 3387 return SCIP_OKAY; 3388 } 3389 3390 3391 /* 3392 * reader specific interface methods 3393 */ 3394 3395 /** includes the lp file reader in SCIP */ 3396 SCIP_RETCODE SCIPincludeReaderLp( 3397 SCIP* scip /**< SCIP data structure */ 3398 ) 3399 { 3400 SCIP_READERDATA* readerdata; 3401 SCIP_READER* reader; 3402 3403 /* create reader data */ 3404 SCIP_CALL( SCIPallocBlockMemory(scip, &readerdata) ); 3405 3406 /* include reader */ 3407 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) ); 3408 3409 /* set non fundamental callbacks via setter functions */ 3410 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyLp) ); 3411 SCIP_CALL( SCIPsetReaderFree(scip, reader, readerFreeLp) ); 3412 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadLp) ); 3413 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteLp) ); 3414 3415 /* add lp-reader parameters */ 3416 SCIP_CALL( SCIPaddBoolParam(scip, 3417 "reading/" READER_NAME "/linearize-and-constraints", 3418 "should possible \"and\" constraint be linearized when writing the lp file?", 3419 &readerdata->linearizeands, TRUE, DEFAULT_LINEARIZE_ANDS, NULL, NULL) ); 3420 SCIP_CALL( SCIPaddBoolParam(scip, 3421 "reading/" READER_NAME "/aggrlinearization-ands", 3422 "should an aggregated linearization for and constraints be used?", 3423 &readerdata->aggrlinearizationands, TRUE, DEFAULT_AGGRLINEARIZATION_ANDS, NULL, NULL) ); 3424 3425 return SCIP_OKAY; 3426 } 3427 3428 3429 /** reads problem from file */ 3430 SCIP_RETCODE SCIPreadLp( 3431 SCIP* scip, /**< SCIP data structure */ 3432 SCIP_READER* reader, /**< the file reader itself */ 3433 const char* filename, /**< full path and name of file to read, or NULL if stdin should be used */ 3434 SCIP_RESULT* result /**< pointer to store the result of the file reading call */ 3435 ) 3436 { /*lint --e{715}*/ 3437 SCIP_RETCODE retcode; 3438 LPINPUT lpinput; 3439 int i; 3440 3441 assert(scip != NULL); 3442 assert(reader != NULL); 3443 3444 /* initialize LP input data */ 3445 lpinput.file = NULL; 3446 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &lpinput.linebuf, LP_MAX_LINELEN) ); 3447 lpinput.linebuf[0] = '\0'; 3448 lpinput.linebufsize = LP_MAX_LINELEN; 3449 lpinput.probname[0] = '\0'; 3450 lpinput.objname[0] = '\0'; 3451 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &lpinput.token, LP_MAX_LINELEN) ); /*lint !e506*/ 3452 lpinput.token[0] = '\0'; 3453 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &lpinput.tokenbuf, LP_MAX_LINELEN) ); /*lint !e506*/ 3454 lpinput.tokenbuf[0] = '\0'; 3455 for( i = 0; i < LP_MAX_PUSHEDTOKENS; ++i ) 3456 { 3457 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(lpinput.pushedtokens[i]), LP_MAX_LINELEN) ); /*lint !e866 !e506*/ 3458 } 3459 3460 lpinput.npushedtokens = 0; 3461 lpinput.linenumber = 0; 3462 lpinput.linepos = 0; 3463 lpinput.section = LP_START; 3464 lpinput.objsense = SCIP_OBJSENSE_MINIMIZE; 3465 lpinput.inlazyconstraints = FALSE; 3466 lpinput.inusercuts = FALSE; 3467 lpinput.haserror = FALSE; 3468 3469 SCIP_CALL( SCIPgetBoolParam(scip, "reading/initialconss", &(lpinput.initialconss)) ); 3470 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicconss", &(lpinput.dynamicconss)) ); 3471 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &(lpinput.dynamiccols)) ); 3472 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicrows", &(lpinput.dynamicrows)) ); 3473 3474 /* read the file */ 3475 retcode = readLPFile(scip, &lpinput, filename); 3476 3477 /* free dynamically allocated memory */ 3478 for( i = 0; i < LP_MAX_PUSHEDTOKENS; ++i ) 3479 { 3480 SCIPfreeBlockMemoryArray(scip, &lpinput.pushedtokens[i], LP_MAX_LINELEN); 3481 } 3482 SCIPfreeBlockMemoryArray(scip, &lpinput.tokenbuf, LP_MAX_LINELEN); 3483 SCIPfreeBlockMemoryArray(scip, &lpinput.token, LP_MAX_LINELEN); 3484 SCIPfreeBlockMemoryArray(scip, &lpinput.linebuf, lpinput.linebufsize); 3485 3486 if( retcode == SCIP_PLUGINNOTFOUND ) 3487 retcode = SCIP_READERROR; 3488 3489 /* check for correct return value */ 3490 SCIP_CALL( retcode ); 3491 3492 /* evaluate the result */ 3493 if( lpinput.haserror ) 3494 return SCIP_READERROR; 3495 else 3496 { 3497 /* set objective sense */ 3498 SCIP_CALL( SCIPsetObjsense(scip, lpinput.objsense) ); 3499 *result = SCIP_SUCCESS; 3500 } 3501 3502 return SCIP_OKAY; 3503 } 3504 3505 3506 /** writes problem to file */ 3507 SCIP_RETCODE SCIPwriteLp( 3508 SCIP* scip, /**< SCIP data structure */ 3509 FILE* file, /**< output file, or NULL if standard output should be used */ 3510 const char* name, /**< problem name */ 3511 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */ 3512 SCIP_OBJSENSE objsense, /**< objective sense */ 3513 SCIP_Real objscale, /**< scalar applied to objective function; external objective value is 3514 * extobj = objsense * objscale * (intobj + objoffset) */ 3515 SCIP_Real objoffset, /**< objective offset from bound shifting and fixing */ 3516 SCIP_VAR** vars, /**< array with active variables ordered binary, integer, implicit, continuous */ 3517 int nvars, /**< number of active variables in the problem */ 3518 int nbinvars, /**< number of binary variables */ 3519 int nintvars, /**< number of general integer variables */ 3520 int nimplvars, /**< number of implicit integer variables */ 3521 int ncontvars, /**< number of continuous variables */ 3522 SCIP_CONS** conss, /**< array with constraints of the problem */ 3523 int nconss, /**< number of constraints in the problem */ 3524 SCIP_RESULT* result /**< pointer to store the result of the file writing call */ 3525 ) 3526 { 3527 SCIP_READER* reader; 3528 SCIP_READERDATA* readerdata; 3529 SCIP_Bool linearizeands; 3530 SCIP_Bool aggrlinearizationands; 3531 int c; 3532 int v; 3533 3534 int linecnt; 3535 char linebuffer[LP_MAX_PRINTLEN+1]; 3536 3537 char varname[LP_MAX_NAMELEN]; 3538 char buffer[LP_MAX_PRINTLEN]; 3539 3540 SCIP_CONSHDLR* conshdlr; 3541 SCIP_CONSHDLR* conshdlrInd; 3542 const char* conshdlrname; 3543 SCIP_CONS* cons; 3544 SCIP_CONS** consSOS1; 3545 SCIP_CONS** consSOS2; 3546 SCIP_CONS** consExpr; 3547 SCIP_CONS** consIndicator; 3548 int nConsSOS1 = 0; 3549 int nConsSOS2 = 0; 3550 int nConsExpr = 0; 3551 int nConsIndicator = 0; 3552 char consname[LP_MAX_NAMELEN]; 3553 3554 SCIP_VAR** aggvars; 3555 SCIP_VAR** tmpvars; 3556 int tmpvarssize; 3557 int naggvars = 0; 3558 int saggvars; 3559 SCIP_HASHTABLE* varAggregated; 3560 SCIP_HASHMAP* consHidden; 3561 3562 SCIP_VAR** consvars; 3563 SCIP_Real* consvals; 3564 int nconsvars; 3565 3566 SCIP_VAR* var; 3567 SCIP_Real lb; 3568 SCIP_Real ub; 3569 3570 SCIP_Bool zeroobj; 3571 3572 assert(scip != NULL); 3573 3574 /* find indicator constraint handler */ 3575 conshdlrInd = SCIPfindConshdlr(scip, "indicator"); 3576 consHidden = NULL; 3577 3578 /* if indicator constraint handler is present */ 3579 if( conshdlrInd != NULL ) 3580 { 3581 /* create hashtable storing linear constraints that should not be output */ 3582 SCIP_CALL( SCIPhashmapCreate(&consHidden, SCIPblkmem(scip), 500) ); 3583 3584 /* loop through indicator constraints (works only in transformed problem) */ 3585 if( transformed ) 3586 { 3587 SCIP_CONS** consInd; 3588 int nConsInd; 3589 3590 consInd = SCIPconshdlrGetConss(conshdlrInd); 3591 nConsInd = SCIPconshdlrGetNConss(conshdlrInd); 3592 SCIPdebugMsg(scip, "Number of indicator constraints: %d\n", nConsInd); 3593 3594 for( c = 0; c < nConsInd; ++c ) 3595 { 3596 assert( consInd[c] != NULL ); 3597 cons = SCIPgetLinearConsIndicator(consInd[c]); 3598 3599 assert( !SCIPhashmapExists(consHidden, (void*) cons) ); 3600 SCIP_CALL( SCIPhashmapSetImage(consHidden, (void*) cons, (void*) TRUE) ); 3601 SCIPdebugMsg(scip, "Marked linear constraint <%s> as hidden.\n", SCIPconsGetName(cons)); 3602 } 3603 } 3604 else 3605 { 3606 /* otherwise we have to pass through all constraints */ 3607 for( c = 0; c < nconss; ++c ) 3608 { 3609 cons = conss[c]; 3610 assert( cons != NULL); 3611 3612 conshdlr = SCIPconsGetHdlr(cons); 3613 assert( conshdlr != NULL ); 3614 conshdlrname = SCIPconshdlrGetName(conshdlr); 3615 3616 if( strcmp(conshdlrname, "indicator") == 0 ) 3617 { 3618 SCIP_CONS* lincons; 3619 3620 lincons = SCIPgetLinearConsIndicator(cons); 3621 assert( lincons != NULL ); 3622 3623 assert( !SCIPhashmapExists(consHidden, (void*) lincons) ); 3624 SCIP_CALL( SCIPhashmapSetImage(consHidden, (void*) lincons, (void*) TRUE) ); 3625 SCIPdebugMsg(scip, "Marked linear constraint <%s> as hidden.\n", SCIPconsGetName(lincons)); 3626 } 3627 } 3628 } 3629 } 3630 3631 /* check if the variable names are not to long */ 3632 checkVarnames(scip, vars, nvars); 3633 /* check if the constraint names are to long */ 3634 checkConsnames(scip, conss, nconss, transformed); 3635 3636 /* print statistics as comment to file */ 3637 SCIPinfoMessage(scip, file, "\\ SCIP STATISTICS\n"); 3638 SCIPinfoMessage(scip, file, "\\ Problem name : %s\n", name); 3639 SCIPinfoMessage(scip, file, "\\ Variables : %d (%d binary, %d integer, %d implicit integer, %d continuous)\n", 3640 nvars, nbinvars, nintvars, nimplvars, ncontvars); 3641 SCIPinfoMessage(scip, file, "\\ Constraints : %d\n", nconss); 3642 3643 /* print objective sense */ 3644 SCIPinfoMessage(scip, file, "%s\n", objsense == SCIP_OBJSENSE_MINIMIZE ? "Minimize" : "Maximize"); 3645 3646 clearLine(linebuffer, &linecnt); 3647 appendLine(scip, file, linebuffer, &linecnt, " Obj:"); 3648 3649 zeroobj = TRUE; 3650 for( v = 0; v < nvars; ++v ) 3651 { 3652 var = vars[v]; 3653 3654 #ifndef NDEBUG 3655 /* in case the original problem has to be written, the variables have to be either "original" or "negated" */ 3656 if( ! transformed ) 3657 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED ); 3658 #endif 3659 3660 if( SCIPisZero(scip, SCIPvarGetObj(var)) ) 3661 continue; 3662 3663 zeroobj = FALSE; 3664 3665 /* we start a new line; therefore we tab this line */ 3666 if( linecnt == 0 ) 3667 appendLine(scip, file, linebuffer, &linecnt, " "); 3668 3669 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var)); 3670 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g %s", objscale * SCIPvarGetObj(var), varname ); 3671 3672 appendLine(scip, file, linebuffer, &linecnt, buffer); 3673 } 3674 3675 /* add objective offset */ 3676 if ( ! SCIPisZero(scip, objoffset) ) 3677 { 3678 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %+.15g", objscale * objoffset); 3679 appendLine(scip, file, linebuffer, &linecnt, buffer); 3680 } 3681 else 3682 { 3683 /* add a linear term to avoid troubles when reading the lp file with another MIP solver */ 3684 if( zeroobj && nvars >= 1 ) 3685 { 3686 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(vars[0])); 3687 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " 0 %s", varname ); 3688 3689 appendLine(scip, file, linebuffer, &linecnt, buffer); 3690 } 3691 } 3692 3693 endLine(scip, file, linebuffer, &linecnt); 3694 3695 /* print "Subject to" section */ 3696 SCIPinfoMessage(scip, file, "Subject to\n"); 3697 3698 reader = SCIPfindReader(scip, READER_NAME); 3699 if( reader != NULL ) 3700 { 3701 readerdata = SCIPreaderGetData(reader); 3702 assert(readerdata != NULL); 3703 3704 linearizeands = readerdata->linearizeands; 3705 aggrlinearizationands = readerdata->aggrlinearizationands; 3706 } 3707 else 3708 { 3709 linearizeands = DEFAULT_LINEARIZE_ANDS; 3710 aggrlinearizationands = DEFAULT_AGGRLINEARIZATION_ANDS; 3711 } 3712 3713 /* collect SOS, quadratic, and SOC constraints in array for later output */ 3714 SCIP_CALL( SCIPallocBufferArray(scip, &consSOS1, nconss) ); 3715 SCIP_CALL( SCIPallocBufferArray(scip, &consSOS2, nconss) ); 3716 SCIP_CALL( SCIPallocBufferArray(scip, &consExpr, nconss) ); 3717 SCIP_CALL( SCIPallocBufferArray(scip, &consIndicator, nconss) ); 3718 3719 tmpvarssize = SCIPgetNTotalVars(scip); 3720 SCIP_CALL( SCIPallocBufferArray(scip, &tmpvars, tmpvarssize) ); 3721 3722 for( c = 0; c < nconss; ++c ) 3723 { 3724 cons = conss[c]; 3725 assert( cons != NULL); 3726 3727 /* in case the transformed is written only constraints are posted which are enabled in the current node */ 3728 assert(!transformed || SCIPconsIsEnabled(cons)); 3729 3730 /* skip marked constraints in connection with indicator constraints */ 3731 if( conshdlrInd != NULL && SCIPhashmapExists(consHidden, (void*) cons) ) 3732 { 3733 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 ); 3734 continue; 3735 } 3736 3737 conshdlr = SCIPconsGetHdlr(cons); 3738 assert( conshdlr != NULL ); 3739 3740 (void) SCIPsnprintf(consname, LP_MAX_NAMELEN, "%s", SCIPconsGetName(cons)); 3741 conshdlrname = SCIPconshdlrGetName(conshdlr); 3742 assert( transformed == SCIPconsIsTransformed(cons) ); 3743 3744 if( strcmp(conshdlrname, "linear") == 0 ) 3745 { 3746 SCIP_CALL( printQuadraticCons(scip, file, consname, 3747 SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons), 3748 NULL, SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), transformed) ); 3749 } 3750 else if( strcmp(conshdlrname, "setppc") == 0 ) 3751 { 3752 consvars = SCIPgetVarsSetppc(scip, cons); 3753 nconsvars = SCIPgetNVarsSetppc(scip, cons); 3754 3755 switch( SCIPgetTypeSetppc(scip, cons) ) 3756 { 3757 case SCIP_SETPPCTYPE_PARTITIONING : 3758 SCIP_CALL( printQuadraticCons(scip, file, consname, 3759 consvars, NULL, nconsvars, NULL, 1.0, 1.0, transformed) ); 3760 break; 3761 case SCIP_SETPPCTYPE_PACKING : 3762 SCIP_CALL( printQuadraticCons(scip, file, consname, 3763 consvars, NULL, nconsvars, NULL, -SCIPinfinity(scip), 1.0, transformed) ); 3764 break; 3765 case SCIP_SETPPCTYPE_COVERING : 3766 SCIP_CALL( printQuadraticCons(scip, file, consname, 3767 consvars, NULL, nconsvars, NULL, 1.0, SCIPinfinity(scip), transformed) ); 3768 break; 3769 } 3770 } 3771 else if( strcmp(conshdlrname, "logicor") == 0 ) 3772 { 3773 SCIP_CALL( printQuadraticCons(scip, file, consname, 3774 SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), 3775 NULL, 1.0, SCIPinfinity(scip), transformed) ); 3776 } 3777 else if( strcmp(conshdlrname, "knapsack") == 0 ) 3778 { 3779 SCIP_Longint* weights; 3780 3781 consvars = SCIPgetVarsKnapsack(scip, cons); 3782 nconsvars = SCIPgetNVarsKnapsack(scip, cons); 3783 3784 /* copy Longint array to SCIP_Real array */ 3785 weights = SCIPgetWeightsKnapsack(scip, cons); 3786 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) ); 3787 for( v = 0; v < nconsvars; ++v ) 3788 consvals[v] = (SCIP_Real)weights[v]; 3789 3790 SCIP_CALL( printQuadraticCons(scip, file, consname, consvars, consvals, nconsvars, 3791 NULL, -SCIPinfinity(scip), (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), transformed) ); 3792 3793 SCIPfreeBufferArray(scip, &consvals); 3794 } 3795 else if( strcmp(conshdlrname, "varbound") == 0 ) 3796 { 3797 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) ); 3798 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) ); 3799 3800 consvars[0] = SCIPgetVarVarbound(scip, cons); 3801 consvars[1] = SCIPgetVbdvarVarbound(scip, cons); 3802 3803 consvals[0] = 1.0; 3804 consvals[1] = SCIPgetVbdcoefVarbound(scip, cons); 3805 3806 SCIP_CALL( printQuadraticCons(scip, file, consname, consvars, consvals, 2, NULL, 3807 SCIPgetLhsVarbound(scip, cons), SCIPgetRhsVarbound(scip, cons), transformed) ); 3808 3809 SCIPfreeBufferArray(scip, &consvals); 3810 SCIPfreeBufferArray(scip, &consvars); 3811 } 3812 else if( strcmp(conshdlrname, "SOS1") == 0 ) 3813 { 3814 /* store constraint */ 3815 consSOS1[nConsSOS1++] = cons; 3816 } 3817 else if( strcmp(conshdlrname, "SOS2") == 0 ) 3818 { 3819 /* store constraint */ 3820 consSOS2[nConsSOS2++] = cons; 3821 } 3822 else if( strcmp(conshdlrname, "indicator") == 0 ) 3823 { 3824 SCIP_CONS* lincons; 3825 SCIP_VAR* binvar; 3826 SCIP_VAR* slackvar; 3827 SCIP_VAR** linvars; 3828 SCIP_Real* linvals; 3829 int nlinvars; 3830 int cnt; 3831 int rhs; 3832 3833 assert( conshdlrInd != NULL ); 3834 3835 lincons = SCIPgetLinearConsIndicator(cons); 3836 binvar = SCIPgetBinaryVarIndicator(cons); 3837 slackvar = SCIPgetSlackVarIndicator(cons); 3838 3839 assert( lincons != NULL ); 3840 assert( binvar != NULL ); 3841 assert( slackvar != NULL ); 3842 3843 rhs = 1; 3844 if ( SCIPvarIsNegated(binvar) ) 3845 { 3846 rhs = 0; 3847 binvar = SCIPvarGetNegatedVar(binvar); 3848 } 3849 3850 /* collect linear constraint information (remove slack variable) */ 3851 linvars = SCIPgetVarsLinear(scip, lincons); 3852 linvals = SCIPgetValsLinear(scip, lincons); 3853 nlinvars = SCIPgetNVarsLinear(scip, lincons); 3854 assert( linvars != NULL ); 3855 assert( linvals != NULL ); 3856 3857 /* linvars always contains slack variable, thus nlinvars >= 1 */ 3858 if( nlinvars > 1 && !SCIPconsIsDeleted(lincons) ) 3859 { 3860 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(binvar) ); 3861 if( strlen(consname) > 0 ) 3862 SCIPinfoMessage(scip, file, " %s: %s = %d ->", consname, varname, rhs); 3863 else 3864 SCIPinfoMessage(scip, file, " %s = %d ->", varname, rhs); 3865 3866 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nlinvars-1) ); 3867 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nlinvars-1) ); 3868 3869 cnt = 0; 3870 for( v = 0; v < nlinvars; ++v ) 3871 { 3872 var = linvars[v]; 3873 if( var != slackvar ) 3874 { 3875 consvars[cnt] = var; 3876 consvals[cnt++] = linvals[v]; 3877 } 3878 } 3879 /* if slackvariable is fixed, it might have been removed from constraint */ 3880 assert( nlinvars == 0 || cnt == nlinvars-1 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(slackvar), SCIPvarGetUbGlobal(slackvar)) ); 3881 3882 SCIP_CALL( printQuadraticCons(scip, file, "", consvars, consvals, cnt, NULL, 3883 SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons), transformed) ); 3884 3885 SCIPfreeBufferArray(scip, &consvals); 3886 SCIPfreeBufferArray(scip, &consvars); 3887 } 3888 3889 /* store constraint */ 3890 consIndicator[nConsIndicator++] = cons; 3891 } 3892 else if( strcmp(conshdlrname, "nonlinear") == 0 ) 3893 { 3894 SCIP_Bool isquadratic; 3895 3896 /* check whether there is a quadratic representation of the nonlinear constraint */ 3897 SCIP_CALL( SCIPcheckQuadraticNonlinear(scip, cons, &isquadratic) ); 3898 3899 /* we cannot handle nonlinear constraint that are not quadratically representable */ 3900 if( !isquadratic ) 3901 { 3902 SCIPwarningMessage(scip, "constraint handler <%s> cannot print constraint\n", SCIPconshdlrGetName(SCIPconsGetHdlr(cons))); 3903 SCIPinfoMessage(scip, file, "\\ "); 3904 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3905 SCIPinfoMessage(scip, file, ";\n"); 3906 3907 return SCIP_OKAY; 3908 } 3909 3910 SCIP_CALL( printQuadraticCons(scip, file, consname, NULL, NULL, 0, SCIPgetExprNonlinear(cons), 3911 SCIPgetLhsNonlinear(cons), SCIPgetRhsNonlinear(cons), transformed) ); 3912 3913 consExpr[nConsExpr++] = cons; 3914 } 3915 else if( strcmp(conshdlrname, "and") == 0 ) 3916 { 3917 if( linearizeands ) 3918 { 3919 SCIP_CALL( printAndCons(scip, file, consname, cons, aggrlinearizationands, transformed) ); 3920 } 3921 else 3922 { 3923 SCIPwarningMessage(scip, "change parameter \"reading/" READER_NAME "/linearize-and-constraints\" to TRUE to print and-constraints\n"); 3924 SCIPinfoMessage(scip, file, "\\ "); 3925 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3926 SCIPinfoMessage(scip, file, ";\n"); 3927 } 3928 } 3929 else 3930 { 3931 SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname ); 3932 SCIPinfoMessage(scip, file, "\\ "); 3933 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3934 SCIPinfoMessage(scip, file, ";\n"); 3935 } 3936 } 3937 3938 /* allocate array for storing aggregated and negated variables (dynamically adjusted) */ 3939 saggvars = MAX(10, nvars); 3940 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &aggvars, saggvars) ); 3941 3942 /* create hashtable for storing aggregated variables */ 3943 SCIP_CALL( SCIPhashtableCreate(&varAggregated, SCIPblkmem(scip), saggvars, hashGetKeyVar, hashKeyEqVar, hashKeyValVar, NULL) ); 3944 3945 /* check for aggregated variables in SOS1 constraints and output aggregations as linear constraints */ 3946 for( c = 0; c < nConsSOS1; ++c ) 3947 { 3948 cons = consSOS1[c]; 3949 consvars = SCIPgetVarsSOS1(scip, cons); 3950 nconsvars = SCIPgetNVarsSOS1(scip, cons); 3951 3952 SCIP_CALL( collectAggregatedVars(scip, consvars, nconsvars, &aggvars, &naggvars, &saggvars, varAggregated) ); 3953 } 3954 3955 /* check for aggregated variables in SOS2 constraints and output aggregations as linear constraints */ 3956 for( c = 0; c < nConsSOS2; ++c ) 3957 { 3958 cons = consSOS2[c]; 3959 consvars = SCIPgetVarsSOS2(scip, cons); 3960 nconsvars = SCIPgetNVarsSOS2(scip, cons); 3961 3962 SCIP_CALL( collectAggregatedVars(scip, consvars, nconsvars, &aggvars, &naggvars, &saggvars, varAggregated) ); 3963 } 3964 3965 /* check for aggregated variables in nonlinear constraints and output aggregations as linear constraints */ 3966 for( c = 0; c < nConsExpr; ++c ) 3967 { 3968 SCIP_Bool success; 3969 int ntmpvars; 3970 3971 /* get variables of the nonlinear constraint */ 3972 SCIP_CALL( SCIPgetConsNVars(scip, consExpr[c], &ntmpvars, &success) ); 3973 assert(success); 3974 if( ntmpvars > tmpvarssize ) 3975 { 3976 tmpvarssize = SCIPcalcMemGrowSize(scip, ntmpvars); 3977 SCIP_CALL( SCIPreallocBufferArray(scip, &tmpvars, tmpvarssize) ); 3978 } 3979 SCIP_CALL( SCIPgetConsVars(scip, consExpr[c], tmpvars, tmpvarssize, &success) ); 3980 assert(success); 3981 3982 SCIP_CALL( collectAggregatedVars(scip, tmpvars, ntmpvars, &aggvars, &naggvars, &saggvars, varAggregated) ); 3983 } 3984 3985 /* check for aggregated variables in indicator constraints and output aggregations as linear constraints */ 3986 for( c = 0; c < nConsIndicator; ++c ) 3987 { 3988 SCIP_VAR* binvar; 3989 3990 cons = consIndicator[c]; 3991 binvar = SCIPgetBinaryVarIndicator(cons); 3992 if ( ! SCIPvarIsNegated(binvar) ) 3993 { 3994 /* we take care of negated variables above, but not of aggregated variables */ 3995 SCIP_CALL( collectAggregatedVars(scip, &binvar, 1, &aggvars, &naggvars, &saggvars, varAggregated) ); 3996 } 3997 } 3998 3999 /* print aggregation constraints */ 4000 SCIP_CALL( printAggregatedCons(scip, file, transformed, nvars, naggvars, aggvars) ); 4001 4002 /* print "Bounds" section */ 4003 SCIPinfoMessage(scip, file, "Bounds\n"); 4004 for( v = 0; v < nvars; ++v ) 4005 { 4006 var = vars[v]; 4007 assert( var != NULL ); 4008 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4009 4010 if( transformed ) 4011 { 4012 /* in case the transformed is written only local bounds are posted which are valid in the current node */ 4013 lb = SCIPvarGetLbLocal(var); 4014 ub = SCIPvarGetUbLocal(var); 4015 } 4016 else 4017 { 4018 lb = SCIPvarGetLbOriginal(var); 4019 ub = SCIPvarGetUbOriginal(var); 4020 } 4021 4022 if( SCIPisInfinity(scip, -lb) && SCIPisInfinity(scip, ub) ) 4023 SCIPinfoMessage(scip, file, " %s free\n", varname); 4024 else 4025 { 4026 /* print lower bound */ 4027 if( SCIPisInfinity(scip, -lb) ) 4028 SCIPinfoMessage(scip, file, " -inf <= "); 4029 else 4030 { 4031 if( SCIPisZero(scip, lb) ) 4032 { 4033 /* variables are nonnegative by default - so we skip these variables */ 4034 if( SCIPisInfinity(scip, ub) ) 4035 continue; 4036 lb = 0.0; 4037 } 4038 4039 SCIPinfoMessage(scip, file, " %.15g <= ", lb); 4040 } 4041 /* print variable name */ 4042 SCIPinfoMessage(scip, file, "%s", varname); 4043 4044 /* print upper bound as far this one is not infinity */ 4045 if( !SCIPisInfinity(scip, ub) ) 4046 SCIPinfoMessage(scip, file, " <= %.15g", ub); 4047 4048 SCIPinfoMessage(scip, file, "\n"); 4049 } 4050 } 4051 4052 /* output aggregated variables as 'free' */ 4053 for( v = 0; v < naggvars; ++v ) 4054 { 4055 var = aggvars[v]; 4056 assert( var != NULL ); 4057 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4058 4059 SCIPinfoMessage(scip, file, " %s free\n", varname); 4060 } 4061 4062 /* print binaries section */ 4063 if( nbinvars > 0 ) 4064 { 4065 SCIPinfoMessage(scip, file, "Binaries\n"); 4066 4067 clearLine(linebuffer, &linecnt); 4068 4069 /* output active variables */ 4070 for( v = 0; v < nvars; ++v ) 4071 { 4072 var = vars[v]; 4073 assert( var != NULL ); 4074 4075 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY ) 4076 { 4077 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4078 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s", varname); 4079 appendLine(scip, file, linebuffer, &linecnt, buffer); 4080 } 4081 } 4082 4083 /* possibly output aggregated variables */ 4084 for( v = 0; v < naggvars; ++v ) 4085 { 4086 var = aggvars[v]; 4087 assert( var != NULL ); 4088 4089 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY ) 4090 { 4091 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4092 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s", varname); 4093 appendLine(scip, file, linebuffer, &linecnt, buffer); 4094 } 4095 } 4096 4097 endLine(scip, file, linebuffer, &linecnt); 4098 } 4099 4100 /* print generals section */ 4101 if( nintvars > 0 ) 4102 { 4103 SCIPinfoMessage(scip, file, "Generals\n"); 4104 4105 /* output active variables */ 4106 for( v = 0; v < nvars; ++v ) 4107 { 4108 var = vars[v]; 4109 assert( var != NULL ); 4110 4111 if( SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER ) 4112 { 4113 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4114 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s", varname); 4115 appendLine(scip, file, linebuffer, &linecnt, buffer); 4116 } 4117 } 4118 4119 /* possibly output aggregated variables */ 4120 for( v = 0; v < naggvars; ++v ) 4121 { 4122 var = aggvars[v]; 4123 assert( var != NULL ); 4124 4125 if( SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER ) 4126 { 4127 (void) SCIPsnprintf(varname, LP_MAX_NAMELEN, "%s", SCIPvarGetName(var) ); 4128 (void) SCIPsnprintf(buffer, LP_MAX_PRINTLEN, " %s", varname); 4129 appendLine(scip, file, linebuffer, &linecnt, buffer); 4130 } 4131 } 4132 4133 endLine(scip, file, linebuffer, &linecnt); 4134 } 4135 4136 /* free space */ 4137 SCIPfreeBlockMemoryArray(scip, &aggvars, saggvars); 4138 SCIPhashtableFree(&varAggregated); 4139 if( conshdlrInd != NULL ) 4140 SCIPhashmapFree(&consHidden); 4141 4142 /* print SOS section */ 4143 if( nConsSOS1 > 0 || nConsSOS2 > 0 ) 4144 { 4145 SCIP_Real* weights; 4146 SCIPinfoMessage(scip, file, "SOS\n"); 4147 4148 /* first output SOS1 constraints */ 4149 for( c = 0; c < nConsSOS1; ++c ) 4150 { 4151 cons = consSOS1[c]; 4152 consvars = SCIPgetVarsSOS1(scip, cons); 4153 nconsvars = SCIPgetNVarsSOS1(scip, cons); 4154 weights = SCIPgetWeightsSOS1(scip, cons); 4155 4156 (void) SCIPsnprintf(consname, LP_MAX_NAMELEN, "%s", SCIPconsGetName(cons) ); 4157 printSosCons(scip, file, consname, consvars, weights, nconsvars, 1); 4158 } 4159 4160 /* next output SOS2 constraints */ 4161 for( c = 0; c < nConsSOS2; ++c ) 4162 { 4163 cons = consSOS2[c]; 4164 consvars = SCIPgetVarsSOS2(scip, cons); 4165 nconsvars = SCIPgetNVarsSOS2(scip, cons); 4166 weights = SCIPgetWeightsSOS2(scip, cons); 4167 4168 (void) SCIPsnprintf(consname, LP_MAX_NAMELEN, "%s", SCIPconsGetName(cons) ); 4169 printSosCons(scip, file, consname, consvars, weights, nconsvars, 2); 4170 } 4171 } 4172 4173 /* free space */ 4174 SCIPfreeBufferArray(scip, &tmpvars); 4175 SCIPfreeBufferArray(scip, &consIndicator); 4176 SCIPfreeBufferArray(scip, &consExpr); 4177 SCIPfreeBufferArray(scip, &consSOS2); 4178 SCIPfreeBufferArray(scip, &consSOS1); 4179 4180 /* end of lp format */ 4181 SCIPinfoMessage(scip, file, "%s\n", "End"); 4182 4183 *result = SCIP_SUCCESS; 4184 4185 return SCIP_OKAY; 4186 } 4187