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_opb.c 26 * @ingroup DEFPLUGINS_READER 27 * @brief pseudo-Boolean file reader (opb format) 28 * @author Stefan Heinz 29 * @author Michael Winkler 30 * 31 * This file reader parses the @a opb format and is also used by the @a wbo reader for the @a wbo format. For a 32 * detailed description of this format see 33 * 34 * - http://www.cril.univ-artois.fr/PB07/solver_req.html 35 * - http://www.cril.univ-artois.fr/PB10/format.pdf 36 * 37 * The syntax of the input file format can be described by a simple Backus-Naur 38 * form. \<formula\> is the start symbol of this grammar. 39 * 40 * \<formula\>::= \<sequence_of_comments\> 41 * [\<objective\>] | [\<softheader\>] 42 * \<sequence_of_comments_or_constraints\> 43 * 44 * \<sequence_of_comments\>::= \<comment\> [\<sequence_of_comments\>] 45 * \<comment\>::= "*" \<any_sequence_of_characters_other_than_EOL\> \<EOL\> 46 * \<sequence_of_comments_or_constraints\>::=\<comment_or_constraint\> [\<sequence_of_comments_or_constraints\>] 47 * \<comment_or_constraint\>::=\<comment\>|\<constraint\> 48 * 49 * \<objective\>::= "min:" \<zeroOrMoreSpace\> \<sum\> ";" 50 * \<constraint\>::= \<sum\> \<relational_operator\> \<zeroOrMoreSpace\> \<integer\> \<zeroOrMoreSpace\> ";" 51 * 52 * \<sum\>::= \<weightedterm\> | \<weightedterm\> \<sum\> 53 * \<weightedterm\>::= \<integer\> \<oneOrMoreSpace\> \<term\> \<oneOrMoreSpace\> 54 * 55 * \<integer\>::= \<unsigned_integer\> | "+" \<unsigned_integer\> | "-" \<unsigned_integer\> 56 * \<unsigned_integer\>::= \<digit\> | \<digit\>\<unsigned_integer\> 57 * 58 * \<relational_operator\>::= "\>=" | "=" 59 * 60 * \<variablename\>::= "x" \<unsigned_integer\> 61 * 62 * \<oneOrMoreSpace\>::= " " [\<oneOrMoreSpace\>] 63 * \<zeroOrMoreSpace\>::= [" " \<zeroOrMoreSpace\>] 64 * 65 * For linear pseudo-Boolean instances, \<term\> is defined as 66 * 67 * \<term\>::=\<variablename\> 68 * 69 * For non-linear instances, \<term\> is defined as 70 * 71 * \<term\>::= \<oneOrMoreLiterals\> 72 * \<oneOrMoreLiterals\>::= \<literal\> | \<literal\> \<oneOrMoreSpace\> \<oneOrMoreLiterals\> 73 * \<literal\>::= \<variablename\> | "~"\<variablename\> 74 * 75 * For wbo-files are the following additional/changed things possible. 76 * 77 * \<softheader\>::= "soft:" [\<unsigned integer\>] ";" 78 * 79 * \<comment_or_constraint\>::=\<comment\>|\<constraint\>|\<softconstraint\> 80 * 81 * \<softconstraint\>::= "[" \<zeroOrMoreSpace\> \<unsigned integer\> \<zeroOrMoreSpace\> "]" \<constraint\> 82 * 83 */ 84 85 /* Our parser should also be lax by handling variable names and it's possible to read doubles instead of integer and 86 * possible some more :). */ 87 88 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 89 90 #include "blockmemshell/memory.h" 91 #include <ctype.h> 92 #include "scip/cons_and.h" 93 #include "scip/cons_indicator.h" 94 #include "scip/cons_knapsack.h" 95 #include "scip/cons_linear.h" 96 #include "scip/cons_logicor.h" 97 #include "scip/cons_pseudoboolean.h" 98 #include "scip/cons_setppc.h" 99 #include "scip/cons_varbound.h" 100 #include "scip/debug.h" 101 #include "scip/pub_cons.h" 102 #include "scip/pub_fileio.h" 103 #include "scip/pub_message.h" 104 #include "scip/pub_misc.h" 105 #include "scip/pub_misc_sort.h" 106 #include "scip/pub_reader.h" 107 #include "scip/pub_var.h" 108 #include "scip/reader_opb.h" 109 #include "scip/scip_cons.h" 110 #include "scip/scip_mem.h" 111 #include "scip/scip_message.h" 112 #include "scip/scip_numerics.h" 113 #include "scip/scip_param.h" 114 #include "scip/scip_prob.h" 115 #include "scip/scip_reader.h" 116 #include "scip/scip_solvingstats.h" 117 #include "scip/scip_var.h" 118 #include <stdlib.h> 119 #include <string.h> 120 121 #if !defined(_WIN32) && !defined(_WIN64) 122 #include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */ 123 #endif 124 125 #define READER_NAME "opbreader" 126 #define READER_DESC "file reader for pseudo-Boolean problem in opb format" 127 #define READER_EXTENSION "opb" 128 129 #define GENCONSNAMES TRUE /* remove if no constraint names should be generated */ 130 #define LINEAROBJECTIVE TRUE /* will all non-linear parts inside the objective function be linearized or will 131 * an artificial integer variable be created which will represent the objective 132 * function 133 */ 134 135 #define INDICATORVARNAME "indicatorvar" /* standard part of name for all indicator variables */ 136 #define INDICATORSLACKVARNAME "indslack" /* standard part of name for all indicator slack variables; should be the same in cons_indicator */ 137 #define TOPCOSTCONSNAME "topcostcons" /* standard name for artificial topcost constraint in wbo problems */ 138 139 /* 140 * Data structures 141 */ 142 #define OPB_MAX_LINELEN 65536 /**< size of the line buffer for reading or writing */ 143 #define OPB_MAX_PUSHEDTOKENS 2 144 #define OPB_INIT_COEFSSIZE 8192 145 146 /** Section in OPB File */ 147 enum OpbExpType 148 { 149 OPB_EXP_NONE, 150 OPB_EXP_UNSIGNED, 151 OPB_EXP_SIGNED 152 }; 153 typedef enum OpbExpType OPBEXPTYPE; 154 155 enum OpbSense 156 { 157 OPB_SENSE_NOTHING, 158 OPB_SENSE_LE, 159 OPB_SENSE_GE, 160 OPB_SENSE_EQ 161 }; 162 typedef enum OpbSense OPBSENSE; 163 164 /** OPB reading data */ 165 struct OpbInput 166 { 167 SCIP_FILE* file; 168 char* linebuf; 169 char* token; 170 char* tokenbuf; 171 char* pushedtokens[OPB_MAX_PUSHEDTOKENS]; 172 int npushedtokens; 173 int linenumber; 174 int linepos; 175 int linebufsize; 176 SCIP_OBJSENSE objsense; 177 SCIP_Bool eof; 178 SCIP_Bool haserror; 179 int nproblemcoeffs; 180 SCIP_Bool wbo; 181 SCIP_Real topcost; 182 int nindvars; 183 #if GENCONSNAMES == TRUE 184 int consnumber; 185 #endif 186 }; 187 188 typedef struct OpbInput OPBINPUT; 189 190 static const char commentchars[] = "*"; 191 /* 192 * Local methods (for reading) 193 */ 194 195 /** issues an error message and marks the OPB data to have errors */ 196 static 197 void syntaxError( 198 SCIP* scip, /**< SCIP data structure */ 199 OPBINPUT* opbinput, /**< OPB reading data */ 200 const char* msg /**< error message */ 201 ) 202 { 203 assert(scip != NULL); 204 assert(opbinput != NULL); 205 206 SCIPerrorMessage("Syntax error in line %d: %s found <%s>\n", opbinput->linenumber, msg, opbinput->token); 207 if( opbinput->linebuf[opbinput->linebufsize - 1] == '\n' ) 208 { 209 SCIPerrorMessage(" input: %s", opbinput->linebuf); 210 } 211 else 212 { 213 SCIPerrorMessage(" input: %s\n", opbinput->linebuf); 214 } 215 216 opbinput->haserror = TRUE; 217 } 218 219 /** returns whether a syntax error was detected */ 220 static 221 SCIP_Bool hasError( 222 OPBINPUT* opbinput /**< OPB reading data */ 223 ) 224 { 225 assert(opbinput != NULL); 226 227 return opbinput->haserror; 228 } 229 230 /** returns whether the given character is a token delimiter */ 231 static 232 SCIP_Bool isDelimChar( 233 char c /**< input character */ 234 ) 235 { 236 switch (c) 237 { 238 case ' ': 239 case '\f': 240 case '\n': 241 case '\r': 242 case '\t': 243 case '\v': 244 case '\0': 245 return TRUE; 246 default: 247 return FALSE; 248 } 249 } 250 251 /** returns whether the given character is a single token */ 252 static 253 SCIP_Bool isTokenChar( 254 char c /**< input character */ 255 ) 256 { 257 switch (c) 258 { 259 case '-': 260 case '+': 261 case ':': 262 case '<': 263 case '>': 264 case '=': 265 case '[': 266 case ']': 267 case ';': 268 return TRUE; 269 default: 270 return FALSE; 271 } 272 } 273 274 /** returns whether the current character is member of a value string */ 275 static 276 SCIP_Bool isValueChar( 277 char c, /**< input character */ 278 char nextc, /**< next input character */ 279 SCIP_Bool firstchar, /**< is the given character the first char of the token? */ 280 SCIP_Bool* hasdot, /**< pointer to update the dot flag */ 281 OPBEXPTYPE* exptype /**< pointer to update the exponent type */ 282 ) 283 { 284 assert(hasdot != NULL); 285 assert(exptype != NULL); 286 287 if( isdigit((unsigned char)c) ) 288 return TRUE; 289 else if( (*exptype == OPB_EXP_NONE) && !(*hasdot) && (c == '.') ) 290 { 291 *hasdot = TRUE; 292 return TRUE; 293 } 294 else if( !firstchar && (*exptype == OPB_EXP_NONE) && (c == 'e' || c == 'E') ) 295 { 296 if( nextc == '+' || nextc == '-' ) 297 { 298 *exptype = OPB_EXP_SIGNED; 299 return TRUE; 300 } 301 else if( isdigit((unsigned char)nextc) ) 302 { 303 *exptype = OPB_EXP_UNSIGNED; 304 return TRUE; 305 } 306 } 307 else if( (*exptype == OPB_EXP_SIGNED) && (c == '+' || c == '-') ) 308 { 309 *exptype = OPB_EXP_UNSIGNED; 310 return TRUE; 311 } 312 313 return FALSE; 314 } 315 316 /** reads the next line from the input file into the line buffer; skips comments; 317 * returns whether a line could be read 318 */ 319 static 320 SCIP_Bool getNextLine( 321 SCIP* scip, /**< SCIP data structure */ 322 OPBINPUT* opbinput /**< OPB reading data */ 323 ) 324 { 325 int i; 326 327 assert(opbinput != NULL); 328 329 /* read next line */ 330 opbinput->linepos = 0; 331 opbinput->linebuf[opbinput->linebufsize - 2] = '\0'; 332 333 if( SCIPfgets(opbinput->linebuf, opbinput->linebufsize, opbinput->file) == NULL ) 334 return FALSE; 335 336 opbinput->linenumber++; 337 338 /* if line is too long for our buffer reallocate buffer */ 339 while( opbinput->linebuf[opbinput->linebufsize - 2] != '\0' ) 340 { 341 int newsize; 342 343 newsize = SCIPcalcMemGrowSize(scip, opbinput->linebufsize + 1); 344 SCIP_CALL_ABORT( SCIPreallocBlockMemoryArray(scip, &opbinput->linebuf, opbinput->linebufsize, newsize) ); 345 346 opbinput->linebuf[newsize-2] = '\0'; 347 if ( SCIPfgets(opbinput->linebuf + opbinput->linebufsize - 1, newsize - opbinput->linebufsize + 1, opbinput->file) == NULL ) 348 return FALSE; 349 opbinput->linebufsize = newsize; 350 } 351 352 opbinput->linebuf[opbinput->linebufsize - 1] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */ 353 354 /* skip characters after comment symbol */ 355 for( i = 0; commentchars[i] != '\0'; ++i ) 356 { 357 char* commentstart; 358 359 commentstart = strchr(opbinput->linebuf, commentchars[i]); 360 if( commentstart != NULL ) 361 { 362 *commentstart = '\0'; 363 *(commentstart+1) = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */ 364 break; 365 } 366 } 367 368 SCIPdebugMsg(scip, "%s\n", opbinput->linebuf); 369 370 return TRUE; 371 } 372 373 /** swaps the addresses of two pointers */ 374 static 375 void swapPointers( 376 char** pointer1, /**< first pointer */ 377 char** pointer2 /**< second pointer */ 378 ) 379 { 380 char* tmp; 381 382 tmp = *pointer1; 383 *pointer1 = *pointer2; 384 *pointer2 = tmp; 385 } 386 387 /** reads the next token from the input file into the token buffer; returns whether a token was read */ 388 static 389 SCIP_Bool getNextToken( 390 SCIP* scip, /**< SCIP data structure */ 391 OPBINPUT* opbinput /**< OPB reading data */ 392 ) 393 { 394 SCIP_Bool hasdot; 395 OPBEXPTYPE exptype; 396 char* buf; 397 int tokenlen; 398 399 assert(opbinput != NULL); 400 assert(opbinput->linepos < opbinput->linebufsize); 401 402 /* check the token stack */ 403 if( opbinput->npushedtokens > 0 ) 404 { 405 swapPointers(&opbinput->token, &opbinput->pushedtokens[opbinput->npushedtokens-1]); 406 opbinput->npushedtokens--; 407 SCIPdebugMsg(scip, "(line %d) read token again: '%s'\n", opbinput->linenumber, opbinput->token); 408 return TRUE; 409 } 410 411 /* skip delimiters */ 412 buf = opbinput->linebuf; 413 while( isDelimChar(buf[opbinput->linepos]) ) 414 { 415 if( buf[opbinput->linepos] == '\0' ) 416 { 417 if( !getNextLine(scip, opbinput) ) 418 { 419 SCIPdebugMsg(scip, "(line %d) end of file\n", opbinput->linenumber); 420 return FALSE; 421 } 422 assert(opbinput->linepos == 0); 423 /* update buf, because the linebuffer may have been reallocated */ 424 buf = opbinput->linebuf; 425 } 426 else 427 opbinput->linepos++; 428 } 429 assert(opbinput->linepos < opbinput->linebufsize); 430 assert(!isDelimChar(buf[opbinput->linepos])); 431 432 /* check if the token is a value */ 433 hasdot = FALSE; 434 exptype = OPB_EXP_NONE; 435 if( isValueChar(buf[opbinput->linepos], buf[opbinput->linepos+1], TRUE, &hasdot, &exptype) ) 436 { 437 /* read value token */ 438 tokenlen = 0; 439 do 440 { 441 assert(tokenlen < OPB_MAX_LINELEN); 442 assert(!isDelimChar(buf[opbinput->linepos])); 443 opbinput->token[tokenlen] = buf[opbinput->linepos]; 444 tokenlen++; 445 opbinput->linepos++; 446 } 447 while( isValueChar(buf[opbinput->linepos], buf[opbinput->linepos+1], FALSE, &hasdot, &exptype) ); 448 } 449 else 450 { 451 /* read non-value token */ 452 tokenlen = 0; 453 do 454 { 455 assert(tokenlen < OPB_MAX_LINELEN); 456 opbinput->token[tokenlen] = buf[opbinput->linepos]; 457 tokenlen++; 458 opbinput->linepos++; 459 if( tokenlen == 1 && isTokenChar(opbinput->token[0]) ) 460 break; 461 } 462 while( !isDelimChar(buf[opbinput->linepos]) && !isTokenChar(buf[opbinput->linepos]) ); 463 464 /* if the token is an equation sense '<', '>', or '=', skip a following '=' 465 * if the token is an equality token '=' and the next character is a '<' or '>', 466 * replace the token by the inequality sense 467 */ 468 if( tokenlen >= 1 469 && (opbinput->token[tokenlen-1] == '<' || opbinput->token[tokenlen-1] == '>' || opbinput->token[tokenlen-1] == '=') 470 && buf[opbinput->linepos] == '=' ) 471 { 472 opbinput->linepos++; 473 } 474 else if( opbinput->token[tokenlen-1] == '=' && (buf[opbinput->linepos] == '<' || buf[opbinput->linepos] == '>') ) 475 { 476 opbinput->token[tokenlen-1] = buf[opbinput->linepos]; 477 opbinput->linepos++; 478 } 479 } 480 assert(tokenlen < OPB_MAX_LINELEN); 481 opbinput->token[tokenlen] = '\0'; 482 483 SCIPdebugMsg(scip, "(line %d) read token: '%s'\n", opbinput->linenumber, opbinput->token); 484 485 return TRUE; 486 } 487 488 /** puts the current token on the token stack, such that it is read at the next call to getNextToken() */ 489 static 490 void pushToken( 491 OPBINPUT* opbinput /**< OPB reading data */ 492 ) 493 { 494 assert(opbinput != NULL); 495 assert(opbinput->npushedtokens < OPB_MAX_PUSHEDTOKENS); 496 497 swapPointers(&opbinput->pushedtokens[opbinput->npushedtokens], &opbinput->token); 498 opbinput->npushedtokens++; 499 } 500 501 /** puts the buffered token on the token stack, such that it is read at the next call to getNextToken() */ 502 static 503 void pushBufferToken( 504 OPBINPUT* opbinput /**< OPB reading data */ 505 ) 506 { 507 assert(opbinput != NULL); 508 assert(opbinput->npushedtokens < OPB_MAX_PUSHEDTOKENS); 509 510 swapPointers(&opbinput->pushedtokens[opbinput->npushedtokens], &opbinput->tokenbuf); 511 opbinput->npushedtokens++; 512 } 513 514 /** swaps the current token with the token buffer */ 515 static 516 void swapTokenBuffer( 517 OPBINPUT* opbinput /**< OPB reading data */ 518 ) 519 { 520 assert(opbinput != NULL); 521 522 swapPointers(&opbinput->token, &opbinput->tokenbuf); 523 } 524 525 /** checks whether the current token is a section identifier, and if yes, switches to the corresponding section */ 526 static 527 SCIP_Bool isEndLine( 528 OPBINPUT* opbinput /**< OPB reading data */ 529 ) 530 { 531 assert(opbinput != NULL); 532 533 if( *(opbinput->token) == ';') 534 return TRUE; 535 536 return FALSE; 537 } 538 539 /** returns whether the current token is a sign */ 540 static 541 SCIP_Bool isSign( 542 OPBINPUT* opbinput, /**< OPB reading data */ 543 int* sign /**< pointer to update the sign */ 544 ) 545 { 546 assert(opbinput != NULL); 547 assert(sign != NULL); 548 assert(*sign == +1 || *sign == -1); 549 550 if( strlen(opbinput->token) == 1 ) 551 { 552 assert(opbinput->token[1] == '\0'); 553 554 if( *opbinput->token == '+' ) 555 return TRUE; 556 else if( *opbinput->token == '-' ) 557 { 558 *sign *= -1; 559 return TRUE; 560 } 561 } 562 563 return FALSE; 564 } 565 566 /** returns whether the current token is a value */ 567 static 568 SCIP_Bool isValue( 569 SCIP* scip, /**< SCIP data structure */ 570 OPBINPUT* opbinput, /**< OPB reading data */ 571 SCIP_Real* value /**< pointer to store the value (unchanged, if token is no value) */ 572 ) 573 { 574 assert(opbinput != NULL); 575 assert(value != NULL); 576 577 if( strcasecmp(opbinput->token, "INFINITY") == 0 || strcasecmp(opbinput->token, "INF") == 0 ) 578 { 579 *value = SCIPinfinity(scip); 580 return TRUE; 581 } 582 else 583 { 584 double val; 585 char* endptr; 586 587 val = strtod(opbinput->token, &endptr); 588 if( endptr != opbinput->token && *endptr == '\0' ) 589 { 590 *value = val; 591 if( strlen(opbinput->token) > 18 ) 592 opbinput->nproblemcoeffs++; 593 return TRUE; 594 } 595 } 596 597 return FALSE; 598 } 599 600 /** returns whether the current token is an equation sense */ 601 static 602 SCIP_Bool isSense( 603 OPBINPUT* opbinput, /**< OPB reading data */ 604 OPBSENSE* sense /**< pointer to store the equation sense, or NULL */ 605 ) 606 { 607 assert(opbinput != NULL); 608 609 if( strcmp(opbinput->token, "<") == 0 ) 610 { 611 if( sense != NULL ) 612 *sense = OPB_SENSE_LE; 613 return TRUE; 614 } 615 else if( strcmp(opbinput->token, ">") == 0 ) 616 { 617 if( sense != NULL ) 618 *sense = OPB_SENSE_GE; 619 return TRUE; 620 } 621 else if( strcmp(opbinput->token, "=") == 0 ) 622 { 623 if( sense != NULL ) 624 *sense = OPB_SENSE_EQ; 625 return TRUE; 626 } 627 628 return FALSE; 629 } 630 631 /** returns whether the current token is a value */ 632 static 633 SCIP_Bool isStartingSoftConstraintWeight( 634 SCIP* scip, /**< SCIP data structure */ 635 OPBINPUT* opbinput /**< OPB reading data */ 636 ) 637 { 638 assert(scip != NULL); 639 assert(opbinput != NULL); 640 641 if( strcmp(opbinput->token, "[") == 0 ) 642 return TRUE; 643 644 return FALSE; 645 } 646 647 /** returns whether the current token is a value */ 648 static 649 SCIP_Bool isEndingSoftConstraintWeight( 650 SCIP* scip, /**< SCIP data structure */ 651 OPBINPUT* opbinput /**< OPB reading data */ 652 ) 653 { 654 assert(scip != NULL); 655 assert(opbinput != NULL); 656 657 if( strcmp(opbinput->token, "]") == 0 ) 658 return TRUE; 659 660 return FALSE; 661 } 662 663 /** create binary variable with given name */ 664 static 665 SCIP_RETCODE createVariable( 666 SCIP* scip, /**< SCIP data structure */ 667 SCIP_VAR** var, /**< pointer to store the variable */ 668 char* name /**< name for the variable */ 669 ) 670 { 671 SCIP_VAR* newvar; 672 SCIP_Bool dynamiccols; 673 SCIP_Bool initial; 674 SCIP_Bool removable; 675 676 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &dynamiccols) ); 677 initial = !dynamiccols; 678 removable = dynamiccols; 679 680 /* create new variable of the given name */ 681 SCIPdebugMsg(scip, "creating new variable: <%s>\n", name); 682 683 SCIP_CALL( SCIPcreateVar(scip, &newvar, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, 684 initial, removable, NULL, NULL, NULL, NULL, NULL) ); 685 SCIP_CALL( SCIPaddVar(scip, newvar) ); 686 *var = newvar; 687 688 /* because the variable was added to the problem, it is captured by SCIP and we 689 * can safely release it right now without making the returned *var invalid */ 690 SCIP_CALL( SCIPreleaseVar(scip, &newvar) ); 691 692 return SCIP_OKAY; 693 } 694 695 /** returns the variable with the given name, or creates a new variable if it does not exist */ 696 static 697 SCIP_RETCODE getVariableOrTerm( 698 SCIP* scip, /**< SCIP data structure */ 699 OPBINPUT* opbinput, /**< OPB reading data */ 700 SCIP_VAR*** vars, /**< pointer to store the variables */ 701 int* nvars, /**< pointer to store the number of variables */ 702 int* varssize /**< pointer to store the varsize, if changed (should already be initialized) */ 703 ) 704 { 705 SCIP_Bool negated; 706 char* name; 707 708 assert(scip != NULL); 709 assert(opbinput != NULL); 710 assert(vars != NULL); 711 assert(nvars != NULL); 712 assert(varssize != NULL); 713 assert(*varssize >= 0); 714 715 *nvars = 0; 716 717 name = opbinput->token; 718 assert(name != NULL); 719 720 /* parse AND terms */ 721 while(!isdigit((unsigned char) *name ) && !isTokenChar(*name) && !opbinput->haserror ) 722 { 723 SCIP_VAR* var; 724 725 negated = FALSE; 726 if( *name == '~' ) 727 { 728 negated = TRUE; 729 ++name; 730 } 731 732 var = SCIPfindVar(scip, name); 733 if( var == NULL ) 734 { 735 SCIP_CALL( createVariable(scip, &var, name) ); 736 } 737 738 if( negated ) 739 { 740 SCIP_VAR* negvar; 741 SCIP_CALL( SCIPgetNegatedVar(scip, var, &negvar) ); 742 743 var = negvar; 744 } 745 746 /* reallocated memory */ 747 if( *nvars == *varssize ) 748 { 749 *varssize = SCIPcalcMemGrowSize(scip, *varssize + 1); 750 SCIP_CALL( SCIPreallocBufferArray(scip, vars, *varssize) ); 751 } 752 753 (*vars)[*nvars] = var; 754 ++(*nvars); 755 756 if( !getNextToken(scip, opbinput) ) 757 opbinput->haserror = TRUE; 758 759 name = opbinput->token; 760 } 761 762 /* check if we found at least on variable */ 763 if( *nvars == 0 ) 764 syntaxError(scip, opbinput, "expected a variable name"); 765 766 pushToken(opbinput); 767 768 return SCIP_OKAY; 769 } 770 771 /** reads an objective or constraint with name and coefficients */ 772 static 773 SCIP_RETCODE readCoefficients( 774 SCIP*const scip, /**< SCIP data structure */ 775 OPBINPUT*const opbinput, /**< OPB reading data */ 776 char*const name, /**< pointer to store the name of the line; must be at least of size 777 * OPB_MAX_LINELEN */ 778 SCIP_VAR*** linvars, /**< pointer to store the array with linear variables (must be freed by caller) */ 779 SCIP_Real** lincoefs, /**< pointer to store the array with linear coefficients (must be freed by caller) */ 780 int*const nlincoefs, /**< pointer to store the number of linear coefficients */ 781 int* lincoefssize, /**< pointer to store the size of linvars/lincoefs arrays */ 782 SCIP_VAR**** terms, /**< pointer to store the array with nonlinear variables (must be freed by caller) */ 783 SCIP_Real** termcoefs, /**< pointer to store the array with nonlinear coefficients (must be freed by caller) */ 784 int** ntermvars, /**< pointer to store the number of nonlinear variables in the terms (must be freed by caller) */ 785 int* termcoefssize, /**< pointer to store the size of terms/termcoefs */ 786 int*const ntermcoefs, /**< pointer to store the number of nonlinear coefficients */ 787 SCIP_Bool*const newsection, /**< pointer to store whether a new section was encountered */ 788 SCIP_Bool*const isNonlinear, /**< pointer to store if we have a nonlinear constraint */ 789 SCIP_Bool*const issoftcons, /**< pointer to store whether it is a soft constraint (for wbo files) */ 790 SCIP_Real*const weight /**< pointer to store the weight of the soft constraint */ 791 ) 792 { 793 SCIP_VAR** tmpvars; 794 SCIP_Real* tmpcoefs; 795 SCIP_Bool havesign; 796 SCIP_Bool havevalue; 797 SCIP_Bool haveweightstart; 798 SCIP_Bool haveweightend; 799 SCIP_Real coef; 800 int coefsign; 801 int tmpvarssize; 802 int ntmpcoefs; 803 int ntmpvars; 804 805 assert(opbinput != NULL); 806 assert(name != NULL); 807 assert(linvars != NULL); 808 assert(lincoefs != NULL); 809 assert(lincoefssize != NULL); 810 assert(nlincoefs != NULL); 811 assert(terms != NULL); 812 assert(termcoefs != NULL); 813 assert(ntermvars != NULL); 814 assert(termcoefssize != NULL); 815 assert(ntermcoefs != NULL); 816 assert(newsection != NULL); 817 818 *linvars = NULL; 819 *lincoefs = NULL; 820 *lincoefssize = 0; 821 *terms = NULL; 822 *termcoefs = NULL; 823 *ntermvars = NULL; 824 *termcoefssize = 0; 825 *name = '\0'; 826 *nlincoefs = 0; 827 *ntermcoefs = 0; 828 *newsection = FALSE; 829 *isNonlinear = FALSE; 830 *issoftcons = FALSE; 831 832 SCIPdebugMsg(scip, "read coefficients\n"); 833 834 /* read the first token, which may be the name of the line */ 835 if( getNextToken(scip, opbinput) ) 836 { 837 /* remember the token in the token buffer */ 838 swapTokenBuffer(opbinput); 839 840 /* get the next token and check, whether it is a colon */ 841 if( getNextToken(scip, opbinput) ) 842 { 843 if( strcmp(opbinput->token, ":") == 0 ) 844 { 845 /* the second token was a colon ':' the first token is a constraint name */ 846 (void)SCIPmemccpy(name, opbinput->tokenbuf, '\0', SCIP_MAXSTRLEN); 847 848 name[SCIP_MAXSTRLEN-1] = '\0'; 849 SCIPdebugMsg(scip, "(line %d) read constraint name: '%s'\n", opbinput->linenumber, name); 850 851 /* all but the first coefficient need a sign */ 852 if( strcmp(name, "soft") == 0 && (SCIPgetNVars(scip) > 0 || SCIPgetNConss(scip) > 0) ) 853 { 854 syntaxError(scip, opbinput, "Soft top cost line needs to be the first non-comment line, and without any objective function.\n"); 855 return SCIP_OKAY; 856 } 857 } 858 else 859 { 860 /* the second token was no colon: push the tokens back onto the token stack and parse them as coefficients */ 861 SCIPdebugMsg(scip, "(line %d) constraint has no name\n", opbinput->linenumber); 862 pushToken(opbinput); 863 pushBufferToken(opbinput); 864 } 865 } 866 else 867 { 868 /* there was only one token left: push it back onto the token stack and parse it as coefficient */ 869 pushBufferToken(opbinput); 870 } 871 } 872 else 873 { 874 assert(SCIPfeof( opbinput->file ) ); 875 opbinput->eof = TRUE; 876 return SCIP_OKAY; 877 } 878 879 /* initialize buffers for storing the coefficients */ 880 *lincoefssize = OPB_INIT_COEFSSIZE; 881 *termcoefssize = OPB_INIT_COEFSSIZE; 882 tmpvarssize = OPB_INIT_COEFSSIZE; 883 SCIP_CALL( SCIPallocBlockMemoryArray(scip, linvars, *lincoefssize) ); 884 SCIP_CALL( SCIPallocBlockMemoryArray(scip, lincoefs, *lincoefssize) ); 885 SCIP_CALL( SCIPallocBlockMemoryArray(scip, terms, *termcoefssize) ); 886 SCIP_CALL( SCIPallocBlockMemoryArray(scip, termcoefs, *termcoefssize) ); 887 SCIP_CALL( SCIPallocBlockMemoryArray(scip, ntermvars, *termcoefssize) ); 888 889 SCIP_CALL( SCIPallocBufferArray(scip, &tmpvars, tmpvarssize) ); 890 SCIP_CALL( SCIPallocBufferArray(scip, &tmpcoefs, tmpvarssize) ); 891 892 /* read the coefficients */ 893 coefsign = +1; 894 coef = 1.0; 895 havesign = FALSE; 896 havevalue = FALSE; 897 haveweightstart = FALSE; 898 haveweightend = FALSE; 899 ntmpcoefs = 0; 900 ntmpvars = 0; 901 902 while( getNextToken(scip, opbinput) && !hasError(opbinput) ) 903 { 904 if( isEndLine(opbinput) ) 905 { 906 *newsection = TRUE; 907 goto TERMINATE; 908 } 909 910 /* check if we reached an equation sense */ 911 if( isSense(opbinput, NULL) ) 912 { 913 /* put the sense back onto the token stack */ 914 pushToken(opbinput); 915 goto TERMINATE; 916 } 917 918 /* check if we read a sign */ 919 if( isSign(opbinput, &coefsign) ) 920 { 921 SCIPdebugMsg(scip, "(line %d) read coefficient sign: %+d\n", opbinput->linenumber, coefsign); 922 havesign = TRUE; 923 continue; 924 } 925 926 /* check if we read a value */ 927 if( isValue(scip, opbinput, &coef) ) 928 { 929 /* coefficients without a sign are treated as "+" */ 930 if( (*nlincoefs > 0 || *ntermcoefs > 0 || ntmpcoefs > 0) && !havesign ) 931 { 932 coefsign = 1; 933 havesign = TRUE; 934 } 935 936 SCIPdebugMsg(scip, "(line %d) read coefficient value: %g with sign %+d\n", opbinput->linenumber, coef, coefsign); 937 if( havevalue ) 938 { 939 syntaxError(scip, opbinput, "two consecutive values"); 940 goto TERMINATE; 941 } 942 havevalue = TRUE; 943 944 /* if we read a wbo file, the first line should be something like "soft: <weight>;", where weight is a value or nothing */ 945 if( strcmp(name, "soft") == 0 ) 946 { 947 assert(ntmpcoefs == 0); 948 949 tmpcoefs[ntmpcoefs] = coefsign * coef; 950 ++ntmpcoefs; 951 } 952 953 continue; 954 } 955 956 /* check if we are reading a soft constraint line, it start with "[<weight>]", where weight is a value */ 957 if( *nlincoefs == 0 && *ntermcoefs == 0 && ntmpcoefs == 0 && !havesign && !havevalue && strcmp(name, "soft") != 0 && isStartingSoftConstraintWeight(scip, opbinput) ) 958 { 959 if( !opbinput->wbo ) 960 { 961 SCIPwarningMessage(scip, "Found in line %d a soft constraint, without having read a starting top-cost line.\n", opbinput->linenumber); 962 } 963 haveweightstart = TRUE; 964 965 continue; 966 } 967 if( *nlincoefs == 0 && *ntermcoefs == 0 && ntmpcoefs == 0 && havevalue && haveweightstart && isEndingSoftConstraintWeight(scip, opbinput) ) 968 { 969 *weight = coefsign * coef; 970 SCIPdebugMsg(scip, "(line %d) found soft constraint weight: %g\n", opbinput->linenumber, *weight); 971 972 coefsign = +1; 973 havesign = FALSE; 974 havevalue = FALSE; 975 haveweightend = TRUE; 976 *issoftcons = TRUE; 977 978 continue; 979 } 980 981 /* if we read a '[' we should already read a ']', which indicates that we read a soft constraint, 982 * we have a parsing error */ 983 if( haveweightstart != haveweightend ) 984 { 985 syntaxError(scip, opbinput, "Wrong soft constraint."); 986 goto TERMINATE; 987 } 988 989 /* if we read the first non-comment line of a wbo file we should never be here */ 990 if( strcmp(name, "soft") == 0 ) 991 { 992 syntaxError(scip, opbinput, "Wrong soft top cost line."); 993 goto TERMINATE; 994 } 995 996 /* the token is a variable name: get the corresponding variables (or create a new ones) */ 997 SCIP_CALL( getVariableOrTerm(scip, opbinput, &tmpvars, &ntmpvars, &tmpvarssize) ); 998 999 if( ntmpvars > 1 ) 1000 { 1001 /* insert non-linear term */ 1002 *isNonlinear = TRUE; 1003 1004 SCIPdebugMsg(scip, "(line %d) found linear term: %+g", opbinput->linenumber, coefsign * coef); 1005 #ifndef NDEBUG 1006 { 1007 int v; 1008 for( v = 0; v < ntmpvars; ++v ) 1009 { 1010 SCIPdebugMsgPrint(scip, " %s * ", SCIPvarGetName(tmpvars[v])); 1011 } 1012 SCIPdebugMsgPrint(scip, "\n"); 1013 } 1014 #endif 1015 if( !SCIPisZero(scip, coef) ) 1016 { 1017 assert(*ntermcoefs <= *termcoefssize); 1018 /* resize the terms, ntermvars, and termcoefs array if needed */ 1019 if( *ntermcoefs >= *termcoefssize ) 1020 { 1021 int newsize; 1022 1023 newsize = SCIPcalcMemGrowSize(scip, *ntermcoefs + 1); 1024 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, terms, *termcoefssize, newsize) ); 1025 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, termcoefs, *termcoefssize, newsize) ); 1026 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, ntermvars, *termcoefssize, newsize) ); 1027 *termcoefssize = newsize; 1028 } 1029 assert(*ntermcoefs < *termcoefssize); 1030 1031 /* get memory for the last term */ 1032 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*terms)[*ntermcoefs]), ntmpvars) ); /*lint !e866 */ 1033 1034 /* set the number of variable in this term */ 1035 (*ntermvars)[*ntermcoefs] = ntmpvars; 1036 1037 /* add all variables */ 1038 for( --ntmpvars; ntmpvars >= 0; --ntmpvars ) 1039 { 1040 (*terms)[*ntermcoefs][ntmpvars] = tmpvars[ntmpvars]; 1041 } 1042 /* add coefficient */ 1043 (*termcoefs)[*ntermcoefs] = coefsign * coef; 1044 1045 /***********************/ 1046 if( !SCIPisIntegral(scip, (*termcoefs)[*ntermcoefs]) ) 1047 { 1048 SCIPwarningMessage(scip, "coefficient %g in line %d not integral.\n", (*termcoefs)[*ntermcoefs], opbinput->linenumber); 1049 } 1050 1051 ++(*ntermcoefs); 1052 } 1053 1054 /* reset the flags and coefficient value for the next coefficient */ 1055 coefsign = +1; 1056 coef = 1.0; 1057 havesign = FALSE; 1058 havevalue = FALSE; 1059 ntmpvars = 0; 1060 } 1061 else 1062 { 1063 assert(ntmpvars == 1); 1064 /* insert linear term */ 1065 SCIPdebugMsg(scip, "(line %d) found linear term: %+g<%s>\n", opbinput->linenumber, coefsign * coef, SCIPvarGetName(tmpvars[0])); 1066 if( !SCIPisZero(scip, coef) ) 1067 { 1068 assert(*nlincoefs <= *lincoefssize); 1069 /* resize the vars and coefs array if needed */ 1070 if( *nlincoefs >= *lincoefssize ) 1071 { 1072 int newsize; 1073 1074 newsize = SCIPcalcMemGrowSize(scip, *nlincoefs + 1); 1075 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, linvars, *lincoefssize, newsize) ); 1076 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, lincoefs, *lincoefssize, newsize) ); 1077 *lincoefssize = newsize; 1078 } 1079 assert(*nlincoefs < *lincoefssize); 1080 1081 /* add coefficient */ 1082 (*linvars)[*nlincoefs] = tmpvars[0]; 1083 (*lincoefs)[*nlincoefs] = coefsign * coef; 1084 1085 /***********************/ 1086 if( !SCIPisIntegral(scip, (*lincoefs)[*nlincoefs]) ) 1087 { 1088 SCIPwarningMessage(scip, "coefficient %g in line %d not integral.\n", (*lincoefs)[*nlincoefs], opbinput->linenumber); 1089 } 1090 1091 ++(*nlincoefs); 1092 } 1093 1094 /* reset the flags and coefficient value for the next coefficient */ 1095 coefsign = +1; 1096 coef = 1.0; 1097 havesign = FALSE; 1098 havevalue = FALSE; 1099 ntmpvars = 0; 1100 } 1101 } 1102 1103 TERMINATE: 1104 if( !opbinput->haserror ) 1105 { 1106 /* all variables should be in the right arrays */ 1107 assert(ntmpvars == 0); 1108 /* the following is only the case if we read topcost's of a wbo file, we need to move this topcost value to the 1109 * right array */ 1110 if( ntmpcoefs > 0 ) 1111 { 1112 /* maximal one topcost value is possible */ 1113 assert(ntmpcoefs == 1); 1114 /* no other coefficient should be found here */ 1115 assert(*nlincoefs == 0 && *ntermcoefs == 0); 1116 1117 /* copy value */ 1118 (*lincoefs)[*nlincoefs] = tmpcoefs[0]; 1119 1120 /***********************/ 1121 if( !SCIPisIntegral(scip, (*lincoefs)[*nlincoefs]) ) 1122 { 1123 SCIPwarningMessage(scip, "topcost not integral.\n"); 1124 } 1125 1126 *nlincoefs = 1; 1127 } 1128 } 1129 /* clear memory */ 1130 SCIPfreeBufferArray(scip, &tmpcoefs); 1131 SCIPfreeBufferArray(scip, &tmpvars); 1132 1133 return SCIP_OKAY; 1134 } 1135 1136 /** set the objective section */ 1137 static 1138 SCIP_RETCODE setObjective( 1139 SCIP*const scip, /**< SCIP data structure */ 1140 OPBINPUT*const opbinput, /**< OPB reading data */ 1141 const char* sense, /**< objective sense */ 1142 SCIP_Real const scale, /**< objective scale */ 1143 SCIP_VAR**const linvars, /**< array of linear variables */ 1144 SCIP_Real*const coefs, /**< array of objective values for linear variables */ 1145 int const ncoefs, /**< number of coefficients for linear part */ 1146 SCIP_VAR***const terms, /**< array with nonlinear variables */ 1147 SCIP_Real*const termcoefs, /**< array of objective values for nonlinear variables */ 1148 int*const ntermvars, /**< number of nonlinear variables in the terms */ 1149 int const ntermcoefs /**< number of nonlinear coefficients */ 1150 ) 1151 { 1152 assert(scip != NULL); 1153 assert(opbinput != NULL); 1154 assert(isEndLine(opbinput)); 1155 assert(ncoefs == 0 || (linvars != NULL && coefs != NULL)); 1156 assert(ntermcoefs == 0 || (terms != NULL && ntermvars != NULL && termcoefs != NULL)); 1157 1158 if( !hasError(opbinput) ) 1159 { 1160 SCIP_VAR* var; 1161 int v; 1162 char name[SCIP_MAXSTRLEN]; 1163 1164 if( strcmp(sense, "max" ) == 0 ) 1165 opbinput->objsense = SCIP_OBJSENSE_MAXIMIZE; 1166 1167 /* @todo: what todo with non-linear objectives, maybe create the necessary and-constraints and add the arising linear 1168 * objective (with and-resultants) or add a integer variable to this constraint and put only this variable in the 1169 * objective, for this we need to expand the pseudo-boolean constraints to handle integer variables 1170 * 1171 * integer variant is not implemented 1172 */ 1173 if( ntermcoefs > 0 ) 1174 { 1175 #if (LINEAROBJECTIVE == TRUE) 1176 /* all non-linear parts are created as and-constraints, even if the same non-linear part was already part of the objective function */ 1177 1178 SCIP_VAR** vars; 1179 int nvars; 1180 int t; 1181 SCIP_CONS* andcons; 1182 1183 for( t = 0; t < ntermcoefs; ++t ) 1184 { 1185 assert(terms != NULL); /* for lint */ 1186 assert(ntermvars != NULL); 1187 assert(termcoefs != NULL); 1188 1189 vars = terms[t]; 1190 nvars = ntermvars[t]; 1191 assert(vars != NULL); 1192 assert(nvars > 1); 1193 1194 /* create auxiliary variable */ 1195 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, ARTIFICIALVARNAMEPREFIX"obj_%d", t); 1196 SCIP_CALL( SCIPcreateVar(scip, &var, name, 0.0, 1.0, termcoefs[t], SCIP_VARTYPE_BINARY, 1197 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 1198 1199 /* @todo: check if it is better to change the branching priority for the artificial variables */ 1200 #if 1 1201 /* change branching priority of artificial variable to -1 */ 1202 SCIP_CALL( SCIPchgVarBranchPriority(scip, var, -1) ); 1203 #endif 1204 1205 /* add auxiliary variable to the problem */ 1206 SCIP_CALL( SCIPaddVar(scip, var) ); 1207 1208 #ifdef WITH_DEBUG_SOLUTION 1209 if( SCIPdebugIsMainscip(scip) ) 1210 { 1211 SCIP_Real val = 0.0; 1212 1213 for( v = nvars - 1; v >= 0; --v ) 1214 { 1215 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) ); 1216 assert(SCIPisFeasZero(scip, val) || SCIPisFeasEQ(scip, val, 1.0)); 1217 1218 if( val < 0.5 ) 1219 break; 1220 } 1221 SCIP_CALL( SCIPdebugAddSolVal(scip, var, (val < 0.5) ? 0.0 : 1.0) ); 1222 } 1223 #endif 1224 1225 /* @todo: check whether all constraint creation flags are the best option */ 1226 /* create and-constraint */ 1227 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "obj_andcons_%d", t); 1228 SCIP_CALL( SCIPcreateConsAnd(scip, &andcons, name, var, nvars, vars, 1229 TRUE, TRUE, TRUE, TRUE, TRUE, 1230 FALSE, FALSE, FALSE, FALSE, FALSE) ); 1231 SCIP_CALL( SCIPaddCons(scip, andcons) ); 1232 SCIPdebugPrintCons(scip, andcons, NULL); 1233 SCIP_CALL( SCIPreleaseCons(scip, &andcons) ); 1234 1235 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 1236 } 1237 #else /* now the integer variant */ 1238 SCIP_CONS* pseudocons; 1239 SCIP_Real lb; 1240 SCIP_Real ub; 1241 1242 lb = 0.0; 1243 ub = 0.0; 1244 1245 /* add all non linear coefficients up */ 1246 for( v = 0; v < ntermcoefs; ++v ) 1247 { 1248 if( termcoefs[v] < 0 ) 1249 lb += termcoefs[v]; 1250 else 1251 ub += termcoefs[v]; 1252 } 1253 /* add all linear coefficients up */ 1254 for( v = 0; v < ncoefs; ++v ) 1255 { 1256 if( coefs[v] < 0 ) 1257 lb += coefs[v]; 1258 else 1259 ub += coefs[v]; 1260 } 1261 assert(lb < ub); 1262 1263 /* create auxiliary variable */ 1264 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "artificial_int_obj"); 1265 SCIP_CALL( SCIPcreateVar(scip, &var, name, lb, ub, 1.0, SCIP_VARTYPE_INTEGER, 1266 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 1267 1268 /* @todo: check if it is better to change the branching priority for the artificial variables */ 1269 #if 1 1270 /* change branching priority of artificial variable to -1 */ 1271 SCIP_CALL( SCIPchgVarBranchPriority(scip, var, -1) ); 1272 #endif 1273 /* add auxiliary variable to the problem */ 1274 SCIP_CALL( SCIPaddVar(scip, var) ); 1275 1276 #ifdef WITH_DEBUG_SOLUTION 1277 if( SCIPdebugIsMainscip(scip) ) 1278 { 1279 SCIP_Real artval = 0.0; 1280 SCIP_Real val; 1281 1282 for( t = 0; t < ntermcoefs; ++t ) 1283 { 1284 vars = terms[t]; 1285 nvars = ntermvars[t]; 1286 assert(vars != NULL); 1287 assert(nvars > 1); 1288 1289 for( v = nvars - 1; v >= 0; --v ) 1290 { 1291 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) ); 1292 assert(SCIPisFeasZero(scip, val) || SCIPisFeasEQ(scip, val, 1.0)); 1293 1294 if( val < 0.5 ) 1295 break; 1296 } 1297 1298 artval += (((val < 0.5) ? 0.0 : 1.0) * termcoefs[t]); 1299 } 1300 assert(SCIPisFeasLE(scip, lb, artval) && SCIPisFeasGE(scip, ub, artval)); 1301 1302 SCIP_CALL( SCIPdebugAddSolVal(scip, var, artval) ); 1303 } 1304 #endif 1305 1306 /* create artificial objection function constraint containing the artificial integer variable */ 1307 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "artificial_obj_cons"); 1308 SCIP_CALL( SCIPcreateConsPseudoboolean(scip, &pseudocons, name, linvars, ncoefs, coefs, terms, ntermcoefs, 1309 ntermvars, termcoefs, NULL, 0.0, FALSE, var, 0.0, 0.0, 1310 TRUE, TRUE, TRUE, TRUE, TRUE, 1311 FALSE, FALSE, FALSE, FALSE, FALSE) ); 1312 1313 SCIP_CALL( SCIPaddCons(scip, pseudocons) ); 1314 SCIPdebugPrintCons(scip, pseudocons, NULL); 1315 SCIP_CALL( SCIPreleaseCons(scip, &pseudocons) ); 1316 1317 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 1318 1319 return SCIP_OKAY; 1320 #endif 1321 } 1322 /* set the objective values */ 1323 for( v = 0; v < ncoefs; ++v ) 1324 { 1325 assert(linvars != NULL); /* for lint */ 1326 assert(coefs != NULL); 1327 1328 if( SCIPvarIsNegated(linvars[v]) ) 1329 { 1330 SCIP_VAR* negvar = SCIPvarGetNegationVar(linvars[v]); 1331 1332 SCIP_CALL( SCIPaddOrigObjoffset(scip, coefs[v]) ); 1333 SCIP_CALL( SCIPaddVarObj(scip, negvar, -scale * coefs[v]) ); 1334 } 1335 else 1336 { 1337 SCIP_CALL( SCIPaddVarObj(scip, linvars[v], scale * coefs[v]) ); 1338 } 1339 } 1340 } 1341 1342 return SCIP_OKAY; 1343 } 1344 1345 /** reads the constraints section */ 1346 static 1347 SCIP_RETCODE readConstraints( 1348 SCIP* scip, /**< SCIP data structure */ 1349 OPBINPUT* opbinput, /**< OPB reading data */ 1350 SCIP_Real objscale, /**< objective scale */ 1351 int* nNonlinearConss /**< pointer to store number of nonlinear constraints */ 1352 ) 1353 { 1354 char name[OPB_MAX_LINELEN]; 1355 SCIP_CONS* cons; 1356 SCIP_VAR** linvars; 1357 SCIP_Real* lincoefs; 1358 int lincoefssize; 1359 int nlincoefs; 1360 SCIP_VAR*** terms; 1361 SCIP_Real* termcoefs; 1362 int* ntermvars; 1363 int termcoefssize; 1364 int ntermcoefs; 1365 OPBSENSE sense; 1366 SCIP_RETCODE retcode; 1367 SCIP_Real sidevalue; 1368 SCIP_Real lhs; 1369 SCIP_Real rhs; 1370 SCIP_Bool newsection; 1371 SCIP_Bool initialconss; 1372 SCIP_Bool dynamicconss; 1373 SCIP_Bool dynamicrows; 1374 SCIP_Bool initial; 1375 SCIP_Bool separate; 1376 SCIP_Bool enforce; 1377 SCIP_Bool check; 1378 SCIP_Bool propagate; 1379 SCIP_Bool local; 1380 SCIP_Bool modifiable; 1381 SCIP_Bool dynamic; 1382 SCIP_Bool removable; 1383 SCIP_Bool isNonlinear; 1384 int sidesign; 1385 SCIP_Bool issoftcons; 1386 SCIP_Real weight; 1387 SCIP_VAR* indvar; 1388 char indname[SCIP_MAXSTRLEN]; 1389 int t; 1390 1391 assert(scip != NULL); 1392 assert(opbinput != NULL); 1393 assert(nNonlinearConss != NULL); 1394 1395 weight = -SCIPinfinity(scip); 1396 retcode = SCIP_OKAY; 1397 1398 /* read the objective coefficients */ 1399 SCIP_CALL( readCoefficients(scip, opbinput, name, &linvars, &lincoefs, &nlincoefs, &lincoefssize, &terms, &termcoefs, &ntermvars, &termcoefssize, 1400 &ntermcoefs, &newsection, &isNonlinear, &issoftcons, &weight) ); 1401 1402 if( hasError(opbinput) || opbinput->eof ) 1403 goto TERMINATE; 1404 if( newsection ) 1405 { 1406 if( strcmp(name, "min") == 0 || strcmp(name, "max") == 0 ) 1407 { 1408 if( opbinput->wbo ) 1409 { 1410 syntaxError(scip, opbinput, "Cannot have an objective function when having soft constraints.\n"); 1411 goto TERMINATE; 1412 } 1413 1414 /* set objective function */ 1415 SCIP_CALL( setObjective(scip, opbinput, name, objscale, linvars, lincoefs, nlincoefs, terms, termcoefs, ntermvars, ntermcoefs) ); 1416 } 1417 else if( strcmp(name, "soft") == 0 ) 1418 { 1419 /* we have a "weighted boolean optimization"-file(wbo) */ 1420 opbinput->wbo = TRUE; 1421 if( nlincoefs == 0 ) 1422 opbinput->topcost = SCIPinfinity(scip); 1423 else 1424 { 1425 assert(nlincoefs == 1); 1426 assert(lincoefs != NULL); 1427 opbinput->topcost = lincoefs[0]; 1428 } 1429 SCIPdebugMsg(scip, "Weighted Boolean Optimization problem has topcost of %g\n", opbinput->topcost); 1430 } 1431 else if( nlincoefs > 0 ) 1432 syntaxError(scip, opbinput, "expected constraint sense '=' or '>='"); 1433 goto TERMINATE; 1434 } 1435 1436 /* read the constraint sense */ 1437 if( !getNextToken(scip, opbinput) ) 1438 { 1439 syntaxError(scip, opbinput, "expected constraint sense."); 1440 goto TERMINATE; 1441 } 1442 if( !isSense(opbinput, &sense) ) 1443 { 1444 syntaxError(scip, opbinput, "expected constraint sense '=' or '>='."); 1445 goto TERMINATE; 1446 } 1447 1448 /* read the right hand side */ 1449 sidesign = +1; 1450 if( !getNextToken(scip, opbinput) ) 1451 { 1452 syntaxError(scip, opbinput, "missing right hand side"); 1453 goto TERMINATE; 1454 } 1455 if( isSign(opbinput, &sidesign) ) 1456 { 1457 if( !getNextToken(scip, opbinput) ) 1458 { 1459 syntaxError(scip, opbinput, "missing value of right hand side"); 1460 goto TERMINATE; 1461 } 1462 } 1463 if( !isValue(scip, opbinput, &sidevalue) ) 1464 { 1465 syntaxError(scip, opbinput, "expected value as right hand side"); 1466 goto TERMINATE; 1467 } 1468 sidevalue *= sidesign; 1469 1470 /* check if we reached the line end */ 1471 if( !getNextToken(scip, opbinput) || !isEndLine(opbinput) ) 1472 { 1473 syntaxError(scip, opbinput, "expected endline character ';'"); 1474 goto TERMINATE; 1475 } 1476 1477 /* assign the left and right hand side, depending on the constraint sense */ 1478 switch( sense ) /*lint !e530*/ 1479 { 1480 case OPB_SENSE_GE: 1481 lhs = sidevalue; 1482 rhs = SCIPinfinity(scip); 1483 break; 1484 case OPB_SENSE_LE: 1485 lhs = -SCIPinfinity(scip); 1486 rhs = sidevalue; 1487 break; 1488 case OPB_SENSE_EQ: 1489 lhs = sidevalue; 1490 rhs = sidevalue; 1491 break; 1492 case OPB_SENSE_NOTHING: 1493 default: 1494 SCIPerrorMessage("invalid constraint sense <%d>\n", sense); 1495 return SCIP_INVALIDDATA; 1496 } 1497 1498 /* create and add the linear constraint */ 1499 SCIP_CALL( SCIPgetBoolParam(scip, "reading/initialconss", &initialconss) ); 1500 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicrows", &dynamicrows) ); 1501 SCIP_CALL( SCIPgetBoolParam(scip, "reading/" READER_NAME "/dynamicconss", &dynamicconss) ); 1502 1503 initial = initialconss; 1504 separate = TRUE; 1505 enforce = TRUE; 1506 check = TRUE; 1507 propagate = TRUE; 1508 local = FALSE; 1509 modifiable = FALSE; 1510 dynamic = FALSE;/*dynamicconss;*/ 1511 removable = dynamicrows; 1512 1513 /* create corresponding constraint */ 1514 if( issoftcons ) 1515 { 1516 (void) SCIPsnprintf(indname, SCIP_MAXSTRLEN, INDICATORVARNAME"%d", opbinput->nindvars); 1517 ++(opbinput->nindvars); 1518 SCIP_CALL( createVariable(scip, &indvar, indname) ); 1519 1520 assert(!SCIPisInfinity(scip, -weight)); 1521 SCIP_CALL( SCIPchgVarObj(scip, indvar, objscale * weight) ); 1522 } 1523 else 1524 indvar = NULL; 1525 1526 if( ntermcoefs > 0 || issoftcons ) 1527 { 1528 #if GENCONSNAMES == TRUE 1529 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pseudoboolean%d", opbinput->consnumber); 1530 ++(opbinput->consnumber); 1531 #else 1532 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pseudoboolean"); 1533 #endif 1534 retcode = SCIPcreateConsPseudoboolean(scip, &cons, name, linvars, nlincoefs, lincoefs, terms, ntermcoefs, 1535 ntermvars, termcoefs, indvar, weight, issoftcons, NULL, lhs, rhs, 1536 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE); 1537 if( retcode != SCIP_OKAY ) 1538 goto TERMINATE; 1539 } 1540 else 1541 { 1542 #if GENCONSNAMES == TRUE 1543 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear%d", opbinput->consnumber); 1544 ++(opbinput->consnumber); 1545 #else 1546 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "linear"); 1547 #endif 1548 retcode = SCIPcreateConsLinear(scip, &cons, name, nlincoefs, linvars, lincoefs, lhs, rhs, 1549 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE); 1550 if( retcode != SCIP_OKAY ) 1551 goto TERMINATE; 1552 } 1553 1554 SCIP_CALL( SCIPaddCons(scip, cons) ); 1555 SCIPdebugMsg(scip, "(line %d) created constraint: ", opbinput->linenumber); 1556 SCIPdebugPrintCons(scip, cons, NULL); 1557 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1558 1559 if( isNonlinear ) 1560 ++(*nNonlinearConss); 1561 1562 TERMINATE: 1563 1564 /* free memory */ 1565 for( t = ntermcoefs - 1; t >= 0; --t ) 1566 { 1567 assert(terms != NULL); /* for lint */ 1568 SCIPfreeBlockMemoryArray(scip, &(terms[t]), ntermvars[t]); 1569 } 1570 1571 SCIPfreeBlockMemoryArrayNull(scip, &ntermvars, termcoefssize); 1572 SCIPfreeBlockMemoryArrayNull(scip, &termcoefs, termcoefssize); 1573 SCIPfreeBlockMemoryArrayNull(scip, &terms, termcoefssize); 1574 SCIPfreeBlockMemoryArrayNull(scip, &lincoefs, lincoefssize); 1575 SCIPfreeBlockMemoryArrayNull(scip, &linvars, lincoefssize); 1576 1577 SCIP_CALL( retcode ); 1578 1579 return SCIP_OKAY; 1580 } 1581 1582 /** tries to read the first comment line which usually contains information about the max size of "and" products */ 1583 static 1584 SCIP_RETCODE getMaxAndConsDim( 1585 SCIP* scip, /**< SCIP data structure */ 1586 OPBINPUT* opbinput, /**< OPB reading data */ 1587 SCIP_Real* objscale, /**< pointer to store objective scale */ 1588 SCIP_Real* objoffset /**< pointer to store objective offset */ 1589 ) 1590 { 1591 SCIP_Bool stop; 1592 char* commentstart; 1593 char* nproducts; 1594 char* str; 1595 int i; 1596 1597 assert(scip != NULL); 1598 assert(opbinput != NULL); 1599 assert(objoffset != NULL); 1600 1601 stop = FALSE; 1602 commentstart = NULL; 1603 nproducts = NULL; 1604 *objscale = 1.0; 1605 *objoffset = 0.0; 1606 opbinput->linebuf[opbinput->linebufsize - 2] = '\0'; 1607 1608 do 1609 { 1610 if( SCIPfgets(opbinput->linebuf, opbinput->linebufsize, opbinput->file) == NULL ) 1611 { 1612 assert( SCIPfeof(opbinput->file) ); 1613 break; 1614 } 1615 1616 /* if line is too long for our buffer reallocate buffer */ 1617 while( opbinput->linebuf[opbinput->linebufsize - 2] != '\0' ) 1618 { 1619 int newsize; 1620 1621 newsize = SCIPcalcMemGrowSize(scip, opbinput->linebufsize + 1); 1622 SCIP_CALL_ABORT( SCIPreallocBlockMemoryArray(scip, &opbinput->linebuf, opbinput->linebufsize, newsize) ); 1623 1624 opbinput->linebuf[newsize-2] = '\0'; 1625 if ( SCIPfgets(opbinput->linebuf + opbinput->linebufsize - 1, newsize - opbinput->linebufsize + 1, opbinput->file) == NULL ) 1626 return SCIP_READERROR; 1627 opbinput->linebufsize = newsize; 1628 } 1629 opbinput->linebuf[opbinput->linebufsize - 1] = '\0'; /* we want to use lookahead of one char -> we need two \0 at the end */ 1630 1631 /* read characters after comment symbol */ 1632 for( i = 0; commentchars[i] != '\0'; ++i ) 1633 { 1634 commentstart = strchr(opbinput->linebuf, commentchars[i]); 1635 1636 /* found a comment line */ 1637 if( commentstart != NULL ) 1638 { 1639 /* search for "#product= xyz" in comment line, where xyz represents the number of and constraints */ 1640 nproducts = strstr(opbinput->linebuf, "#product= "); 1641 if( nproducts != NULL ) 1642 { 1643 const char delimchars[] = " \t"; 1644 char* pos; 1645 1646 nproducts += strlen("#product= "); 1647 1648 pos = strtok(nproducts, delimchars); 1649 1650 if( pos != NULL ) 1651 { 1652 SCIPdebugMsg(scip, "%d products supposed to be in file.\n", atoi(pos)); 1653 } 1654 1655 pos = strtok (NULL, delimchars); 1656 1657 if( pos != NULL && strcmp(pos, "sizeproduct=") == 0 ) 1658 { 1659 pos = strtok (NULL, delimchars); 1660 if( pos != NULL ) 1661 { 1662 SCIPdebugMsg(scip, "sizeproducts = %d\n", atoi(pos)); 1663 } 1664 } 1665 1666 stop = TRUE; 1667 } 1668 1669 /* search for "Obj. scale : <number>" in comment line */ 1670 str = strstr(opbinput->linebuf, "Obj. scale : "); 1671 if( str != NULL ) 1672 { 1673 str += strlen("Obj. scale : "); 1674 *objscale = atof(str); 1675 break; 1676 } 1677 1678 /* search for "Obj. offset : <number>" in comment line */ 1679 str = strstr(opbinput->linebuf, "Obj. offset : "); 1680 if( str != NULL ) 1681 { 1682 str += strlen("Obj. offset : "); 1683 *objoffset = atof(str); 1684 break; 1685 } 1686 1687 /* make sure that comment vanishes */ 1688 *commentstart = '\0'; 1689 1690 break; 1691 } 1692 } 1693 } 1694 while(commentstart != NULL && !stop); 1695 1696 return SCIP_OKAY; 1697 } 1698 1699 /** reads an OPB file */ 1700 static 1701 SCIP_RETCODE readOPBFile( 1702 SCIP* scip, /**< SCIP data structure */ 1703 OPBINPUT* opbinput, /**< OPB reading data */ 1704 const char* filename /**< name of the input file */ 1705 ) 1706 { 1707 SCIP_Real objscale; 1708 SCIP_Real objoffset; 1709 int nNonlinearConss; 1710 int i; 1711 1712 assert(scip != NULL); 1713 assert(opbinput != NULL); 1714 1715 /* open file */ 1716 opbinput->file = SCIPfopen(filename, "r"); 1717 if( opbinput->file == NULL ) 1718 { 1719 SCIPerrorMessage("cannot open file <%s> for reading\n", filename); 1720 SCIPprintSysError(filename); 1721 return SCIP_NOFILE; 1722 } 1723 1724 /* @todo: reading additional information about the number of and constraints in comments to avoid reallocating 1725 * "opbinput.andconss" 1726 */ 1727 1728 /* tries to read the first comment line which usually contains information about the max size of "and" products */ 1729 SCIP_CALL( getMaxAndConsDim(scip, opbinput, &objscale, &objoffset) ); 1730 1731 /* create problem */ 1732 SCIP_CALL( SCIPcreateProb(scip, filename, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 1733 1734 /* opb format supports only minimization; therefore, flip objective sense for negative objective scale */ 1735 if( objscale < 0.0 ) 1736 opbinput->objsense = (SCIP_OBJSENSE)(-1 * (int)(opbinput->objsense)); 1737 1738 if( ! SCIPisZero(scip, objoffset) ) 1739 { 1740 SCIP_CALL( SCIPaddOrigObjoffset(scip, objscale * objoffset) ); 1741 } 1742 1743 nNonlinearConss = 0; 1744 1745 while( !SCIPfeof( opbinput->file ) && !hasError(opbinput) ) 1746 { 1747 SCIP_CALL( readConstraints(scip, opbinput, objscale, &nNonlinearConss) ); 1748 } 1749 1750 /* if we read a wbo file we need to make sure that the top cost won't be exceeded */ 1751 if( opbinput->wbo ) 1752 { 1753 SCIP_VAR** topcostvars; 1754 SCIP_Real* topcosts; 1755 SCIP_VAR** vars; 1756 int nvars; 1757 int ntopcostvars; 1758 SCIP_Longint topcostrhs; 1759 SCIP_CONS* topcostcons; 1760 1761 nvars = SCIPgetNVars(scip); 1762 vars = SCIPgetVars(scip); 1763 assert(nvars > 0 || vars != NULL); 1764 1765 SCIP_CALL( SCIPallocBufferArray(scip, &topcostvars, nvars) ); 1766 SCIP_CALL( SCIPallocBufferArray(scip, &topcosts, nvars) ); 1767 1768 ntopcostvars = 0; 1769 for( i = nvars - 1; i >= 0; --i ) 1770 if( !SCIPisZero(scip, SCIPvarGetObj(vars[i])) ) 1771 { 1772 topcostvars[ntopcostvars] = vars[i]; 1773 topcosts[ntopcostvars] = SCIPvarGetObj(vars[i]); 1774 ++ntopcostvars; 1775 } 1776 1777 if( SCIPisIntegral(scip, opbinput->topcost) ) 1778 topcostrhs = (SCIP_Longint) SCIPfloor(scip, opbinput->topcost - 1); 1779 else 1780 topcostrhs = (SCIP_Longint) SCIPfloor(scip, opbinput->topcost); 1781 1782 SCIP_CALL( SCIPcreateConsLinear(scip, &topcostcons, TOPCOSTCONSNAME, ntopcostvars, topcostvars, topcosts, -SCIPinfinity(scip), 1783 (SCIP_Real) topcostrhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1784 SCIP_CALL( SCIPaddCons(scip, topcostcons) ); 1785 SCIPdebugPrintCons(scip, topcostcons, NULL); 1786 SCIP_CALL( SCIPreleaseCons(scip, &topcostcons) ); 1787 1788 SCIPfreeBufferArray(scip, &topcosts); 1789 SCIPfreeBufferArray(scip, &topcostvars); 1790 } 1791 1792 /* close file */ 1793 SCIPfclose(opbinput->file); 1794 1795 return SCIP_OKAY; 1796 } 1797 1798 1799 /* 1800 * Local methods (for writing) 1801 */ 1802 1803 /** transforms given and constraint variables to the corresponding active or negated variables */ 1804 static 1805 SCIP_RETCODE getBinVarsRepresentatives( 1806 SCIP*const scip, /**< SCIP data structure */ 1807 SCIP_VAR**const vars, /**< vars array to get active variables for */ 1808 int const nvars, /**< pointer to number of variables and values in vars and vals array */ 1809 SCIP_Bool const transformed /**< transformed constraint? */ 1810 ) 1811 { 1812 SCIP_Bool negated; 1813 int v; 1814 1815 assert( scip != NULL ); 1816 assert( vars != NULL ); 1817 assert( nvars > 0 ); 1818 1819 if( transformed ) 1820 { 1821 for( v = nvars - 1; v >= 0; --v ) 1822 { 1823 /* gets a binary variable that is equal to the given binary variable, and that is either active, fixed, or 1824 * multi-aggregated, or the negated variable of an active, fixed, or multi-aggregated variable 1825 */ 1826 SCIP_CALL( SCIPgetBinvarRepresentative( scip, vars[v], &vars[v], &negated) ); 1827 } 1828 } 1829 else 1830 { 1831 SCIP_Real scalar; 1832 SCIP_Real constant; 1833 1834 for( v = nvars - 1; v >= 0; --v ) 1835 { 1836 scalar = 1.0; 1837 constant = 0.0; 1838 1839 /* retransforms given variable, scalar and constant to the corresponding original variable, scalar and constant, 1840 * if possible; if the retransformation is impossible, NULL is returned as variable 1841 */ 1842 SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalar, &constant) ); 1843 1844 if( vars[v] == NULL ) 1845 { 1846 SCIPdebugMsg(scip, "A variable couldn't retransformed to an original variable.\n"); 1847 return SCIP_INVALIDDATA; 1848 } 1849 if( SCIPisEQ(scip, scalar, -1.0) && SCIPisEQ(scip, constant, 1.0) ) 1850 { 1851 SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &vars[v]) ); 1852 } 1853 else 1854 { 1855 if( !SCIPisEQ(scip, scalar, 1.0) || !SCIPisZero(scip, constant) ) 1856 { 1857 SCIPdebugMsg(scip, "A variable couldn't retransformed to an original variable or a negated variable of an original variable (scalar = %g, constant = %g).\n", scalar, constant); 1858 return SCIP_INVALIDDATA; 1859 } 1860 } 1861 } 1862 } 1863 1864 return SCIP_OKAY; 1865 } 1866 1867 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */ 1868 static 1869 SCIP_RETCODE getActiveVariables( 1870 SCIP* scip, /**< SCIP data structure */ 1871 SCIP_VAR** vars, /**< vars array to get active variables for */ 1872 SCIP_Real* scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */ 1873 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 1874 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 1875 SCIP_Bool transformed /**< transformed constraint? */ 1876 ) 1877 { 1878 int requiredsize; 1879 int v; 1880 1881 assert(scip != NULL); 1882 assert(vars != NULL); 1883 assert(scalars != NULL); 1884 assert(nvars != NULL); 1885 assert(constant != NULL); 1886 1887 if( transformed ) 1888 { 1889 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) ); 1890 1891 if( requiredsize > *nvars ) 1892 { 1893 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) ); 1894 SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) ); 1895 1896 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) ); 1897 assert( requiredsize <= *nvars ); 1898 } 1899 } 1900 else 1901 for( v = 0; v < *nvars; ++v ) 1902 { 1903 SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) ); 1904 1905 if( vars[v] == NULL ) 1906 return SCIP_INVALIDDATA; 1907 } 1908 1909 return SCIP_OKAY; 1910 } 1911 1912 /* computes all and-resultants and their corresponding constraint variables */ 1913 static 1914 SCIP_RETCODE computeAndConstraintInfos( 1915 SCIP*const scip, /**< SCIP data structure */ 1916 SCIP_Bool const transformed, /**< transformed problem? */ 1917 SCIP_VAR*** resvars, /**< pointer to store all resultant variables */ 1918 int* nresvars, /**< pointer to store the number of all resultant variables */ 1919 SCIP_VAR**** andvars, /**< pointer to store to all resultant variables their corresponding active( or negated) and-constraint variables */ 1920 int** nandvars, /**< pointer to store the number of all corresponding and-variables to their corresponding resultant variable */ 1921 SCIP_Bool*const existandconshdlr, /**< pointer to store whether the and-constrainthandler exists*/ 1922 SCIP_Bool*const existands /**< pointer to store if their exists some and-constraints */ 1923 ) 1924 { 1925 SCIP_CONSHDLR* conshdlr; 1926 1927 assert(scip != NULL); 1928 assert(resvars != NULL); 1929 assert(nresvars != NULL); 1930 assert(andvars != NULL); 1931 assert(nandvars != NULL); 1932 assert(existandconshdlr != NULL); 1933 assert(existands != NULL); 1934 1935 *resvars = NULL; 1936 *nandvars = NULL; 1937 *andvars = NULL; 1938 *nresvars = 0; 1939 1940 /* detect all and-resultants */ 1941 conshdlr = SCIPfindConshdlr(scip, "and"); 1942 if( conshdlr != NULL ) 1943 { 1944 SCIP_CONS** andconss; 1945 int nandconss; 1946 int* shouldnotbeinand; 1947 int a; 1948 int c; 1949 int r; 1950 int v; 1951 int pos; 1952 int ncontainedands; 1953 1954 andconss = NULL; 1955 nandconss = 0; 1956 *existandconshdlr = TRUE; 1957 1958 /* if we write the original problem we need to get the original and constraints */ 1959 if( !transformed ) 1960 { 1961 SCIP_CONS** origconss; 1962 int norigconss; 1963 1964 origconss = SCIPgetOrigConss(scip); 1965 norigconss = SCIPgetNOrigConss(scip); 1966 1967 /* allocate memory for all possible and-constraints */ 1968 SCIP_CALL( SCIPallocBufferArray(scip, &andconss, norigconss) ); 1969 1970 /* collect all original and-constraints */ 1971 for( c = norigconss - 1; c >= 0; --c ) 1972 { 1973 conshdlr = SCIPconsGetHdlr(origconss[c]); 1974 assert( conshdlr != NULL ); 1975 1976 if( strcmp(SCIPconshdlrGetName(conshdlr), "and") == 0 ) 1977 { 1978 andconss[nandconss] = origconss[c]; 1979 ++nandconss; 1980 } 1981 } 1982 } 1983 else 1984 { 1985 nandconss = SCIPconshdlrGetNConss(conshdlr); 1986 andconss = SCIPconshdlrGetConss(conshdlr); 1987 } 1988 1989 assert(andconss != NULL || nandconss == 0); 1990 1991 *nresvars = nandconss; 1992 1993 if( nandconss > 0 ) 1994 { 1995 *existands = TRUE; 1996 1997 assert(andconss != NULL); 1998 1999 SCIP_CALL( SCIPallocMemoryArray(scip, resvars, *nresvars) ); 2000 SCIP_CALL( SCIPallocMemoryArray(scip, andvars, *nresvars) ); 2001 SCIP_CALL( SCIPallocMemoryArray(scip, nandvars, *nresvars) ); 2002 2003 /* collect all and-constraint variables */ 2004 for( c = nandconss - 1; c >= 0; --c ) 2005 { 2006 SCIP_VAR** scipandvars; 2007 2008 assert(andconss[c] != NULL); 2009 2010 scipandvars = SCIPgetVarsAnd(scip, andconss[c]); 2011 (*nandvars)[c] = SCIPgetNVarsAnd(scip, andconss[c]); 2012 SCIP_CALL( SCIPduplicateMemoryArray(scip, &((*andvars)[c]), scipandvars, (*nandvars)[c]) ); /*lint !e866 */ 2013 SCIP_CALL( getBinVarsRepresentatives(scip, (*andvars)[c], (*nandvars)[c], transformed) ); 2014 2015 (*resvars)[c] = SCIPgetResultantAnd(scip, andconss[c]); 2016 2017 assert((*andvars)[c] != NULL && (*nandvars)[c] > 0); 2018 assert((*resvars)[c] != NULL); 2019 } 2020 2021 /* sorted the array */ 2022 SCIPsortPtrPtrInt((void**)(*resvars), (void**)(*andvars), (*nandvars), SCIPvarComp, (*nresvars)); 2023 } 2024 else 2025 *existands = FALSE; 2026 2027 SCIP_CALL( SCIPallocBufferArray(scip, &shouldnotbeinand, *nresvars) ); 2028 2029 /* check that all and-constraints doesn't contain any and-resultants, if they do try to resolve this */ 2030 /* attention: if resolving leads to x = x*y*... , we can't do anything here ( this only means (... >=x and) y >= x, so normally the and-constraint needs to be 2031 deleted and the inequality from before needs to be added ) */ 2032 assert(*nandvars != NULL || *nresvars == 0); 2033 for( r = *nresvars - 1; r >= 0; --r ) 2034 { 2035 ncontainedands = 0; 2036 shouldnotbeinand[ncontainedands] = r; 2037 ++ncontainedands; 2038 v = 0; 2039 2040 assert(*nandvars != NULL); 2041 while( v < (*nandvars)[r] ) 2042 { 2043 assert(*andvars != NULL); 2044 assert(*resvars != NULL); 2045 if( SCIPsortedvecFindPtr((void**)(*resvars), SCIPvarComp, (*andvars)[r][v], *nresvars, &pos) ) 2046 { 2047 /* check if the found position "pos" is equal to an already visited and resultant in this constraint, 2048 * than here could exist a directed cycle 2049 */ 2050 /* better use tarjan's algorithm 2051 * <http://algowiki.net/wiki/index.php?title=Tarjan%27s_algorithm>, 2052 * <http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm> 2053 * because it could be that the same resultant is part of this and-constraint and than it would fail 2054 * without no cycle 2055 * Note1: tarjans standard algorithm doesn't find cycle from one node to the same; 2056 * Note2: when tarjan's algorithm find a cycle, it's still possible that this cycle is not "real" e.g. 2057 * y = y ~y z (z can also be a product) where y = 0 follows and therefor only "0 = z" is necessary 2058 */ 2059 for( a = ncontainedands - 1; a >= 0; --a ) 2060 if( shouldnotbeinand[a] == pos ) 2061 { 2062 SCIPwarningMessage(scip, "This should not happen here. The and-constraint with resultant variable: "); 2063 SCIP_CALL( SCIPprintVar(scip, (*resvars)[r], NULL) ); 2064 SCIPwarningMessage(scip, "possible contains a loop with and-resultant:"); 2065 SCIP_CALL( SCIPprintVar(scip, (*resvars)[pos], NULL) ); 2066 2067 /* free memory iff necessary */ 2068 SCIPfreeBufferArray(scip, &shouldnotbeinand); 2069 if( !transformed ) 2070 { 2071 SCIPfreeBufferArray(scip, &andconss); 2072 } 2073 return SCIP_INVALIDDATA; 2074 } 2075 SCIPdebugMsg(scip, "Another and-constraint contains and-resultant:"); 2076 SCIPdebug( SCIP_CALL( SCIPprintVar(scip, (*resvars)[pos], NULL) ) ); 2077 SCIPdebugMsg(scip, "Trying to resolve.\n"); 2078 2079 shouldnotbeinand[ncontainedands] = pos; 2080 ++ncontainedands; 2081 2082 /* try to resolve containing ands */ 2083 2084 /* resize array and number of variables */ 2085 (*nandvars)[r] = (*nandvars)[r] + (*nandvars)[pos] - 1; 2086 SCIP_CALL( SCIPreallocMemoryArray(scip, &((*andvars)[r]), (*nandvars)[r]) ); /*lint !e866 */ 2087 2088 /* copy all variables */ 2089 for( a = (*nandvars)[pos] - 1; a >= 0; --a ) 2090 (*andvars)[r][(*nandvars)[r] - a - 1] = (*andvars)[pos][a]; 2091 2092 /* check same position with new variable, so we do not increase v */ 2093 } 2094 else 2095 ++v; 2096 } 2097 } 2098 SCIPfreeBufferArray(scip, &shouldnotbeinand); 2099 2100 /* free memory iff necessary */ 2101 if( !transformed ) 2102 { 2103 SCIPfreeBufferArray(scip, &andconss); 2104 } 2105 } 2106 else 2107 { 2108 SCIPdebugMsg(scip, "found no and-constraint-handler\n"); 2109 *existands = FALSE; 2110 *existandconshdlr = FALSE; 2111 } 2112 2113 return SCIP_OKAY; 2114 } 2115 2116 /** clears the given line buffer */ 2117 static 2118 void clearBuffer( 2119 char* linebuffer, /**< line */ 2120 int* linecnt /**< number of characters in line */ 2121 ) 2122 { 2123 assert( linebuffer != NULL ); 2124 assert( linecnt != NULL ); 2125 2126 (*linecnt) = 0; 2127 linebuffer[0] = '\0'; 2128 } 2129 2130 2131 /** ends the given line with '\\0' and prints it to the given file stream */ 2132 static 2133 void writeBuffer( 2134 SCIP* scip, /**< SCIP data structure */ 2135 FILE* file, /**< output file (or NULL for standard output) */ 2136 char* linebuffer, /**< line */ 2137 int* linecnt /**< number of characters in line */ 2138 ) 2139 { 2140 assert( scip != NULL ); 2141 assert( linebuffer != NULL ); 2142 assert( linecnt != NULL ); 2143 assert( 0 <= *linecnt && *linecnt < OPB_MAX_LINELEN ); 2144 2145 if( (*linecnt) > 0 ) 2146 { 2147 linebuffer[(*linecnt)] = '\0'; 2148 SCIPinfoMessage(scip, file, "%s", linebuffer); 2149 clearBuffer(linebuffer, linecnt); 2150 } 2151 } 2152 2153 2154 /** appends extension to line and prints it to the give file stream if the line buffer get full */ 2155 static 2156 void appendBuffer( 2157 SCIP* scip, /**< SCIP data structure */ 2158 FILE* file, /**< output file (or NULL for standard output) */ 2159 char* linebuffer, /**< line buffer */ 2160 int* linecnt, /**< number of characters in line */ 2161 const char* extension /**< string to extent the line */ 2162 ) 2163 { 2164 assert(scip != NULL); 2165 assert(linebuffer != NULL); 2166 assert(linecnt != NULL); 2167 assert(extension != NULL); 2168 2169 if( (*linecnt) + (int) strlen(extension) >= OPB_MAX_LINELEN - 1 ) 2170 writeBuffer(scip, file, linebuffer, linecnt); 2171 2172 /* append extension to linebuffer */ 2173 (void) strncat(linebuffer, extension, OPB_MAX_LINELEN - (unsigned int)(*linecnt)); 2174 (*linecnt) += (int) strlen(extension); 2175 } 2176 2177 /** write objective function */ 2178 static 2179 SCIP_RETCODE writeOpbObjective( 2180 SCIP*const scip, /**< SCIP data structure */ 2181 FILE*const file, /**< output file, or NULL if standard output should be used */ 2182 SCIP_VAR**const vars, /**< array with active (binary) variables */ 2183 int const nvars, /**< number of active variables in the problem */ 2184 SCIP_VAR** const resvars, /**< array of resultant variables */ 2185 int const nresvars, /**< number of resultant variables */ 2186 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 2187 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 2188 SCIP_OBJSENSE const objsense, /**< objective sense */ 2189 SCIP_Real const objscale, /**< scalar applied to objective function; external objective value is 2190 * extobj = objsense * objscale * (intobj + objoffset) */ 2191 SCIP_Real const objoffset, /**< objective offset from bound shifting and fixing */ 2192 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */ 2193 SCIP_Bool const existands, /**< does some and-constraints exist? */ 2194 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */ 2195 ) 2196 { 2197 SCIP_VAR* var; 2198 char linebuffer[OPB_MAX_LINELEN+1]; 2199 char buffer[OPB_MAX_LINELEN]; 2200 SCIP_Longint mult; 2201 SCIP_Bool objective; 2202 int v; 2203 int linecnt; 2204 int pos; 2205 2206 assert(scip != NULL); 2207 assert(file != NULL); 2208 assert(vars != NULL || nvars == 0); 2209 assert(resvars != NULL || nresvars == 0); 2210 assert(andvars != NULL || nandvars == NULL); 2211 assert(multisymbol != NULL); 2212 2213 mult = 1; 2214 objective = !SCIPisZero(scip, objoffset); 2215 2216 clearBuffer(linebuffer, &linecnt); 2217 2218 /* check if a objective function exits and compute the multiplier to 2219 * shift the coefficients to integers */ 2220 for( v = 0; v < nvars; ++v ) 2221 { 2222 var = vars[v]; /*lint !e613 */ 2223 2224 #ifndef NDEBUG 2225 { 2226 /* in case the original problem has to be posted the variables have to be either "original" or "negated" */ 2227 if( !transformed ) 2228 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL || 2229 SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED ); 2230 } 2231 #endif 2232 2233 /* we found a indicator variable so we assume this is a wbo file */ 2234 if( strstr(SCIPvarGetName(var), INDICATORVARNAME) != NULL ) 2235 { 2236 /* find the topcost linear inequality which gives us the maximal cost which could be violated by our 2237 * solution, which is an artificial constraint and print this at first 2238 * 2239 * @note: only linear constraint handler is enough in problem stage, otherwise it could be any upgraded linear 2240 * constraint which handles pure binary variables 2241 */ 2242 SCIP_CONSHDLR* conshdlr; 2243 SCIP_CONS* topcostcons; 2244 SCIP_Bool printed; 2245 2246 printed = FALSE; 2247 topcostcons = SCIPfindCons(scip, TOPCOSTCONSNAME); 2248 2249 if( topcostcons != NULL ) 2250 { 2251 conshdlr = SCIPconsGetHdlr(topcostcons); 2252 assert(conshdlr != NULL); 2253 2254 if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 ) 2255 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %g;\n", SCIPgetRhsLinear(scip, topcostcons)); 2256 else if( strcmp(SCIPconshdlrGetName(conshdlr), "knapsack") == 0 ) 2257 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %" SCIP_LONGINT_FORMAT ";\n", 2258 SCIPgetCapacityKnapsack(scip, topcostcons)); 2259 else if( strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0 ) 2260 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: 1;\n"); 2261 else 2262 { 2263 SCIPABORT(); 2264 return SCIP_INVALIDDATA; /*lint !e527 */ 2265 } 2266 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2267 writeBuffer(scip, file, linebuffer, &linecnt); 2268 printed = TRUE; 2269 } 2270 /* following works only in transformed stage */ 2271 else 2272 { 2273 /* first try linear constraints */ 2274 conshdlr = SCIPfindConshdlr(scip, "linear"); 2275 2276 if( conshdlr != NULL ) 2277 { 2278 SCIP_CONS** conss; 2279 int nconss; 2280 int c; 2281 2282 conss = SCIPconshdlrGetConss(conshdlr); 2283 nconss = SCIPconshdlrGetNConss(conshdlr); 2284 2285 assert(conss != NULL || nconss == 0); 2286 2287 for( c = 0; c < nconss; ++c ) 2288 { 2289 SCIP_VAR** linvars; 2290 int nlinvars; 2291 int w; 2292 SCIP_Bool topcostfound; 2293 SCIP_CONS* cons; 2294 2295 cons = conss[c]; /*lint !e613 */ 2296 assert(cons != NULL); 2297 2298 linvars = SCIPgetVarsLinear(scip, cons); 2299 nlinvars = SCIPgetNVarsLinear(scip, cons); 2300 2301 assert(linvars != NULL || nlinvars == 0); 2302 topcostfound = FALSE; 2303 2304 for( w = 0; w < nlinvars; ++w ) 2305 { 2306 if( strstr(SCIPvarGetName(linvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */ 2307 topcostfound = TRUE; 2308 else 2309 { 2310 assert(!topcostfound); 2311 topcostfound = FALSE; 2312 } 2313 } 2314 2315 if( topcostfound ) 2316 { 2317 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %g;\n", SCIPgetRhsLinear(scip, cons)); 2318 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2319 writeBuffer(scip, file, linebuffer, &linecnt); 2320 printed = TRUE; 2321 break; 2322 } 2323 } 2324 } 2325 2326 if( !printed ) 2327 { 2328 /* second try knapsack constraints */ 2329 conshdlr = SCIPfindConshdlr(scip, "knapsack"); 2330 2331 if( conshdlr != NULL ) 2332 { 2333 SCIP_CONS** conss; 2334 int nconss; 2335 int c; 2336 2337 conss = SCIPconshdlrGetConss(conshdlr); 2338 nconss = SCIPconshdlrGetNConss(conshdlr); 2339 2340 assert(conss != NULL || nconss == 0); 2341 2342 for( c = 0; c < nconss; ++c ) 2343 { 2344 SCIP_VAR** topvars; 2345 int ntopvars; 2346 int w; 2347 SCIP_Bool topcostfound; 2348 SCIP_CONS* cons; 2349 2350 cons = conss[c]; /*lint !e613 */ 2351 assert(cons != NULL); 2352 2353 topvars = SCIPgetVarsKnapsack(scip, cons); 2354 ntopvars = SCIPgetNVarsKnapsack(scip, cons); 2355 2356 assert(topvars != NULL || ntopvars == 0); 2357 topcostfound = FALSE; 2358 2359 for( w = 0; w < ntopvars; ++w ) 2360 { 2361 if( strstr(SCIPvarGetName(topvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */ 2362 topcostfound = TRUE; 2363 else 2364 { 2365 assert(!topcostfound); 2366 topcostfound = FALSE; 2367 } 2368 } 2369 2370 if( topcostfound ) 2371 { 2372 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: %" SCIP_LONGINT_FORMAT ";\n", 2373 SCIPgetCapacityKnapsack(scip, cons)); 2374 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2375 writeBuffer(scip, file, linebuffer, &linecnt); 2376 printed = TRUE; 2377 break; 2378 } 2379 } 2380 } 2381 } 2382 2383 if( !printed ) 2384 { 2385 /* third try setppc constraints */ 2386 conshdlr = SCIPfindConshdlr(scip, "setppc"); 2387 2388 if( conshdlr != NULL ) 2389 { 2390 SCIP_CONS** conss; 2391 int nconss; 2392 int c; 2393 2394 conss = SCIPconshdlrGetConss(conshdlr); 2395 nconss = SCIPconshdlrGetNConss(conshdlr); 2396 2397 assert(conss != NULL || nconss == 0); 2398 2399 for( c = 0; c < nconss; ++c ) 2400 { 2401 SCIP_VAR** topvars; 2402 int ntopvars; 2403 int w; 2404 SCIP_Bool topcostfound; 2405 SCIP_CONS* cons; 2406 2407 cons = conss[c]; /*lint !e613 */ 2408 assert(cons != NULL); 2409 2410 topvars = SCIPgetVarsSetppc(scip, cons); 2411 ntopvars = SCIPgetNVarsSetppc(scip, cons); 2412 2413 assert(topvars != NULL || ntopvars == 0); 2414 topcostfound = FALSE; 2415 2416 for( w = 0; w < ntopvars; ++w ) 2417 { 2418 if( strstr(SCIPvarGetName(topvars[w]), INDICATORVARNAME) != NULL ) /*lint !e613 */ 2419 topcostfound = TRUE; 2420 else 2421 { 2422 assert(!topcostfound); 2423 topcostfound = FALSE; 2424 } 2425 } 2426 2427 if( topcostfound ) 2428 { 2429 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: 1;\n"); 2430 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2431 writeBuffer(scip, file, linebuffer, &linecnt); 2432 printed = TRUE; 2433 break; 2434 } 2435 } 2436 } 2437 } 2438 } 2439 2440 /* no topcost constraint found, so print empty topcost line, which means there is no upper bound on violated soft constraints */ 2441 if( !printed ) 2442 { 2443 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "soft: ;\n"); 2444 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2445 writeBuffer(scip, file, linebuffer, &linecnt); 2446 } 2447 2448 return SCIP_OKAY; 2449 } 2450 2451 if( !SCIPisZero(scip, SCIPvarGetObj(var)) ) 2452 { 2453 objective = TRUE; 2454 while( !SCIPisIntegral(scip, SCIPvarGetObj(var) * mult) ) 2455 { 2456 assert(mult * 10 > mult); 2457 mult *= 10; 2458 } 2459 } 2460 } 2461 2462 if( objective ) 2463 { 2464 /* opb format supports only minimization; therefore, a maximization problem has to be converted */ 2465 if( ( objsense == SCIP_OBJSENSE_MAXIMIZE ) != ( objscale < 0.0 ) ) 2466 mult *= -1; 2467 2468 /* there exist a objective function*/ 2469 SCIPinfoMessage(scip, file, "* Obj. scale : %.15g\n", objscale / mult); 2470 SCIPinfoMessage(scip, file, "* Obj. offset : %.15g\n", objoffset * mult); 2471 2472 clearBuffer(linebuffer, &linecnt); 2473 2474 SCIPdebugMsg(scip, "print objective function multiplied with %" SCIP_LONGINT_FORMAT "\n", mult); 2475 2476 appendBuffer(scip, file, linebuffer, &linecnt, "min:"); 2477 2478 #ifndef NDEBUG 2479 if( existands ) 2480 { 2481 int c; 2482 /* check that these variables are sorted */ 2483 for( c = nresvars - 1; c > 0; --c ) 2484 assert(SCIPvarGetIndex(resvars[c]) >= SCIPvarGetIndex(resvars[c - 1])); /*lint !e613 */ 2485 } 2486 #endif 2487 2488 for( v = nvars - 1; v >= 0; --v ) 2489 { 2490 SCIP_Bool negated; 2491 var = vars[v]; /*lint !e613 */ 2492 2493 assert(var != NULL); 2494 2495 if( SCIPisZero(scip, SCIPvarGetObj(var)) ) 2496 continue; 2497 2498 negated = SCIPvarIsNegated(var); 2499 2500 assert( linecnt != 0 ); 2501 2502 if( SCIPvarGetObj(var) * mult > (SCIP_Real)SCIP_LONGINT_MAX ) 2503 { 2504 SCIPerrorMessage("Integral objective value to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", mult, SCIPvarGetObj(var), SCIPvarGetObj(var) * mult, (SCIP_Longint) SCIPround(scip, SCIPvarGetObj(var) * mult)); 2505 } 2506 2507 /* replace and-resultant with corresponding variables */ 2508 if( existands && SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, var, nresvars, &pos) ) 2509 { 2510 int a; 2511 2512 assert(andvars != NULL); 2513 assert(nandvars != NULL); 2514 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL); 2515 assert(andvars[pos][nandvars[pos] - 1] != NULL); 2516 2517 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]); 2518 2519 /* print and-vars */ 2520 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " %+" SCIP_LONGINT_FORMAT "%s%s%s", 2521 (SCIP_Longint) (SCIPvarGetObj(var) * mult), multisymbol, negated ? "~" : "", 2522 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x")); 2523 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2524 2525 for(a = nandvars[pos] - 2; a >= 0; --a ) 2526 { 2527 negated = SCIPvarIsNegated(andvars[pos][a]); 2528 2529 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x")); 2530 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2531 } 2532 } 2533 else 2534 { 2535 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " %+" SCIP_LONGINT_FORMAT "%s%s%s", 2536 (SCIP_Longint) (SCIPvarGetObj(var) * mult), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); 2537 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2538 } 2539 } 2540 2541 /* and objective function line ends with a ';' */ 2542 appendBuffer(scip, file, linebuffer, &linecnt, " ;\n"); 2543 writeBuffer(scip, file, linebuffer, &linecnt); 2544 } 2545 2546 return SCIP_OKAY; 2547 } 2548 2549 /* print maybe non linear row in OPB format to file stream */ 2550 static 2551 SCIP_RETCODE printNLRow( 2552 SCIP*const scip, /**< SCIP data structure */ 2553 FILE*const file, /**< output file (or NULL for standard output) */ 2554 char const*const type, /**< row type ("=" or ">=") */ 2555 SCIP_VAR**const vars, /**< array of variables */ 2556 SCIP_Real const*const vals, /**< array of values */ 2557 int const nvars, /**< number of variables */ 2558 SCIP_Real lhs, /**< left hand side */ 2559 SCIP_VAR** const resvars, /**< array of resultant variables */ 2560 int const nresvars, /**< number of resultant variables */ 2561 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 2562 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 2563 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */ 2564 SCIP_Longint*const mult, /**< multiplier for the coefficients */ 2565 char const*const multisymbol /**< the multiplication symbol to use between coefficient and variable */ 2566 ) 2567 { 2568 SCIP_VAR* var; 2569 char buffer[OPB_MAX_LINELEN]; 2570 char linebuffer[OPB_MAX_LINELEN + 1]; 2571 int v; 2572 int pos; 2573 int linecnt; 2574 2575 assert(scip != NULL); 2576 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0); 2577 assert(mult != NULL); 2578 assert(resvars != NULL); 2579 assert(nresvars > 0); 2580 assert(andvars != NULL && nandvars != NULL); 2581 2582 clearBuffer(linebuffer, &linecnt); 2583 2584 /* check if all coefficients are internal; if not commentstart multiplier */ 2585 for( v = 0; v < nvars; ++v ) 2586 { 2587 while( !SCIPisIntegral(scip, vals[v] * (*mult)) ) 2588 { 2589 if( ABS(*mult) > ABS(*mult * 10) ) 2590 return SCIP_INVALIDDATA; 2591 (*mult) *= 10; 2592 } 2593 } 2594 2595 while( !SCIPisIntegral(scip, lhs * (*mult)) ) 2596 { 2597 if( ABS(*mult) > ABS(*mult * 10) ) 2598 return SCIP_INVALIDDATA; 2599 (*mult) *= 10; 2600 } 2601 2602 /* print comment line if we have to multiply the coefficients to get integrals */ 2603 if( ABS(*mult) != 1 ) 2604 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) ); 2605 2606 #ifndef NDEBUG 2607 /* check that these variables are sorted */ 2608 for( v = nresvars - 1; v > 0; --v ) 2609 assert(SCIPvarGetIndex(resvars[v]) >= SCIPvarGetIndex(resvars[v - 1])); 2610 #endif 2611 2612 /* if we have a soft constraint print the weight*/ 2613 if( weight != 0 ) 2614 { 2615 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+" SCIP_LONGINT_FORMAT "] ", weight); 2616 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2617 } 2618 2619 /* print coefficients */ 2620 for( v = 0; v < nvars; ++v ) 2621 { 2622 SCIP_Bool negated; 2623 2624 var = vars[v]; 2625 assert( var != NULL ); 2626 2627 negated = SCIPvarIsNegated(var); 2628 2629 /* replace and-resultant with corresponding variables */ 2630 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, var, nresvars, &pos) ) 2631 { 2632 int a; 2633 2634 assert(andvars != NULL); 2635 assert(nandvars != NULL); 2636 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL); 2637 assert(andvars[pos][nandvars[pos] - 1] != NULL); 2638 2639 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]); 2640 2641 if( vals[v] * (*mult) > (SCIP_Real)SCIP_LONGINT_MAX ) 2642 { 2643 SCIPerrorMessage("Integral coefficient to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", *mult, vals[v], vals[v] * (*mult), (SCIP_Longint) SCIPround(scip, vals[v] * (*mult))); 2644 } 2645 2646 /* print and-vars */ 2647 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s", 2648 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "", 2649 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x") ); 2650 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2651 2652 for(a = nandvars[pos] - 2; a >= 0; --a ) 2653 { 2654 negated = SCIPvarIsNegated(andvars[pos][a]); 2655 2656 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x")); 2657 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2658 } 2659 2660 appendBuffer(scip, file, linebuffer, &linecnt, " "); 2661 } 2662 else 2663 { 2664 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ", 2665 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); 2666 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2667 } 2668 } 2669 2670 /* print left hand side */ 2671 if( SCIPisZero(scip, lhs) ) 2672 lhs = 0.0; 2673 2674 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) ); 2675 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2676 2677 writeBuffer(scip, file, linebuffer, &linecnt); 2678 2679 return SCIP_OKAY; 2680 } 2681 2682 2683 /** prints given maybe non-linear constraint information in OPB format to file stream */ 2684 static 2685 SCIP_RETCODE printNonLinearCons( 2686 SCIP*const scip, /**< SCIP data structure */ 2687 FILE*const file, /**< output file (or NULL for standard output) */ 2688 SCIP_VAR**const vars, /**< array of variables */ 2689 SCIP_Real*const vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */ 2690 int const nvars, /**< number of variables */ 2691 SCIP_Real const lhs, /**< left hand side */ 2692 SCIP_Real const rhs, /**< right hand side */ 2693 SCIP_VAR** const resvars, /**< array of resultant variables */ 2694 int const nresvars, /**< number of resultant variables */ 2695 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 2696 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 2697 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */ 2698 SCIP_Bool const transformed, /**< transformed constraint? */ 2699 char const*const multisymbol /**< the multiplication symbol to use between coefficient and variable */ 2700 ) 2701 { 2702 SCIP_VAR** activevars; 2703 SCIP_Real* activevals; 2704 SCIP_Real activeconstant; 2705 SCIP_Longint mult; 2706 SCIP_RETCODE retcode; 2707 int nactivevars; 2708 int v; 2709 2710 assert(scip != NULL); 2711 assert(vars != NULL || nvars == 0); 2712 assert(resvars != NULL); 2713 assert(nresvars > 0); 2714 assert(andvars != NULL && nandvars != NULL); 2715 2716 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 2717 return SCIP_OKAY; 2718 2719 nactivevars = nvars; 2720 activevars = NULL; 2721 activevals = NULL; 2722 activeconstant = 0.0; 2723 2724 /* duplicate variable and value array */ 2725 if( vars != NULL ) 2726 { 2727 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) ); 2728 if( vals != NULL ) 2729 { 2730 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) ); 2731 } 2732 else 2733 { 2734 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) ); 2735 2736 for( v = 0; v < nactivevars; ++v ) 2737 activevals[v] = 1.0; 2738 } 2739 2740 /* retransform given variables to active variables */ 2741 SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) ); 2742 } 2743 2744 mult = 1; 2745 retcode = SCIP_OKAY; 2746 2747 /* print row(s) in OPB format */ 2748 if( SCIPisEQ(scip, lhs, rhs) ) 2749 { 2750 assert( !SCIPisInfinity(scip, rhs) ); 2751 2752 /* equality constraint */ 2753 retcode = printNLRow(scip, file, "=", activevars, activevals, nactivevars, rhs - activeconstant, resvars, 2754 nresvars, andvars, nandvars, weight, &mult, multisymbol); 2755 } 2756 else 2757 { 2758 if( !SCIPisInfinity(scip, -lhs) ) 2759 { 2760 /* print inequality ">=" */ 2761 retcode = printNLRow(scip, file, ">=", activevars, activevals, nactivevars, lhs - activeconstant, resvars, 2762 nresvars, andvars, nandvars, weight, &mult, multisymbol); 2763 } 2764 2765 if( !SCIPisInfinity(scip, rhs) ) 2766 { 2767 mult *= -1; 2768 2769 /* print inequality ">=" and multiplying all coefficients by -1 */ 2770 retcode = printNLRow(scip, file, ">=", activevars, activevals, nactivevars, rhs - activeconstant, resvars, 2771 nresvars, andvars, nandvars, weight, &mult, multisymbol); 2772 } 2773 } 2774 2775 /* free buffer arrays */ 2776 if( vars != NULL ) 2777 { 2778 SCIPfreeBufferArray(scip, &activevals); 2779 SCIPfreeBufferArray(scip, &activevars); 2780 } 2781 2782 return retcode; 2783 } 2784 2785 2786 /* print row in OPB format to file stream */ 2787 static 2788 SCIP_RETCODE printRow( 2789 SCIP* scip, /**< SCIP data structure */ 2790 FILE* file, /**< output file (or NULL for standard output) */ 2791 const char* type, /**< row type ("=" or ">=") */ 2792 SCIP_VAR** vars, /**< array of variables */ 2793 SCIP_Real* vals, /**< array of values */ 2794 int nvars, /**< number of variables */ 2795 SCIP_Real lhs, /**< left hand side */ 2796 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */ 2797 SCIP_Longint* mult, /**< multiplier for the coefficients */ 2798 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */ 2799 ) 2800 { 2801 SCIP_VAR* var; 2802 char buffer[OPB_MAX_LINELEN]; 2803 char linebuffer[OPB_MAX_LINELEN + 1]; 2804 int v; 2805 int linecnt; 2806 2807 assert(scip != NULL); 2808 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0); 2809 assert(mult != NULL); 2810 2811 clearBuffer(linebuffer, &linecnt); 2812 2813 /* if we found the topcost linear inequality which gives us the maximal cost which could be violated by our solution, 2814 * we can stop printing because it is an artificial constraint 2815 */ 2816 if( nvars > 0 && strstr(SCIPvarGetName(vars[0]), INDICATORVARNAME) != NULL ) 2817 return SCIP_OKAY; 2818 2819 /* check if all coefficients are integral; if not commentstart multiplier */ 2820 for( v = 0; v < nvars; ++v ) 2821 { 2822 while( !SCIPisIntegral(scip, vals[v] * (*mult)) ) 2823 { 2824 if( ABS(*mult) > ABS(*mult * 10) ) 2825 return SCIP_INVALIDDATA; 2826 (*mult) *= 10; 2827 } 2828 } 2829 2830 while( !SCIPisIntegral(scip, lhs * (*mult)) ) 2831 { 2832 if( ABS(*mult) > ABS(*mult * 10) ) 2833 return SCIP_INVALIDDATA; 2834 (*mult) *= 10; 2835 } 2836 2837 /* print comment line if we have to multiply the coefficients to get integrals */ 2838 if( ABS(*mult) != 1 ) 2839 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) ); 2840 2841 /* if we have a soft constraint print the weight*/ 2842 if( weight != 0 ) 2843 { 2844 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+" SCIP_LONGINT_FORMAT "] ", weight); 2845 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2846 } 2847 2848 /* print coefficients */ 2849 for( v = 0; v < nvars; ++v ) 2850 { 2851 SCIP_Bool negated; 2852 2853 var = vars[v]; 2854 assert( var != NULL ); 2855 2856 negated = SCIPvarIsNegated(var); 2857 2858 if( vals[v] * (*mult) > (SCIP_Real)SCIP_LONGINT_MAX ) 2859 { 2860 SCIPerrorMessage("Integral coefficient to big (mult = %" SCIP_LONGINT_FORMAT ", value = %g, mult*value = %g, printingvalue = %" SCIP_LONGINT_FORMAT ")for printing in opb format.\n", *mult, vals[v], vals[v] * (*mult), (SCIP_Longint) SCIPround(scip, vals[v] * (*mult))); 2861 } 2862 2863 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ", 2864 (SCIP_Longint) SCIPround(scip, vals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); 2865 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2866 } 2867 2868 /* print left hand side */ 2869 if( SCIPisZero(scip, lhs) ) 2870 lhs = 0.0; 2871 2872 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) ); 2873 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 2874 2875 writeBuffer(scip, file, linebuffer, &linecnt); 2876 2877 return SCIP_OKAY; 2878 } 2879 2880 2881 /** prints given linear constraint information in OPB format to file stream */ 2882 static 2883 SCIP_RETCODE printLinearCons( 2884 SCIP* scip, /**< SCIP data structure */ 2885 FILE* file, /**< output file (or NULL for standard output) */ 2886 SCIP_VAR** vars, /**< array of variables */ 2887 SCIP_Real* vals, /**< array of coefficients values (or NULL if all coefficient values are 1) */ 2888 int nvars, /**< number of variables */ 2889 SCIP_Real lhs, /**< left hand side */ 2890 SCIP_Real rhs, /**< right hand side */ 2891 SCIP_Longint weight, /**< if we found a soft constraint this is the weight, otherwise 0 */ 2892 SCIP_Bool transformed, /**< transformed constraint? */ 2893 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */ 2894 ) 2895 { 2896 SCIP_VAR** activevars; 2897 SCIP_Real* activevals; 2898 SCIP_Real activeconstant; 2899 SCIP_Longint mult; 2900 SCIP_RETCODE retcode; 2901 int nactivevars; 2902 int v; 2903 2904 assert( scip != NULL ); 2905 assert( vars != NULL || nvars == 0 ); 2906 2907 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 2908 return SCIP_OKAY; 2909 2910 nactivevars = nvars; 2911 activevars = NULL; 2912 activevals = NULL; 2913 activeconstant = 0.0; 2914 2915 /* duplicate variable and value array */ 2916 if( vars != NULL ) 2917 { 2918 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) ); 2919 if( vals != NULL ) 2920 { 2921 SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) ); 2922 } 2923 else 2924 { 2925 SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) ); 2926 2927 for( v = 0; v < nactivevars; ++v ) 2928 activevals[v] = 1.0; 2929 } 2930 2931 /* retransform given variables to active variables */ 2932 SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) ); 2933 } 2934 2935 mult = 1; 2936 retcode = SCIP_OKAY; 2937 2938 /* print row(s) in OPB format */ 2939 if( SCIPisEQ(scip, lhs, rhs) ) 2940 { 2941 assert( !SCIPisInfinity(scip, rhs) ); 2942 2943 /* equality constraint */ 2944 retcode = printRow(scip, file, "=", activevars, activevals, nactivevars, rhs - activeconstant, weight, &mult, 2945 multisymbol); 2946 } 2947 else 2948 { 2949 if( !SCIPisInfinity(scip, -lhs) ) 2950 { 2951 /* print inequality ">=" */ 2952 retcode = printRow(scip, file, ">=", activevars, activevals, nactivevars, lhs - activeconstant, weight, &mult, 2953 multisymbol); 2954 } 2955 2956 if( !SCIPisInfinity(scip, rhs) ) 2957 { 2958 mult *= -1; 2959 2960 /* print inequality ">=" and multiplying all coefficients by -1 */ 2961 retcode = printRow(scip, file, ">=", activevars, activevals, nactivevars, rhs - activeconstant, weight, &mult, 2962 multisymbol); 2963 } 2964 } 2965 2966 /* free buffer arrays */ 2967 if( vars != NULL ) 2968 { 2969 SCIPfreeBufferArray(scip, &activevals); 2970 SCIPfreeBufferArray(scip, &activevars); 2971 } 2972 2973 return retcode; 2974 } 2975 2976 /* print row in OPB format to file stream */ 2977 static 2978 SCIP_RETCODE printPBRow( 2979 SCIP*const scip, /**< SCIP data structure */ 2980 FILE*const file, /**< output file (or NULL for standard output) */ 2981 const char* type, /**< row type ("=" or ">=") */ 2982 SCIP_VAR**const linvars, /**< array of variables */ 2983 SCIP_Real*const linvals, /**< array of values */ 2984 int const nlinvars, /**< number of variables */ 2985 SCIP_VAR***const termvars, /**< term array with array of variables to print */ 2986 int*const ntermvars, /**< array with number of variables in each term */ 2987 SCIP_Real*const termvals, /**< array of coefficient values for non-linear variables */ 2988 int const ntermvals, /**< number non-linear variables in the problem */ 2989 SCIP_Bool**const negatedarrays, /**< array of arrays to know which variable in a non-linear part is negated */ 2990 SCIP_VAR*const indvar, /**< indicator variable, or NULL */ 2991 SCIP_Real lhs, /**< left hand side */ 2992 SCIP_Longint* mult, /**< multiplier for the coefficients */ 2993 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */ 2994 ) 2995 { 2996 SCIP_VAR* var; 2997 char buffer[OPB_MAX_LINELEN]; 2998 char linebuffer[OPB_MAX_LINELEN + 1]; 2999 int v; 3000 int t; 3001 int linecnt; 3002 3003 assert(scip != NULL); 3004 assert(strcmp(type, "=") == 0 || strcmp(type, ">=") == 0); 3005 assert(linvars != NULL || nlinvars == 0); 3006 assert(linvals != NULL || nlinvars == 0); 3007 assert(termvars != NULL || ntermvals == 0); 3008 assert(ntermvars != NULL || ntermvals == 0); 3009 assert(termvals != NULL || ntermvals == 0); 3010 assert(negatedarrays != NULL || ntermvals == 0); 3011 assert(mult != NULL); 3012 3013 clearBuffer(linebuffer, &linecnt); 3014 3015 /* if we found the topcost linear inequality which gives us the maximal cost which could be violated by our solution, 3016 * we can stop printing because it is an artificial constraint 3017 */ 3018 if( ntermvals == 0 && nlinvars > 0 && strstr(SCIPvarGetName(linvars[0]), INDICATORVARNAME) != NULL ) /*lint !e613 */ 3019 return SCIP_OKAY; 3020 3021 /* check if all linear coefficients are internal; if not commentstart multiplier */ 3022 for( v = 0; v < nlinvars; ++v ) 3023 { 3024 while( !SCIPisIntegral(scip, linvals[v] * (*mult)) ) /*lint !e613 */ 3025 { 3026 if( ABS(*mult) > ABS(*mult * 10) ) 3027 return SCIP_INVALIDDATA; 3028 (*mult) *= 10; 3029 } 3030 } 3031 3032 /* check if all non-linear coefficients are internal; if not commentstart multiplier */ 3033 for( v = 0; v < ntermvals; ++v ) 3034 { 3035 while( !SCIPisIntegral(scip, termvals[v] * (*mult)) ) /*lint !e613 */ 3036 { 3037 if( ABS(*mult) > ABS(*mult * 10) ) 3038 return SCIP_INVALIDDATA; 3039 (*mult) *= 10; 3040 } 3041 } 3042 3043 while( !SCIPisIntegral(scip, lhs * (*mult)) ) 3044 { 3045 if( ABS(*mult) > ABS(*mult * 10) ) 3046 return SCIP_INVALIDDATA; 3047 (*mult) *= 10; 3048 } 3049 3050 /* print comment line if we have to multiply the coefficients to get integrals */ 3051 if( ABS(*mult) != 1 ) 3052 SCIPinfoMessage(scip, file, "* the following constraint is multiplied by %" SCIP_LONGINT_FORMAT " to get integral coefficients\n", ABS(*mult) ); 3053 3054 /* if indicator variable exist we have a soft constraint */ 3055 if( indvar != NULL ) 3056 { 3057 SCIP_Real weight; 3058 3059 weight = SCIPvarGetObj(indvar); 3060 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "[%+g] ", weight); 3061 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3062 } 3063 3064 /* print linear part */ 3065 for( v = 0; v < nlinvars; ++v ) 3066 { 3067 SCIP_Bool negated; 3068 3069 var = linvars[v]; /*lint !e613 */ 3070 assert(var != NULL); 3071 3072 negated = SCIPvarIsNegated(var); 3073 3074 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT "%s%s%s ", 3075 (SCIP_Longint) SCIPround(scip, linvals[v] * (*mult)), multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); /*lint !e613 */ 3076 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3077 } 3078 3079 /* print non-linear part */ 3080 for( t = 0; t < ntermvals; ++t ) 3081 { 3082 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%+" SCIP_LONGINT_FORMAT, (SCIP_Longint) SCIPround(scip, termvals[t] * (*mult))); /*lint !e613 */ 3083 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3084 3085 for( v = 0; v < ntermvars[t]; ++v ) /*lint !e613 */ 3086 { 3087 SCIP_Bool negated; 3088 3089 var = termvars[t][v]; /*lint !e613 */ 3090 assert(var != NULL); 3091 3092 negated = negatedarrays[t][v]; /*lint !e613 */ 3093 3094 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(var) : var), "x")); 3095 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3096 } 3097 appendBuffer(scip, file, linebuffer, &linecnt, " "); 3098 } 3099 3100 /* print left hand side */ 3101 if( SCIPisZero(scip, lhs) ) 3102 lhs = 0.0; 3103 3104 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s %" SCIP_LONGINT_FORMAT " ;\n", type, (SCIP_Longint) (lhs * (*mult)) ); 3105 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3106 3107 writeBuffer(scip, file, linebuffer, &linecnt); 3108 3109 return SCIP_OKAY; 3110 } 3111 3112 3113 /** prints given pseudo boolean constraint information in OPB format to file stream */ 3114 static 3115 SCIP_RETCODE printPseudobooleanCons( 3116 SCIP*const scip, /**< SCIP data structure */ 3117 FILE*const file, /**< output file, or NULL if standard output should be used */ 3118 SCIP_VAR**const linvars, /**< array with variables of linear part */ 3119 SCIP_Real*const linvals, /**< array of coefficients values of linear part */ 3120 int const nlinvars, /**< number variables in linear part of the problem */ 3121 SCIP_VAR***const termvars, /**< term array with array of variables to print */ 3122 int*const ntermvars, /**< array with number of variables in each term */ 3123 SCIP_Real*const termvals, /**< array of coefficient values for non-linear variables */ 3124 int const ntermvals, /**< number non-linear variables in the problem */ 3125 SCIP_VAR*const indvar, /**< indicator variable, or NULL */ 3126 SCIP_Real const lhs, /**< left hand side of constraint */ 3127 SCIP_Real const rhs, /**< right hand side of constraint */ 3128 SCIP_Bool transformed, /**< should the transformed problem be printed ? */ 3129 const char* multisymbol /**< the multiplication symbol to use between coefficient and variable */ 3130 ) 3131 { 3132 SCIP_VAR*** activetermvars; 3133 SCIP_Bool** negatedarrays; 3134 SCIP_VAR** activelinvars; 3135 SCIP_Real* activelinvals; 3136 int nactivelinvars; 3137 SCIP_Real activelinconstant; 3138 SCIP_Longint mult; 3139 SCIP_RETCODE retcode; 3140 int v; 3141 3142 assert(scip != NULL); 3143 assert(linvars != NULL || nlinvars == 0); 3144 assert(linvals != NULL || nlinvars == 0); 3145 assert(termvars != NULL || 0 == ntermvals); 3146 assert(ntermvars != NULL || 0 == ntermvals); 3147 assert(termvals != NULL || 0 == ntermvals); 3148 assert(lhs <= rhs); 3149 3150 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 3151 return SCIP_OKAY; 3152 3153 activelinconstant = 0.0; 3154 3155 /* duplicate variable and value array for linear part */ 3156 nactivelinvars = nlinvars; 3157 if( nactivelinvars > 0 ) 3158 { 3159 SCIP_CALL( SCIPduplicateBufferArray(scip, &activelinvars, linvars, nactivelinvars ) ); 3160 SCIP_CALL( SCIPduplicateBufferArray(scip, &activelinvals, linvals, nactivelinvars ) ); 3161 3162 /* retransform given variables to active variables */ 3163 SCIP_CALL( getActiveVariables(scip, activelinvars, activelinvals, &nactivelinvars, &activelinconstant, transformed) ); 3164 } 3165 else 3166 { 3167 activelinvars = NULL; 3168 activelinvals = NULL; 3169 } 3170 3171 /* create non-linear information for printing */ 3172 if( ntermvals > 0 ) 3173 { 3174 assert(termvars != NULL); 3175 assert(ntermvars != NULL); 3176 assert(termvals != NULL); 3177 3178 SCIP_CALL( SCIPallocBufferArray(scip, &activetermvars, ntermvals) ); 3179 SCIP_CALL( SCIPallocBufferArray(scip, &negatedarrays, ntermvals) ); 3180 for( v = ntermvals - 1; v >= 0; --v ) 3181 { 3182 assert(ntermvars[v] > 0); /*lint !e613 */ 3183 3184 if( transformed ) 3185 { 3186 SCIP_CALL( SCIPallocBufferArray(scip, &(activetermvars[v]), ntermvars[v]) ); /*lint !e866 */ 3187 SCIP_CALL( SCIPallocBufferArray(scip, &(negatedarrays[v]), ntermvars[v]) ); /*lint !e866 */ 3188 3189 /* get binary representatives of binary variables in non-linear terms */ 3190 SCIP_CALL( SCIPgetBinvarRepresentatives(scip, ntermvars[v], termvars[v], activetermvars[v], negatedarrays[v]) ); 3191 } 3192 else 3193 { 3194 SCIP_CALL( SCIPduplicateBufferArray(scip, &(activetermvars[v]), termvars[v], ntermvars[v]) ); /*lint !e866 */ 3195 SCIP_CALL( SCIPallocBufferArray(scip, &(negatedarrays[v]), ntermvars[v]) ); /*lint !e866 */ 3196 BMSclearMemoryArray(negatedarrays[v], ntermvars[v]); /*lint !e866 */ 3197 } 3198 } 3199 } 3200 else 3201 { 3202 activetermvars = NULL; 3203 negatedarrays = NULL; 3204 } 3205 3206 mult = 1; 3207 retcode = SCIP_OKAY; 3208 3209 /* print row(s) in OPB format */ 3210 if( SCIPisEQ(scip, lhs, rhs) ) 3211 { 3212 assert( !SCIPisInfinity(scip, rhs) ); 3213 3214 /* equality constraint */ 3215 retcode = printPBRow(scip, file, "=", activelinvars, activelinvals, nactivelinvars, activetermvars, 3216 ntermvars, termvals, ntermvals, negatedarrays, indvar, rhs - activelinconstant, &mult, multisymbol); 3217 } 3218 else 3219 { 3220 if( !SCIPisInfinity(scip, -lhs) ) 3221 { 3222 /* print inequality ">=" */ 3223 retcode = printPBRow(scip, file, ">=", activelinvars, activelinvals, nactivelinvars, activetermvars, 3224 ntermvars, termvals, ntermvals, negatedarrays, indvar, lhs - activelinconstant, &mult, multisymbol); 3225 } 3226 3227 if( !SCIPisInfinity(scip, rhs) ) 3228 { 3229 mult *= -1; 3230 3231 /* print inequality ">=" and multiplying all coefficients by -1 */ 3232 /* coverity[var_deref_model] */ 3233 retcode = printPBRow(scip, file, ">=", activelinvars, activelinvals, nactivelinvars, activetermvars, 3234 ntermvars, termvals, ntermvals, negatedarrays, indvar, rhs - activelinconstant, &mult, multisymbol); 3235 } 3236 } 3237 3238 /* free buffers for non-linear arrays */ 3239 if( ntermvals > 0 ) 3240 { 3241 assert(negatedarrays != NULL); 3242 assert(activetermvars != NULL); 3243 3244 for( v = 0; v < ntermvals; ++v ) 3245 { 3246 assert(negatedarrays[v] != NULL); 3247 assert(activetermvars[v] != NULL); 3248 SCIPfreeBufferArray(scip, &(negatedarrays[v])); 3249 SCIPfreeBufferArray(scip, &(activetermvars[v])); 3250 } 3251 SCIPfreeBufferArray(scip, &negatedarrays); 3252 SCIPfreeBufferArray(scip, &activetermvars); 3253 } 3254 3255 /* free buffer for linear arrays */ 3256 if( nactivelinvars > 0 ) 3257 { 3258 SCIPfreeBufferArray(scip, &activelinvals); 3259 SCIPfreeBufferArray(scip, &activelinvars); 3260 } 3261 3262 return retcode; 3263 } 3264 3265 /** determine total number of linear constraints split into lhs/rhs */ 3266 static 3267 void determineTotalNumberLinearConss( 3268 SCIP*const scip, /**< SCIP data structure */ 3269 SCIP_CONS**const conss, /**< array with constraints of the problem */ 3270 int const nconss, /**< number of constraints in the problem */ 3271 int* nlinearconss, /**< pointer to store the total number of linear constraints */ 3272 int* nsplitlinearconss /**< pointer to store the total number of linear constraints split into lhs/rhs */ 3273 ) 3274 { 3275 SCIP_CONSHDLR* conshdlr; 3276 const char* conshdlrname; 3277 SCIP_CONS* cons; 3278 int c; 3279 3280 assert(scip != NULL); 3281 assert(conss != NULL || nconss == 0); 3282 assert(nlinearconss != NULL); 3283 assert(nsplitlinearconss != NULL); 3284 3285 *nlinearconss = 0; 3286 *nsplitlinearconss = 0; 3287 3288 /* loop over all constraints */ 3289 for( c = 0; c < nconss; ++c ) 3290 { 3291 cons = conss[c]; 3292 assert(cons != NULL); 3293 conshdlr = SCIPconsGetHdlr(cons); /*lint !e613*/ 3294 assert(conshdlr != NULL); 3295 3296 conshdlrname = SCIPconshdlrGetName(conshdlr); 3297 3298 if( strcmp(conshdlrname, "linear") == 0 ) 3299 { 3300 if( ! SCIPisInfinity(scip, SCIPgetLhsLinear(scip, cons)) ) 3301 ++(*nsplitlinearconss); 3302 3303 if( ! SCIPisInfinity(scip, SCIPgetRhsLinear(scip, cons)) ) 3304 ++(*nsplitlinearconss); 3305 3306 ++(*nlinearconss); 3307 } 3308 3309 if( strcmp(conshdlrname, "varbound") == 0 ) 3310 { 3311 if( ! SCIPisInfinity(scip, SCIPgetLhsVarbound(scip, cons)) ) 3312 ++(*nsplitlinearconss); 3313 3314 if( ! SCIPisInfinity(scip, SCIPgetRhsVarbound(scip, cons)) ) 3315 ++(*nsplitlinearconss); 3316 3317 ++(*nlinearconss); 3318 } 3319 } 3320 } 3321 3322 /** write constraints */ 3323 static 3324 SCIP_RETCODE writeOpbConstraints( 3325 SCIP*const scip, /**< SCIP data structure */ 3326 FILE*const file, /**< output file, or NULL if standard output should be used */ 3327 SCIP_CONS**const conss, /**< array with constraints of the problem */ 3328 int const nconss, /**< number of constraints in the problem */ 3329 SCIP_VAR**const vars, /**< array with active (binary) variables */ 3330 int const nvars, /**< number of active variables in the problem */ 3331 SCIP_VAR** const resvars, /**< array of resultant variables */ 3332 int const nresvars, /**< number of resultant variables */ 3333 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 3334 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 3335 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */ 3336 SCIP_Bool const existandconshdlr, /**< does and-constrainthandler exist? */ 3337 SCIP_Bool const existands, /**< does some and-constraints exist? */ 3338 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */ 3339 ) 3340 { 3341 SCIP_CONSHDLR* conshdlr; 3342 const char* conshdlrname; 3343 SCIP_CONS* cons; 3344 SCIP_VAR** consvars; 3345 SCIP_Real* consvals; 3346 SCIP_RETCODE retcode; 3347 int nconsvars; 3348 int v, c; 3349 SCIP_HASHMAP* linconssofindicatorsmap = NULL; 3350 SCIP_HASHMAP* linconssofpbsmap = NULL; 3351 3352 assert(scip != NULL); 3353 assert(file != NULL); 3354 assert(conss != NULL || nconss == 0); 3355 assert(vars != NULL || nvars == 0); 3356 assert(resvars != NULL || nresvars == 0); 3357 assert(andvars != NULL || nandvars == 0); 3358 assert(multisymbol != NULL); 3359 3360 if( transformed ) 3361 { 3362 conshdlr = SCIPfindConshdlr(scip, "indicator"); 3363 3364 /* find artificial linear constraints which correspond to indicator constraints to avoid double printing */ 3365 if( conshdlr != NULL ) 3366 { 3367 SCIP_CONS** indconss; 3368 int nindconss; 3369 3370 indconss = SCIPconshdlrGetConss(conshdlr); 3371 nindconss = SCIPconshdlrGetNConss(conshdlr); 3372 assert(indconss != NULL || nindconss == 0); 3373 3374 if( nindconss > 0 ) 3375 { 3376 SCIP_CONS* lincons; 3377 3378 /* create the linear constraint of indicator constraints hash map */ 3379 SCIP_CALL( SCIPhashmapCreate(&linconssofindicatorsmap, SCIPblkmem(scip), nindconss) ); 3380 assert(indconss != NULL); 3381 3382 for( c = 0; c < nindconss; ++c ) 3383 { 3384 assert(indconss[c] != NULL); 3385 lincons = SCIPgetLinearConsIndicator(indconss[c]); 3386 assert(lincons != NULL); 3387 3388 /* insert constraint into mapping between */ 3389 SCIP_CALL( SCIPhashmapInsert(linconssofindicatorsmap, (void*)lincons, (void*)lincons) ); 3390 } 3391 } 3392 } 3393 3394 conshdlr = SCIPfindConshdlr(scip, "pseudoboolean"); 3395 3396 /* find artifical linear constraints which correspond to indicator constraints to avoid double printing */ 3397 if( conshdlr != NULL ) 3398 { 3399 SCIP_CONS** pbconss; 3400 int npbconss; 3401 3402 pbconss = SCIPconshdlrGetConss(conshdlr); 3403 npbconss = SCIPconshdlrGetNConss(conshdlr); 3404 assert(pbconss != NULL || npbconss == 0); 3405 3406 if( npbconss > 0 ) 3407 { 3408 SCIP_CONS* lincons; 3409 3410 /* create the linear constraint of indicator constraints hash map */ 3411 SCIP_CALL( SCIPhashmapCreate(&linconssofpbsmap, SCIPblkmem(scip), npbconss) ); 3412 3413 for( c = 0; c < npbconss; ++c ) 3414 { 3415 assert(pbconss[c] != NULL); /*lint !e613*/ 3416 lincons = SCIPgetLinearConsPseudoboolean(scip, pbconss[c]); /*lint !e613*/ 3417 assert(lincons != NULL); 3418 3419 /* insert constraint into mapping between */ 3420 SCIP_CALL( SCIPhashmapInsert(linconssofpbsmap, (void*)lincons, (void*)lincons) ); 3421 } 3422 } 3423 } 3424 } 3425 /* in original space we cannot ask the constraint handler for its constraints, therefore we have to loop over all 3426 * original to check for artificial linear once 3427 */ 3428 else 3429 { 3430 SCIP_CONS* lincons; 3431 SCIP_Bool pbhashmapcreated = FALSE; 3432 SCIP_Bool indhashmapcreated = FALSE; 3433 3434 /* loop over all constraint for printing */ 3435 for( c = 0; c < nconss; ++c ) 3436 { 3437 conshdlr = SCIPconsGetHdlr(conss[c]); /*lint !e613*/ 3438 assert(conshdlr != NULL); 3439 3440 conshdlrname = SCIPconshdlrGetName(conshdlr); 3441 3442 if( strcmp(conshdlrname, "pseudoboolean") == 0 ) 3443 { 3444 if( !pbhashmapcreated ) 3445 { 3446 /* create the linear constraint of indicator constraints hash map */ 3447 SCIP_CALL( SCIPhashmapCreate(&linconssofpbsmap, SCIPblkmem(scip), nconss) ); 3448 pbhashmapcreated = TRUE; 3449 } 3450 3451 lincons = SCIPgetLinearConsPseudoboolean(scip, conss[c]); /*lint !e613*/ 3452 assert(lincons != NULL); 3453 3454 /* insert constraint into mapping between */ 3455 SCIP_CALL( SCIPhashmapInsert(linconssofpbsmap, (void*)lincons, (void*)lincons) ); 3456 } 3457 else if( strcmp(conshdlrname, "indicator") == 0 ) 3458 { 3459 if( !indhashmapcreated ) 3460 { 3461 /* create the linear constraint of indicator constraints hash map */ 3462 SCIP_CALL( SCIPhashmapCreate(&linconssofindicatorsmap, SCIPblkmem(scip), nconss) ); 3463 indhashmapcreated = TRUE; 3464 } 3465 3466 lincons = SCIPgetLinearConsIndicator(conss[c]); /*lint !e613*/ 3467 assert(lincons != NULL); 3468 3469 /* insert constraint into mapping between */ 3470 SCIP_CALL( SCIPhashmapInsert(linconssofindicatorsmap, (void*)lincons, (void*)lincons) ); 3471 } 3472 } 3473 } 3474 3475 retcode = SCIP_OKAY; 3476 cons = NULL; 3477 3478 /* loop over all constraint for printing */ 3479 for( c = 0; c < nconss && retcode == SCIP_OKAY; ++c ) 3480 { 3481 SCIP_CONS* artcons; 3482 3483 artcons = NULL; 3484 3485 cons = conss[c]; /*lint !e613 */ 3486 assert(cons != NULL); 3487 3488 conshdlr = SCIPconsGetHdlr(cons); 3489 assert(conshdlr != NULL); 3490 3491 conshdlrname = SCIPconshdlrGetName(conshdlr); 3492 assert(transformed == SCIPconsIsTransformed(cons)); 3493 3494 /* in case the transformed is written only constraint are posted which are enabled in the current node */ 3495 assert(!transformed || SCIPconsIsEnabled(cons)); 3496 3497 if( linconssofpbsmap != NULL ) 3498 artcons = (SCIP_CONS*) SCIPhashmapGetImage(linconssofpbsmap, (void*)cons); 3499 if( artcons == NULL && linconssofindicatorsmap != NULL ) 3500 artcons = (SCIP_CONS*) SCIPhashmapGetImage(linconssofindicatorsmap, (void*)cons); 3501 3502 if( artcons == NULL ) 3503 { 3504 if( strcmp(conshdlrname, "linear") == 0 ) 3505 { 3506 if( existands ) 3507 { 3508 retcode = printNonLinearCons(scip, file, 3509 SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons), 3510 SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), resvars, nresvars, andvars, nandvars, 3511 0LL, transformed, multisymbol); 3512 } 3513 else 3514 { 3515 retcode = printLinearCons(scip, file, 3516 SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons), 3517 SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons), 0LL, transformed, multisymbol); 3518 } 3519 } 3520 else if( strcmp(conshdlrname, "setppc") == 0 ) 3521 { 3522 consvars = SCIPgetVarsSetppc(scip, cons); 3523 nconsvars = SCIPgetNVarsSetppc(scip, cons); 3524 3525 switch( SCIPgetTypeSetppc(scip, cons) ) 3526 { 3527 case SCIP_SETPPCTYPE_PARTITIONING : 3528 if( existands ) 3529 { 3530 retcode = printNonLinearCons(scip, file, consvars, NULL, nconsvars, 1.0, 1.0, resvars, nresvars, 3531 andvars, nandvars, 0LL, transformed, multisymbol); 3532 } 3533 else 3534 { 3535 retcode = printLinearCons(scip, file, 3536 consvars, NULL, nconsvars, 1.0, 1.0, 0LL, transformed, multisymbol); 3537 } 3538 break; 3539 case SCIP_SETPPCTYPE_PACKING : 3540 if( existands ) 3541 { 3542 retcode = printNonLinearCons(scip, file, 3543 consvars, NULL, nconsvars, -SCIPinfinity(scip), 1.0, resvars, nresvars, andvars, nandvars, 3544 0LL, transformed, multisymbol); 3545 } 3546 else 3547 { 3548 retcode = printLinearCons(scip, file, 3549 consvars, NULL, nconsvars, -SCIPinfinity(scip), 1.0, 0LL, transformed, multisymbol); 3550 } 3551 break; 3552 case SCIP_SETPPCTYPE_COVERING : 3553 if( existands ) 3554 { 3555 retcode = printNonLinearCons(scip, file, 3556 consvars, NULL, nconsvars, 1.0, SCIPinfinity(scip), resvars, nresvars, andvars, nandvars, 3557 0LL, transformed, multisymbol); 3558 } 3559 else 3560 { 3561 retcode = printLinearCons(scip, file, 3562 consvars, NULL, nconsvars, 1.0, SCIPinfinity(scip), 0LL, transformed, multisymbol); 3563 } 3564 break; 3565 } 3566 } 3567 else if( strcmp(conshdlrname, "logicor") == 0 ) 3568 { 3569 if( existands ) 3570 { 3571 retcode = printNonLinearCons(scip, file, 3572 SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip), 3573 resvars, nresvars, andvars, nandvars, 0LL, transformed, multisymbol); 3574 } 3575 else 3576 { 3577 retcode = printLinearCons(scip, file, 3578 SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), 3579 1.0, SCIPinfinity(scip), 0LL, transformed, multisymbol); 3580 } 3581 } 3582 else if( strcmp(conshdlrname, "knapsack") == 0 ) 3583 { 3584 SCIP_Longint* weights; 3585 3586 consvars = SCIPgetVarsKnapsack(scip, cons); 3587 nconsvars = SCIPgetNVarsKnapsack(scip, cons); 3588 3589 /* copy Longint array to SCIP_Real array */ 3590 weights = SCIPgetWeightsKnapsack(scip, cons); 3591 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) ); 3592 for( v = 0; v < nconsvars; ++v ) 3593 consvals[v] = (SCIP_Real)weights[v]; 3594 3595 if( existands ) 3596 { 3597 retcode = printNonLinearCons(scip, file, consvars, consvals, nconsvars, -SCIPinfinity(scip), 3598 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), resvars, nresvars, andvars, nandvars, 3599 0LL, transformed, multisymbol); 3600 } 3601 else 3602 { 3603 retcode = printLinearCons(scip, file, consvars, consvals, nconsvars, -SCIPinfinity(scip), 3604 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), 0LL, transformed, multisymbol); 3605 } 3606 3607 SCIPfreeBufferArray(scip, &consvals); 3608 } 3609 else if( strcmp(conshdlrname, "varbound") == 0 ) 3610 { 3611 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) ); 3612 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) ); 3613 3614 consvars[0] = SCIPgetVarVarbound(scip, cons); 3615 consvars[1] = SCIPgetVbdvarVarbound(scip, cons); 3616 3617 consvals[0] = 1.0; 3618 consvals[1] = SCIPgetVbdcoefVarbound(scip, cons); 3619 3620 if( existands ) 3621 { 3622 retcode = printNonLinearCons(scip, file, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons), 3623 SCIPgetRhsVarbound(scip, cons), resvars, nresvars, andvars, nandvars, 0LL, transformed, multisymbol); 3624 } 3625 else 3626 { 3627 retcode = printLinearCons(scip, file, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons), 3628 SCIPgetRhsVarbound(scip, cons), 0LL, transformed, multisymbol); 3629 } 3630 3631 SCIPfreeBufferArray(scip, &consvals); 3632 SCIPfreeBufferArray(scip, &consvars); 3633 } 3634 else if( strcmp(conshdlrname, "pseudoboolean") == 0 ) 3635 { 3636 SCIP_VAR*** termvars; 3637 int* ntermvars; 3638 int termvarssize; 3639 SCIP_CONS** andconss; 3640 SCIP_Real* andcoefs ; 3641 SCIP_VAR** linvars; 3642 SCIP_Real* lincoefs ; 3643 int nlinvars; 3644 int t; 3645 3646 /* get the required array size for the variables array and for the number of variables in each variable array */ 3647 termvarssize = SCIPgetNAndsPseudoboolean(scip, cons); 3648 assert(termvarssize >= 0); 3649 3650 /* allocate temporary memory */ 3651 SCIP_CALL( SCIPallocBufferArray(scip, &andconss, termvarssize) ); 3652 SCIP_CALL( SCIPallocBufferArray(scip, &termvars, termvarssize) ); 3653 SCIP_CALL( SCIPallocBufferArray(scip, &andcoefs, termvarssize) ); 3654 SCIP_CALL( SCIPallocBufferArray(scip, &ntermvars, termvarssize) ); 3655 3656 /* get all corresponding and-constraints and therefor all variables */ 3657 SCIP_CALL( SCIPgetAndDatasPseudoboolean(scip, cons, andconss, andcoefs, &termvarssize) ); 3658 for( t = termvarssize - 1; t >= 0; --t ) 3659 { 3660 termvars[t] = SCIPgetVarsAnd(scip, andconss[t]); 3661 ntermvars[t] = SCIPgetNVarsAnd(scip, andconss[t]); 3662 } 3663 3664 /* gets number of linear variables without artificial terms variables of pseudoboolean constraint */ 3665 nlinvars = SCIPgetNLinVarsWithoutAndPseudoboolean(scip, cons); 3666 3667 /* allocate temporary memory */ 3668 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, nlinvars) ); 3669 SCIP_CALL( SCIPallocBufferArray(scip, &lincoefs, nlinvars) ); 3670 3671 /* gets linear constraint of pseudoboolean constraint */ 3672 SCIP_CALL( SCIPgetLinDatasWithoutAndPseudoboolean(scip, cons, linvars, lincoefs, &nlinvars) ); 3673 3674 retcode = printPseudobooleanCons(scip, file, linvars, lincoefs, nlinvars, 3675 termvars, ntermvars, andcoefs, termvarssize, SCIPgetIndVarPseudoboolean(scip, cons), 3676 SCIPgetLhsPseudoboolean(scip, cons), SCIPgetRhsPseudoboolean(scip, cons), transformed, multisymbol); 3677 3678 /* free temporary memory */ 3679 SCIPfreeBufferArray(scip, &lincoefs); 3680 SCIPfreeBufferArray(scip, &linvars); 3681 SCIPfreeBufferArray(scip, &ntermvars); 3682 SCIPfreeBufferArray(scip, &andcoefs); 3683 SCIPfreeBufferArray(scip, &termvars); 3684 SCIPfreeBufferArray(scip, &andconss); 3685 } 3686 else if( strcmp(conshdlrname, "indicator") == 0 ) 3687 { 3688 SCIP_CONS* lincons; 3689 SCIP_VAR* indvar; 3690 SCIP_VAR* slackvar; 3691 SCIP_Longint weight; 3692 3693 /* get artificial binary indicator variables */ 3694 indvar = SCIPgetBinaryVarIndicator(cons); 3695 assert(indvar != NULL); 3696 3697 if( SCIPvarGetStatus(indvar) == SCIP_VARSTATUS_NEGATED ) 3698 { 3699 indvar = SCIPvarGetNegationVar(indvar); 3700 assert(indvar != NULL); 3701 assert(SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_AGGREGATED && SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_MULTAGGR); 3702 3703 /* get the soft cost of this constraint */ 3704 weight = (SCIP_Longint) SCIPvarGetObj(indvar); 3705 } 3706 else 3707 { 3708 assert(SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_AGGREGATED && SCIPvarGetStatus(indvar) != SCIP_VARSTATUS_MULTAGGR); 3709 3710 /* get the soft cost of this constraint */ 3711 weight = -(SCIP_Longint) SCIPvarGetObj(indvar); 3712 } 3713 3714 /* get artificial slack variable */ 3715 slackvar = SCIPgetSlackVarIndicator(cons); 3716 assert(slackvar != NULL); 3717 3718 /* only need to print indicator constraints with weights on their indicator variable */ 3719 if( weight != 0 ) 3720 { 3721 SCIP_VAR** scipvarslinear; 3722 SCIP_Real* scipvalslinear; 3723 SCIP_Bool cont; 3724 int nonbinarypos; 3725 3726 lincons = SCIPgetLinearConsIndicator(cons); 3727 assert(lincons != NULL); 3728 3729 nconsvars = SCIPgetNVarsLinear(scip, lincons); 3730 scipvarslinear = SCIPgetVarsLinear(scip, lincons); 3731 scipvalslinear = SCIPgetValsLinear(scip, lincons); 3732 3733 /* allocate temporary memory */ 3734 SCIP_CALL( SCIPduplicateBufferArray(scip, &consvars, scipvarslinear, nconsvars) ); 3735 SCIP_CALL( SCIPduplicateBufferArray(scip, &consvals, scipvalslinear, nconsvars) ); 3736 3737 nonbinarypos = -1; 3738 cont = FALSE; 3739 3740 /* find non-binary variable */ 3741 for( v = 0; v < nconsvars; ++v ) 3742 { 3743 if( SCIPvarGetType(consvars[v]) != SCIP_VARTYPE_BINARY ) 3744 { 3745 if( consvars[v] == slackvar ) 3746 { 3747 assert(nonbinarypos == -1); 3748 nonbinarypos = v; 3749 } 3750 else 3751 { 3752 SCIPwarningMessage(scip, "cannot print linear constraint <%s> of indicator constraint <%s> because it has more than one non-binary variable\n", SCIPconsGetName(lincons), SCIPconsGetName(cons) ); 3753 SCIPinfoMessage(scip, file, "* "); 3754 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3755 SCIPinfoMessage(scip, file, ";\n"); 3756 cont = TRUE; 3757 break; 3758 } 3759 } 3760 } 3761 3762 /* if we have not found any non-binary variable we do not print the constraint, maybe we should ??? */ 3763 if( nonbinarypos == -1 ) 3764 { 3765 SCIPwarningMessage(scip, "cannot print linear constraint <%s> of indicator constraint <%s> because it has no slack variable\n", SCIPconsGetName(lincons), SCIPconsGetName(cons) ); 3766 SCIPinfoMessage(scip, file, "* "); 3767 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3768 SCIPinfoMessage(scip, file, ";\n"); 3769 3770 /* free temporary memory */ 3771 SCIPfreeBufferArray(scip, &consvals); 3772 SCIPfreeBufferArray(scip, &consvars); 3773 continue; 3774 } 3775 3776 /* if the constraint has more than two non-binary variables is not printable and we go to the next */ 3777 if( cont ) 3778 { 3779 /* free temporary memory */ 3780 SCIPfreeBufferArray(scip, &consvals); 3781 SCIPfreeBufferArray(scip, &consvars); 3782 continue; 3783 } 3784 3785 assert(0 <= nonbinarypos && nonbinarypos < nconsvars); 3786 3787 /* remove slackvariable in linear constraint for printing */ 3788 --nconsvars; 3789 consvars[nonbinarypos] = consvars[nconsvars]; 3790 consvals[nonbinarypos] = consvals[nconsvars]; 3791 3792 if( existands ) 3793 { 3794 retcode = printNonLinearCons(scip, file, 3795 consvars, consvals, nconsvars, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons), 3796 resvars, nresvars, andvars, nandvars, 3797 weight, transformed, multisymbol); 3798 } 3799 else 3800 { 3801 retcode = printLinearCons(scip, file, 3802 consvars, consvals, nconsvars, SCIPgetLhsLinear(scip, lincons), SCIPgetRhsLinear(scip, lincons), 3803 weight, transformed, multisymbol); 3804 } 3805 3806 /* free temporary memory */ 3807 SCIPfreeBufferArray(scip, &consvals); 3808 SCIPfreeBufferArray(scip, &consvars); 3809 } 3810 else 3811 { 3812 SCIPwarningMessage(scip, "indicator constraint <%s> will not be printed because the indicator variable has no objective value(= weight of this soft constraint)\n", SCIPconsGetName(cons) ); 3813 SCIPinfoMessage(scip, file, "* "); 3814 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3815 SCIPinfoMessage(scip, file, ";\n"); 3816 } 3817 } 3818 else if( strcmp(conshdlrname, "and") == 0 ) 3819 { 3820 /* all resultants of the and constraint will be replaced by all corresponding variables of this constraint, 3821 * so no and-constraint will be printed directly */ 3822 assert(existandconshdlr); 3823 } 3824 else 3825 { 3826 SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname ); 3827 SCIPinfoMessage(scip, file, "* "); 3828 SCIP_CALL( SCIPprintCons(scip, cons, file) ); 3829 SCIPinfoMessage(scip, file, ";\n"); 3830 } 3831 } 3832 } 3833 3834 if( retcode == SCIP_INVALIDDATA ) 3835 { 3836 assert(cons != NULL); 3837 3838 SCIPerrorMessage("Cannot print constraint %s with non-integral coefficient or sides in opb-format\n", 3839 SCIPconsGetName(cons)); 3840 SCIP_CALL( SCIPprintCons(scip, cons, stderr) ); 3841 SCIPinfoMessage(scip, file, ";\n"); 3842 } 3843 3844 if( linconssofpbsmap != NULL ) 3845 { 3846 /* free hash map */ 3847 SCIPhashmapFree(&linconssofpbsmap); 3848 } 3849 if( linconssofindicatorsmap != NULL ) 3850 { 3851 /* free hash map */ 3852 SCIPhashmapFree(&linconssofindicatorsmap); 3853 } 3854 3855 return retcode; 3856 } 3857 3858 /* write fixed variables (unless already done because they are an and resultant or and variable) */ 3859 static 3860 SCIP_RETCODE writeOpbFixedVars( 3861 SCIP*const scip, /**< SCIP data structure */ 3862 FILE*const file, /**< output file, or NULL if standard output should be used */ 3863 SCIP_VAR** vars, /**< array with active (binary) variables */ 3864 int nvars, /**< number of active variables in the problem */ 3865 SCIP_HASHTABLE*const printedfixing, /**< hashmap to store if a fixed variable was already printed */ 3866 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */ 3867 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */ 3868 ) 3869 { 3870 char linebuffer[OPB_MAX_LINELEN+1]; 3871 char buffer[OPB_MAX_LINELEN]; 3872 int linecnt; 3873 int v; 3874 3875 assert(scip != NULL); 3876 assert(file != NULL); 3877 assert(vars != NULL || nvars == 0); 3878 assert(printedfixing != NULL); 3879 assert(multisymbol != NULL); 3880 3881 clearBuffer(linebuffer, &linecnt); 3882 3883 /* print variables which are fixed */ 3884 for( v = 0; v < nvars; ++v ) 3885 { 3886 SCIP_VAR* var; 3887 SCIP_Real lb; 3888 SCIP_Real ub; 3889 SCIP_Bool neg = FALSE; 3890 3891 assert( vars != NULL ); 3892 var = vars[v]; 3893 3894 if( transformed ) 3895 { 3896 /* in case the transformed is written only local bounds are posted which are valid in the current node */ 3897 lb = SCIPvarGetLbLocal(var); 3898 ub = SCIPvarGetUbLocal(var); 3899 } 3900 else 3901 { 3902 lb = SCIPvarGetLbOriginal(var); 3903 ub = SCIPvarGetUbOriginal(var); 3904 } 3905 assert(lb > -0.5 && ub < 1.5); 3906 assert(SCIPisFeasIntegral(scip, lb)); 3907 assert(SCIPisFeasIntegral(scip, ub)); 3908 3909 /* print fixed and-resultants */ 3910 if( lb > 0.5 || ub < 0.5 ) 3911 { 3912 if( transformed ) { 3913 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &var, &neg) ); 3914 } 3915 3916 if( SCIPhashtableExists(printedfixing, (void*)var) ) 3917 continue; 3918 3919 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb); 3920 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3921 3922 /* add variable to the hashmap */ 3923 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) ); 3924 } 3925 } 3926 3927 writeBuffer(scip, file, linebuffer, &linecnt); 3928 3929 return SCIP_OKAY; 3930 } 3931 3932 /* write and constraints of inactive but relevant and-resultants and and variables which are fixed to one */ 3933 static 3934 SCIP_RETCODE writeOpbRelevantAnds( 3935 SCIP*const scip, /**< SCIP data structure */ 3936 FILE*const file, /**< output file, or NULL if standard output should be used */ 3937 SCIP_VAR**const resvars, /**< array of resultant variables */ 3938 int const nresvars, /**< number of resultant variables */ 3939 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 3940 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 3941 SCIP_HASHTABLE*const printedfixing, /**< hashmap to store if a fixed variable was already printed */ 3942 char const*const multisymbol, /**< the multiplication symbol to use between coefficient and variable */ 3943 SCIP_Bool const transformed /**< TRUE iff problem is the transformed problem */ 3944 ) 3945 { 3946 SCIP_VAR* resvar; 3947 SCIP_Longint rhslhs; 3948 char linebuffer[OPB_MAX_LINELEN+1]; 3949 char buffer[OPB_MAX_LINELEN]; 3950 int linecnt; 3951 int r, v; 3952 3953 assert(scip != NULL); 3954 assert(file != NULL); 3955 assert(resvars != NULL || nresvars == 0); 3956 assert(nandvars != NULL || nresvars == 0); 3957 assert(andvars != NULL || nandvars == NULL); 3958 assert(multisymbol != NULL); 3959 3960 clearBuffer(linebuffer, &linecnt); 3961 3962 /* print and-variables which are fixed */ 3963 /* @todo remove this block here and the hashtable and let writeOpbFixedVars() do the job? */ 3964 for( r = nresvars - 1; r >= 0; --r ) 3965 { 3966 SCIP_VAR* var; 3967 SCIP_Bool neg; 3968 SCIP_Real lb; 3969 SCIP_Real ub; 3970 3971 assert( resvars != NULL ); 3972 resvar = resvars[r]; 3973 3974 if( transformed ) 3975 { 3976 /* in case the transformed is written only local bounds are posted which are valid in the current node */ 3977 lb = SCIPvarGetLbLocal(resvar); 3978 ub = SCIPvarGetUbLocal(resvar); 3979 } 3980 else 3981 { 3982 lb = SCIPvarGetLbOriginal(resvar); 3983 ub = SCIPvarGetUbOriginal(resvar); 3984 } 3985 3986 /* print fixed and-resultants */ 3987 if( lb > 0.5 || ub < 0.5 ) 3988 { 3989 /* coverity[copy_paste_error] */ 3990 SCIP_CALL( SCIPgetBinvarRepresentative(scip, resvar, &var, &neg) ); 3991 3992 assert(SCIPisFeasIntegral(scip, lb)); 3993 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb); 3994 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 3995 3996 /* add variable to the hashmap */ 3997 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) ); 3998 } 3999 4000 assert( andvars != NULL && nandvars != NULL ); 4001 assert( andvars[r] != NULL || nandvars[r] == 0 ); 4002 4003 /* print fixed and-variables */ 4004 for( v = nandvars[r] - 1; v >= 0; --v ) /*lint !e613 */ 4005 { 4006 assert( andvars[r] != NULL ); 4007 assert( andvars[r][v] != NULL ); 4008 4009 if( transformed ) 4010 { 4011 /* in case the transformed is written only local bounds are posted which are valid in the current node */ 4012 lb = SCIPvarGetLbLocal(andvars[r][v]); 4013 ub = SCIPvarGetUbLocal(andvars[r][v]); 4014 } 4015 else 4016 { 4017 lb = SCIPvarGetLbOriginal(andvars[r][v]); 4018 ub = SCIPvarGetUbOriginal(andvars[r][v]); 4019 } 4020 4021 if( lb > 0.5 || ub < 0.5 ) 4022 { 4023 SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[r][v], &var, &neg) ); /*lint !e613 */ 4024 4025 assert(SCIPisFeasIntegral(scip, lb)); 4026 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "+1%s%s%s = %g ;\n", multisymbol, neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x"), lb); 4027 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4028 4029 /* add variable to the hashmap */ 4030 SCIP_CALL( SCIPhashtableInsert(printedfixing, (void*)var) ); 4031 } 4032 } 4033 } 4034 4035 /* print and-constraints with fixed and-resultant to zero and all and-constraints with 4036 * aggregated resultant, otherwise we would loose this information 4037 */ 4038 for( r = nresvars - 1; r >= 0; --r ) 4039 { 4040 assert( resvars != NULL ); 4041 resvar = resvars[r]; 4042 rhslhs = (SCIPvarGetUbLocal(resvar) < 0.5) ? 0 : ((SCIPvarGetLbLocal(resvar) > 0.5) ? 1 : -1); 4043 4044 /* if and resultant is fixed to 0 and at least one and-variable is fixed to zero, we don't print this redundant constraint */ 4045 if( rhslhs == 0 ) 4046 { 4047 SCIP_Bool cont; 4048 4049 cont = FALSE; 4050 4051 assert( andvars != NULL && nandvars != NULL ); 4052 assert( andvars[r] != NULL || nandvars[r] == 0 ); 4053 4054 /* if resultant variable and one other and variable is already zero, so we did not need to print this and 4055 * constraint because all other variables are free 4056 */ 4057 for( v = nandvars[r] - 1; v >= 0; --v ) /*lint !e613 */ 4058 { 4059 assert( andvars[r] != NULL ); 4060 assert( andvars[r][v] != NULL ); 4061 4062 if( SCIPvarGetUbLocal(andvars[r][v]) < 0.5 ) /*lint !e613 */ 4063 { 4064 cont = TRUE; 4065 break; 4066 } 4067 } 4068 4069 if( cont ) 4070 continue; 4071 } 4072 /* if and resultant is fixed to 1 and all and-variable are fixed to 1 too, we don't print this redundant constraint */ 4073 else if( rhslhs == 1 ) 4074 { 4075 SCIP_Bool cont; 4076 4077 cont = TRUE; 4078 4079 assert( andvars != NULL && nandvars != NULL ); 4080 assert( andvars[r] != NULL || nandvars[r] == 0 ); 4081 4082 /* if all variables are already fixed to one, we do not need to print this and constraint */ 4083 for( v = nandvars[r] - 1; v >= 0; --v ) 4084 { 4085 assert( andvars[r] != NULL ); 4086 assert( andvars[r][v] != NULL ); 4087 4088 if( SCIPvarGetLbLocal(andvars[r][v]) < 0.5 ) /*lint !e613 */ 4089 { 4090 cont = FALSE; 4091 break; 4092 } 4093 } 4094 4095 if( cont ) 4096 continue; 4097 } 4098 4099 /* print and with fixed or aggregated and-resultant */ 4100 /* rhslhs equals to 0 means the and constraint is relevant due to it's not clear on which values the and variables are 4101 * rhslhs equals to 1 means the and constraint is irrelevant cause all and variables have to be 1 too 4102 * rhslhs equals to -1 means the and constraint is relevant cause the variable is only aggregated */ 4103 if( !SCIPvarIsActive(resvar) ) 4104 { 4105 SCIP_VAR* var; 4106 SCIP_Bool neg; 4107 SCIP_Bool firstprinted; 4108 4109 firstprinted = FALSE; 4110 4111 assert( andvars != NULL && nandvars != NULL ); 4112 assert( andvars[r] != NULL || nandvars[r] == 0 ); 4113 4114 for( v = nandvars[r] - 1; v >= 0; --v ) 4115 { 4116 assert( andvars[r] != NULL ); 4117 assert( andvars[r][v] != NULL ); 4118 4119 SCIP_CALL( SCIPgetBinvarRepresentative(scip, andvars[r][v], &var, &neg) ); /*lint !e613 */ 4120 4121 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", (firstprinted) ? multisymbol : "", neg ? "~" : "", strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(var) : var), "x")); 4122 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4123 4124 firstprinted = TRUE; 4125 } 4126 4127 /* if the resultant is aggregated we need to print his binary representation */ 4128 if( rhslhs == -1 ) 4129 { 4130 int pos; 4131 4132 assert(transformed); 4133 4134 SCIP_CALL( SCIPgetBinvarRepresentative(scip, resvar, &resvar, &neg) ); 4135 4136 #ifndef NDEBUG 4137 if( neg ) 4138 assert(SCIPvarIsActive(SCIPvarGetNegationVar(resvar))); 4139 else 4140 assert(SCIPvarIsActive(resvar)); 4141 #endif 4142 4143 /* replace and-resultant with corresponding variables */ 4144 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, neg ? SCIPvarGetNegationVar(resvar) : resvar, nresvars, &pos) ) 4145 { 4146 SCIP_Bool negated; 4147 int a; 4148 4149 assert(andvars != NULL); 4150 assert(nandvars != NULL); 4151 assert(pos >= 0 && nandvars[pos] > 0 && andvars[pos] != NULL); 4152 assert(andvars[pos][nandvars[pos] - 1] != NULL); 4153 4154 negated = SCIPvarIsNegated(andvars[pos][nandvars[pos] - 1]); 4155 4156 /* print and-vars */ 4157 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, neg ? " +1%s%s%s" : " -1%s%s%s", multisymbol, negated ? "~" : "", 4158 strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][nandvars[pos] - 1]) : andvars[pos][nandvars[pos] - 1]), "x")); 4159 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4160 4161 for(a = nandvars[pos] - 2; a >= 0; --a ) 4162 { 4163 negated = SCIPvarIsNegated(andvars[pos][a]); 4164 4165 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, "%s%s%s", multisymbol, negated ? "~" : "", strstr(SCIPvarGetName(negated ? SCIPvarGetNegationVar(andvars[pos][a]) : andvars[pos][a]), "x")); 4166 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4167 } 4168 4169 appendBuffer(scip, file, linebuffer, &linecnt, " "); 4170 4171 if( neg ) 4172 rhslhs = 1; 4173 else 4174 rhslhs = 0; 4175 } 4176 else 4177 { 4178 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " -1%s%s%s", multisymbol, neg ? "~" : "", 4179 strstr(SCIPvarGetName(neg ? SCIPvarGetNegationVar(resvar) : resvar), "x")); 4180 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4181 4182 rhslhs = 0; 4183 } 4184 } 4185 4186 /* print rhslhs */ 4187 (void) SCIPsnprintf(buffer, OPB_MAX_LINELEN, " = %" SCIP_LONGINT_FORMAT " ;\n", rhslhs); 4188 appendBuffer(scip, file, linebuffer, &linecnt, buffer); 4189 4190 writeBuffer(scip, file, linebuffer, &linecnt); 4191 } 4192 } 4193 4194 return SCIP_OKAY; 4195 } 4196 4197 /* writes problem to file */ 4198 static 4199 SCIP_RETCODE writeOpb( 4200 SCIP* scip, /**< SCIP data structure */ 4201 FILE* file, /**< output file, or NULL if standard output should be used */ 4202 const char* name, /**< problem name */ 4203 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */ 4204 SCIP_OBJSENSE objsense, /**< objective sense */ 4205 SCIP_Real objscale, /**< scalar applied to objective function; external objective value is 4206 * extobj = objsense * objscale * (intobj + objoffset) */ 4207 SCIP_Real objoffset, /**< objective offset from bound shifting and fixing */ 4208 SCIP_VAR** vars, /**< array with active (binary) variables */ 4209 int nvars, /**< number of active variables in the problem */ 4210 SCIP_CONS** conss, /**< array with constraints of the problem */ 4211 int nconss, /**< number of constraints in the problem */ 4212 SCIP_VAR** const resvars, /**< array of resultant variables */ 4213 int const nresvars, /**< number of resultant variables */ 4214 SCIP_VAR**const*const andvars, /**< corresponding array of and-variables */ 4215 int const*const nandvars, /**< array of numbers of corresponding and-variables */ 4216 SCIP_Bool const existandconshdlr, /**< does and-constrainthandler exist? */ 4217 SCIP_Bool const existands, /**< does some and-constraints exist? */ 4218 SCIP_RESULT* result /**< pointer to store the result of the file writing call */ 4219 ) 4220 { 4221 char multisymbol[OPB_MAX_LINELEN]; 4222 SCIP_HASHTABLE* printedfixing; 4223 SCIP_Bool usesymbol; 4224 SCIP_RETCODE retcode; 4225 int nlinearconss; 4226 int nsplitlinearconss; 4227 4228 assert( scip != NULL ); 4229 assert( vars != NULL || nvars == 0 ); 4230 assert( conss != NULL || nconss == 0 ); 4231 assert( result != NULL ); 4232 4233 /* check if should use a multipliers symbol star '*' between coefficients and variables */ 4234 SCIP_CALL( SCIPgetBoolParam(scip, "reading/" READER_NAME "/multisymbol", &usesymbol) ); 4235 (void) SCIPsnprintf(multisymbol, OPB_MAX_LINELEN, "%s", usesymbol ? " * " : " "); 4236 4237 /* determine how many linear constraints are split */ 4238 determineTotalNumberLinearConss(scip, conss, nconss, &nlinearconss, &nsplitlinearconss); 4239 4240 /* print statistics as comment to file */ 4241 SCIPinfoMessage(scip, file, "* SCIP STATISTICS\n"); 4242 SCIPinfoMessage(scip, file, "* Problem name : %s\n", name); 4243 SCIPinfoMessage(scip, file, "* Variables : %d (all binary)\n", nvars); 4244 SCIPinfoMessage(scip, file, "* Constraints : %d\n", nconss - nlinearconss + nsplitlinearconss); 4245 4246 /* create a hash table */ 4247 SCIP_CALL( SCIPhashtableCreate(&printedfixing, SCIPblkmem(scip), nvars, 4248 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) ); 4249 4250 /* write objective function */ 4251 SCIP_CALL( writeOpbObjective(scip, file, vars, nvars, resvars, nresvars, andvars, nandvars, 4252 objsense, objscale, objoffset, multisymbol, existands, transformed) ); 4253 4254 /* write constraints */ 4255 retcode = writeOpbConstraints(scip, file, conss, nconss, vars, nvars, resvars, nresvars, andvars, nandvars, 4256 multisymbol, existandconshdlr, existands, transformed); 4257 4258 if( existands && (retcode == SCIP_OKAY) ) 4259 { 4260 /* write and constraints of inactive but relevant and-resultants and and-variables which are fixed to one 4261 with no fixed and resultant */ 4262 SCIP_CALL( writeOpbRelevantAnds(scip, file, resvars, nresvars, andvars, nandvars, printedfixing, multisymbol, transformed) ); 4263 } 4264 4265 /* write fixed variables */ 4266 SCIP_CALL( writeOpbFixedVars(scip, file, vars, nvars, printedfixing, multisymbol, transformed) ); 4267 4268 SCIPhashtableFree(&printedfixing); 4269 4270 *result = SCIP_SUCCESS; 4271 4272 return retcode; 4273 } 4274 4275 4276 /* 4277 * extern methods 4278 */ 4279 4280 /** reads problem from file */ 4281 SCIP_RETCODE SCIPreadOpb( 4282 SCIP* scip, /**< SCIP data structure */ 4283 SCIP_READER* reader, /**< the file reader itself */ 4284 const char* filename, /**< full path and name of file to read, or NULL if stdin should be used */ 4285 SCIP_RESULT* result /**< pointer to store the result of the file reading call */ 4286 ) 4287 { /*lint --e{715}*/ 4288 OPBINPUT opbinput; 4289 SCIP_RETCODE retcode; 4290 int i; 4291 4292 assert(scip != NULL); /* for lint */ 4293 assert(reader != NULL); 4294 4295 /* initialize OPB input data (use block memory because order can change during execution) */ 4296 opbinput.file = NULL; 4297 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &opbinput.linebuf, OPB_MAX_LINELEN) ); 4298 opbinput.linebuf[0] = '\0'; 4299 opbinput.linebufsize = OPB_MAX_LINELEN; 4300 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &opbinput.token, OPB_MAX_LINELEN) ); 4301 opbinput.token[0] = '\0'; 4302 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &opbinput.tokenbuf, OPB_MAX_LINELEN) ); 4303 opbinput.tokenbuf[0] = '\0'; 4304 for( i = 0; i < OPB_MAX_PUSHEDTOKENS; ++i ) 4305 { 4306 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(opbinput.pushedtokens[i]), OPB_MAX_LINELEN) ); /*lint !e866 */ 4307 } 4308 4309 opbinput.npushedtokens = 0; 4310 opbinput.linenumber = 1; 4311 opbinput.linepos = 0; 4312 opbinput.objsense = SCIP_OBJSENSE_MINIMIZE; 4313 opbinput.eof = FALSE; 4314 opbinput.haserror = FALSE; 4315 opbinput.nproblemcoeffs = 0; 4316 opbinput.wbo = FALSE; 4317 opbinput.topcost = -SCIPinfinity(scip); 4318 opbinput.nindvars = 0; 4319 #if GENCONSNAMES == TRUE 4320 opbinput.consnumber = 0; 4321 #endif 4322 4323 /* read the file */ 4324 retcode = readOPBFile(scip, &opbinput, filename); 4325 4326 /* free dynamically allocated memory */ 4327 for( i = OPB_MAX_PUSHEDTOKENS - 1; i >= 0; --i ) 4328 { 4329 SCIPfreeBlockMemoryArray(scip, &(opbinput.pushedtokens[i]), OPB_MAX_LINELEN); 4330 } 4331 SCIPfreeBlockMemoryArray(scip, &opbinput.tokenbuf, OPB_MAX_LINELEN); 4332 SCIPfreeBlockMemoryArray(scip, &opbinput.token, OPB_MAX_LINELEN); 4333 SCIPfreeBlockMemoryArray(scip, &opbinput.linebuf, opbinput.linebufsize); 4334 4335 if( retcode == SCIP_PLUGINNOTFOUND ) 4336 retcode = SCIP_READERROR; 4337 4338 SCIP_CALL( retcode ); 4339 4340 if( opbinput.nproblemcoeffs > 0 ) 4341 { 4342 SCIPwarningMessage(scip, "there might be <%d> coefficients or weight out of range!\n", opbinput.nproblemcoeffs); 4343 } 4344 4345 /* evaluate the result */ 4346 if( opbinput.haserror ) 4347 return SCIP_READERROR; 4348 else 4349 { 4350 /* set objective sense */ 4351 SCIP_CALL( SCIPsetObjsense(scip, opbinput.objsense) ); 4352 *result = SCIP_SUCCESS; 4353 } 4354 4355 return SCIP_OKAY; 4356 } 4357 4358 /** writes problem to file */ 4359 SCIP_RETCODE SCIPwriteOpb( 4360 SCIP* scip, /**< SCIP data structure */ 4361 FILE* file, /**< output file, or NULL if standard output should be used */ 4362 const char* name, /**< problem name */ 4363 SCIP_Bool transformed, /**< TRUE iff problem is the transformed problem */ 4364 SCIP_OBJSENSE objsense, /**< objective sense */ 4365 SCIP_Real objscale, /**< scalar applied to objective function; external objective value is 4366 * extobj = objsense * objscale * (intobj + objoffset) */ 4367 SCIP_Real objoffset, /**< objective offset from bound shifting and fixing */ 4368 SCIP_VAR** vars, /**< array with active variables ordered binary, integer, implicit, continuous */ 4369 int nvars, /**< number of active variables in the problem */ 4370 int nbinvars, /**< number of binary variables */ 4371 int nintvars, /**< number of general integer variables */ 4372 int nimplvars, /**< number of implicit integer variables */ 4373 int ncontvars, /**< number of continuous variables */ 4374 SCIP_VAR** fixedvars, /**< array with fixed variables */ 4375 int nfixedvars, /**< number of fixed and aggregated variables in the problem */ 4376 SCIP_CONS** conss, /**< array with constraints of the problem */ 4377 int nconss, /**< number of constraints in the problem */ 4378 SCIP_Bool genericnames, /**< should generic variable and constraint names be used */ 4379 SCIP_RESULT* result /**< pointer to store the result of the file writing call */ 4380 ) 4381 { /*lint --e{715}*/ 4382 SCIP_RETCODE retcode = SCIP_OKAY; 4383 4384 if( nvars != nbinvars && (nintvars > 0 || SCIPfindConshdlr(scip, "indicator") != NULL 4385 || ncontvars + nimplvars != SCIPconshdlrGetNConss(SCIPfindConshdlr(scip, "indicator"))) ) 4386 { 4387 SCIPwarningMessage(scip, "only binary problems can be written in OPB format.\n"); 4388 *result = SCIP_DIDNOTRUN; 4389 } 4390 else 4391 { 4392 SCIP_VAR*** andvars; 4393 SCIP_VAR** resvars; 4394 int* nandvars; 4395 SCIP_Bool existands; 4396 SCIP_Bool existandconshdlr; 4397 int nresvars; 4398 int v; 4399 4400 /* computes all and-resultants and their corresponding constraint variables */ 4401 /* coverity[leaked_storage] */ 4402 SCIP_CALL( computeAndConstraintInfos(scip, transformed, &resvars, &nresvars, &andvars, &nandvars, &existandconshdlr, &existands) ); 4403 4404 if( genericnames ) 4405 { 4406 #ifndef NDEBUG 4407 /* check for correct names for opb-format */ 4408 int idx; 4409 int pos; 4410 4411 for( v = nvars - 1; v >= 0; --v ) 4412 { 4413 if( existands ) 4414 { 4415 /* and variables are artificial */ 4416 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) ) 4417 continue; 4418 } 4419 4420 assert(sscanf(SCIPvarGetName(vars[v]), "x%d", &idx) == 1); 4421 } 4422 #endif 4423 retcode = writeOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars, 4424 nvars, conss, nconss, resvars, nresvars, andvars, nandvars, existandconshdlr, existands, result); 4425 } 4426 else 4427 { 4428 SCIP_Bool printed; 4429 int idx; 4430 int pos; 4431 4432 printed = FALSE; 4433 4434 /* check if there are already generic names for all (not fixed variables)*/ 4435 for( v = nvars - 1; v >= 0; --v ) 4436 if( !existands || !SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) ) 4437 { 4438 if( sscanf(SCIPvarGetName(vars[v]), transformed ? "t_x%d" : "x%d", &idx) != 1 && strstr(SCIPvarGetName(vars[v]), INDICATORVARNAME) == NULL && strstr(SCIPvarGetName(vars[v]), INDICATORSLACKVARNAME) == NULL ) 4439 { 4440 SCIPwarningMessage(scip, "At least following variable name isn't allowed in opb format.\n"); 4441 SCIP_CALL( SCIPprintVar(scip, vars[v], NULL) ); 4442 SCIPwarningMessage(scip, "OPB format needs generic variable names!\n"); 4443 4444 if( transformed ) 4445 { 4446 SCIPwarningMessage(scip, "write transformed problem with generic variable names.\n"); 4447 SCIP_CALL( SCIPprintTransProblem(scip, file, "opb", TRUE) ); 4448 } 4449 else 4450 { 4451 SCIPwarningMessage(scip, "write original problem with generic variable names.\n"); 4452 SCIP_CALL( SCIPprintOrigProblem(scip, file, "opb", TRUE) ); 4453 } 4454 printed = TRUE; 4455 break; 4456 } 4457 } 4458 4459 if( !printed ) 4460 { 4461 /* check if there are already generic names for all (fixed variables)*/ 4462 for( v = nfixedvars - 1; v >= 0; --v ) 4463 if( !existands || !SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) ) 4464 { 4465 /* coverity[secure_coding] */ 4466 if( sscanf(SCIPvarGetName(fixedvars[v]), transformed ? "t_x%d" : "x%d", &idx) != 1 && strstr(SCIPvarGetName(fixedvars[v]), INDICATORVARNAME) == NULL && strstr(SCIPvarGetName(fixedvars[v]), INDICATORSLACKVARNAME) == NULL ) 4467 { 4468 SCIPwarningMessage(scip, "At least following variable name isn't allowed in opb format.\n"); 4469 SCIP_CALL( SCIPprintVar(scip, fixedvars[v], NULL) ); 4470 SCIPwarningMessage(scip, "OPB format needs generic variable names!\n"); 4471 4472 if( transformed ) 4473 { 4474 SCIPwarningMessage(scip, "write transformed problem with generic variable names.\n"); 4475 SCIP_CALL( SCIPprintTransProblem(scip, file, "opb", TRUE) ); 4476 } 4477 else 4478 { 4479 SCIPwarningMessage(scip, "write original problem with generic variable names.\n"); 4480 SCIP_CALL( SCIPprintOrigProblem(scip, file, "opb", TRUE) ); 4481 } 4482 printed = TRUE; 4483 break; 4484 } 4485 } 4486 } 4487 4488 if( !printed ) 4489 { 4490 #ifndef NDEBUG 4491 for( v = nvars - 1; v >= 0; --v ) 4492 { 4493 if( existands ) 4494 { 4495 if( SCIPsortedvecFindPtr((void**)resvars, SCIPvarComp, vars[v], nresvars, &pos) ) 4496 continue; 4497 } 4498 4499 assert(sscanf(SCIPvarGetName(vars[v]), transformed ? "t_x%d" : "x%d", &idx) == 1 || strstr(SCIPvarGetName(vars[v]), INDICATORVARNAME) != NULL || strstr(SCIPvarGetName(vars[v]), INDICATORSLACKVARNAME) != NULL ); 4500 } 4501 #endif 4502 retcode = writeOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars, 4503 nvars, conss, nconss, resvars, nresvars, andvars, nandvars, existandconshdlr, existands, result); 4504 } 4505 } 4506 4507 if( existands ) 4508 { 4509 /* free temporary buffers */ 4510 assert(resvars != NULL); 4511 assert(andvars != NULL); 4512 assert(nandvars != NULL); 4513 4514 for( v = nresvars - 1; v >= 0; --v ) 4515 { 4516 assert(andvars[v] != NULL); 4517 SCIPfreeMemoryArray(scip, &andvars[v]); 4518 } 4519 SCIPfreeMemoryArray(scip, &nandvars); 4520 SCIPfreeMemoryArray(scip, &andvars); 4521 SCIPfreeMemoryArray(scip, &resvars); 4522 } 4523 4524 *result = SCIP_SUCCESS; 4525 } 4526 4527 if( retcode == SCIP_INVALIDDATA ) 4528 return SCIP_WRITEERROR; 4529 4530 return retcode; 4531 } 4532 4533 /* 4534 * Callback methods of reader 4535 */ 4536 4537 /** copy method for reader plugins (called when SCIP copies plugins) */ 4538 static 4539 SCIP_DECL_READERCOPY(readerCopyOpb) 4540 { /*lint --e{715}*/ 4541 assert(scip != NULL); 4542 assert(reader != NULL); 4543 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 4544 4545 /* call inclusion method of reader */ 4546 SCIP_CALL( SCIPincludeReaderOpb(scip) ); 4547 4548 return SCIP_OKAY; 4549 } 4550 4551 4552 /** problem reading method of reader */ 4553 static 4554 SCIP_DECL_READERREAD(readerReadOpb) 4555 { /*lint --e{715}*/ 4556 4557 SCIP_CALL( SCIPreadOpb(scip, reader, filename, result) ); 4558 4559 return SCIP_OKAY; 4560 } 4561 4562 4563 /** problem writing method of reader */ 4564 static 4565 SCIP_DECL_READERWRITE(readerWriteOpb) 4566 { /*lint --e{715}*/ 4567 4568 SCIP_CALL( SCIPwriteOpb(scip, file, name, transformed, objsense, objscale, objoffset, vars, 4569 nvars, nbinvars, nintvars, nimplvars, ncontvars, fixedvars, nfixedvars, conss, nconss, genericnames, result) ); 4570 4571 return SCIP_OKAY; 4572 } 4573 4574 /* 4575 * reader specific interface methods 4576 */ 4577 4578 /** includes the opb file reader in SCIP */ 4579 SCIP_RETCODE SCIPincludeReaderOpb( 4580 SCIP* scip /**< SCIP data structure */ 4581 ) 4582 { 4583 SCIP_READER* reader; 4584 4585 /* include reader */ 4586 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) ); 4587 4588 /* set non fundamental callbacks via setter functions */ 4589 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyOpb) ); 4590 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadOpb) ); 4591 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteOpb) ); 4592 4593 /* add opb reader parameters */ 4594 SCIP_CALL( SCIPaddBoolParam(scip, 4595 "reading/" READER_NAME "/dynamicconss", "should model constraints be subject to aging?", 4596 NULL, FALSE, FALSE/*TRUE*/, NULL, NULL) ); /* have to be FALSE, otherwise an error might inccur in restart during branch and bound */ 4597 SCIP_CALL( SCIPaddBoolParam(scip, 4598 "reading/" READER_NAME "/multisymbol", "use '*' between coefficients and variables by writing to problem?", 4599 NULL, TRUE, FALSE, NULL, NULL) ); 4600 4601 return SCIP_OKAY; 4602 } 4603