Changeset 1344 for branches/sandbox/Cbc/src/CbcClique.cpp
 Timestamp:
 Dec 3, 2009 2:36:52 PM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/sandbox/Cbc/src/CbcClique.cpp
r1293 r1344 330 330 return branch; 331 331 } 332 333 // Default Constructor 334 CbcCliqueBranchingObject::CbcCliqueBranchingObject() 335 : CbcBranchingObject() 336 { 337 clique_ = NULL; 338 downMask_[0] = 0; 339 downMask_[1] = 0; 340 upMask_[0] = 0; 341 upMask_[1] = 0; 342 } 343 344 // Useful constructor 345 CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model, 346 const CbcClique * clique, 347 int way , 348 int numberOnDownSide, const int * down, 349 int numberOnUpSide, const int * up) 350 : CbcBranchingObject(model, clique>id(), way, 0.5) 351 { 352 clique_ = clique; 353 downMask_[0] = 0; 354 downMask_[1] = 0; 355 upMask_[0] = 0; 356 upMask_[1] = 0; 357 int i; 358 for (i = 0; i < numberOnDownSide; i++) { 359 int sequence = down[i]; 360 int iWord = sequence >> 5; 361 int iBit = sequence  32 * iWord; 362 unsigned int k = 1 << iBit; 363 downMask_[iWord] = k; 364 } 365 for (i = 0; i < numberOnUpSide; i++) { 366 int sequence = up[i]; 367 int iWord = sequence >> 5; 368 int iBit = sequence  32 * iWord; 369 unsigned int k = 1 << iBit; 370 upMask_[iWord] = k; 371 } 372 } 373 374 // Copy constructor 375 CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) : CbcBranchingObject(rhs) 376 { 377 clique_ = rhs.clique_; 378 downMask_[0] = rhs.downMask_[0]; 379 downMask_[1] = rhs.downMask_[1]; 380 upMask_[0] = rhs.upMask_[0]; 381 upMask_[1] = rhs.upMask_[1]; 382 } 383 384 // Assignment operator 385 CbcCliqueBranchingObject & 386 CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject & rhs) 387 { 388 if (this != &rhs) { 389 CbcBranchingObject::operator=(rhs); 390 clique_ = rhs.clique_; 391 downMask_[0] = rhs.downMask_[0]; 392 downMask_[1] = rhs.downMask_[1]; 393 upMask_[0] = rhs.upMask_[0]; 394 upMask_[1] = rhs.upMask_[1]; 395 } 396 return *this; 397 } 398 CbcBranchingObject * 399 CbcCliqueBranchingObject::clone() const 400 { 401 return (new CbcCliqueBranchingObject(*this)); 402 } 403 404 405 // Destructor 406 CbcCliqueBranchingObject::~CbcCliqueBranchingObject () 407 { 408 } 409 double 410 CbcCliqueBranchingObject::branch() 411 { 412 decrementNumberBranchesLeft(); 413 int iWord; 414 int numberMembers = clique_>numberMembers(); 415 const int * which = clique_>members(); 416 const int * integerVariables = model_>integerVariable(); 417 int numberWords = (numberMembers + 31) >> 5; 418 // *** for way  up means fix all those in down section 419 if (way_ < 0) { 420 #ifdef FULL_PRINT 421 printf("Down Fix "); 422 #endif 423 for (iWord = 0; iWord < numberWords; iWord++) { 424 int i; 425 for (i = 0; i < 32; i++) { 426 unsigned int k = 1 << i; 427 if ((upMask_[iWord]&k) != 0) { 428 int iColumn = which[i+32*iWord]; 429 #ifdef FULL_PRINT 430 printf("%d ", i + 32*iWord); 431 #endif 432 // fix weak way 433 if (clique_>type(i + 32*iWord)) 434 model_>solver()>setColUpper(integerVariables[iColumn], 0.0); 435 else 436 model_>solver()>setColLower(integerVariables[iColumn], 1.0); 437 } 438 } 439 } 440 way_ = 1; // Swap direction 441 } else { 442 #ifdef FULL_PRINT 443 printf("Up Fix "); 444 #endif 445 for (iWord = 0; iWord < numberWords; iWord++) { 446 int i; 447 for (i = 0; i < 32; i++) { 448 unsigned int k = 1 << i; 449 if ((downMask_[iWord]&k) != 0) { 450 int iColumn = which[i+32*iWord]; 451 #ifdef FULL_PRINT 452 printf("%d ", i + 32*iWord); 453 #endif 454 // fix weak way 455 if (clique_>type(i + 32*iWord)) 456 model_>solver()>setColUpper(integerVariables[iColumn], 0.0); 457 else 458 model_>solver()>setColLower(integerVariables[iColumn], 1.0); 459 } 460 } 461 } 462 way_ = 1; // Swap direction 463 } 464 #ifdef FULL_PRINT 465 printf("\n"); 466 #endif 467 return 0.0; 468 } 469 // Print what would happen 470 void 471 CbcCliqueBranchingObject::print() 472 { 473 int iWord; 474 int numberMembers = clique_>numberMembers(); 475 const int * which = clique_>members(); 476 const int * integerVariables = model_>integerVariable(); 477 int numberWords = (numberMembers + 31) >> 5; 478 // *** for way  up means fix all those in down section 479 if (way_ < 0) { 480 printf("Clique  Down Fix "); 481 for (iWord = 0; iWord < numberWords; iWord++) { 482 int i; 483 for (i = 0; i < 32; i++) { 484 unsigned int k = 1 << i; 485 if ((upMask_[iWord]&k) != 0) { 486 int iColumn = which[i+32*iWord]; 487 printf("%d ", integerVariables[iColumn]); 488 } 489 } 490 } 491 } else { 492 printf("Clique  Up Fix "); 493 for (iWord = 0; iWord < numberWords; iWord++) { 494 int i; 495 for (i = 0; i < 32; i++) { 496 unsigned int k = 1 << i; 497 if ((downMask_[iWord]&k) != 0) { 498 int iColumn = which[i+32*iWord]; 499 printf("%d ", integerVariables[iColumn]); 500 } 501 } 502 } 503 } 504 printf("\n"); 505 } 506 507 static inline int 508 CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1) 509 { 510 if (cl0>cliqueType() < cl1>cliqueType()) { 511 return 1; 512 } 513 if (cl0>cliqueType() > cl1>cliqueType()) { 514 return 1; 515 } 516 if (cl0>numberMembers() != cl1>numberMembers()) { 517 return cl0>numberMembers()  cl1>numberMembers(); 518 } 519 if (cl0>numberNonSOSMembers() != cl1>numberNonSOSMembers()) { 520 return cl0>numberNonSOSMembers()  cl1>numberNonSOSMembers(); 521 } 522 return memcmp(cl0>members(), cl1>members(), 523 cl0>numberMembers() * sizeof(int)); 524 } 525 526 /** Compare the original object of \c this with the original object of \c 527 brObj. Assumes that there is an ordering of the original objects. 528 This method should be invoked only if \c this and brObj are of the same 529 type. 530 Return negative/0/positive depending on whether \c this is 531 smaller/same/larger than the argument. 532 */ 533 int 534 CbcCliqueBranchingObject::compareOriginalObject 535 (const CbcBranchingObject* brObj) const 536 { 537 const CbcCliqueBranchingObject* br = 538 dynamic_cast<const CbcCliqueBranchingObject*>(brObj); 539 assert(br); 540 return CbcCompareCliques(clique_, br>clique_); 541 } 542 543 /** Compare the \c this with \c brObj. \c this and \c brObj must be os the 544 same type and must have the same original object, but they may have 545 different feasible regions. 546 Return the appropriate CbcRangeCompare value (first argument being the 547 sub/superset if that's the case). In case of overlap (and if \c 548 replaceIfOverlap is true) replace the current branching object with one 549 whose feasible region is the overlap. 550 */ 551 CbcRangeCompare 552 CbcCliqueBranchingObject::compareBranchingObject 553 (const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/) 554 { 555 const CbcCliqueBranchingObject* br = 556 dynamic_cast<const CbcCliqueBranchingObject*>(brObj); 557 assert(br); 558 unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_; 559 const unsigned int* otherMask = br>way_ < 0 ? br>upMask_ : br>downMask_; 560 const CoinUInt64 cl0 = 561 (static_cast<CoinUInt64>(thisMask[0]) << 32)  thisMask[1]; 562 const CoinUInt64 cl1 = 563 (static_cast<CoinUInt64>(otherMask[0]) << 32)  otherMask[1]; 564 if (cl0 == cl1) { 565 return CbcRangeSame; 566 } 567 const CoinUInt64 cl_intersection = (cl0 & cl1); 568 if (cl_intersection == cl0) { 569 return CbcRangeSuperset; 570 } 571 if (cl_intersection == cl1) { 572 return CbcRangeSubset; 573 } 574 const CoinUInt64 cl_xor = (cl0 ^ cl1); 575 if (cl_intersection == 0 && cl_xor == 0) { 576 return CbcRangeDisjoint; 577 } 578 const CoinUInt64 cl_union = (cl0  cl1); 579 thisMask[0] = static_cast<unsigned int>(cl_union >> 32); 580 thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff); 581 return CbcRangeOverlap; 582 } 583 584 //############################################################################## 585 586 // Default Constructor 587 CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject() 588 : CbcBranchingObject() 589 { 590 clique_ = NULL; 591 downMask_ = NULL; 592 upMask_ = NULL; 593 } 594 595 // Useful constructor 596 CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model, 597 const CbcClique * clique, 598 int way , 599 int numberOnDownSide, const int * down, 600 int numberOnUpSide, const int * up) 601 : CbcBranchingObject(model, clique>id(), way, 0.5) 602 { 603 clique_ = clique; 604 int numberMembers = clique_>numberMembers(); 605 int numberWords = (numberMembers + 31) >> 5; 606 downMask_ = new unsigned int [numberWords]; 607 upMask_ = new unsigned int [numberWords]; 608 memset(downMask_, 0, numberWords*sizeof(unsigned int)); 609 memset(upMask_, 0, numberWords*sizeof(unsigned int)); 610 int i; 611 for (i = 0; i < numberOnDownSide; i++) { 612 int sequence = down[i]; 613 int iWord = sequence >> 5; 614 int iBit = sequence  32 * iWord; 615 unsigned int k = 1 << iBit; 616 downMask_[iWord] = k; 617 } 618 for (i = 0; i < numberOnUpSide; i++) { 619 int sequence = up[i]; 620 int iWord = sequence >> 5; 621 int iBit = sequence  32 * iWord; 622 unsigned int k = 1 << iBit; 623 upMask_[iWord] = k; 624 } 625 } 626 627 // Copy constructor 628 CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) : CbcBranchingObject(rhs) 629 { 630 clique_ = rhs.clique_; 631 if (rhs.downMask_) { 632 int numberMembers = clique_>numberMembers(); 633 int numberWords = (numberMembers + 31) >> 5; 634 downMask_ = new unsigned int [numberWords]; 635 memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int)); 636 upMask_ = new unsigned int [numberWords]; 637 memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int)); 638 } else { 639 downMask_ = NULL; 640 upMask_ = NULL; 641 } 642 } 643 644 // Assignment operator 645 CbcLongCliqueBranchingObject & 646 CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject & rhs) 647 { 648 if (this != &rhs) { 649 CbcBranchingObject::operator=(rhs); 650 clique_ = rhs.clique_; 651 delete [] downMask_; 652 delete [] upMask_; 653 if (rhs.downMask_) { 654 int numberMembers = clique_>numberMembers(); 655 int numberWords = (numberMembers + 31) >> 5; 656 downMask_ = new unsigned int [numberWords]; 657 memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int)); 658 upMask_ = new unsigned int [numberWords]; 659 memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int)); 660 } else { 661 downMask_ = NULL; 662 upMask_ = NULL; 663 } 664 } 665 return *this; 666 } 667 CbcBranchingObject * 668 CbcLongCliqueBranchingObject::clone() const 669 { 670 return (new CbcLongCliqueBranchingObject(*this)); 671 } 672 673 674 // Destructor 675 CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject () 676 { 677 delete [] downMask_; 678 delete [] upMask_; 679 } 680 double 681 CbcLongCliqueBranchingObject::branch() 682 { 683 decrementNumberBranchesLeft(); 684 int iWord; 685 int numberMembers = clique_>numberMembers(); 686 const int * which = clique_>members(); 687 const int * integerVariables = model_>integerVariable(); 688 int numberWords = (numberMembers + 31) >> 5; 689 // *** for way  up means fix all those in down section 690 if (way_ < 0) { 691 #ifdef FULL_PRINT 692 printf("Down Fix "); 693 #endif 694 for (iWord = 0; iWord < numberWords; iWord++) { 695 int i; 696 for (i = 0; i < 32; i++) { 697 unsigned int k = 1 << i; 698 if ((upMask_[iWord]&k) != 0) { 699 int iColumn = which[i+32*iWord]; 700 #ifdef FULL_PRINT 701 printf("%d ", i + 32*iWord); 702 #endif 703 // fix weak way 704 if (clique_>type(i + 32*iWord)) 705 model_>solver()>setColUpper(integerVariables[iColumn], 0.0); 706 else 707 model_>solver()>setColLower(integerVariables[iColumn], 1.0); 708 } 709 } 710 } 711 way_ = 1; // Swap direction 712 } else { 713 #ifdef FULL_PRINT 714 printf("Up Fix "); 715 #endif 716 for (iWord = 0; iWord < numberWords; iWord++) { 717 int i; 718 for (i = 0; i < 32; i++) { 719 unsigned int k = 1 << i; 720 if ((downMask_[iWord]&k) != 0) { 721 int iColumn = which[i+32*iWord]; 722 #ifdef FULL_PRINT 723 printf("%d ", i + 32*iWord); 724 #endif 725 // fix weak way 726 if (clique_>type(i + 32*iWord)) 727 model_>solver()>setColUpper(integerVariables[iColumn], 0.0); 728 else 729 model_>solver()>setColLower(integerVariables[iColumn], 1.0); 730 } 731 } 732 } 733 way_ = 1; // Swap direction 734 } 735 #ifdef FULL_PRINT 736 printf("\n"); 737 #endif 738 return 0.0; 739 } 740 void 741 CbcLongCliqueBranchingObject::print() 742 { 743 int iWord; 744 int numberMembers = clique_>numberMembers(); 745 const int * which = clique_>members(); 746 const int * integerVariables = model_>integerVariable(); 747 int numberWords = (numberMembers + 31) >> 5; 748 // *** for way  up means fix all those in down section 749 if (way_ < 0) { 750 printf("Clique  Down Fix "); 751 for (iWord = 0; iWord < numberWords; iWord++) { 752 int i; 753 for (i = 0; i < 32; i++) { 754 unsigned int k = 1 << i; 755 if ((upMask_[iWord]&k) != 0) { 756 int iColumn = which[i+32*iWord]; 757 printf("%d ", integerVariables[iColumn]); 758 } 759 } 760 } 761 } else { 762 printf("Clique  Up Fix "); 763 for (iWord = 0; iWord < numberWords; iWord++) { 764 int i; 765 for (i = 0; i < 32; i++) { 766 unsigned int k = 1 << i; 767 if ((downMask_[iWord]&k) != 0) { 768 int iColumn = which[i+32*iWord]; 769 printf("%d ", integerVariables[iColumn]); 770 } 771 } 772 } 773 } 774 printf("\n"); 775 } 776 777 /** Compare the original object of \c this with the original object of \c 778 brObj. Assumes that there is an ordering of the original objects. 779 This method should be invoked only if \c this and brObj are of the same 780 type. 781 Return negative/0/positive depending on whether \c this is 782 smaller/same/larger than the argument. 783 */ 784 int 785 CbcLongCliqueBranchingObject::compareOriginalObject 786 (const CbcBranchingObject* brObj) const 787 { 788 const CbcLongCliqueBranchingObject* br = 789 dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj); 790 assert(br); 791 return CbcCompareCliques(clique_, br>clique_); 792 } 793 794 /** Compare the \c this with \c brObj. \c this and \c brObj must be os the 795 same type and must have the same original object, but they may have 796 different feasible regions. 797 Return the appropriate CbcRangeCompare value (first argument being the 798 sub/superset if that's the case). In case of overlap (and if \c 799 replaceIfOverlap is true) replace the current branching object with one 800 whose feasible region is the overlap. 801 */ 802 CbcRangeCompare 803 CbcLongCliqueBranchingObject::compareBranchingObject 804 (const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/) 805 { 806 const CbcLongCliqueBranchingObject* br = 807 dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj); 808 assert(br); 809 const int numberMembers = clique_>numberMembers(); 810 const int numberWords = (numberMembers + 31) >> 5; 811 unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_; 812 const unsigned int* otherMask = br>way_ < 0 ? br>upMask_ : br>downMask_; 813 814 if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) { 815 return CbcRangeSame; 816 } 817 bool canBeSuperset = true; 818 bool canBeSubset = true; 819 int i; 820 for (i = numberWords  1; i >= 0 && (canBeSuperset  canBeSubset); i) { 821 const unsigned int both = (thisMask[i] & otherMask[i]); 822 canBeSuperset &= (both == thisMask[i]); 823 canBeSubset &= (both == otherMask[i]); 824 } 825 if (canBeSuperset) { 826 return CbcRangeSuperset; 827 } 828 if (canBeSubset) { 829 return CbcRangeSubset; 830 } 831 832 for (i = numberWords  1; i >= 0; i) { 833 if ((thisMask[i] ^ otherMask[i]) != 0) { 834 break; 835 } 836 } 837 if (i == 1) { // complement 838 return CbcRangeDisjoint; 839 } 840 // must be overlap 841 for (i = numberWords  1; i >= 0; i) { 842 thisMask[i] = otherMask[i]; 843 } 844 return CbcRangeOverlap; 845 }
Note: See TracChangeset
for help on using the changeset viewer.