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_cip.c 26 * @ingroup DEFPLUGINS_READER 27 * @brief CIP file reader 28 * @author Stefan Heinz 29 * @author Marc Pfetsch 30 * @author Michael Winkler 31 * 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #include "blockmemshell/memory.h" 37 #include "scip/cons_linear.h" 38 #include "scip/pub_fileio.h" 39 #include "scip/pub_message.h" 40 #include "scip/pub_misc.h" 41 #include "scip/pub_reader.h" 42 #include "scip/pub_var.h" 43 #include "scip/reader_cip.h" 44 #include "scip/scip_cons.h" 45 #include "scip/scip_mem.h" 46 #include "scip/scip_message.h" 47 #include "scip/scip_numerics.h" 48 #include "scip/scip_param.h" 49 #include "scip/scip_prob.h" 50 #include "scip/scip_reader.h" 51 #include "scip/scip_var.h" 52 #if !defined(_WIN32) && !defined(_WIN64) 53 #include <strings.h> /*lint --e{766}*/ /* needed for strncasecmp() */ 54 #endif 55 56 57 #define READER_NAME "cipreader" 58 #define READER_DESC "file reader for CIP (Constraint Integer Program) format" 59 #define READER_EXTENSION "cip" 60 61 #define DEFAULT_CIP_WRITEFIXEDVARS TRUE /**< Should fixed and aggregated variables be written when writing? */ 62 63 64 /** CIP reading data */ 65 struct SCIP_ReaderData 66 { 67 SCIP_Bool writefixedvars; /**< Should fixed and aggregated variables be written when writing? */ 68 }; 69 70 71 /** Section of the in CIP files */ 72 enum CipSection 73 { 74 CIP_START, /**< start tag */ 75 CIP_STATISTIC, /**< statistics section */ 76 CIP_OBJECTIVE, /**< objective */ 77 CIP_VARS, /**< list of (free) variables */ 78 CIP_FIXEDVARS, /**< list of fixed variables */ 79 CIP_CONSTRAINTS, /**< constraints */ 80 CIP_END /**< end of file tag */ 81 }; 82 typedef enum CipSection CIPSECTION; /**< Section of the in CIP files */ 83 84 85 /* 86 * Data structures 87 */ 88 89 /** CIP reading data */ 90 struct CipInput 91 { 92 SCIP_FILE* file; /**< input file */ 93 char* strbuf; /**< string buffer for input lines */ 94 int len; /**< length of strbuf */ 95 int readingsize; /**< size of block in which len is increased if necessary */ 96 int linenumber; /**< number of line in input file */ 97 CIPSECTION section; /**< current section */ 98 SCIP_Bool haserror; /**< some error occurred */ 99 SCIP_Bool endfile; /**< we have reached the end of the file */ 100 }; 101 typedef struct CipInput CIPINPUT; /**< CIP reading data */ 102 103 104 /* 105 * Local methods for reading/parsing 106 */ 107 108 /** get next input line; this are all characters until the next semicolon */ 109 static 110 SCIP_RETCODE getInputString( 111 SCIP* scip, /**< SCIP data structure */ 112 CIPINPUT* cipinput /**< CIP parsing data */ 113 ) 114 { 115 char* endline; 116 char* endcharacter; 117 char* windowsendlinechar; 118 119 assert(cipinput != NULL); 120 121 /* read next line */ 122 cipinput->endfile = (SCIPfgets(cipinput->strbuf, cipinput->len, cipinput->file) == NULL); 123 124 if( cipinput->endfile ) 125 { 126 /* clear the line for safety reason */ 127 BMSclearMemoryArray(cipinput->strbuf, cipinput->len); 128 return SCIP_OKAY; 129 } 130 131 cipinput->linenumber++; 132 endline = strchr(cipinput->strbuf, '\n'); 133 endcharacter = strchr(cipinput->strbuf, ';'); 134 135 while( endline == NULL || (endcharacter == NULL && cipinput->section == CIP_CONSTRAINTS && strncmp(cipinput->strbuf, "END", 3) != 0 ) ) 136 { 137 int pos; 138 139 /* we refill the buffer from the '\n' character */ 140 if( endline == NULL ) 141 pos = cipinput->len - 1; 142 else 143 pos = (int) (endline - cipinput->strbuf); 144 145 /* don't erase the '\n' from all buffers for constraints */ 146 if( endline != NULL && cipinput->section == CIP_CONSTRAINTS ) 147 pos++; 148 149 /* if necessary reallocate memory */ 150 if( pos + cipinput->readingsize >= cipinput->len ) 151 { 152 cipinput->len = SCIPcalcMemGrowSize(scip, pos + cipinput->readingsize); 153 SCIP_CALL( SCIPreallocBufferArray(scip, &(cipinput->strbuf), cipinput->len) ); 154 } 155 156 /* read next line */ 157 cipinput->endfile = (SCIPfgets(&(cipinput->strbuf[pos]), cipinput->len - pos, cipinput->file) == NULL); 158 159 if( cipinput->endfile ) 160 { 161 /* clear the line for safety reason */ 162 BMSclearMemoryArray(cipinput->strbuf, cipinput->len); 163 return SCIP_OKAY; 164 } 165 166 cipinput->linenumber++; 167 endline = strrchr(&cipinput->strbuf[pos], '\n'); 168 endcharacter = strchr(&cipinput->strbuf[pos], ';'); 169 } 170 assert(endline != NULL); 171 172 /*SCIPdebugMsg(scip, "read line: %s\n", cipinput->strbuf);*/ 173 174 /* check for windows "carriage return" endline character */ 175 windowsendlinechar = strrchr(cipinput->strbuf, '\r'); 176 if( windowsendlinechar != NULL && windowsendlinechar + 1 == endline ) 177 --endline; 178 else 179 /* if the assert should not hold we found a windows "carriage return" which was not at the end of the line */ 180 assert(windowsendlinechar == NULL); 181 182 if( cipinput->section == CIP_CONSTRAINTS && endcharacter != NULL && endline - endcharacter != 1 ) 183 { 184 SCIPerrorMessage("Constraint line has to end with ';\\n' (line: %d).\n", cipinput->linenumber); 185 cipinput->haserror = TRUE; 186 return SCIP_OKAY; /* return error at hightest level */ 187 } 188 189 *endline = '\0'; 190 191 return SCIP_OKAY; 192 } 193 194 /** read the problem name out of the statistics */ 195 static 196 void getStart( 197 SCIP* scip, /**< SCIP data structure */ 198 CIPINPUT* cipinput /**< CIP parsing data */ 199 ) 200 { 201 char* buf; 202 203 assert(scip != NULL); 204 205 buf = cipinput->strbuf; 206 207 if( strncmp(buf, "STATISTICS", 9) == 0 ) 208 { 209 cipinput->section = CIP_STATISTIC; 210 return; 211 } 212 213 if( strncmp(buf, "VARIABLES", 8) == 0 || strncmp(buf, "FIXED", 5) == 0 || strncmp(buf, "CONSTRAINTS", 11) == 0 || strncmp(buf, "OBJECTIVE", 9) == 0 ) 214 { 215 SCIPerrorMessage("Syntax Error: File has to start with 'STATISTICS' section.\n"); 216 cipinput->haserror = TRUE; 217 } 218 } 219 220 221 /** read the problem name out of the statistics */ 222 static 223 SCIP_RETCODE getStatistics( 224 SCIP* scip, /**< SCIP data structure */ 225 CIPINPUT* cipinput /**< CIP parsing data */ 226 ) 227 { 228 char* buf; 229 230 buf = cipinput->strbuf; 231 232 if( strncmp(buf, "OBJECTIVE", 9) == 0 ) 233 { 234 cipinput->section = CIP_OBJECTIVE; 235 return SCIP_OKAY; 236 } 237 238 SCIPdebugMsg(scip, "parse statistics\n"); 239 240 if( strncmp(buf, " Problem name", 14) == 0 ) 241 { 242 char* name; 243 char* s; 244 245 name = strchr(buf, ':'); 246 247 if( name == NULL ) 248 { 249 SCIPwarningMessage(scip, "did not find problem name (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 250 return SCIP_OKAY; /* no error, might work with empty problem name */ 251 } 252 253 /* skip ':' */ 254 ++name; 255 256 /* make sure that we terminate the string at comments ('#') or newline ('\r', '\n')*/ 257 if( NULL != (s = strpbrk(name, "#\r\n")) ) 258 *s = '\0'; 259 260 /* remove white space (tabs, ' ') in front of the name */ 261 SCIP_CALL( SCIPskipSpace(&name) ); 262 263 /* set problem name */ 264 SCIP_CALL( SCIPsetProbName(scip, name) ); 265 266 SCIPdebugMsg(scip, "problem name <%s>\n", name); 267 } 268 269 return SCIP_OKAY; 270 } 271 272 /** read objective sense, offset, and scale */ 273 static 274 SCIP_RETCODE getObjective( 275 SCIP* scip, /**< SCIP data structure */ 276 CIPINPUT* cipinput, /**< CIP parsing data */ 277 SCIP_Real* objscale, /**< buffer where to multiply with objective scale */ 278 SCIP_Real* objoffset /**< buffer where to add with objective offset */ 279 ) 280 { 281 char* buf; 282 char* name; 283 284 assert(objscale != NULL); 285 assert(objoffset != NULL); 286 287 buf = cipinput->strbuf; 288 289 if( strncmp(buf, "VARIABLES", 8) == 0 ) 290 cipinput->section = CIP_VARS; 291 else if( strncmp(buf, "FIXED", 5) == 0 ) 292 cipinput->section = CIP_FIXEDVARS; 293 else if( strncmp(buf, "CONSTRAINTS", 11) == 0 ) 294 cipinput->section = CIP_CONSTRAINTS; 295 else if( strncmp(buf, "END", 3) == 0 ) 296 cipinput->section = CIP_END; 297 298 if( cipinput->section != CIP_OBJECTIVE ) 299 return SCIP_OKAY; 300 301 SCIPdebugMsg(scip, "parse objective information\n"); 302 303 /* remove white space */ 304 SCIP_CALL( SCIPskipSpace(&buf) ); 305 306 if( strncasecmp(buf, "Sense", 5) == 0 ) 307 { 308 SCIP_OBJSENSE objsense; 309 310 name = strchr(buf, ':'); 311 312 if( name == NULL ) 313 { 314 SCIPwarningMessage(scip, "did not find objective sense (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 315 return SCIP_OKAY; /* no error - might work with default */ 316 } 317 318 /* skip ':' */ 319 ++name; 320 321 /* remove white space in front of the name */ 322 SCIP_CALL( SCIPskipSpace(&name) ); 323 324 if( strncasecmp(name, "minimize", 3) == 0 ) 325 objsense = SCIP_OBJSENSE_MINIMIZE; 326 else if( strncasecmp(name, "maximize", 3) == 0 ) 327 objsense = SCIP_OBJSENSE_MAXIMIZE; 328 else 329 { 330 SCIPwarningMessage(scip, "unknown objective sense '%s' (line: %d):\n%s\n", name, cipinput->linenumber, cipinput->strbuf); 331 return SCIP_OKAY; /* no error - might work with default */ 332 } 333 334 /* set problem name */ 335 SCIP_CALL( SCIPsetObjsense(scip, objsense) ); 336 SCIPdebugMsg(scip, "objective sense <%s>\n", objsense == SCIP_OBJSENSE_MINIMIZE ? "minimize" : "maximize"); 337 } 338 else if( strncasecmp(buf, "Offset", 6) == 0 ) 339 { 340 SCIP_Real off = 0; 341 char* endptr; 342 343 name = strchr(buf, ':'); 344 345 if( name == NULL ) 346 { 347 SCIPwarningMessage(scip, "did not find offset (line: %d)\n", cipinput->linenumber); 348 return SCIP_OKAY; 349 } 350 351 /* skip ':' */ 352 ++name; 353 354 /* remove white space in front of the name */ 355 SCIP_CALL( SCIPskipSpace(&name) ); 356 357 if ( SCIPstrToRealValue(name, &off, &endptr) ) 358 { 359 *objoffset += off; 360 SCIPdebugMsg(scip, "offset <%g> (total: %g)\n", off, *objoffset); 361 } 362 else 363 { 364 SCIPwarningMessage(scip, "could not parse offset (line: %d)\n%s\n", cipinput->linenumber, cipinput->strbuf); 365 return SCIP_OKAY; 366 } 367 } 368 else if( strncasecmp(buf, "Scale", 5) == 0 ) 369 { 370 SCIP_Real scale = 1.0; 371 char* endptr; 372 373 name = strchr(buf, ':'); 374 375 if( name == NULL ) 376 { 377 SCIPwarningMessage(scip, "did not find scale (line: %d)\n", cipinput->linenumber); 378 return SCIP_OKAY; 379 } 380 381 /* skip ':' */ 382 ++name; 383 384 /* remove white space in front of the name */ 385 SCIP_CALL( SCIPskipSpace(&name) ); 386 387 if ( SCIPstrToRealValue(name, &scale, &endptr) ) 388 { 389 *objscale *= scale; 390 SCIPdebugMsg(scip, "objscale <%g> (total: %g)\n", scale, *objscale); 391 } 392 else 393 { 394 SCIPwarningMessage(scip, "could not parse objective scale (line: %d)\n%s\n", cipinput->linenumber, cipinput->strbuf); 395 return SCIP_OKAY; 396 } 397 } 398 399 return SCIP_OKAY; 400 } 401 402 /** read variable */ 403 static 404 SCIP_RETCODE getVariable( 405 SCIP* scip, /**< SCIP data structure */ 406 CIPINPUT* cipinput, /**< CIP parsing data */ 407 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */ 408 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */ 409 SCIP_Real objscale /**< objective scale */ 410 ) 411 { 412 SCIP_Bool success; 413 SCIP_VAR* var; 414 char* buf; 415 char* endptr; 416 417 buf = cipinput->strbuf; 418 419 if( strncmp(buf, "FIXED", 5) == 0 ) 420 cipinput->section = CIP_FIXEDVARS; 421 else if( strncmp(buf, "CONSTRAINTS", 4) == 0 ) 422 cipinput->section = CIP_CONSTRAINTS; 423 else if( strncmp(buf, "END", 3) == 0 ) 424 cipinput->section = CIP_END; 425 426 if( cipinput->section != CIP_VARS ) 427 return SCIP_OKAY; 428 429 SCIPdebugMsg(scip, "parse variable\n"); 430 431 /* parse the variable */ 432 SCIP_CALL( SCIPparseVar(scip, &var, buf, initial, removable, NULL, NULL, NULL, NULL, NULL, &endptr, &success) ); 433 434 if( !success ) 435 { 436 SCIPerrorMessage("syntax error in variable information (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 437 cipinput->haserror = TRUE; 438 return SCIP_OKAY; 439 } 440 441 if( objscale != 1.0 ) 442 { 443 SCIP_CALL( SCIPchgVarObj(scip, var, SCIPvarGetObj(var) * objscale) ); 444 } 445 446 SCIP_CALL( SCIPaddVar(scip, var) ); 447 448 SCIPdebug( SCIP_CALL( SCIPprintVar(scip, var, NULL) ) ); 449 450 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 451 452 return SCIP_OKAY; 453 } 454 455 /** read fixed variable */ 456 static 457 SCIP_RETCODE getFixedVariable( 458 SCIP* scip, /**< SCIP data structure */ 459 CIPINPUT* cipinput /**< CIP parsing data */ 460 ) 461 { 462 SCIP_Bool success; 463 SCIP_VAR* var; 464 char* buf; 465 char* endptr; 466 char name[SCIP_MAXSTRLEN]; 467 468 buf = cipinput->strbuf; 469 470 if( strncmp(buf, "CONSTRAINTS", 11) == 0 ) 471 cipinput->section = CIP_CONSTRAINTS; 472 else if( strncmp(buf, "END", 3) == 0 ) 473 cipinput->section = CIP_END; 474 475 if( cipinput->section != CIP_FIXEDVARS ) 476 return SCIP_OKAY; 477 478 SCIPdebugMsg(scip, "parse fixed variable\n"); 479 480 /* parse the variable */ 481 SCIP_CALL( SCIPparseVar(scip, &var, buf, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL, &endptr, &success) ); 482 483 if( !success ) 484 { 485 SCIPerrorMessage("syntax error in variable information (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 486 cipinput->haserror = TRUE; 487 return SCIP_OKAY; 488 } 489 490 /* skip intermediate stuff */ 491 buf = endptr; 492 493 while ( *buf != '\0' && (*buf == ' ' || *buf == ',') ) 494 ++buf; 495 496 /* check whether variable is fixed */ 497 if ( strncmp(buf, "fixed:", 6) == 0 ) 498 { 499 SCIP_CALL( SCIPaddVar(scip, var) ); 500 SCIPdebug( SCIP_CALL( SCIPprintVar(scip, var, NULL) ) ); 501 } 502 else if ( strncmp(buf, "negated:", 8) == 0 ) 503 { 504 SCIP_CONS* lincons; 505 SCIP_VAR* negvar; 506 SCIP_Real vals[2]; 507 SCIP_VAR* vars[2]; 508 509 buf += 8; 510 511 /* we can just parse the next variable (ignoring all other information in between) */ 512 SCIP_CALL( SCIPparseVarName(scip, buf, &negvar, &endptr) ); 513 514 if ( negvar == NULL ) 515 { 516 SCIPerrorMessage("could not parse negated variable (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 517 cipinput->haserror = TRUE; 518 return SCIP_OKAY; 519 } 520 521 assert(SCIPvarIsBinary(var)); 522 assert(SCIPvarIsBinary(negvar)); 523 524 SCIP_CALL( SCIPaddVar(scip, var) ); 525 526 SCIPdebugMsg(scip, "creating negated variable <%s> (of <%s>) ...\n", SCIPvarGetName(var), SCIPvarGetName(negvar) ); 527 SCIPdebug( SCIP_CALL( SCIPprintVar(scip, var, NULL) ) ); 528 529 /* add linear constraint for negation */ 530 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "neg_%s", SCIPvarGetName(var) ); 531 vars[0] = var; 532 vars[1] = negvar; 533 vals[0] = 1.0; 534 vals[1] = 1.0; 535 SCIPdebugMsg(scip, "coupling constraint:\n"); 536 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, name, 2, vars, vals, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE) ); 537 SCIPdebugPrintCons(scip, lincons, NULL); 538 SCIP_CALL( SCIPaddCons(scip, lincons) ); 539 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); 540 } 541 else if ( strncmp(buf, "aggregated:", 11) == 0 ) 542 { 543 /* handle (multi-)aggregated variables */ 544 SCIP_CONS* lincons; 545 SCIP_Real* vals; 546 SCIP_VAR** vars; 547 SCIP_Real rhs = 0.0; 548 const char* str; 549 int nvarssize = 20; 550 int requsize; 551 int nvars; 552 553 buf += 11; 554 555 SCIPdebugMsg(scip, "parsing aggregated variable <%s> ...\n", SCIPvarGetName(var)); 556 557 /* first parse constant */ 558 if ( ! SCIPstrToRealValue(buf, &rhs, &endptr) ) 559 { 560 SCIPerrorMessage("expected constant when aggregated variable information (line: %d):\n%s\n", cipinput->linenumber, buf); 561 cipinput->haserror = TRUE; 562 return SCIP_OKAY; 563 } 564 565 /* check whether constant is 0.0 */ 566 str = endptr; 567 SCIP_CALL( SCIPskipSpace((char**)&str) ); 568 /* if next char is '<' we found a variable -> constant is 0 */ 569 if ( *str != '<' ) 570 { 571 SCIPdebugMsg(scip, "constant: %f\n", rhs); 572 buf = endptr; 573 } 574 else 575 { 576 /* otherwise keep buf */ 577 rhs = 0.0; 578 } 579 580 /* initialize buffers for storing the variables and values */ 581 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvarssize) ); 582 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvarssize) ); 583 584 vars[0] = var; 585 vals[0] = -1.0; 586 --nvarssize; 587 588 /* parse linear sum to get variables and coefficients */ 589 SCIP_CALL( SCIPparseVarsLinearsum(scip, buf, &(vars[1]), &(vals[1]), &nvars, nvarssize, &requsize, &endptr, &success) ); 590 if ( success && requsize > nvarssize ) 591 { 592 /* realloc buffers and try again */ 593 nvarssize = requsize; 594 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, nvarssize + 1) ); 595 SCIP_CALL( SCIPreallocBufferArray(scip, &vals, nvarssize + 1) ); 596 597 SCIP_CALL( SCIPparseVarsLinearsum(scip, buf, &(vars[1]), &(vals[1]), &nvars, nvarssize, &requsize, &endptr, &success) ); 598 assert( ! success || requsize <= nvarssize); /* if successful, then should have had enough space now */ 599 } 600 601 if( success ) 602 { 603 /* add aggregated variable */ 604 SCIP_CALL( SCIPaddVar(scip, var) ); 605 606 /* special handling of variables that seem to be slack variables of indicator constraints */ 607 str = SCIPvarGetName(var); 608 if ( strncmp(str, "indslack", 8) == 0 ) 609 { 610 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "indlin"); 611 (void) strncat(name, str+8, SCIP_MAXSTRLEN-7); 612 } 613 else if ( strncmp(str, "t_indslack", 10) == 0 ) 614 { 615 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "indlin"); 616 (void) strncat(name, str+10, SCIP_MAXSTRLEN-7); 617 } 618 else 619 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPvarGetName(var) ); 620 621 /* add linear constraint for (multi-)aggregation */ 622 SCIPdebugMsg(scip, "coupling constraint:\n"); 623 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, name, nvars + 1, vars, vals, -rhs, -rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE) ); 624 SCIPdebugPrintCons(scip, lincons, NULL); 625 SCIP_CALL( SCIPaddCons(scip, lincons) ); 626 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); 627 } 628 else 629 { 630 SCIPwarningMessage(scip, "Could not read (multi-)aggregated variable <%s>: dependent variables unkown - consider changing the order (line: %d):\n%s\n", 631 SCIPvarGetName(var), cipinput->linenumber, buf); 632 } 633 634 SCIPfreeBufferArray(scip, &vals); 635 SCIPfreeBufferArray(scip, &vars); 636 } 637 else 638 { 639 SCIPerrorMessage("unknown section when parsing variables (line: %d):\n%s\n", cipinput->linenumber, buf); 640 cipinput->haserror = TRUE; 641 return SCIP_OKAY; 642 } 643 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 644 645 return SCIP_OKAY; 646 } 647 648 /** read constraint */ 649 static 650 SCIP_RETCODE getConstraint( 651 SCIP* scip, /**< SCIP data structure */ 652 CIPINPUT* cipinput, /**< CIP parsing data */ 653 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 654 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 655 SCIP_Bool dynamic, /**< Is constraint subject to aging? 656 * Usually set to FALSE. Set to TRUE for own cuts which 657 * are separated as constraints. */ 658 SCIP_Bool removable /**< should the relaxation be removed from the LP due to aging or cleanup? 659 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 660 ) 661 { 662 SCIP_CONS* cons; 663 char* buf; 664 char* copybuf; 665 SCIP_RETCODE retcode; 666 SCIP_Bool separate; 667 SCIP_Bool enforce; 668 SCIP_Bool check; 669 SCIP_Bool propagate; 670 SCIP_Bool local; 671 SCIP_Bool modifiable; 672 SCIP_Bool success; 673 int len; 674 675 buf = cipinput->strbuf; 676 677 if( strncmp(buf, "END", 3) == 0 ) 678 { 679 cipinput->section = CIP_END; 680 return SCIP_OKAY; 681 } 682 683 SCIPdebugMsg(scip, "parse constraints in line %d\n", cipinput->linenumber); 684 685 separate = TRUE; 686 enforce = TRUE; 687 check = TRUE; 688 propagate = TRUE; 689 local = FALSE; 690 modifiable = FALSE; 691 692 /* get length of line and check for correct ending of constraint line */ 693 len = (int)strlen(buf); 694 if( len < 1 ) 695 { 696 SCIPerrorMessage("syntax error: expected constraint in line %d.\n", cipinput->linenumber); 697 cipinput->haserror = TRUE; 698 return SCIP_OKAY; 699 } 700 if ( buf[len - 1] != ';' ) 701 { 702 SCIPerrorMessage("syntax error: line has to end with ';' (line: %d)\n", cipinput->linenumber); 703 cipinput->haserror = TRUE; 704 return SCIP_OKAY; 705 } 706 707 /* copy buffer for working purpose */ 708 SCIP_CALL( SCIPduplicateBufferArray(scip, ©buf, buf, len) ); 709 copybuf[len - 1] = '\0'; 710 711 /* parse the constraint */ 712 retcode = SCIPparseCons(scip, &cons, copybuf, 713 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, FALSE, &success); 714 715 /* free temporary buffer */ 716 SCIPfreeBufferArray(scip, ©buf); 717 718 SCIP_CALL( retcode ); 719 720 if( !success ) 721 { 722 SCIPerrorMessage("syntax error when reading constraint (line: %d):\n%s\n", cipinput->linenumber, cipinput->strbuf); 723 cipinput->haserror = TRUE; 724 return SCIP_OKAY; 725 } 726 727 SCIP_CALL( SCIPaddCons(scip, cons) ); 728 SCIPdebugPrintCons(scip, cons, NULL); 729 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 730 731 return SCIP_OKAY; 732 } 733 734 /* 735 * Callback methods of reader 736 */ 737 738 /** copy method for reader plugins (called when SCIP copies plugins) */ 739 static 740 SCIP_DECL_READERCOPY(readerCopyCip) 741 { /*lint --e{715}*/ 742 assert(scip != NULL); 743 assert(reader != NULL); 744 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 745 746 /* call inclusion method of reader */ 747 SCIP_CALL( SCIPincludeReaderCip(scip) ); 748 749 return SCIP_OKAY; 750 } 751 752 /** destructor of reader to free user data (called when SCIP is exiting) */ 753 static 754 SCIP_DECL_READERFREE(readerFreeCip) 755 { 756 SCIP_READERDATA* readerdata; 757 758 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 759 readerdata = SCIPreaderGetData(reader); 760 assert(readerdata != NULL); 761 SCIPfreeBlockMemory(scip, &readerdata); 762 763 return SCIP_OKAY; 764 } 765 766 767 /** problem reading method of reader */ 768 static 769 SCIP_DECL_READERREAD(readerReadCip) 770 { /*lint --e{715}*/ 771 CIPINPUT cipinput; 772 SCIP_Real objscale; 773 SCIP_Real objoffset; 774 SCIP_Bool initialconss; 775 SCIP_Bool dynamicconss; 776 SCIP_Bool dynamiccols; 777 SCIP_Bool dynamicrows; 778 SCIP_Bool initialvar; 779 SCIP_Bool removablevar; 780 SCIP_RETCODE retcode; 781 782 if( NULL == (cipinput.file = SCIPfopen(filename, "r")) ) 783 { 784 SCIPerrorMessage("cannot open file <%s> for reading\n", filename); 785 SCIPprintSysError(filename); 786 return SCIP_NOFILE; 787 } 788 789 cipinput.len = 131071; 790 SCIP_CALL( SCIPallocBufferArray(scip, &(cipinput.strbuf), cipinput.len) ); 791 792 cipinput.linenumber = 0; 793 cipinput.section = CIP_START; 794 cipinput.haserror = FALSE; 795 cipinput.endfile = FALSE; 796 cipinput.readingsize = 65535; 797 798 SCIP_CALL( SCIPcreateProb(scip, filename, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 799 800 SCIP_CALL( SCIPgetBoolParam(scip, "reading/initialconss", &initialconss) ); 801 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamiccols", &dynamiccols) ); 802 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicconss", &dynamicconss) ); 803 SCIP_CALL( SCIPgetBoolParam(scip, "reading/dynamicrows", &dynamicrows) ); 804 805 initialvar = !dynamiccols; 806 removablevar = dynamiccols; 807 808 objscale = 1.0; 809 objoffset = 0.0; 810 811 while( cipinput.section != CIP_END && !cipinput.haserror ) 812 { 813 /* get next input string */ 814 SCIP_CALL( getInputString(scip, &cipinput) ); 815 816 if( cipinput.endfile ) 817 break; 818 819 switch( cipinput.section ) 820 { 821 case CIP_START: 822 getStart(scip, &cipinput); 823 break; 824 case CIP_STATISTIC: 825 SCIP_CALL( getStatistics(scip, &cipinput) ); 826 break; 827 case CIP_OBJECTIVE: 828 SCIP_CALL( getObjective(scip, &cipinput, &objscale, &objoffset) ); 829 break; 830 case CIP_VARS: 831 retcode = getVariable(scip, &cipinput, initialvar, removablevar, objscale); 832 833 if( retcode == SCIP_READERROR ) 834 { 835 cipinput.haserror = TRUE; 836 goto TERMINATE; 837 } 838 SCIP_CALL(retcode); 839 840 break; 841 case CIP_FIXEDVARS: 842 retcode = getFixedVariable(scip, &cipinput); 843 844 if( retcode == SCIP_READERROR ) 845 { 846 cipinput.haserror = TRUE; 847 goto TERMINATE; 848 } 849 SCIP_CALL(retcode); 850 851 break; 852 case CIP_CONSTRAINTS: 853 retcode = getConstraint(scip, &cipinput, initialconss, dynamicconss, dynamicrows); 854 855 if( retcode == SCIP_READERROR ) 856 { 857 cipinput.haserror = TRUE; 858 goto TERMINATE; 859 } 860 SCIP_CALL(retcode); 861 862 break; 863 default: 864 SCIPerrorMessage("invalid CIP state\n"); 865 SCIPABORT(); 866 return SCIP_INVALIDDATA; /*lint !e527*/ 867 } /*lint !e788*/ 868 } 869 870 if( !SCIPisZero(scip, objoffset) && !cipinput.haserror ) 871 { 872 SCIP_VAR* objoffsetvar; 873 874 objoffset *= objscale; 875 SCIP_CALL( SCIPcreateVar(scip, &objoffsetvar, "objoffset", objoffset, objoffset, 1.0, SCIP_VARTYPE_CONTINUOUS, 876 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 877 SCIP_CALL( SCIPaddVar(scip, objoffsetvar) ); 878 SCIP_CALL( SCIPreleaseVar(scip, &objoffsetvar) ); 879 SCIPdebugMsg(scip, "added variables <objoffset> for objective offset of <%g>\n", objoffset); 880 } 881 882 if( cipinput.section != CIP_END && !cipinput.haserror ) 883 { 884 SCIPerrorMessage("unexpected EOF\n"); 885 } 886 887 TERMINATE: 888 /* close file stream */ 889 SCIPfclose(cipinput.file); 890 891 SCIPfreeBufferArray(scip, &cipinput.strbuf); 892 893 if( cipinput.haserror ) 894 return SCIP_READERROR; 895 896 /* successfully parsed cip format */ 897 *result = SCIP_SUCCESS; 898 return SCIP_OKAY; 899 } 900 901 /** hash key retrieval function for variables */ 902 static 903 SCIP_DECL_HASHGETKEY(hashGetKeyVar) 904 { /*lint --e{715}*/ 905 return elem; 906 } 907 908 /** returns TRUE iff the indices of both variables are equal */ 909 static 910 SCIP_DECL_HASHKEYEQ(hashKeyEqVar) 911 { /*lint --e{715}*/ 912 if( key1 == key2 ) 913 return TRUE; 914 return FALSE; 915 } 916 917 /** returns the hash value of the key */ 918 static 919 SCIP_DECL_HASHKEYVAL(hashKeyValVar) 920 { /*lint --e{715}*/ 921 assert( SCIPvarGetIndex((SCIP_VAR*) key) >= 0 ); 922 return (unsigned int) SCIPvarGetIndex((SCIP_VAR*) key); 923 } 924 925 /** problem writing method of reader */ 926 static 927 SCIP_DECL_READERWRITE(readerWriteCip) 928 { /*lint --e{715}*/ 929 SCIP_HASHTABLE* varhash = NULL; 930 SCIP_READERDATA* readerdata; 931 int i; 932 933 assert(reader != NULL); 934 assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0); 935 936 SCIPinfoMessage(scip, file, "STATISTICS\n"); 937 SCIPinfoMessage(scip, file, " Problem name : %s\n", name); 938 SCIPinfoMessage(scip, file, " Variables : %d (%d binary, %d integer, %d implicit integer, %d continuous)\n", 939 nvars, nbinvars, nintvars, nimplvars, ncontvars); 940 SCIPinfoMessage(scip, file, " Constraints : %d initial, %d maximal\n", startnconss, maxnconss); 941 942 SCIPinfoMessage(scip, file, "OBJECTIVE\n"); 943 SCIPinfoMessage(scip, file, " Sense : %s\n", objsense == SCIP_OBJSENSE_MINIMIZE ? "minimize" : "maximize"); 944 if( !SCIPisZero(scip, objoffset) ) 945 SCIPinfoMessage(scip, file, " Offset : %+.15g\n", objoffset); 946 if( !SCIPisEQ(scip, objscale, 1.0) ) 947 SCIPinfoMessage(scip, file, " Scale : %.15g\n", objscale); 948 949 if ( nfixedvars > 0 ) 950 { 951 /* set up hash table for variables that have been written property (used for writing out fixed vars in the right order) */ 952 SCIP_CALL( SCIPhashtableCreate(&varhash, SCIPblkmem(scip), nvars + nfixedvars, hashGetKeyVar, hashKeyEqVar, hashKeyValVar, NULL) ); 953 } 954 955 if ( nvars + nfixedvars > 0 ) 956 { 957 SCIPinfoMessage(scip, file, "VARIABLES\n"); 958 } 959 960 if( nvars > 0 ) 961 { 962 for( i = 0; i < nvars; ++i ) 963 { 964 SCIP_VAR* var; 965 966 var = vars[i]; 967 assert( var != NULL ); 968 SCIP_CALL( SCIPprintVar(scip, var, file) ); 969 if ( varhash != NULL ) 970 { 971 /* add free variable to hashtable */ 972 if ( ! SCIPhashtableExists(varhash, (void*) var) ) 973 { 974 SCIP_CALL( SCIPhashtableInsert(varhash, (void*) var) ); 975 } 976 } 977 } 978 } 979 980 readerdata = SCIPreaderGetData(reader); 981 assert(readerdata != NULL); 982 983 if( readerdata->writefixedvars && nfixedvars > 0 ) 984 { 985 int nwritten = 0; 986 987 SCIPinfoMessage(scip, file, "FIXED\n"); 988 989 /* loop through variables until each has been written after the variables that it depends on have been written; this 990 * requires several runs over the variables, but the depth (= number of loops) is usually small. */ 991 while ( nwritten < nfixedvars ) 992 { 993 SCIPdebugMsg(scip, "written %d of %d fixed variables.\n", nwritten, nfixedvars); 994 for (i = 0; i < nfixedvars; ++i) 995 { 996 SCIP_VAR* var; 997 SCIP_VAR* tmpvar; 998 999 var = fixedvars[i]; 1000 assert( var != NULL ); 1001 1002 /* skip variables already written */ 1003 if ( SCIPhashtableExists(varhash, (void*) var) ) 1004 continue; 1005 1006 switch ( SCIPvarGetStatus(var) ) 1007 { 1008 case SCIP_VARSTATUS_FIXED: 1009 1010 /* fixed variables can simply be output and added to the hashtable */ 1011 SCIP_CALL( SCIPprintVar(scip, var, file) ); 1012 assert( ! SCIPhashtableExists(varhash, (void*) var) ); 1013 SCIP_CALL( SCIPhashtableInsert(varhash, (void*) var) ); 1014 ++nwritten; 1015 1016 break; 1017 1018 case SCIP_VARSTATUS_NEGATED: 1019 1020 tmpvar = SCIPvarGetNegationVar(var); 1021 assert( tmpvar != NULL ); 1022 assert( var == SCIPvarGetNegatedVar(tmpvar) ); 1023 1024 /* if the negated variable has been written, we can write the current variable */ 1025 if ( SCIPhashtableExists(varhash, (void*) tmpvar) ) 1026 { 1027 SCIP_CALL( SCIPprintVar(scip, var, file) ); 1028 assert( ! SCIPhashtableExists(varhash, (void*) var) ); 1029 SCIP_CALL( SCIPhashtableInsert(varhash, (void*) var) ); 1030 ++nwritten; 1031 } 1032 break; 1033 1034 case SCIP_VARSTATUS_AGGREGATED: 1035 1036 tmpvar = SCIPvarGetAggrVar(var); 1037 assert( tmpvar != NULL ); 1038 1039 /* if the aggregating variable has been written, we can write the current variable */ 1040 if ( SCIPhashtableExists(varhash, (void*) tmpvar) ) 1041 { 1042 SCIP_CALL( SCIPprintVar(scip, var, file) ); 1043 assert( ! SCIPhashtableExists(varhash, (void*) var) ); 1044 SCIP_CALL( SCIPhashtableInsert(varhash, (void*) var) ); 1045 ++nwritten; 1046 } 1047 break; 1048 1049 case SCIP_VARSTATUS_MULTAGGR: 1050 { 1051 SCIP_VAR** aggrvars; 1052 int naggrvars; 1053 int j; 1054 1055 /* get the active representation */ 1056 SCIP_CALL( SCIPflattenVarAggregationGraph(scip, var) ); 1057 1058 naggrvars = SCIPvarGetMultaggrNVars(var); 1059 aggrvars = SCIPvarGetMultaggrVars(var); 1060 assert(aggrvars != NULL || naggrvars == 0); 1061 1062 for (j = 0; j < naggrvars; ++j) 1063 { 1064 if( !SCIPhashtableExists(varhash, (void*) aggrvars[j]) ) /*lint !e613*/ 1065 break; 1066 } 1067 1068 /* if all multi-aggregating variables have been written, we can write the current variable */ 1069 if ( j >= naggrvars ) 1070 { 1071 SCIP_CALL( SCIPprintVar(scip, var, file) ); 1072 assert( ! SCIPhashtableExists(varhash, (void*) var) ); 1073 SCIP_CALL( SCIPhashtableInsert(varhash, (void*) var) ); 1074 ++nwritten; 1075 } 1076 break; 1077 } 1078 1079 case SCIP_VARSTATUS_ORIGINAL: 1080 case SCIP_VARSTATUS_LOOSE: 1081 case SCIP_VARSTATUS_COLUMN: 1082 SCIPerrorMessage("Only fixed variables are allowed to be present in fixedvars list.\n"); 1083 SCIPABORT(); 1084 return SCIP_ERROR; /*lint !e527*/ 1085 } 1086 } 1087 } 1088 } 1089 1090 if( nconss > 0 ) 1091 { 1092 SCIPinfoMessage(scip, file, "CONSTRAINTS\n"); 1093 1094 for( i = 0; i < nconss; ++i ) 1095 { 1096 SCIP_CALL( SCIPprintCons(scip, conss[i], file) ); 1097 SCIPinfoMessage(scip, file, ";\n"); 1098 } 1099 } 1100 SCIPinfoMessage(scip, file, "END\n"); 1101 1102 *result = SCIP_SUCCESS; 1103 1104 if( nfixedvars > 0 ) 1105 SCIPhashtableFree(&varhash); 1106 else 1107 assert(varhash == NULL); 1108 1109 return SCIP_OKAY; 1110 } 1111 1112 1113 /* 1114 * reader specific interface methods 1115 */ 1116 1117 /** includes the cip file reader in SCIP */ 1118 SCIP_RETCODE SCIPincludeReaderCip( 1119 SCIP* scip /**< SCIP data structure */ 1120 ) 1121 { 1122 SCIP_READERDATA* readerdata; 1123 SCIP_READER* reader; 1124 1125 /* create cip reader data */ 1126 SCIP_CALL( SCIPallocBlockMemory(scip, &readerdata) ); 1127 1128 /* include reader */ 1129 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) ); 1130 1131 /* set non fundamental callbacks via setter functions */ 1132 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCip) ); 1133 SCIP_CALL( SCIPsetReaderFree(scip, reader, readerFreeCip) ); 1134 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCip) ); 1135 SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteCip) ); 1136 1137 /* add cip reader parameters */ 1138 SCIP_CALL( SCIPaddBoolParam(scip, 1139 "reading/cipreader/writefixedvars", "should fixed and aggregated variables be printed (if not, re-parsing might fail)", 1140 &readerdata->writefixedvars, FALSE, DEFAULT_CIP_WRITEFIXEDVARS, NULL, NULL) ); 1141 1142 return SCIP_OKAY; 1143 } 1144