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 cons_countsols.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for counting feasible solutions 28 * @author Stefan Heinz 29 * @author Michael Winkler 30 * 31 * If this constraint handler is activated than it counts or collects all feasible solutions. We refer to \ref COUNTER for 32 * more details about using SCIP for counting feasible solutions. 33 * 34 * @todo In the last round of presolving we should check if variables exist, which have up and down lock one. In this 35 * case we know that these locks are coming from this constraint handler. Therefore, they are totally free and can 36 * be ignored in the branch and bound process. To get this result we have to store these variables in the 37 * constraint handler data structure (to remember this free dimensions) and fix them to any feasible value. 38 */ 39 40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 41 42 #include "blockmemshell/memory.h" 43 #include "scip/cons_bounddisjunction.h" 44 #include "scip/cons_countsols.h" 45 #include "scip/cons_knapsack.h" 46 #include "scip/cons_logicor.h" 47 #include "scip/cons_setppc.h" 48 #include "scip/cons_varbound.h" 49 #include "scip/dialog_default.h" 50 #include "scip/pub_cons.h" 51 #include "scip/pub_dialog.h" 52 #include "scip/pub_disp.h" 53 #include "scip/pub_heur.h" 54 #include "scip/pub_message.h" 55 #include "scip/pub_misc.h" 56 #include "scip/pub_misc_sort.h" 57 #include "scip/pub_sol.h" 58 #include "scip/pub_var.h" 59 #include "scip/scip_branch.h" 60 #include "scip/scip_cons.h" 61 #include "scip/scip_dialog.h" 62 #include "scip/scip_disp.h" 63 #include "scip/scip_general.h" 64 #include "scip/scip_heur.h" 65 #include "scip/scip_mem.h" 66 #include "scip/scip_message.h" 67 #include "scip/scip_numerics.h" 68 #include "scip/scip_param.h" 69 #include "scip/scip_prob.h" 70 #include "scip/scip_sol.h" 71 #include "scip/scip_solve.h" 72 #include "scip/scip_var.h" 73 #include "symmetry/type_symmetry.h" 74 #include <string.h> 75 76 /* depending on whether the GMP library is available we use a GMP data type or a SCIP_Longint */ 77 #ifdef SCIP_WITH_GMP 78 #include <gmp.h> 79 typedef mpz_t Int; 80 #else 81 typedef SCIP_Longint Int; 82 #endif 83 84 /* constraint handler properties */ 85 #define CONSHDLR_NAME "countsols" 86 #define CONSHDLR_DESC "constraint to count feasible solutions" 87 #define CONSHDLR_ENFOPRIORITY -9999999 /**< priority of the constraint handler for constraint enforcing */ 88 #define CONSHDLR_CHECKPRIORITY -9999999 /**< priority of the constraint handler for checking feasibility */ 89 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 90 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 91 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */ 92 93 /* default parameter settings */ 94 #define DEFAULT_SPARSETEST TRUE /**< sparse test on or off */ 95 #define DEFAULT_DISCARDSOLS TRUE /**< is it allowed to discard solutions */ 96 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active */ 97 #define DEFAULT_COLLECT FALSE /**< should the solutions be collected */ 98 #define DEFAULT_SOLLIMIT -1LL /**< counting stops, if the given number of solutions were found (-1: no limit) */ 99 100 /* default column settings */ 101 #define DISP_SOLS_NAME "sols" 102 #define DISP_SOLS_DESC "number of detected feasible solutions" 103 #define DISP_SOLS_HEADER " sols " 104 #define DISP_SOLS_WIDTH 7 105 #define DISP_SOLS_PRIORITY 110000 106 #define DISP_SOLS_POSITION 100000 107 #define DISP_SOLS_STRIPLINE TRUE 108 109 #define DISP_CUTS_NAME "feasST" 110 #define DISP_CUTS_DESC "number of detected non trivial feasible subtrees" 111 #define DISP_CUTS_HEADER "feasST" 112 #define DISP_CUTS_WIDTH 6 113 #define DISP_CUTS_PRIORITY 110000 114 #define DISP_CUTS_POSITION 110000 115 #define DISP_CUTS_STRIPLINE TRUE 116 117 /** creates and adds a constraint which cuts off the solution from the feasibility region 118 * 119 * input: 120 * - scip : SCIP main data structure 121 * - sol : solution to cut off 122 * - conshdlrdata : constraint handler data 123 */ 124 #define CUTOFF_CONSTRAINT(x) SCIP_RETCODE x (SCIP* scip, SCIP_SOL* sol, SCIP_CONSHDLRDATA* conshdlrdata) 125 126 127 /** constraint handler data */ 128 struct SCIP_ConshdlrData 129 { 130 /* solution data and statistic variables */ 131 SCIP_SPARSESOL** solutions; /**< array to store all solutions */ 132 int nsolutions; /**< number of solution stored */ 133 int ssolutions; /**< size of the solution array */ 134 int feasST; /**< number of non trivial feasible subtrees */ 135 int nDiscardSols; /**< number of discarded solutions */ 136 int nNonSparseSols; /**< number of non sparse solutions */ 137 Int nsols; /**< number of solutions */ 138 CUTOFF_CONSTRAINT((*cutoffSolution)); /**< method for cutting of a solution */ 139 140 /* constraint handler parameters */ 141 SCIP_Longint sollimit; /**< counting stops, if the given number of solutions have been found (-1: no limit) */ 142 SCIP_Bool active; /**< constraint handler active */ 143 SCIP_Bool discardsols; /**< allow to discard solutions */ 144 SCIP_Bool sparsetest; /**< allow to check for sparse solutions */ 145 SCIP_Bool collect; /**< should the solutions be collected */ 146 147 SCIP_Bool warning; /**< has the warning message already been posted? */ 148 149 /* specific problem data */ 150 SCIP_HASHMAP* hashmap; /**< hashmap to store position of active transformed problem variable in our vars array */ 151 SCIP_VAR** allvars; /**< array containing a copy of all variables before presolving */ 152 SCIP_VAR** vars; /**< array containing a copy of all active variables (after presolving) */ 153 int nallvars; /**< number of all variables in the problem */ 154 int nvars; /**< number of all active variables in the problem */ 155 SCIP_Bool continuous; /**< are there continuous variables */ 156 }; 157 158 159 /* 160 * Local methods for handling the <Int> data structure 161 */ 162 163 /** allocates memory for the value pointer */ 164 static 165 void allocInt( 166 Int* value /**< pointer to the value to allocate memory */ 167 ) 168 { /*lint --e{715}*/ 169 #ifdef SCIP_WITH_GMP 170 mpz_init(*value); 171 #endif 172 } 173 174 175 /** sets the value pointer to the new value */ 176 static 177 void setInt( 178 Int* value, /**< pointer to the value to initialize */ 179 SCIP_Longint newvalue /**< new value */ 180 ) 181 { 182 assert(newvalue < LONG_MAX); 183 184 #ifdef SCIP_WITH_GMP 185 mpz_set_si(*value, (long) newvalue); 186 #else 187 (*value) = newvalue; 188 #endif 189 } 190 191 192 /** sets a power of 2 to the given value */ 193 static 194 void setPowerOfTwo( 195 Int* value, /**< pointer to the value to increase */ 196 SCIP_Longint exponent /**< exponent for the base 2 */ 197 ) 198 { 199 assert(0 <= exponent && exponent < LONG_MAX); 200 201 #ifdef SCIP_WITH_GMP 202 mpz_ui_pow_ui(*value, 2UL, (unsigned long) exponent); 203 #else 204 assert(exponent < 64); 205 (*value) = (SCIP_Longint)1 << exponent; 206 #endif 207 } 208 209 210 /** free memory */ 211 static 212 void freeInt( 213 Int* value /**< pointer to the value to free */ 214 ) 215 { /*lint --e{715}*/ 216 #ifdef SCIP_WITH_GMP 217 mpz_clear(*value); 218 #endif 219 } 220 221 222 /** adds one to the given value */ 223 static 224 void addOne( 225 Int* value /**< pointer to the value to increase */ 226 ) 227 { 228 #ifdef SCIP_WITH_GMP 229 mpz_add_ui(*value, *value, 1UL); 230 #else 231 (*value)++; 232 #endif 233 } 234 235 236 /** adds the summand to the given value */ 237 static 238 void addInt( 239 Int* value, /**< pointer to the value to increase */ 240 Int* summand /**< summand to add on */ 241 ) 242 { 243 #ifdef SCIP_WITH_GMP 244 mpz_add(*value, *value, *summand); 245 #else 246 (*value) += (*summand); 247 #endif 248 } 249 250 251 /** multiplies the factor by the given value */ 252 static 253 void multInt( 254 Int* value, /**< pointer to the value to increase */ 255 SCIP_Longint factor /**< factor to multiply with */ 256 ) 257 { 258 assert(0 <= factor && factor < LONG_MAX); 259 260 #ifdef SCIP_WITH_GMP 261 mpz_mul_ui(*value, *value, (unsigned long) factor); 262 #else 263 (*value) *= factor; 264 #endif 265 } 266 267 268 /** method for creating a string out of an Int which is a mpz_t or SCIP_Longint */ /*lint -e{715}*/ 269 static 270 void toString( 271 Int value, /**< number */ 272 char** buffer, /**< pointer to buffer for storing the string */ 273 int buffersize /**< length of the buffer */ 274 ) 275 { /*lint --e{715}*/ 276 #ifdef SCIP_WITH_GMP 277 (void) mpz_get_str(*buffer, 10, value); 278 #else 279 (void) SCIPsnprintf (*buffer, buffersize, "%" SCIP_LONGINT_FORMAT "", value); 280 #endif 281 } 282 283 284 /** method for creating a SCIP_Longing out of an Int */ 285 static 286 SCIP_Longint getNCountedSols( 287 Int value, /**< number to convert */ 288 SCIP_Bool* valid /**< pointer to store if the return value is valid */ 289 ) 290 { 291 #ifdef SCIP_WITH_GMP 292 *valid = FALSE; 293 if( 0 != mpz_fits_sint_p(value) ) 294 (*valid) = TRUE; 295 296 return mpz_get_si(value); 297 #else 298 *valid = TRUE; 299 return value; 300 #endif 301 } 302 303 304 /* 305 * Local methods 306 */ 307 308 309 /** returns whether a given integer variable is unfixed in the local domain */ 310 static 311 SCIP_Bool varIsUnfixedLocal( 312 SCIP_VAR* var /**< integer variable */ 313 ) 314 { 315 assert( var != NULL ); 316 assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ); 317 assert( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) >= 0.0 ); 318 319 return ( SCIPvarGetUbLocal(var) - SCIPvarGetLbLocal(var) > 0.5 ); 320 } 321 322 323 /** creates the constraint handler data */ 324 static 325 SCIP_RETCODE conshdlrdataCreate( 326 SCIP* scip, /**< SCIP data structure */ 327 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to store constraint handler data */ 328 ) 329 { 330 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) ); 331 332 (*conshdlrdata)->feasST = 0; 333 (*conshdlrdata)->nDiscardSols = 0; 334 (*conshdlrdata)->nNonSparseSols = 0; 335 (*conshdlrdata)->solutions = NULL; 336 (*conshdlrdata)->nsolutions = 0; 337 (*conshdlrdata)->ssolutions = 0; 338 339 allocInt(&(*conshdlrdata)->nsols); /*lint !e545*/ 340 341 (*conshdlrdata)->cutoffSolution = NULL; 342 (*conshdlrdata)->warning = FALSE; 343 (*conshdlrdata)->hashmap = NULL; 344 (*conshdlrdata)->allvars = NULL; 345 (*conshdlrdata)->vars = NULL; 346 (*conshdlrdata)->nallvars = 0; 347 (*conshdlrdata)->nvars = 0; 348 (*conshdlrdata)->continuous = FALSE; 349 350 return SCIP_OKAY; 351 } 352 353 354 #ifndef NDEBUG 355 /** check solution in original space */ 356 static 357 void checkSolutionOrig( 358 SCIP* scip, /**< SCIP data structure */ 359 SCIP_SOL* sol, /**< solution to add */ 360 SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */ 361 ) 362 { 363 SCIP_Bool feasible; 364 SCIP_RETCODE retcode; 365 366 /* turn off solution counting to be able to check the solution */ 367 conshdlrdata->active = FALSE; 368 369 SCIPdebugMsg(scip, "check solution in original space before counting\n"); 370 371 feasible = FALSE; 372 373 /* check solution in original space */ 374 retcode = SCIPcheckSolOrig(scip, sol, &feasible, TRUE, TRUE); 375 assert(feasible); 376 377 /* check return code manually */ 378 if( retcode != SCIP_OKAY ) 379 { 380 SCIPprintError(retcode); 381 SCIPABORT(); 382 } 383 384 /* turn on solution counting to continue */ 385 conshdlrdata->active = TRUE; 386 } 387 #else 388 #define checkSolutionOrig(scip, sol, conshdlrdata) /**/ 389 #endif 390 391 /** check if the current parameter setting is correct for a safe counting process */ 392 static 393 SCIP_RETCODE checkParameters( 394 SCIP* scip /**< SCIP data structure */ 395 ) 396 { 397 SCIP_HEUR** heuristics; 398 int nheuristics; 399 int h; 400 int intvalue; 401 SCIP_Bool valid; 402 403 assert( scip != NULL ); 404 405 valid = TRUE; 406 407 /* check if all heuristics are turned off */ 408 heuristics = SCIPgetHeurs(scip); 409 nheuristics = SCIPgetNHeurs(scip); 410 411 for( h = 0; h < nheuristics && valid; ++h ) 412 { 413 if( SCIPheurGetFreq(heuristics[h]) != -1 ) 414 valid = FALSE; 415 } 416 417 if( valid ) 418 { 419 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 420 "At least one heuristic is not turned off! Heuristic solutions are currently not accepted while couting.\n"); 421 } 422 423 /* check if restart is turned off */ 424 SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &intvalue) ); 425 if( intvalue != 0 ) 426 { 427 /* need to disable restarts, since collecting solutions won't work, but also the capturing for variables is not 428 * correctly handled 429 */ 430 SCIPwarningMessage(scip, "counting forces parameter <presolving/maxrestarts> to 0.\n"); 431 if( SCIPisParamFixed(scip, "presolving/maxrestarts") ) 432 { 433 SCIP_CALL( SCIPunfixParam(scip, "presolving/maxrestarts") ); 434 } 435 436 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) ); 437 } 438 439 /* check if symmetry handling is turned off */ 440 SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &intvalue) ); 441 if ( intvalue != 0 ) 442 { 443 /* need to disable symmetry handling, since counting is not supported if symmetry handling is enabled */ 444 SCIPwarningMessage(scip, "counting forces parameter <misc/usesymmetry> to 0.\n"); 445 if( SCIPisParamFixed(scip, "misc/usesymmetry") ) 446 { 447 SCIP_CALL( SCIPunfixParam(scip, "misc/usesymmetry") ); 448 } 449 450 SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) ); 451 } 452 453 return SCIP_OKAY; 454 } 455 456 /** creates and adds a constraints which cuts off the current solution from the feasibility region in the case there are 457 * only binary variables 458 */ 459 static 460 CUTOFF_CONSTRAINT(addBinaryCons) 461 { 462 int v; 463 SCIP_VAR** consvars; 464 SCIP_VAR** vars; 465 int nvars; 466 SCIP_Real value; 467 SCIP_VAR* var; 468 SCIP_CONS* cons; 469 470 assert( scip != NULL ); 471 assert( sol != NULL ); 472 assert( conshdlrdata != NULL ); 473 474 vars = conshdlrdata->vars; 475 nvars = conshdlrdata->nvars; 476 477 /* allocate buffer memory */ 478 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) ); 479 480 for( v = 0; v < nvars; ++v ) 481 { 482 var = vars[v]; 483 484 assert( var != NULL ); 485 assert( SCIPvarIsBinary(var) ); 486 487 value = SCIPgetSolVal(scip, sol, var); 488 assert( SCIPisFeasIntegral(scip, value) ); 489 490 if( value > 0.5 ) 491 { 492 SCIP_CALL( SCIPgetNegatedVar(scip, var, &consvars[v]) ); 493 } 494 else 495 consvars[v] = var; 496 } 497 498 /* create constraint */ 499 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, "Setcovering created by countsols", nvars, consvars, 500 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 501 502 /* add and release constraint */ 503 SCIP_CALL( SCIPaddCons(scip, cons) ); 504 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 505 506 /* free buffer array */ 507 SCIPfreeBufferArray(scip, &consvars); 508 509 return SCIP_OKAY; 510 } 511 512 513 /** creates and adds a bound disjunction constraints which cuts off the current solution from the feasibility region; if 514 * only binary variables are involved, then a set covering constraint is created which is a special case of a bound 515 * disjunction constraint 516 */ 517 static 518 CUTOFF_CONSTRAINT(addIntegerCons) 519 { 520 int v; 521 SCIP_VAR** consvars; 522 SCIP_VAR** vars; 523 SCIP_Real* bounds; 524 SCIP_BOUNDTYPE* boundtypes; 525 int nvars; 526 int nbinvars = 0; 527 int nconsvars; 528 SCIP_VAR* var; 529 SCIP_Real value; 530 SCIP_CONS* cons; 531 532 assert( scip != NULL ); 533 assert( sol != NULL ); 534 assert( conshdlrdata != NULL ); 535 536 vars = conshdlrdata->vars; 537 nvars = conshdlrdata->nvars; 538 539 nconsvars = nvars * 2; 540 assert( nvars > 0 ); 541 542 /* allocate buffer memory */ 543 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) ); 544 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nconsvars) ); 545 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nconsvars) ); 546 547 nconsvars = 0; 548 549 for( v = nvars - 1; v >= 0; --v ) 550 { 551 var = vars[v]; 552 553 assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ); 554 555 if( SCIPvarIsBinary(var) ) 556 { 557 ++nbinvars; 558 value = SCIPgetSolVal(scip, sol, var); 559 assert( SCIPisFeasIntegral(scip, value) ); 560 561 if( value < 0.5 ) 562 { 563 boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER; 564 bounds[nconsvars] = 1; 565 } 566 else 567 { 568 boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER; 569 bounds[nconsvars] = 0; 570 } 571 } 572 else 573 { 574 SCIP_Real lb; 575 SCIP_Real ub; 576 SCIP_Real valueInt; 577 578 assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(var)) ); 579 assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(var)) ); 580 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var)) ); 581 582 lb = SCIPvarGetLbLocal(var); 583 ub = SCIPvarGetUbLocal(var); 584 valueInt = SCIPgetSolVal(scip, sol, var); 585 586 if( SCIPisFeasEQ(scip, valueInt, lb) ) 587 { 588 boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER; 589 bounds[nconsvars] = lb + 1.0; 590 } 591 else if( SCIPisFeasEQ(scip, valueInt, ub) ) 592 { 593 boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER; 594 bounds[nconsvars] = ub - 1.0; 595 } 596 else 597 { 598 boundtypes[nconsvars] = SCIP_BOUNDTYPE_LOWER; 599 bounds[nconsvars] = valueInt + 1.0; 600 consvars[nconsvars] = var; 601 ++nconsvars; 602 boundtypes[nconsvars] = SCIP_BOUNDTYPE_UPPER; 603 bounds[nconsvars] = valueInt - 1.0; 604 } 605 } 606 607 consvars[nconsvars] = var; 608 ++nconsvars; 609 } 610 611 /* check if only binary variables appear in the constraint; if this is the case, we 612 * create a set covering constraint instead of a bound disjunction constraint 613 */ 614 if( nvars == nbinvars ) 615 { 616 for( v = nbinvars - 1; v >= 0; --v ) 617 { 618 /* in the case the bound is zero we have use the negated variable */ 619 if( bounds[v] == 0) 620 { 621 SCIP_CALL( SCIPgetNegatedVar(scip, consvars[v], &consvars[v])); 622 } 623 } 624 625 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, "Setcovering created by countsols", nbinvars, consvars, 626 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 627 } 628 else 629 { 630 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, "Bounddisjunction created by countsols", 631 nconsvars, consvars, boundtypes, bounds, 632 FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 633 } 634 635 /* add and release constraint locally */ 636 SCIP_CALL( SCIPaddCons(scip, cons) ); 637 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 638 639 /* free buffer memory */ 640 SCIPfreeBufferArray(scip, &consvars); 641 SCIPfreeBufferArray(scip, &bounds); 642 SCIPfreeBufferArray(scip, &boundtypes); 643 644 return SCIP_OKAY; 645 } 646 647 /** collect given solution or local domains as sparse solution */ 648 static 649 SCIP_RETCODE collectSolution( 650 SCIP* scip, /**< SCIP data structure */ 651 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 652 SCIP_SOL* sol /**< solution, or NULL if local domains */ 653 ) 654 { 655 SCIP_SPARSESOL* solution; 656 SCIP_Longint* lbvalues; 657 SCIP_Longint* ubvalues; 658 int nvars; 659 int v; 660 661 /* ensure size of solution array 662 * 663 * we use normal memory instead of block memory because this plugin is rarely used, the size of 'solutions' 664 * can be arbitrary large, and the change that the other blocks can be used is quite small 665 */ 666 if( conshdlrdata->nsolutions == conshdlrdata->ssolutions ) 667 { 668 if( conshdlrdata->ssolutions == 0 ) 669 { 670 conshdlrdata->ssolutions = 100; 671 SCIP_CALL( SCIPallocMemoryArray(scip, &conshdlrdata->solutions, conshdlrdata->ssolutions) ); 672 } 673 else 674 { 675 assert( conshdlrdata->ssolutions < INT_MAX / 2); 676 conshdlrdata->ssolutions *= 2; 677 SCIP_CALL( SCIPreallocMemoryArray(scip, &conshdlrdata->solutions, conshdlrdata->ssolutions) ); 678 } 679 } 680 assert( conshdlrdata->nsolutions < conshdlrdata->ssolutions ); 681 682 /* get number of active variables */ 683 nvars = conshdlrdata->nvars; 684 685 SCIPdebugMsg(scip, "creating solution number %d\n", conshdlrdata->nsolutions); 686 687 /* create a solution */ 688 SCIP_CALL_FINALLY( SCIPsparseSolCreate(&solution, conshdlrdata->vars, nvars, FALSE), SCIPsparseSolFree(&solution) ); 689 assert(solution != NULL); 690 691 lbvalues = SCIPsparseSolGetLbs(solution); 692 ubvalues = SCIPsparseSolGetUbs(solution); 693 assert(ubvalues != NULL); 694 assert(lbvalues != NULL); 695 696 for( v = nvars - 1; v >= 0; --v ) 697 { 698 SCIP_VAR* var; 699 700 var = conshdlrdata->vars[v]; 701 assert(var != NULL); 702 703 if( sol == NULL ) 704 { 705 lbvalues[v] = SCIPconvertRealToLongint(scip, SCIPvarGetLbLocal(var)); 706 ubvalues[v] = SCIPconvertRealToLongint(scip, SCIPvarGetUbLocal(var)); 707 } 708 else 709 { 710 lbvalues[v] = SCIPconvertRealToLongint(scip, SCIPgetSolVal(scip, sol, var)); 711 ubvalues[v] = lbvalues[v]; 712 } 713 714 SCIPdebugMsg(scip, "variable <%s> [%" SCIP_LONGINT_FORMAT ",%" SCIP_LONGINT_FORMAT "]\n", 715 SCIPvarGetName(var), lbvalues[v], ubvalues[v]); 716 } 717 718 conshdlrdata->solutions[conshdlrdata->nsolutions] = solution; 719 conshdlrdata->nsolutions++; 720 721 return SCIP_OKAY; 722 } 723 724 725 /** counts the number of solutions represented by sol */ 726 static 727 SCIP_RETCODE countSparseSol( 728 SCIP* scip, /**< SCIP data structure */ 729 SCIP_SOL* sol, /**< solution */ 730 SCIP_Bool feasible, /**< is solution feasible? */ 731 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 732 SCIP_RESULT* result /**< pointer to store the result of the checking process */ 733 ) 734 { 735 assert( scip != NULL ); 736 assert( sol != NULL ); 737 assert( conshdlrdata != NULL ); 738 assert( result != NULL ); 739 740 /* the result should be infeasible since we reject any solution; however, if the solution passes the sparse test, the 741 * result is set to SCIP_CUTOFF which cuts off the subtree initialized through the current node 742 */ 743 assert(*result == SCIP_INFEASIBLE); 744 745 if( feasible ) 746 { 747 int v; 748 Int newsols; 749 SCIP_VAR** vars; 750 int nvars; 751 SCIP_VAR* var; 752 SCIP_Real lb; 753 SCIP_Real ub; 754 755 SCIPdebugMsg(scip, "counts number of solutions represented through the given one\n"); 756 757 /**@note aggregations and multi aggregations: we do not have to care about these things 758 * since we count solutions from the transformed problem and therefore, SCIP does 759 * it for us 760 */ 761 assert( SCIPgetNPseudoBranchCands(scip) != 0 ); 762 763 allocInt(&newsols); /*lint !e545*/ 764 765 /* set newsols to one */ 766 setInt(&newsols, 1LL); /*lint !e545*/ 767 768 if( SCIPgetNBinVars(scip) == SCIPgetNVars(scip) ) 769 { 770 int npseudocands; 771 772 npseudocands = SCIPgetNPseudoBranchCands(scip); 773 774 /* sets a power of 2 to the number of solutions */ 775 setPowerOfTwo(&newsols, (SCIP_Longint) npseudocands); /*lint !e545*/ 776 } 777 else 778 { 779 SCIP_VAR* origvar; 780 SCIP_Real scalar = 1.0; 781 SCIP_Real constant = 0.0; 782 783 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &vars, &nvars, NULL) ); 784 785 for( v = 0; v < nvars; ++v ) 786 { 787 var = vars[v]; 788 origvar = var; 789 790 /* get original variable to decide if we will count the domain; continuous variables aren't counted */ 791 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 792 793 if( origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS ) 794 { 795 lb = SCIPvarGetLbLocal(var); 796 ub = SCIPvarGetUbLocal(var); 797 798 SCIPdebugMsg(scip, "variable <%s> Local Bounds are [%g,%g]\n", SCIPvarGetName(var), lb, ub); 799 800 assert( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ); 801 assert( SCIPisFeasIntegral(scip, lb) ); 802 assert( SCIPisFeasIntegral(scip, ub) ); 803 assert( SCIPisFeasIntegral(scip, ub - lb) ); 804 assert( SCIPisFeasLT(scip, lb, ub) ); 805 806 /* the number of integers lying in the interval [lb,ub] is (ub - lb + 1); to make everything integral we 807 * add another 0.5 and cut the fractional part off 808 */ 809 multInt(&newsols, (SCIP_Longint)(ub - lb + 1.5) ); /*lint !e545*/ 810 } 811 } 812 } 813 814 *result = SCIP_CUTOFF; 815 conshdlrdata->feasST++; 816 817 if( conshdlrdata->collect ) 818 { 819 SCIP_CALL( collectSolution(scip, conshdlrdata, NULL) ); 820 } 821 822 addInt(&conshdlrdata->nsols, &newsols); /*lint !e545*/ 823 freeInt(&newsols); /*lint !e545*/ 824 } 825 else if(!conshdlrdata->discardsols) 826 { 827 SCIP_CALL( conshdlrdata->cutoffSolution(scip, sol, conshdlrdata) ); 828 addOne(&conshdlrdata->nsols); /*lint !e545*/ 829 conshdlrdata->nNonSparseSols++; 830 if( conshdlrdata->collect ) 831 { 832 SCIP_CALL( collectSolution(scip, conshdlrdata, sol) ); 833 } 834 } 835 else 836 conshdlrdata->nDiscardSols++; 837 838 return SCIP_OKAY; 839 } 840 841 842 /** checks if the new solution is feasible for the logicor constraints */ 843 static 844 SCIP_RETCODE checkLogicor( 845 SCIP* scip, /**< SCIP data structure */ 846 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 847 int nconss, /**< number of enabled constraints */ 848 SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */ 849 ) 850 { 851 /**@note the logicor constraints are not fully propagated; therefore, we have to check 852 * them by hand if they are satisfied or not; if a constraint is satisfied we 853 * delete it locally from the branch and bound tree. 854 */ 855 856 SCIP_CONS** conss; 857 SCIP_VAR** vars; 858 SCIP_Bool fixedone; 859 int nvars; 860 int c; 861 int v; 862 863 SCIPdebugMsg(scip, "check logicor %d constraints\n", nconss); 864 865 assert( scip != NULL ); 866 assert( conshdlr != NULL ); 867 assert( strcmp(SCIPconshdlrGetName(conshdlr),"logicor") == 0 ); 868 assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) ); 869 870 conss = SCIPconshdlrGetConss(conshdlr); 871 assert( conss != NULL ); 872 873 (*satisfied) = TRUE; 874 c = SCIPconshdlrGetNActiveConss(conshdlr) - 1; 875 876 for( ; c >= 0 && nconss > 0 && (*satisfied); --c ) 877 { 878 SCIPdebugMsg(scip, "logicor constraint %d\n", c); 879 880 if( !SCIPconsIsEnabled(conss[c]) ) 881 continue; 882 883 nconss--; 884 885 nvars = SCIPgetNVarsLogicor(scip, conss[c]); 886 vars = SCIPgetVarsLogicor(scip, conss[c]); 887 888 /* calculate the constraint's activity */ 889 fixedone = FALSE; 890 for( v = 0; v < nvars && !fixedone; ++v ) 891 { 892 assert(SCIPvarIsBinary(vars[v])); 893 894 if( !varIsUnfixedLocal(vars[v] ) ) 895 fixedone = SCIPvarGetLbLocal(vars[v]) > 0.5; 896 } 897 898 if( !fixedone ) 899 { 900 SCIPdebugMsg(scip, "constraint <%s> cannot be disabled\n", SCIPconsGetName(conss[c])); 901 SCIPdebugPrintCons(scip, conss[c], NULL); 902 (*satisfied) = FALSE; 903 } 904 else 905 { 906 /* delete constraint from the problem locally since it is satisfied */ 907 SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) ); 908 } 909 } 910 911 return SCIP_OKAY; 912 } 913 914 915 /** checks if the new solution is feasible for the knapsack constraints */ 916 static 917 SCIP_RETCODE checkKnapsack( 918 SCIP* scip, /**< SCIP data structure */ 919 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 920 int nconss, /**< number of enabled constraints */ 921 SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */ 922 ) 923 { 924 /**@note the knapsack constraints are not fully propagated; therefore, we have to check 925 * them by hand if they are satisfied or not; if a constraint is satisfied we 926 * delete it locally from the branch and bound tree. 927 */ 928 929 SCIP_CONS** conss; 930 SCIP_VAR** vars; 931 SCIP_Longint* weights; 932 SCIP_Longint capacity; 933 SCIP_Real capa; 934 int nvars; 935 int c; 936 int v; 937 938 SCIPdebugMsg(scip, "check knapsack %d constraints\n", nconss); 939 940 assert( scip != NULL ); 941 assert( conshdlr != NULL ); 942 assert( strcmp(SCIPconshdlrGetName(conshdlr),"knapsack") == 0 ); 943 assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) ); 944 945 conss = SCIPconshdlrGetConss(conshdlr); 946 assert( conss != NULL ); 947 948 (*satisfied) = TRUE; 949 c = SCIPconshdlrGetNActiveConss(conshdlr) - 1; 950 951 for( ; c >= 0 && nconss > 0 && (*satisfied); --c ) 952 { 953 SCIPdebugMsg(scip, "knapsack constraint %d\n", c); 954 955 if( !SCIPconsIsEnabled(conss[c]) ) 956 continue; 957 958 nconss--; 959 960 nvars = SCIPgetNVarsKnapsack(scip, conss[c]); 961 vars = SCIPgetVarsKnapsack(scip, conss[c]); 962 capacity = SCIPgetCapacityKnapsack(scip, conss[c]); 963 weights = SCIPgetWeightsKnapsack(scip,conss[c]); 964 965 SCIPdebugMsg(scip, "knapsack capacity = %" SCIP_LONGINT_FORMAT "\n", capacity); 966 967 capa = capacity + 0.1; 968 969 for( v = nvars - 1; v >= 0 && capa >= 0 ; --v ) 970 { 971 SCIPdebug( SCIP_CALL( SCIPprintVar( scip, vars[v], NULL) ) ); 972 SCIPdebugMsg(scip, "weight = %" SCIP_LONGINT_FORMAT " :\n", weights[v]); 973 assert( SCIPvarIsIntegral(vars[v]) ); 974 975 /* the weights should be greater or equal to zero */ 976 assert( weights[v] >= 0); 977 978 if( !varIsUnfixedLocal(vars[v]) ) 979 { 980 /* variable is fixed locally; therefore, subtract fixed variable value multiplied by 981 * the weight; 982 */ 983 capa -= weights[v] * SCIPvarGetLbLocal(vars[v]); 984 } 985 else if( weights[v] >= 1 ) 986 { 987 /* variable is unfixed and weight is greater than 0; therefore, subtract upper bound 988 * value multiplied by the weight 989 */ 990 capa -= weights[v] * SCIPvarGetUbLocal(vars[v]); 991 } 992 } 993 994 if( SCIPisFeasLT(scip, capa, 0.0) ) 995 { 996 SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c])); 997 SCIPdebugPrintCons(scip, conss[c], NULL); 998 (*satisfied) = FALSE; 999 } 1000 else 1001 { 1002 /* delete constraint from the problem locally since it is satisfied */ 1003 SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) ); 1004 } 1005 } 1006 return SCIP_OKAY; 1007 } 1008 1009 1010 /** checks if the new solution is feasible for the bounddisjunction constraints */ 1011 static 1012 SCIP_RETCODE checkBounddisjunction( 1013 SCIP* scip, /**< SCIP data structure */ 1014 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1015 int nconss, /**< number of enabled constraints */ 1016 SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */ 1017 ) 1018 { 1019 /**@note the bounddisjunction constraints are not fully propagated; therefore, we have to check 1020 * them by hand if they are satisfied or not; if a constraint is satisfied we 1021 * delete it locally from the branch and bound tree 1022 */ 1023 1024 SCIP_CONS** conss; 1025 SCIP_VAR** vars; 1026 SCIP_BOUNDTYPE* boundtypes; 1027 SCIP_Real* bounds; 1028 SCIP_Bool satisfiedbound; 1029 int nvars; 1030 int c; 1031 int v; 1032 1033 assert( scip != NULL ); 1034 assert( conshdlr != NULL ); 1035 assert( strcmp(SCIPconshdlrGetName(conshdlr),"bounddisjunction") == 0 ); 1036 assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) ); 1037 1038 conss = SCIPconshdlrGetConss(conshdlr); 1039 assert( conss != NULL ); 1040 1041 (*satisfied) = TRUE; 1042 c = SCIPconshdlrGetNActiveConss(conshdlr) - 1; 1043 1044 for( ; c >= 0 && nconss > 0 && (*satisfied); --c ) 1045 { 1046 if( !SCIPconsIsEnabled(conss[c]) ) 1047 continue; 1048 1049 nconss--; 1050 satisfiedbound = FALSE; 1051 1052 nvars = SCIPgetNVarsBounddisjunction(scip, conss[c]); 1053 vars = SCIPgetVarsBounddisjunction(scip, conss[c]); 1054 1055 boundtypes = SCIPgetBoundtypesBounddisjunction(scip, conss[c]); 1056 bounds = SCIPgetBoundsBounddisjunction(scip, conss[c]); 1057 1058 for( v = nvars-1; v >= 0 && !satisfiedbound; --v ) 1059 { 1060 SCIPdebug( SCIPprintVar(scip, vars[v], NULL) ); 1061 1062 /* variable should be in right bounds to delete constraint */ 1063 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 1064 satisfiedbound = SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[v]), bounds[v]); 1065 else 1066 { 1067 assert( boundtypes[v] == SCIP_BOUNDTYPE_UPPER ); 1068 satisfiedbound = SCIPisFeasLE(scip, SCIPvarGetUbLocal(vars[v]), bounds[v]); 1069 } 1070 } 1071 1072 if( !satisfiedbound ) 1073 { 1074 SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c])); 1075 SCIPdebugPrintCons(scip, conss[c], NULL); 1076 (*satisfied) = FALSE; 1077 } 1078 else 1079 { 1080 /* delete constraint from the problem locally since it is satisfied */ 1081 SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) ); 1082 } 1083 } 1084 return SCIP_OKAY; 1085 } 1086 1087 1088 /** checks if the new solution is feasible for the varbound constraints */ 1089 static 1090 SCIP_RETCODE checkVarbound( 1091 SCIP* scip, /**< SCIP data structure */ 1092 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1093 int nconss, /**< number of enabled constraints */ 1094 SCIP_Bool* satisfied /**< pointer to store if the logicor constraints a satisfied */ 1095 ) 1096 { 1097 /**@note the varbound constraints are not fully propagated; therefore, we have to check 1098 * them by hand if they are satisfied or not; if a constraint is satisfied we 1099 * delete it locally from the branch and bound tree. 1100 */ 1101 1102 SCIP_CONS** conss; 1103 SCIP_VAR* var; 1104 SCIP_VAR* vbdvar; 1105 SCIP_Real lhs; 1106 SCIP_Real rhs; 1107 SCIP_Real coef; 1108 int c; 1109 1110 SCIPdebugMsg(scip, "check varbound %d constraints\n", nconss); 1111 1112 assert( scip != NULL ); 1113 assert( conshdlr != NULL ); 1114 assert( strcmp(SCIPconshdlrGetName(conshdlr),"varbound") == 0 ); 1115 assert( nconss == SCIPconshdlrGetNEnabledConss(conshdlr) ); 1116 1117 conss = SCIPconshdlrGetConss(conshdlr); 1118 assert( conss != NULL ); 1119 1120 (*satisfied) = TRUE; 1121 c = SCIPconshdlrGetNActiveConss(conshdlr) - 1; 1122 1123 for( ; c >= 0 && nconss > 0 && (*satisfied); --c ) 1124 { 1125 SCIPdebugMsg(scip, "varbound constraint %d\n", c); 1126 1127 if( !SCIPconsIsEnabled(conss[c]) ) 1128 continue; 1129 1130 nconss--; 1131 1132 var = SCIPgetVarVarbound(scip, conss[c]); 1133 vbdvar = SCIPgetVbdvarVarbound(scip, conss[c]); 1134 1135 assert (SCIPvarGetType(vbdvar) != SCIP_VARTYPE_CONTINUOUS); 1136 1137 coef = SCIPgetVbdcoefVarbound(scip, conss[c]); 1138 lhs = SCIPgetLhsVarbound(scip, conss[c]); 1139 rhs = SCIPgetRhsVarbound(scip, conss[c]); 1140 1141 /* variables y is fixed locally; therefore, subtract fixed variable value multiplied by 1142 * the coefficient; 1143 */ 1144 if(SCIPisGT(scip, SCIPvarGetUbLocal(var), rhs - SCIPvarGetUbLocal(vbdvar) * coef ) 1145 || !SCIPisGE(scip, SCIPvarGetLbLocal(var), lhs - SCIPvarGetLbLocal(vbdvar) * coef ) ) 1146 { 1147 SCIPdebugMsg(scip, "constraint %s cannot be disabled\n", SCIPconsGetName(conss[c])); 1148 SCIPdebugPrintCons(scip, conss[c], NULL); 1149 SCIPdebugMsg(scip, "<%s> lb: %.15g\t ub: %.15g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 1150 SCIPdebugMsg(scip, "<%s> lb: %.15g\t ub: %.15g\n", SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar)); 1151 (*satisfied) = FALSE; 1152 } 1153 else 1154 { 1155 /* delete constraint from the problem locally since it is satisfied */ 1156 SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) ); 1157 } 1158 } 1159 1160 return SCIP_OKAY; 1161 } 1162 1163 1164 /** check if the current node initializes a non trivial unrestricted subtree */ 1165 static 1166 SCIP_RETCODE checkFeasSubtree( 1167 SCIP* scip, /**< SCIP main data structure */ 1168 SCIP_SOL* sol, /**< solution to check */ 1169 SCIP_Bool* feasible /**< pointer to store the result of the check */ 1170 ) 1171 { 1172 int h; 1173 1174 SCIP_CONSHDLR** conshdlrs; 1175 int nconshdlrs; 1176 1177 SCIP_CONSHDLR* conshdlr; 1178 int nconss; 1179 1180 SCIPdebugMsg(scip, "check if the sparse solution is feasible\n"); 1181 1182 assert( scip != NULL ); 1183 assert( sol != NULL ); 1184 assert( feasible != NULL ); 1185 1186 assert( SCIPgetNPseudoBranchCands(scip) != 0 ); 1187 1188 *feasible = FALSE; 1189 1190 nconshdlrs = SCIPgetNConshdlrs(scip) - 1; 1191 conshdlrs = SCIPgetConshdlrs(scip); 1192 assert(conshdlrs != NULL); 1193 1194 /* check each constraint handler if there are constraints which are not enabled */ 1195 for( h = nconshdlrs ; h >= 0 ; --h ) 1196 { 1197 conshdlr = conshdlrs[h]; 1198 assert( conshdlr != NULL ); 1199 1200 /* skip this constraints handler */ 1201 if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ) 1202 continue; 1203 1204 nconss = SCIPconshdlrGetNEnabledConss(conshdlr); 1205 1206 if( nconss > 0 ) 1207 { 1208 SCIP_Bool satisfied; 1209 1210 SCIPdebugMsg(scip, "constraint handler %s has %d active constraint(s)\n", 1211 SCIPconshdlrGetName(conshdlr), nconss ); 1212 1213 if( strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0 ) 1214 { 1215 SCIP_CALL( checkLogicor(scip, conshdlr, nconss, &satisfied) ); 1216 if( !satisfied ) 1217 { 1218 SCIPdebugMsg(scip, "a <logicor> constraint cannot be disabled\n"); 1219 return SCIP_OKAY; 1220 } 1221 } 1222 else if( strcmp(SCIPconshdlrGetName(conshdlr), "knapsack") == 0 ) 1223 { 1224 SCIP_CALL( checkKnapsack(scip, conshdlr, nconss, &satisfied) ); 1225 if( !satisfied ) 1226 { 1227 SCIPdebugMsg(scip, "a <knapsack> constraint cannot be disabled\n"); 1228 return SCIP_OKAY; 1229 } 1230 } 1231 else if( strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0 ) 1232 { 1233 SCIP_CALL( checkBounddisjunction(scip, conshdlr, nconss, &satisfied) ); 1234 if( !satisfied ) 1235 { 1236 SCIPdebugMsg(scip, "a <bounddisjunction> constraint cannot be disabled\n"); 1237 return SCIP_OKAY; 1238 } 1239 } 1240 else if( strcmp(SCIPconshdlrGetName(conshdlr), "varbound") == 0 ) 1241 { 1242 SCIP_CALL( checkVarbound(scip, conshdlr, nconss, &satisfied) ); 1243 if( !satisfied ) 1244 { 1245 SCIPdebugMsg(scip, "a <varbound> constraint cannot be disabled\n"); 1246 return SCIP_OKAY; 1247 } 1248 } 1249 else 1250 { 1251 SCIPdebugMsg(scip, "sparse solution is infeasible since the following constraint (and maybe more) is(/are) enabled\n"); 1252 SCIPdebugPrintCons(scip, SCIPconshdlrGetConss(conshdlr)[0], NULL); 1253 return SCIP_OKAY; 1254 } 1255 } 1256 } 1257 1258 *feasible = TRUE; 1259 SCIPdebugMsg(scip, "sparse solution is feasible\n"); 1260 1261 return SCIP_OKAY; 1262 } 1263 1264 1265 /** check the given solution */ 1266 static 1267 SCIP_RETCODE checkSolution( 1268 SCIP* scip, /**< SCIP data structure */ 1269 SCIP_SOL* sol, /**< solution to add */ 1270 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 1271 SCIP_RESULT* result /**< pointer to store the result of the checking process */ 1272 ) 1273 { 1274 SCIP_Longint nsols; 1275 SCIP_Bool feasible; 1276 SCIP_Bool valid; 1277 1278 SCIPdebugMsg(scip, "start to add sparse solution\n"); 1279 1280 assert( scip != NULL ); 1281 assert( sol != NULL ); 1282 assert( conshdlrdata != NULL ); 1283 assert( result != NULL ); 1284 1285 /* the solution should not be found through a heuristic since in this case the information of SCIP is not valid for 1286 * this solution 1287 */ 1288 1289 /**@todo it might be not necessary to check this assert since we can check in general all solutions of feasibility 1290 * independently of the origin; however, the locally fixed technique does only work if the solution comes from 1291 * the branch and bound tree; in case the solution comes from a heuristic we should try to sequentially fix the 1292 * variables in the branch and bound tree and check after every fixing if all constraints are disabled; at the 1293 * point where all constraints are disabled the unfixed variables are "stars" (arbitrary); 1294 */ 1295 assert( SCIPgetNOrigVars(scip) != 0); 1296 assert( SCIPsolGetHeur(sol) == NULL); 1297 1298 /* setting result to infeasible since we reject any solution; however, if the solution passes the sparse test or is 1299 * completely fixed, the result is set to SCIP_CUTOFF which cuts off the subtree initialized through the current node 1300 */ 1301 *result = SCIP_INFEASIBLE; 1302 1303 #ifdef SCIP_DEBUG 1304 { 1305 SCIP_VAR* var; 1306 SCIP_VAR** vars; 1307 int v; 1308 int nvars; 1309 1310 nvars = SCIPgetNVars(scip); 1311 vars = SCIPgetVars(scip); 1312 1313 for( v = 0; v < nvars; ++v ) 1314 { 1315 var = vars[v]; 1316 SCIPdebugMsg(scip, "variables <%s> Local Bounds are [%g,%g] Global Bounds are [%g,%g]\n", 1317 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)); 1318 } 1319 } 1320 #endif 1321 1322 /* check if integer variables are completely fixed */ 1323 if( SCIPgetNPseudoBranchCands(scip) == 0 ) 1324 { 1325 /* check solution original space */ 1326 checkSolutionOrig(scip, sol, conshdlrdata); 1327 1328 addOne(&conshdlrdata->nsols); /*lint !e545*/ 1329 conshdlrdata->nNonSparseSols++; 1330 1331 SCIPdebugMsg(scip, "-> add one to number of solutions\n"); 1332 1333 if( conshdlrdata->collect ) 1334 { 1335 SCIP_CALL( collectSolution(scip, conshdlrdata, sol) ); 1336 } 1337 1338 /* in case of continuous variables are present we explicitly cutoff the integer assignment since in case of 1339 * nonlinear constraint we want to avoid to count that integer assignment again 1340 */ 1341 if( conshdlrdata->continuous ) 1342 { 1343 SCIP_CALL( conshdlrdata->cutoffSolution(scip, sol, conshdlrdata) ); 1344 } 1345 1346 /* since all integer are fixed, we cut off the subtree */ 1347 *result = SCIP_CUTOFF; 1348 } 1349 else if( conshdlrdata->sparsetest ) 1350 { 1351 SCIP_CALL( checkFeasSubtree(scip, sol, &feasible) ) ; 1352 SCIP_CALL( countSparseSol(scip, sol, feasible, conshdlrdata, result) ); 1353 } 1354 1355 /* transform the current number of solutions into a SCIP_Longint */ 1356 nsols = getNCountedSols(conshdlrdata->nsols, &valid); 1357 1358 /* check if the solution limit is hit and stop SCIP if this is the case */ 1359 if( conshdlrdata->sollimit > -1 && (!valid || conshdlrdata->sollimit <= nsols) ) 1360 { 1361 SCIP_CALL( SCIPinterruptSolve(scip) ); 1362 } 1363 1364 assert( *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF ); 1365 SCIPdebugMsg(scip, "result is %s\n", *result == SCIP_INFEASIBLE ? "SCIP_INFEASIBLE" : "SCIP_CUTOFF" ); 1366 1367 return SCIP_OKAY; 1368 } 1369 1370 /* 1371 * Callback methods of constraint handler 1372 */ 1373 1374 /** creates the handler for countsols constraints and includes it in SCIP */ 1375 static 1376 SCIP_RETCODE includeConshdlrCountsols( 1377 SCIP* scip, /**< SCIP data structure */ 1378 SCIP_Bool dialogs /**< sould count dialogs be added */ 1379 ); 1380 1381 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1382 static 1383 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCountsols) 1384 { /*lint --e{715}*/ 1385 SCIP_CONSHDLRDATA* conshdlrdata; 1386 1387 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1388 assert(conshdlrdata != NULL); 1389 1390 /* in case the countsols constraint handler is active we avoid copying to ensure a safe count */ 1391 if( conshdlrdata->active ) 1392 *valid = FALSE; 1393 else 1394 { 1395 assert(scip != NULL); 1396 assert(conshdlr != NULL); 1397 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1398 1399 /* call inclusion method of constraint handler and do not add counting dialogs */ 1400 SCIP_CALL( includeConshdlrCountsols(scip, FALSE) ); 1401 1402 *valid = TRUE; 1403 } 1404 1405 return SCIP_OKAY; 1406 } 1407 1408 #define consCopyCountsols NULL 1409 1410 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 1411 static 1412 SCIP_DECL_CONSFREE(consFreeCountsols) 1413 { /*lint --e{715}*/ 1414 SCIP_CONSHDLRDATA* conshdlrdata; 1415 1416 assert(conshdlr != NULL); 1417 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1418 1419 /* free constraint handler data */ 1420 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1421 assert(conshdlrdata != NULL); 1422 1423 /* free conshdlrdata */ 1424 freeInt(&conshdlrdata->nsols); /*lint !e545*/ 1425 1426 assert( conshdlrdata->solutions == NULL ); 1427 assert( conshdlrdata->nsolutions == 0 ); 1428 assert( conshdlrdata->ssolutions == 0 ); 1429 1430 SCIPfreeBlockMemory(scip, &conshdlrdata); 1431 SCIPconshdlrSetData(conshdlr, NULL); 1432 1433 return SCIP_OKAY; 1434 } 1435 1436 /** initialization method of constraint handler (called after problem was transformed) */ 1437 static 1438 SCIP_DECL_CONSINIT(consInitCountsols) 1439 { /*lint --e{715}*/ 1440 SCIP_CONSHDLRDATA* conshdlrdata; 1441 1442 assert( conshdlr != NULL ); 1443 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1444 1445 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1446 assert(conshdlrdata != NULL ); 1447 1448 /* reset counting variables */ 1449 conshdlrdata->feasST = 0; /* number of non trivial unrestricted subtrees */ 1450 conshdlrdata->nDiscardSols = 0; /* number of discard solutions */ 1451 conshdlrdata->nNonSparseSols = 0; /* number of non sparse solutions */ 1452 setInt(&conshdlrdata->nsols, 0LL); /* number of solutions */ /*lint !e545*/ 1453 1454 conshdlrdata->solutions = NULL; 1455 conshdlrdata->nsolutions = 0; 1456 conshdlrdata->ssolutions = 0; 1457 1458 if( conshdlrdata->active ) 1459 { 1460 SCIP_VAR** origvars; 1461 int norigvars; 1462 int nallvars; 1463 int v; 1464 1465 origvars = SCIPgetOrigVars(scip); 1466 norigvars = SCIPgetNOrigVars(scip); 1467 1468 /* get number of integral variables */ 1469 conshdlrdata->nallvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip); 1470 1471 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->allvars, conshdlrdata->nallvars) ); 1472 1473 nallvars = 0; 1474 1475 /* capture and lock all variables */ 1476 for( v = 0; v < norigvars; ++v ) 1477 { 1478 if( SCIPvarGetType(origvars[v]) != SCIP_VARTYPE_CONTINUOUS ) 1479 { 1480 assert(nallvars < conshdlrdata->nallvars); 1481 1482 SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &conshdlrdata->allvars[nallvars]) ); 1483 assert(conshdlrdata->allvars[nallvars] != NULL); 1484 1485 /* capture variable to ensure that the variable will not be deleted */ 1486 SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->allvars[nallvars]) ); 1487 1488 if( strncmp(SCIPvarGetName(conshdlrdata->allvars[nallvars]), "t_andresultant_", strlen("t_andresultant_")) != 0 ) 1489 { 1490 /* lock variable to avoid dual reductions */ 1491 SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[nallvars], SCIP_LOCKTYPE_MODEL, 1, 1) ); 1492 } 1493 1494 nallvars++; 1495 } 1496 } 1497 assert(nallvars == conshdlrdata->nallvars); 1498 1499 /* check if continuous variables are present */ 1500 conshdlrdata->continuous = SCIPgetNContVars(scip) > 0; 1501 } 1502 1503 return SCIP_OKAY; 1504 } 1505 1506 /** deinitialization method of constraint handler (called before transformed problem is freed) */ 1507 static 1508 SCIP_DECL_CONSEXIT(consExitCountsols) 1509 { /*lint --e{715}*/ 1510 SCIP_CONSHDLRDATA* conshdlrdata; 1511 int s; 1512 int v; 1513 1514 assert( conshdlr != NULL ); 1515 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1516 1517 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1518 assert(conshdlrdata != NULL ); 1519 1520 /* release variables to hashmap */ 1521 for( v = conshdlrdata->nvars - 1; v >= 0; --v ) 1522 { 1523 SCIP_CALL( SCIPreleaseVar(scip, &(conshdlrdata->vars[v])) ); 1524 } 1525 1526 if( conshdlrdata->hashmap != NULL) 1527 { 1528 /* free hashmap of active variables to pistions */ 1529 SCIPhashmapFree(&(conshdlrdata->hashmap)); 1530 } 1531 1532 /* free active variables */ 1533 SCIPfreeBlockMemoryArrayNull(scip, &(conshdlrdata->vars), conshdlrdata->nvars); 1534 conshdlrdata->nvars = 0; 1535 1536 if( conshdlrdata->allvars != NULL ) 1537 { 1538 /* release and unlock all variables */ 1539 for( v = 0; v < conshdlrdata->nallvars; ++v ) 1540 { 1541 if( strncmp(SCIPvarGetName(conshdlrdata->allvars[v]), "t_andresultant_", strlen("t_andresultant_")) != 0 ) 1542 { 1543 /* remove the previously added variable locks */ 1544 SCIP_CALL( SCIPaddVarLocksType(scip, conshdlrdata->allvars[v], SCIP_LOCKTYPE_MODEL, -1, -1) ); 1545 } 1546 1547 SCIP_CALL( SCIPreleaseVar(scip, &conshdlrdata->allvars[v]) ); 1548 } 1549 1550 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->allvars, conshdlrdata->nallvars); 1551 conshdlrdata->nallvars = 0; 1552 } 1553 1554 if( conshdlrdata->nsolutions > 0 ) 1555 { 1556 for( s = conshdlrdata->nsolutions - 1; s >= 0 ; --s ) 1557 { 1558 SCIPsparseSolFree(&(conshdlrdata->solutions[s])); 1559 } 1560 1561 SCIPfreeMemoryArrayNull(scip, &conshdlrdata->solutions); 1562 conshdlrdata->nsolutions = 0; 1563 conshdlrdata->ssolutions = 0; 1564 1565 assert( conshdlrdata->solutions == NULL ); 1566 } 1567 conshdlrdata->continuous = FALSE; 1568 1569 assert( conshdlrdata->solutions == NULL ); 1570 assert( conshdlrdata->nsolutions == 0 ); 1571 assert( conshdlrdata->ssolutions == 0 ); 1572 1573 return SCIP_OKAY; 1574 } 1575 1576 1577 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) 1578 * 1579 * This method is called when the presolving was finished and the branch and bound process is about to begin. 1580 * The constraint handler may use this call to initialize its branch and bound specific data. 1581 */ 1582 static 1583 SCIP_DECL_CONSINITSOL(consInitsolCountsols) 1584 { /*lint --e{715}*/ 1585 SCIP_CONSHDLRDATA* conshdlrdata; 1586 1587 assert( conshdlr != NULL ); 1588 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1589 1590 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1591 assert(conshdlrdata != NULL ); 1592 1593 if( conshdlrdata->active ) 1594 { 1595 SCIP_VAR** vars; 1596 int v; 1597 1598 assert(conshdlrdata->nsolutions == 0); 1599 assert(conshdlrdata->solutions == NULL); 1600 1601 conshdlrdata->nvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip); 1602 vars = SCIPgetVars(scip); 1603 1604 /* exclude upgrade continuous original variables */ 1605 for( v = conshdlrdata->nvars - 1; v >= 0; --v ) 1606 { 1607 SCIP_VAR* origvar; 1608 SCIP_Real scalar = 1.0; 1609 SCIP_Real constant = 0.0; 1610 1611 origvar = vars[v]; 1612 1613 /* get original variable to decide if we will count the domain; continuous variables aren't counted */ 1614 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 1615 1616 if( origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS ) 1617 break; 1618 } 1619 conshdlrdata->nvars = v + 1; 1620 1621 /* @todo we need to forbid variable downgrading, from integer type to implicit integer type, e.g. done in 1622 * cons_linear 1623 */ 1624 #ifndef NDEBUG 1625 for( v = conshdlrdata->nvars - 1; v >= 0; --v ) 1626 { 1627 SCIP_VAR* origvar; 1628 SCIP_Real scalar = 1.0; 1629 SCIP_Real constant = 0.0; 1630 1631 origvar = vars[v]; 1632 1633 /* get original variable to decide if we will count the domain; continuous variables aren't counted */ 1634 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 1635 1636 assert(origvar != NULL && SCIPvarGetType(origvar) != SCIP_VARTYPE_CONTINUOUS); 1637 } 1638 #endif 1639 1640 /* copy array of active variables */ 1641 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(conshdlrdata->vars), vars, conshdlrdata->nvars) ); 1642 1643 /* store mapping from all active variables to their position afetr presolving because during solving new variables 1644 * might be added and therefore could destroy writing collected solutions 1645 */ 1646 SCIP_CALL( SCIPhashmapCreate(&(conshdlrdata->hashmap), SCIPblkmem(scip), conshdlrdata->nvars + 1) ); 1647 1648 /* add variables to hashmap */ 1649 for( v = conshdlrdata->nvars - 1; v >= 0; --v ) 1650 { 1651 assert(SCIPvarGetProbindex(conshdlrdata->vars[v]) == v); 1652 SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->hashmap, conshdlrdata->vars[v], v+1) ); 1653 SCIP_CALL( SCIPcaptureVar(scip, conshdlrdata->vars[v]) ); 1654 } 1655 1656 /* check if the problem is binary (ignoring continuous variables) */ 1657 if( SCIPgetNBinVars(scip) == (SCIPgetNVars(scip) - SCIPgetNContVars(scip)) ) 1658 conshdlrdata->cutoffSolution = addBinaryCons; 1659 else 1660 conshdlrdata->cutoffSolution = addIntegerCons; 1661 } 1662 1663 return SCIP_OKAY; 1664 } 1665 1666 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 1667 static 1668 SCIP_DECL_CONSEXITSOL(consExitsolCountsols) 1669 { /*lint --e{715}*/ 1670 SCIP_CONSHDLRDATA* conshdlrdata; 1671 1672 assert(scip != NULL); 1673 assert(conshdlr != NULL); 1674 assert(nconss == 0); 1675 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1676 1677 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1678 assert(conshdlrdata != NULL ); 1679 1680 if( conshdlrdata->active && restart ) 1681 { 1682 SCIPerrorMessage("When collecting and counting solutions restarts need to be disabled (presolving/maxrestarts = 0).\n"); 1683 SCIPABORT(); 1684 return SCIP_INVALIDCALL; /*lint !e527*/ 1685 } 1686 1687 return SCIP_OKAY; 1688 } 1689 1690 /** constraint enforcing method of constraint handler for LP solutions */ 1691 static 1692 SCIP_DECL_CONSENFOLP(consEnfolpCountsols) 1693 { /*lint --e{715}*/ 1694 SCIP_CONSHDLRDATA* conshdlrdata; 1695 1696 SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOLP(consEnfolpCountsols)\n"); 1697 1698 assert( scip != NULL ); 1699 assert( conshdlr != NULL ); 1700 assert( nconss == 0 ); 1701 1702 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1703 assert( conshdlrdata != NULL ); 1704 1705 if( conshdlrdata->active ) 1706 { 1707 if( !solinfeasible ) 1708 { 1709 SCIP_SOL* sol; 1710 1711 SCIP_CALL( SCIPcreateLPSol(scip, &sol, NULL ) ); 1712 1713 SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) ); 1714 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 1715 } 1716 else 1717 *result = SCIP_INFEASIBLE; 1718 } 1719 else 1720 *result = SCIP_FEASIBLE; 1721 1722 assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF ); 1723 1724 return SCIP_OKAY; 1725 } 1726 1727 /** constraint enforcing method of constraint handler for relaxation solutions */ 1728 static 1729 SCIP_DECL_CONSENFORELAX(consEnforelaxCountsols) 1730 { /*lint --e{715}*/ 1731 SCIP_CONSHDLRDATA* conshdlrdata; 1732 1733 SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFORELAX(consEnfolpCountsols)\n"); 1734 1735 assert( scip != NULL ); 1736 assert( conshdlr != NULL ); 1737 assert( nconss == 0 ); 1738 1739 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1740 assert( conshdlrdata != NULL ); 1741 1742 if( conshdlrdata->active ) 1743 { 1744 if( !solinfeasible ) 1745 { 1746 SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) ); 1747 } 1748 else 1749 *result = SCIP_INFEASIBLE; 1750 } 1751 else 1752 *result = SCIP_FEASIBLE; 1753 1754 assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF ); 1755 1756 return SCIP_OKAY; 1757 } 1758 1759 /** constraint enforcing method of constraint handler for pseudo solutions */ 1760 static 1761 SCIP_DECL_CONSENFOPS(consEnfopsCountsols) 1762 { /*lint --e{715}*/ 1763 SCIP_CONSHDLRDATA* conshdlrdata; 1764 1765 SCIPdebugMsg(scip, "method SCIP_DECL_CONSENFOPS(consEnfopsCountsols)\n"); 1766 1767 assert( scip != NULL ); 1768 assert( conshdlr != NULL ); 1769 assert( nconss == 0 ); 1770 1771 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1772 assert( conshdlrdata != NULL ); 1773 1774 if( conshdlrdata->active ) 1775 { 1776 if( !solinfeasible ) 1777 { 1778 SCIP_SOL* sol; 1779 1780 SCIP_CALL( SCIPcreatePseudoSol(scip, &sol, NULL ) ); 1781 1782 SCIP_CALL( checkSolution(scip, sol, conshdlrdata, result) ); 1783 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 1784 } 1785 else 1786 *result = SCIP_INFEASIBLE; 1787 } 1788 else 1789 *result = SCIP_FEASIBLE; 1790 1791 assert( !conshdlrdata->active || *result == SCIP_INFEASIBLE || *result == SCIP_CUTOFF ); 1792 1793 return SCIP_OKAY; 1794 } 1795 1796 1797 /** feasibility check method of constraint handler for integral solutions */ 1798 static 1799 SCIP_DECL_CONSCHECK(consCheckCountsols) 1800 { /*lint --e{715}*/ 1801 /**@todo solutions which come from scip_check should be ignored since it is not clear who 1802 * generated these solution; later we should analyze this problem */ 1803 SCIP_CONSHDLRDATA* conshdlrdata; 1804 1805 SCIPdebugMsg(scip, "method SCIP_DECL_CONSCHECK(consCheckCountsols)\n"); 1806 1807 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1808 assert( conshdlrdata != NULL ); 1809 1810 if( conshdlrdata->active ) 1811 { 1812 if( !conshdlrdata->warning ) 1813 { 1814 SCIPwarningMessage(scip, "a solution comes in over <SCIP_DECL_CONSCHECK(consCheckCountsols)>; currently these solutions are ignored.\n"); 1815 conshdlrdata->warning = TRUE; 1816 } 1817 1818 *result = SCIP_INFEASIBLE; 1819 } 1820 else 1821 *result = SCIP_FEASIBLE; 1822 1823 return SCIP_OKAY; 1824 } 1825 1826 1827 /** variable rounding lock method of constraint handler */ 1828 static 1829 SCIP_DECL_CONSLOCK(consLockCountsols) 1830 { /*lint --e{715}*/ 1831 return SCIP_OKAY; 1832 } 1833 1834 1835 /* 1836 * Callback methods and local method for dialogs 1837 */ 1838 1839 /** dialog execution method for the count command */ 1840 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCountPresolve) 1841 { /*lint --e{715}*/ 1842 SCIP_Bool active; 1843 int usesymmetry; 1844 1845 SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) ); 1846 1847 if ( usesymmetry != 0 ) 1848 { 1849 int symcomptiming = 2; 1850 1851 /* get timing of symmetry computation */ 1852 if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 ) 1853 { 1854 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) ); 1855 } 1856 else if ( usesymmetry == 2 ) 1857 { 1858 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) ); 1859 } 1860 1861 if ( symcomptiming < SYM_COMPUTETIMING_AFTERPRESOL && 1862 (SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE) ) 1863 { 1864 SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \ 1865 "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n"); 1866 1867 return SCIP_INVALIDCALL; 1868 } 1869 1870 SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n"); 1871 SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n"); 1872 1873 SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) ); 1874 } 1875 1876 SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) ); 1877 SCIPdialogMessage(scip, NULL, "\n"); 1878 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) ); 1879 1880 switch( SCIPgetStage(scip) ) 1881 { 1882 case SCIP_STAGE_INIT: 1883 SCIPdialogMessage(scip, NULL, "no problem exists\n"); 1884 break; 1885 1886 case SCIP_STAGE_PROBLEM: 1887 /* activate constraint handler cons_countsols */ 1888 if( !active ) 1889 { 1890 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) ); 1891 } 1892 /*lint -fallthrough*/ 1893 case SCIP_STAGE_TRANSFORMED: 1894 case SCIP_STAGE_PRESOLVING: 1895 /* presolve problem */ 1896 SCIP_CALL( SCIPpresolve(scip) ); 1897 1898 /* reset cons_countsols activation */ 1899 if( !active ) 1900 { 1901 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) ); 1902 } 1903 break; 1904 1905 case SCIP_STAGE_PRESOLVED: 1906 case SCIP_STAGE_SOLVING: 1907 SCIPdialogMessage(scip, NULL, "problem is already presolved\n"); 1908 break; 1909 1910 case SCIP_STAGE_SOLVED: 1911 SCIPdialogMessage(scip, NULL, "problem is already (pre)solved\n"); 1912 break; 1913 1914 case SCIP_STAGE_TRANSFORMING: 1915 case SCIP_STAGE_INITPRESOLVE: 1916 case SCIP_STAGE_EXITPRESOLVE: 1917 case SCIP_STAGE_INITSOLVE: 1918 case SCIP_STAGE_EXITSOLVE: 1919 case SCIP_STAGE_FREETRANS: 1920 case SCIP_STAGE_FREE: 1921 default: 1922 SCIPerrorMessage("invalid SCIP stage\n"); 1923 return SCIP_INVALIDCALL; 1924 } /*lint --e{616}*/ 1925 1926 SCIPdialogMessage(scip, NULL, "\n"); 1927 *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr); 1928 1929 return SCIP_OKAY; 1930 } 1931 1932 /** dialog execution method for the count command */ 1933 SCIP_DECL_DIALOGEXEC(SCIPdialogExecCount) 1934 { /*lint --e{715}*/ 1935 SCIP_RETCODE retcode; 1936 SCIP_Bool active; 1937 1938 SCIP_Bool valid; 1939 SCIP_Longint nsols; 1940 int displayprimalbound; 1941 int displaygap; 1942 int displaysols; 1943 int displayfeasST; 1944 int nrestarts; 1945 int usesymmetry; 1946 1947 SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) ); 1948 SCIPdialogMessage(scip, NULL, "\n"); 1949 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) ); 1950 SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &nrestarts) ); 1951 1952 if( nrestarts != 0 ) 1953 { 1954 /* need to disable restarts, since collecting solutions won't work, but also the capturing for variables is not 1955 * correctly handled 1956 */ 1957 SCIPwarningMessage(scip, "counting forces parameter <presolving/maxrestarts> to 0.\n"); 1958 if( SCIPisParamFixed(scip, "presolving/maxrestarts") ) 1959 { 1960 SCIP_CALL( SCIPunfixParam(scip, "presolving/maxrestarts") ); 1961 } 1962 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) ); 1963 } 1964 1965 SCIP_CALL( SCIPgetIntParam(scip, "misc/usesymmetry", &usesymmetry) ); 1966 1967 if ( usesymmetry != 0 ) 1968 { 1969 int symcomptiming = 2; 1970 1971 /* get timing of symmetry computation */ 1972 if ( ((unsigned) usesymmetry & SYM_HANDLETYPE_SYMCONS) != 0 ) 1973 { 1974 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/addconsstiming", &symcomptiming) ); 1975 } 1976 else if ( usesymmetry == 2 ) 1977 { 1978 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/ofsymcomptiming", &symcomptiming) ); 1979 } 1980 1981 if ( symcomptiming < SYM_COMPUTETIMING_AFTERPRESOL && 1982 (SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE) ) 1983 { 1984 SCIPerrorMessage("Symmetry handling and solution counting are not compatible. " \ 1985 "You might want to disable symmetry by setting parameter <misc/usesymmetry> to 0.\n"); 1986 1987 return SCIP_INVALIDCALL; 1988 } 1989 1990 SCIPwarningMessage(scip, "Symmetry handling has been deactivated since it is not compatible with counting.\n"); 1991 SCIPwarningMessage(scip, "=> counting forces parameter <misc/usesymmetry> to 0.\n"); 1992 1993 SCIP_CALL( SCIPsetIntParam(scip, "misc/usesymmetry", 0) ); 1994 } 1995 1996 switch( SCIPgetStage(scip) ) 1997 { 1998 case SCIP_STAGE_INIT: 1999 SCIPdialogMessage(scip, NULL, "no problem exists\n"); 2000 break; 2001 2002 case SCIP_STAGE_PROBLEM: 2003 /* activate constraint handler cons_countsols */ 2004 if( !active ) 2005 { 2006 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) ); 2007 } 2008 /*lint -fallthrough*/ 2009 case SCIP_STAGE_TRANSFORMED: 2010 case SCIP_STAGE_PRESOLVING: 2011 /* presolve problem */ 2012 SCIP_CALL( SCIPpresolve(scip) ); 2013 /*lint -fallthrough*/ 2014 case SCIP_STAGE_PRESOLVED: 2015 /* reset activity status of constraint handler cons_countsols */ 2016 if( !active ) 2017 { 2018 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) ); 2019 } 2020 /*lint -fallthrough*/ 2021 case SCIP_STAGE_SOLVING: 2022 /* check if the problem contains continuous variables */ 2023 if( SCIPgetNContVars(scip) != 0 ) 2024 { 2025 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 2026 "Problem contains continuous variables (after presolving). Counting projection to integral variables!\n"); 2027 } 2028 2029 /* turn off primal bound and gap column */ 2030 SCIP_CALL( SCIPgetIntParam(scip, "display/primalbound/active", &displayprimalbound) ); 2031 if( displayprimalbound != 0 ) 2032 { 2033 SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", 0) ); 2034 } 2035 SCIP_CALL( SCIPgetIntParam(scip, "display/gap/active", &displaygap) ); 2036 if( displaygap != 0 ) 2037 { 2038 SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", 0) ); 2039 } 2040 2041 /* turn on sols and feasST column */ 2042 SCIP_CALL( SCIPgetIntParam(scip, "display/sols/active", &displaysols) ); 2043 if( displayprimalbound != 2 ) 2044 { 2045 SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", 2) ); 2046 } 2047 SCIP_CALL( SCIPgetIntParam(scip, "display/feasST/active", &displayfeasST) ); 2048 if( displayprimalbound != 2 ) 2049 { 2050 SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", 2) ); 2051 } 2052 2053 /* find the countsols constraint handler */ 2054 assert( SCIPfindConshdlr(scip, CONSHDLR_NAME) != NULL ); 2055 2056 retcode = SCIPcount(scip); 2057 2058 valid = FALSE; 2059 nsols = SCIPgetNCountedSols(scip, &valid); 2060 2061 if( valid ) 2062 SCIPdialogMessage(scip, NULL, "Feasible Solutions : %" SCIP_LONGINT_FORMAT "", nsols); 2063 else 2064 { 2065 char* buffer; 2066 int buffersize = SCIP_MAXSTRLEN; 2067 int requiredsize; 2068 2069 SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) ); 2070 SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize); 2071 2072 if( requiredsize > buffersize ) 2073 { 2074 SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) ); 2075 SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize); 2076 } 2077 2078 assert( buffersize >= requiredsize ); 2079 SCIPdialogMessage(scip, NULL, "Feasible Solutions : %s", buffer); 2080 2081 SCIPfreeBufferArray(scip, &buffer); 2082 } 2083 2084 SCIPdialogMessage(scip, NULL, " (%" SCIP_LONGINT_FORMAT " non-trivial feasible subtrees)\n", SCIPgetNCountedFeasSubtrees(scip)); 2085 2086 *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr); 2087 2088 /* reset display columns */ 2089 if( displayprimalbound != 0 ) 2090 { 2091 SCIP_CALL( SCIPsetIntParam(scip, "display/primalbound/active", displayprimalbound) ); 2092 } 2093 if( displaygap != 0 ) 2094 { 2095 SCIP_CALL( SCIPsetIntParam(scip, "display/gap/active", displaygap) ); 2096 } 2097 2098 /* reset sols and feasST column */ 2099 if( displaysols != 2 ) 2100 { 2101 SCIP_CALL( SCIPsetIntParam(scip, "display/sols/active", displaysols) ); 2102 } 2103 if( displayfeasST != 2 ) 2104 { 2105 SCIP_CALL( SCIPsetIntParam(scip, "display/feasST/active", displayfeasST) ); 2106 } 2107 2108 /* reset cons_countsols activation */ 2109 if( !active ) 2110 { 2111 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) ); 2112 } 2113 2114 /* evaluate retcode */ 2115 SCIP_CALL( retcode ); 2116 break; 2117 2118 case SCIP_STAGE_SOLVED: 2119 SCIPdialogMessage(scip, NULL, "problem is already solved\n"); 2120 break; 2121 2122 case SCIP_STAGE_TRANSFORMING: 2123 case SCIP_STAGE_INITPRESOLVE: 2124 case SCIP_STAGE_EXITPRESOLVE: 2125 case SCIP_STAGE_INITSOLVE: 2126 case SCIP_STAGE_EXITSOLVE: 2127 case SCIP_STAGE_FREETRANS: 2128 case SCIP_STAGE_FREE: 2129 default: 2130 SCIPerrorMessage("invalid SCIP stage\n"); 2131 return SCIP_INVALIDCALL; 2132 } /*lint --e{616}*/ 2133 2134 SCIPdialogMessage(scip, NULL, "\n"); 2135 *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr); 2136 2137 return SCIP_OKAY; 2138 } 2139 2140 /** comparison method for sorting variables by non-decreasing w.r.t. problem index */ 2141 static 2142 SCIP_DECL_SORTPTRCOMP(varCompProbindex) 2143 { 2144 SCIP_VAR* var1; 2145 SCIP_VAR* var2; 2146 2147 var1 = (SCIP_VAR*)elem1; 2148 var2 = (SCIP_VAR*)elem2; 2149 2150 assert(var1 != NULL); 2151 assert(var2 != NULL); 2152 2153 if( SCIPvarGetProbindex(var1) < SCIPvarGetProbindex(var2) ) 2154 return -1; 2155 else if( SCIPvarGetProbindex(var1) > SCIPvarGetProbindex(var2) ) 2156 return +1; 2157 else 2158 { 2159 assert(var1 == var2 || (SCIPvarGetProbindex(var1) == -1 && SCIPvarGetProbindex(var2) == -1)); 2160 return 0; 2161 } 2162 } 2163 2164 /** expands the sparse solutions and writes them to the file */ 2165 static 2166 SCIP_RETCODE writeExpandedSolutions( 2167 SCIP* scip, /**< SCIP data structure */ 2168 FILE* file, /**< file handler */ 2169 SCIP_VAR** allvars, /**< SCIP variables */ 2170 int nallvars, /**< number of all variables */ 2171 SCIP_VAR** activevars, /**< SCIP variables */ 2172 int nactivevars, /**< number of active variables */ 2173 SCIP_HASHMAP* hashmap, /**< hashmap from active solution variable to the position in the active 2174 * variables array 2175 */ 2176 SCIP_SPARSESOL** sols, /**< sparse solutions to expands and write */ 2177 int nsols /**< number of sparse solutions */ 2178 ) 2179 { 2180 SCIP_SPARSESOL* sparsesol; 2181 SCIP_VAR** vars; 2182 SCIP_Real* scalars; 2183 SCIP_Longint* sol; 2184 SCIP_Longint solcnt; 2185 int s; 2186 int v; 2187 2188 assert(scip != NULL); 2189 assert(file != NULL); 2190 assert(hashmap != NULL); 2191 assert(allvars != NULL || nallvars == 0); 2192 assert(activevars != NULL || nactivevars == 0); 2193 assert(sols != NULL || nsols == 0); 2194 2195 solcnt = 0; 2196 2197 /* get memory to store active solution */ 2198 SCIP_CALL( SCIPallocBufferArray(scip, &sol, nactivevars) ); 2199 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nactivevars) ); 2200 SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nactivevars) ); 2201 2202 /* loop over all sparse solutions */ 2203 for( s = 0; s < nsols; ++s ) 2204 { 2205 sparsesol = sols[s]; /*lint !e613*/ 2206 assert(sparsesol != NULL); 2207 assert(SCIPsparseSolGetNVars(sparsesol) == nactivevars); 2208 2209 /* get first solution of the sparse solution */ 2210 SCIPsparseSolGetFirstSol(sparsesol, sol, nactivevars); 2211 2212 do 2213 { 2214 SCIP_Real objval; 2215 2216 solcnt++; 2217 2218 /* print solution number */ 2219 SCIPinfoMessage(scip, file, "%d(%" SCIP_LONGINT_FORMAT "), ", s+1, solcnt); 2220 2221 objval = 0.0; 2222 2223 /* write none active variables */ 2224 for( v = 0; v < nallvars; ++v ) 2225 { 2226 SCIP_Real constant; 2227 SCIP_Real realvalue; 2228 int requiredsize; 2229 int nvars; 2230 int idx; 2231 int i; 2232 2233 vars[0] = allvars[v]; /*lint !e613*/ 2234 scalars[0] = 1.0; 2235 nvars = 1; 2236 constant = 0.0; 2237 2238 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, &nvars, nallvars, &constant, &requiredsize, TRUE) ); 2239 assert(requiredsize <= nallvars); 2240 assert(nvars <= nactivevars); 2241 2242 realvalue = constant; 2243 2244 for( i = 0; i < nvars; ++i ) 2245 { 2246 assert(SCIPhashmapExists(hashmap, vars[i])); 2247 idx = SCIPhashmapGetImageInt(hashmap, vars[i]) - 1; 2248 assert(0 <= idx && idx < nactivevars); 2249 assert(activevars[idx] == vars[i]); /*lint !e613*/ 2250 2251 objval += SCIPvarGetObj(vars[i]) * sol[idx]; 2252 realvalue += scalars[i] * sol[idx]; 2253 } 2254 assert(SCIPisIntegral(scip, realvalue)); 2255 2256 SCIPinfoMessage(scip, file, "%g, ", realvalue); 2257 } 2258 2259 /* transform objective value into original problem space */ 2260 objval = SCIPretransformObj(scip, objval); 2261 2262 /* output the objective value of the solution */ 2263 SCIPinfoMessage(scip, file, "%g\n", objval); 2264 } 2265 while( SCIPsparseSolGetNextSol(sparsesol, sol, nactivevars) ); 2266 } 2267 2268 /* free buffer arrays */ 2269 SCIPfreeBufferArray(scip, &scalars); 2270 SCIPfreeBufferArray(scip, &vars); 2271 SCIPfreeBufferArray(scip, &sol); 2272 2273 return SCIP_OKAY; 2274 } 2275 2276 /** execution method of dialog for writing all solutions */ 2277 SCIP_DECL_DIALOGEXEC(SCIPdialogExecWriteAllsolutions) 2278 { /*lint --e{715}*/ 2279 FILE* file; 2280 SCIP_Longint nsols; 2281 char* filename; 2282 char* word; 2283 SCIP_Bool endoffile; 2284 SCIP_Bool valid; 2285 2286 assert( scip != NULL ); 2287 2288 SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) ); 2289 2290 switch( SCIPgetStage(scip) ) 2291 { 2292 case SCIP_STAGE_INIT: 2293 SCIPdialogMessage(scip, NULL, "no problem available\n"); 2294 break; 2295 case SCIP_STAGE_PROBLEM: 2296 case SCIP_STAGE_TRANSFORMING: 2297 case SCIP_STAGE_FREETRANS: 2298 SCIPdialogMessage(scip, NULL, "the counting process was not started yet\n"); 2299 break; 2300 case SCIP_STAGE_TRANSFORMED: 2301 case SCIP_STAGE_INITPRESOLVE: 2302 case SCIP_STAGE_PRESOLVING: 2303 case SCIP_STAGE_EXITPRESOLVE: 2304 case SCIP_STAGE_PRESOLVED: 2305 case SCIP_STAGE_INITSOLVE: 2306 case SCIP_STAGE_SOLVING: 2307 case SCIP_STAGE_SOLVED: 2308 case SCIP_STAGE_EXITSOLVE: 2309 { 2310 SCIP_CONSHDLR* conshdlr; 2311 SCIP_CONSHDLRDATA* conshdlrdata; 2312 int nsparsesols; 2313 2314 valid = FALSE; 2315 nsols = SCIPgetNCountedSols(scip, &valid); 2316 2317 /* find the countsols constraint handler */ 2318 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2319 assert( conshdlr != NULL ); 2320 2321 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2322 assert( conshdlrdata != NULL ); 2323 2324 nsparsesols = conshdlrdata->nsolutions; 2325 2326 if( !valid ) 2327 { 2328 /* too many solutions, output not "possible" */ 2329 char* buffer; 2330 int buffersize; 2331 int requiredsize; 2332 2333 buffersize = SCIP_MAXSTRLEN; 2334 2335 SCIP_CALL( SCIPallocBufferArray(scip, &buffer, buffersize) ); 2336 SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize); 2337 2338 if( requiredsize > buffersize ) 2339 { 2340 buffersize = requiredsize; 2341 SCIP_CALL( SCIPreallocBufferArray(scip, &buffer, requiredsize) ); 2342 SCIPgetNCountedSolsstr(scip, &buffer, buffersize, &requiredsize); 2343 } 2344 2345 assert( buffersize >= requiredsize ); 2346 SCIPdialogMessage(scip, NULL, "no output, because of too many feasible solutions : %s\n", buffer); 2347 2348 SCIPfreeBufferArray(scip, &buffer); 2349 } 2350 else if( nsols == 0 ) 2351 { 2352 SCIPdialogMessage(scip, NULL, "there are no counted solutions\n"); 2353 } 2354 else if( nsparsesols == 0 ) 2355 { 2356 SCIPdialogMessage(scip, NULL, "there is no solution collect (set parameter <constraints/countsols/collect> to TRUE)\n"); 2357 } 2358 else 2359 { 2360 SCIP_CALL( SCIPdialoghdlrGetWord(dialoghdlr, dialog, "enter filename: ", &word, &endoffile) ); 2361 2362 /* copy the filename for later use */ 2363 SCIP_CALL( SCIPduplicateBufferArray(scip, &filename, word, (int)strlen(word)+1) ); 2364 2365 if( endoffile ) 2366 { 2367 *nextdialog = NULL; 2368 return SCIP_OKAY; 2369 } 2370 2371 SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, filename, TRUE) ); 2372 2373 if( filename[0] != '\0' ) 2374 { 2375 file = fopen(filename, "w"); 2376 2377 if( file == NULL ) 2378 { 2379 SCIPdialogMessage(scip, NULL, "error creating file <%s>\n", filename); 2380 SCIPdialoghdlrClearBuffer(dialoghdlr); 2381 } 2382 else 2383 { 2384 SCIP_SPARSESOL** sparsesols; 2385 SCIP_VAR** origvars; 2386 SCIP_VAR** allvars; 2387 int norigvars; 2388 int nvars; 2389 int v; 2390 2391 SCIP_RETCODE retcode; 2392 2393 /* get sparse solutions defined over the active variables */ 2394 nvars = conshdlrdata->nvars; 2395 sparsesols = conshdlrdata->solutions; 2396 2397 /* get original problem variables */ 2398 retcode = SCIPallocBufferArray(scip, &origvars, SCIPgetNOrigVars(scip)); 2399 if( retcode != SCIP_OKAY ) 2400 { 2401 fclose(file); 2402 SCIP_CALL( retcode ); 2403 } 2404 2405 norigvars = 0; 2406 2407 for( v = 0; v < SCIPgetNOrigVars(scip); ++v ) 2408 { 2409 if( SCIPvarGetType(SCIPgetOrigVars(scip)[v]) != SCIP_VARTYPE_CONTINUOUS ) 2410 { 2411 origvars[norigvars] = SCIPgetOrigVars(scip)[v]; 2412 norigvars++; 2413 } 2414 } 2415 assert(norigvars == conshdlrdata->nallvars); 2416 2417 retcode = SCIPduplicateBufferArray(scip, &allvars, conshdlrdata->allvars, norigvars); 2418 if( retcode != SCIP_OKAY ) 2419 { 2420 fclose(file); /*lint !e449*/ 2421 SCIP_CALL( retcode ); 2422 } 2423 2424 /* sort original variables array and the corresponding transformed variables w.r.t. the problem index */ 2425 SCIPsortDownPtrPtr((void**)allvars, (void**)origvars, varCompProbindex, norigvars); 2426 2427 SCIPdialogMessage(scip, NULL, "saving %" SCIP_LONGINT_FORMAT " (%d) feasible solutions\n", nsols, nsparsesols); 2428 2429 /* first row: output the names of the variables in the given ordering */ 2430 SCIPinfoMessage(scip, file, "#, "); 2431 2432 for( v = 0; v < norigvars; ++v ) 2433 { 2434 #ifndef NDEBUG 2435 { 2436 /* check if the original variable fits to the transformed variable the constraint handler has stored */ 2437 SCIP_VAR* transvar; 2438 SCIP_CALL( SCIPgetTransformedVar(scip, origvars[v], &transvar) ); 2439 assert(transvar != NULL); 2440 assert(transvar == allvars[v]); 2441 } 2442 #endif 2443 SCIPinfoMessage(scip, file, "%s, ", SCIPvarGetName(origvars[v])); 2444 } 2445 2446 SCIPinfoMessage(scip, file, "objval\n"); 2447 2448 /* expand and write solution */ 2449 retcode = writeExpandedSolutions(scip, file, allvars, conshdlrdata->nallvars, conshdlrdata->vars, nvars, conshdlrdata->hashmap, sparsesols, nsparsesols); 2450 if( retcode != SCIP_OKAY ) 2451 { 2452 fclose(file); 2453 SCIP_CALL( retcode ); 2454 } 2455 SCIPdialogMessage(scip, NULL, "written solutions information to file <%s>\n", filename); 2456 2457 SCIPfreeBufferArray(scip, &allvars); 2458 SCIPfreeBufferArray(scip, &origvars); 2459 2460 fclose(file); 2461 } 2462 2463 /* free buffer array */ 2464 SCIPfreeBufferArray(scip, &filename); 2465 } 2466 } 2467 break; 2468 } 2469 case SCIP_STAGE_FREE: 2470 SCIPerrorMessage("invalid call during SCIP_STAGE_FREE\n"); 2471 return SCIP_ERROR; 2472 } 2473 2474 *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr); 2475 2476 return SCIP_OKAY; 2477 } 2478 2479 /** create the interactive shell dialogs for the counting process */ 2480 static 2481 SCIP_RETCODE createCountDialog( 2482 SCIP* scip /**< SCIP data structure */ 2483 ) 2484 { 2485 SCIP_DIALOG* root; 2486 SCIP_DIALOG* dialog; 2487 SCIP_DIALOG* submenu; 2488 2489 root = SCIPgetRootDialog(scip); 2490 2491 /* skip dialogs if they seem to be disabled */ 2492 if( root == NULL ) 2493 return SCIP_OKAY; 2494 2495 /* add dialog entry for counting */ 2496 if( !SCIPdialogHasEntry(root, "count") ) 2497 { 2498 SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCount, NULL, NULL, 2499 "count", "count number of feasible solutions", FALSE, NULL) ); 2500 SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) ); 2501 SCIP_CALL( SCIPreleaseDialog(scip, &dialog) ); 2502 } 2503 2504 /* add dialog entry for counting */ 2505 if( !SCIPdialogHasEntry(root, "countpresolve") ) 2506 { 2507 SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecCountPresolve, NULL, NULL, 2508 "countpresolve", "presolve instance before counting number of feasible solutions", FALSE, NULL) ); 2509 SCIP_CALL( SCIPaddDialogEntry(scip, root, dialog) ); 2510 SCIP_CALL( SCIPreleaseDialog(scip, &dialog) ); 2511 } 2512 2513 /* search for the "write" sub menu to add "allsolutions" dialog */ 2514 if( SCIPdialogFindEntry(root, "write", &submenu) != 1 ) 2515 { 2516 SCIPerrorMessage("write sub menu not found\n"); 2517 return SCIP_PLUGINNOTFOUND; 2518 } 2519 assert(submenu != NULL); 2520 2521 /* add dialog "allsolutions" to sub menu "write" */ 2522 if( !SCIPdialogHasEntry(submenu, "allsolutions") ) 2523 { 2524 SCIP_CALL( SCIPincludeDialog(scip, &dialog, NULL, SCIPdialogExecWriteAllsolutions, NULL, NULL, 2525 "allsolutions", "write all counted primal solutions to file", FALSE, NULL) ); 2526 SCIP_CALL( SCIPaddDialogEntry(scip, submenu, dialog) ); 2527 SCIP_CALL( SCIPreleaseDialog(scip, &dialog) ); 2528 } 2529 2530 return SCIP_OKAY; 2531 } 2532 2533 /* 2534 * Callback methods for columns 2535 */ 2536 2537 /** output method of display column to output file stream 'file' */ 2538 static 2539 SCIP_DECL_DISPOUTPUT(dispOutputSols) 2540 { /*lint --e{715}*/ 2541 #ifndef NDEBUG 2542 SCIP_CONSHDLR* conshdlr; 2543 #endif 2544 SCIP_Longint sols; 2545 SCIP_Bool valid; 2546 2547 assert(disp != NULL); 2548 assert(strcmp(SCIPdispGetName(disp), DISP_SOLS_NAME) == 0); 2549 assert(scip != NULL); 2550 2551 #ifndef NDEBUG 2552 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2553 assert( conshdlr != NULL ); 2554 assert( SCIPconshdlrGetNConss(conshdlr) == 0 ); 2555 #endif 2556 2557 sols = SCIPgetNCountedSols(scip, &valid); 2558 2559 if( !valid ) 2560 { 2561 SCIPinfoMessage(scip, file, "TooMany"); 2562 } 2563 else 2564 { 2565 SCIPdispLongint(SCIPgetMessagehdlr(scip), file, sols, DISP_SOLS_WIDTH); 2566 } 2567 2568 return SCIP_OKAY; 2569 } 2570 2571 2572 /** output method of display column to output file stream 'file' */ 2573 static 2574 SCIP_DECL_DISPOUTPUT(dispOutputFeasSubtrees) 2575 { /*lint --e{715}*/ 2576 #ifndef NDEBUG 2577 SCIP_CONSHDLR* conshdlr; 2578 #endif 2579 2580 assert(disp != NULL); 2581 assert(scip != NULL); 2582 assert(strcmp(SCIPdispGetName(disp), DISP_CUTS_NAME) == 0); 2583 2584 #ifndef NDEBUG 2585 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2586 assert( conshdlr != NULL ); 2587 assert( SCIPconshdlrGetNConss(conshdlr) == 0 ); 2588 #endif 2589 2590 SCIPdispLongint(SCIPgetMessagehdlr(scip), file, SCIPgetNCountedFeasSubtrees(scip), DISP_CUTS_WIDTH); 2591 2592 return SCIP_OKAY; 2593 } 2594 2595 2596 /* 2597 * Interface methods of constraint handler 2598 */ 2599 2600 /** creates the handler for countsols constraints and includes it in SCIP */ 2601 static 2602 SCIP_RETCODE includeConshdlrCountsols( 2603 SCIP* scip, /**< SCIP data structure */ 2604 SCIP_Bool dialogs /**< sould count dialogs be added */ 2605 ) 2606 { 2607 /* create countsol constraint handler data */ 2608 SCIP_CONSHDLRDATA* conshdlrdata; 2609 SCIP_CONSHDLR* conshdlr; 2610 2611 #ifdef SCIP_WITH_GMP 2612 char gmpversion[20]; 2613 #endif 2614 2615 /* create constraint handler specific data here */ 2616 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata) ); 2617 2618 /* include constraint handler */ 2619 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 2620 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 2621 consEnfolpCountsols, consEnfopsCountsols, consCheckCountsols, consLockCountsols, 2622 conshdlrdata) ); 2623 2624 assert(conshdlr != NULL); 2625 2626 /* set non-fundamental callbacks via specific setter functions */ 2627 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCountsols, consCopyCountsols) ); 2628 SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitCountsols) ); 2629 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCountsols) ); 2630 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCountsols) ); 2631 SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitCountsols) ); 2632 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolCountsols) ); 2633 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCountsols) ); 2634 2635 /* add countsols constraint handler parameters */ 2636 SCIP_CALL( SCIPaddBoolParam(scip, 2637 "constraints/" CONSHDLR_NAME "/active", 2638 "is the constraint handler active?", 2639 &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL)); 2640 SCIP_CALL( SCIPaddBoolParam(scip, 2641 "constraints/" CONSHDLR_NAME "/sparsetest", 2642 "should the sparse solution test be turned on?", 2643 &conshdlrdata->sparsetest, FALSE, DEFAULT_SPARSETEST, NULL, NULL)); 2644 SCIP_CALL( SCIPaddBoolParam(scip, 2645 "constraints/" CONSHDLR_NAME "/discardsols", 2646 "is it allowed to discard solutions?", 2647 &conshdlrdata->discardsols, FALSE, DEFAULT_DISCARDSOLS, NULL, NULL)); 2648 SCIP_CALL( SCIPaddBoolParam(scip, 2649 "constraints/" CONSHDLR_NAME "/collect", 2650 "should the solutions be collected?", 2651 &conshdlrdata->collect, FALSE, DEFAULT_COLLECT, NULL, NULL)); 2652 SCIP_CALL( SCIPaddLongintParam(scip, 2653 "constraints/" CONSHDLR_NAME "/sollimit", 2654 "counting stops, if the given number of solutions were found (-1: no limit)", 2655 &conshdlrdata->sollimit, FALSE, DEFAULT_SOLLIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL)); 2656 2657 /* create the interactive shell dialogs for the counting process */ 2658 if( dialogs ) 2659 { 2660 SCIP_CALL( createCountDialog(scip) ); 2661 } 2662 2663 /* include display column */ 2664 SCIP_CALL( SCIPincludeDisp(scip, DISP_SOLS_NAME, DISP_SOLS_DESC, DISP_SOLS_HEADER, SCIP_DISPSTATUS_OFF, 2665 NULL, NULL, NULL, NULL, NULL, NULL, dispOutputSols, 2666 NULL, DISP_SOLS_WIDTH, DISP_SOLS_PRIORITY, DISP_SOLS_POSITION, DISP_SOLS_STRIPLINE) ); 2667 SCIP_CALL( SCIPincludeDisp(scip, DISP_CUTS_NAME, DISP_CUTS_DESC, DISP_CUTS_HEADER, SCIP_DISPSTATUS_OFF, 2668 NULL, NULL, NULL, NULL, NULL, NULL, dispOutputFeasSubtrees, 2669 NULL, DISP_CUTS_WIDTH, DISP_CUTS_PRIORITY, DISP_CUTS_POSITION, DISP_CUTS_STRIPLINE) ); 2670 2671 #ifdef SCIP_WITH_GMP 2672 #ifdef mpir_version 2673 /* add info about using MPIR to external codes information */ 2674 (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "MPIR %s", mpir_version); 2675 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "Multiple Precision Integers and Rationals Library developed by W. Hart (mpir.org)") ); 2676 #else 2677 /* add info about using GMP to external codes information */ 2678 (void) SCIPsnprintf(gmpversion, (int) sizeof(gmpversion), "GMP %s", gmp_version); 2679 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, gmpversion, "GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)") ); 2680 #endif 2681 #endif 2682 2683 return SCIP_OKAY; 2684 } 2685 2686 /** creates the handler for countsols constraints and includes it in SCIP */ 2687 SCIP_RETCODE SCIPincludeConshdlrCountsols( 2688 SCIP* scip /**< SCIP data structure */ 2689 ) 2690 { 2691 /* include constraint handler including the count dialog */ 2692 SCIP_CALL( includeConshdlrCountsols(scip, TRUE) ); 2693 2694 return SCIP_OKAY; 2695 } 2696 2697 2698 /** execute counting */ 2699 SCIP_RETCODE SCIPcount( 2700 SCIP* scip /**< SCIP data structure */ 2701 ) 2702 { 2703 SCIP_Bool active; 2704 2705 /* activate constraint handler cons_countsols */ 2706 SCIP_CALL( SCIPgetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", &active) ); 2707 if( !active ) 2708 { 2709 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", TRUE) ); 2710 } 2711 2712 /* check if the parameter setting allows a valid counting process */ 2713 SCIP_CALL( checkParameters(scip) ); 2714 2715 /* start the solving process */ 2716 SCIP_CALL( SCIPsolve(scip) ); 2717 2718 /* reset activity status of constraint handler cons_countsols */ 2719 if( !active ) 2720 { 2721 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/" CONSHDLR_NAME "/active", FALSE) ); 2722 } 2723 2724 return SCIP_OKAY; 2725 } 2726 2727 2728 /** returns number of feasible solutions found as SCIP_Longint; if the number does not fit into 2729 * a SCIP_Longint the valid flag is set to FALSE 2730 */ 2731 SCIP_Longint SCIPgetNCountedSols( 2732 SCIP* scip, /**< SCIP data structure */ 2733 SCIP_Bool* valid /**< pointer to store if the return value is valid */ 2734 ) 2735 { 2736 SCIP_CONSHDLR* conshdlr; 2737 SCIP_CONSHDLRDATA* conshdlrdata; 2738 2739 /* find the countsols constraint handler */ 2740 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2741 assert( conshdlr != NULL ); 2742 2743 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2744 assert( conshdlrdata != NULL ); 2745 2746 return getNCountedSols(conshdlrdata->nsols, valid); 2747 } 2748 2749 2750 /** puts the number of counted solutions in the given char* buffer */ 2751 void SCIPgetNCountedSolsstr( 2752 SCIP* scip, /**< SCIP data structure */ 2753 char** buffer, /**< buffer to store the number for counted solutions */ 2754 int buffersize, /**< buffer size */ 2755 int* requiredsize /**< pointer to store the required size */ 2756 ) 2757 { 2758 SCIP_CONSHDLR* conshdlr; 2759 SCIP_CONSHDLRDATA* conshdlrdata; 2760 2761 /* find the countsols constraint handler */ 2762 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2763 assert( conshdlr != NULL ); 2764 2765 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2766 assert( conshdlrdata != NULL ); 2767 2768 #ifdef SCIP_WITH_GMP 2769 /* size must be by two larger than the length of the string, since there need to be storage for a sign and a 2770 * null-termination 2771 */ 2772 assert(0 <= (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2)); 2773 *requiredsize = (int) (mpz_sizeinbase( conshdlrdata->nsols, 10 ) + 2); 2774 if( *requiredsize <= buffersize) 2775 toString(conshdlrdata->nsols, buffer, buffersize); 2776 #else 2777 if( conshdlrdata->nsols < pow(10.0, (double)buffersize) ) 2778 { 2779 toString(conshdlrdata->nsols, buffer, buffersize); 2780 *requiredsize = (int)strlen(*buffer); 2781 } 2782 else 2783 *requiredsize = 21; 2784 #endif 2785 } 2786 2787 2788 /** returns number of counted non trivial feasible subtrees */ 2789 SCIP_Longint SCIPgetNCountedFeasSubtrees( 2790 SCIP* scip /**< SCIP data structure */ 2791 ) 2792 { 2793 SCIP_CONSHDLR* conshdlr; 2794 SCIP_CONSHDLRDATA* conshdlrdata; 2795 2796 assert( scip != NULL ); 2797 2798 /* find the countsols constraint handler */ 2799 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2800 assert( conshdlr != NULL ); 2801 2802 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2803 assert( conshdlrdata != NULL ); 2804 2805 return conshdlrdata->feasST; 2806 } 2807 2808 2809 /** Method to get the sparse solution. 2810 * 2811 * @note You get the pointer to the sparse solutions stored in the constraint handler (not a copy). 2812 * 2813 * @note The sparse solutions are stored w.r.t. the active variables. There are the variables which have not been removed 2814 * during presolving. For none active variables the value has to be computed depending on their aggregation 2815 * type. See for more details about that \ref COLLECTALLFEASEBLES. 2816 */ 2817 void SCIPgetCountedSparseSols( 2818 SCIP* scip, /**< SCIP data structure */ 2819 SCIP_VAR*** vars, /**< pointer to active variable array defining to variable order */ 2820 int* nvars, /**< number of active variables */ 2821 SCIP_SPARSESOL*** sols, /**< pointer to the solutions */ 2822 int* nsols /**< pointer to number of solutions */ 2823 ) 2824 { 2825 SCIP_CONSHDLR* conshdlr; 2826 SCIP_CONSHDLRDATA* conshdlrdata; 2827 2828 assert( scip != NULL ); 2829 2830 /* find the countsols constraint handler */ 2831 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2832 assert( conshdlr != NULL ); 2833 2834 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2835 assert( conshdlrdata != NULL ); 2836 2837 *vars = conshdlrdata->vars; 2838 *nvars = conshdlrdata->nvars; 2839 *sols = conshdlrdata->solutions; 2840 *nsols = conshdlrdata->nsolutions; 2841 } 2842 2843 /** setting SCIP parameters for such that a valid counting process is possible */ 2844 SCIP_RETCODE SCIPsetParamsCountsols( 2845 SCIP* scip /**< SCIP data structure */ 2846 ) 2847 { 2848 SCIP_CALL( SCIPsetEmphasis(scip, SCIP_PARAMEMPHASIS_COUNTER, TRUE) ); 2849 return SCIP_OKAY; 2850 } 2851