Changeset 1100 for trunk/Cbc/src/CbcHeuristicLocal.cpp
 Timestamp:
 Nov 6, 2008 4:48:31 PM (11 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Cbc/src/CbcHeuristicLocal.cpp
r961 r1100 593 593 memset(used_,0,numberColumns); 594 594 } 595 595 // Default Constructor 596 CbcHeuristicNaive::CbcHeuristicNaive() 597 :CbcHeuristic() 598 { 599 large_=1.0e6; 600 } 601 602 // Constructor with model  assumed before cuts 603 604 CbcHeuristicNaive::CbcHeuristicNaive(CbcModel & model) 605 :CbcHeuristic(model) 606 { 607 large_=1.0e6; 608 } 609 610 // Destructor 611 CbcHeuristicNaive::~CbcHeuristicNaive () 612 { 613 } 614 615 // Clone 616 CbcHeuristic * 617 CbcHeuristicNaive::clone() const 618 { 619 return new CbcHeuristicNaive(*this); 620 } 621 // Create C++ lines to get to current state 622 void 623 CbcHeuristicNaive::generateCpp( FILE * fp) 624 { 625 CbcHeuristicNaive other; 626 fprintf(fp,"0#include \"CbcHeuristicNaive.hpp\"\n"); 627 fprintf(fp,"3 CbcHeuristicNaive naive(*cbcModel);\n"); 628 CbcHeuristic::generateCpp(fp,"naive"); 629 if (large_!=other.large_) 630 fprintf(fp,"3 naive.setLarge(%g);\n",large_); 631 else 632 fprintf(fp,"4 naive.setLarge(%g);\n",large_); 633 fprintf(fp,"3 cbcModel>addHeuristic(&naive);\n"); 634 } 635 636 // Copy constructor 637 CbcHeuristicNaive::CbcHeuristicNaive(const CbcHeuristicNaive & rhs) 638 : 639 CbcHeuristic(rhs), 640 large_(rhs.large_) 641 { 642 } 643 644 // Assignment operator 645 CbcHeuristicNaive & 646 CbcHeuristicNaive::operator=( const CbcHeuristicNaive& rhs) 647 { 648 if (this!=&rhs) { 649 CbcHeuristic::operator=(rhs); 650 large_ = rhs.large_; 651 } 652 return *this; 653 } 654 655 // Resets stuff if model changes 656 void 657 CbcHeuristicNaive::resetModel(CbcModel * model) 658 { 659 CbcHeuristic::resetModel(model); 660 } 661 int 662 CbcHeuristicNaive::solution(double & solutionValue, 663 double * betterSolution) 664 { 665 numCouldRun_++; 666 // See if to do 667 bool atRoot = model_>getNodeCount()==0; 668 int passNumber = model_>getCurrentPassNumber(); 669 if (!when()(when()==1&&model_>phase()!=1)!atRootpassNumber!=1) 670 return 0; // switched off 671 // Don't do if it was this heuristic which found solution! 672 if (this==model_>lastHeuristic()) 673 return 0; 674 numRuns_++; 675 double cutoff; 676 model_>solver()>getDblParam(OsiDualObjectiveLimit,cutoff); 677 double direction = model_>solver()>getObjSense(); 678 cutoff *= direction; 679 cutoff = CoinMin(cutoff,solutionValue); 680 OsiSolverInterface * solver = model_>continuousSolver(); 681 if (!solver) 682 solver = model_>solver(); 683 const double * colLower = solver>getColLower(); 684 const double * colUpper = solver>getColUpper(); 685 const double * objective = solver>getObjCoefficients(); 686 687 int numberColumns = model_>getNumCols(); 688 int numberIntegers = model_>numberIntegers(); 689 const int * integerVariable = model_>integerVariable(); 596 690 691 int i; 692 bool solutionFound=false; 693 CoinWarmStartBasis saveBasis; 694 CoinWarmStartBasis * basis = 695 dynamic_cast<CoinWarmStartBasis *>(solver>getWarmStart()) ; 696 if (basis) { 697 saveBasis = * basis; 698 delete basis; 699 } 700 // First just fix all integers as close to zero as possible 701 OsiSolverInterface * newSolver = solver>clone(); 702 for (i=0;i<numberIntegers;i++) { 703 int iColumn=integerVariable[i]; 704 double lower = colLower[iColumn]; 705 double upper = colUpper[iColumn]; 706 double value; 707 if (lower>0.0) 708 value=lower; 709 else if (upper<0.0) 710 value=upper; 711 else 712 value=0.0; 713 newSolver>setColLower(iColumn,value); 714 newSolver>setColUpper(iColumn,value); 715 } 716 newSolver>initialSolve(); 717 if (newSolver>isProvenOptimal()) { 718 double solValue = newSolver>getObjValue()*direction ; 719 if (solValue<cutoff) { 720 // we have a solution 721 solutionFound=true; 722 solutionValue=solValue; 723 memcpy(betterSolution,newSolver>getColSolution(), 724 numberColumns*sizeof(double)); 725 printf("Naive fixing close to zero gave solution of %g\n",solutionValue); 726 cutoff = solValue  model_>getCutoffIncrement(); 727 } 728 } 729 // Now fix all integers as close to zero if zero or large cost 730 int nFix=0; 731 for (i=0;i<numberIntegers;i++) { 732 int iColumn=integerVariable[i]; 733 double lower = colLower[iColumn]; 734 double upper = colUpper[iColumn]; 735 double value; 736 if (fabs(objective[i])>0.0&&fabs(objective[i])<large_) { 737 nFix++; 738 if (lower>0.0) 739 value=lower; 740 else if (upper<0.0) 741 value=upper; 742 else 743 value=0.0; 744 newSolver>setColLower(iColumn,value); 745 newSolver>setColUpper(iColumn,value); 746 } 747 } 748 const double * solution = solver>getColSolution(); 749 if (nFix) { 750 newSolver>setWarmStart(&saveBasis); 751 newSolver>setColSolution(solution); 752 newSolver>initialSolve(); 753 if (newSolver>isProvenOptimal()) { 754 double solValue = newSolver>getObjValue()*direction ; 755 if (solValue<cutoff) { 756 // try branch and bound 757 double * newSolution = new double [numberColumns]; 758 printf("%d fixed after fixing costs\n",nFix); 759 int returnCode = smallBranchAndBound(newSolver, 760 numberNodes_,newSolution, 761 solutionValue, 762 solutionValue,"CbcHeuristicNaive1"); 763 if (returnCode<0) 764 returnCode=0; // returned on size 765 if ((returnCode&2)!=0) { 766 // could add cut 767 returnCode &= ~2; 768 } 769 if (returnCode==1) { 770 // solution 771 solutionFound=true; 772 memcpy(betterSolution,newSolution, 773 numberColumns*sizeof(double)); 774 printf("Naive fixing zeros gave solution of %g\n",solutionValue); 775 cutoff = solutionValue  model_>getCutoffIncrement(); 776 } 777 delete [] newSolution; 778 } 779 } 780 } 781 #if 1 782 newSolver>setObjSense(direction); // maximize 783 newSolver>setWarmStart(&saveBasis); 784 newSolver>setColSolution(solution); 785 for (int iColumn=0;iColumn<numberColumns;iColumn++) { 786 double value = solution[iColumn]; 787 double lower = colLower[iColumn]; 788 double upper = colUpper[iColumn]; 789 double newLower; 790 double newUpper; 791 if (newSolver>isInteger(iColumn)) { 792 newLower = CoinMax(lower,floor(value)2.0); 793 newUpper = CoinMin(upper,ceil(value)+2.0); 794 } else { 795 newLower = CoinMax(lower,value1.0e5); 796 newUpper = CoinMin(upper,value+1.0e5); 797 } 798 newSolver>setColLower(iColumn,newLower); 799 newSolver>setColUpper(iColumn,newUpper); 800 } 801 newSolver>initialSolve(); 802 if (newSolver>isProvenOptimal()) { 803 double solValue = newSolver>getObjValue()*direction ; 804 if (solValue<cutoff) { 805 nFix=0; 806 newSolver>setObjSense(direction); // correct direction 807 const double * thisSolution = newSolver>getColSolution(); 808 for (int iColumn=0;iColumn<numberColumns;iColumn++) { 809 double value = solution[iColumn]; 810 double lower = colLower[iColumn]; 811 double upper = colUpper[iColumn]; 812 double newLower=lower; 813 double newUpper=upper; 814 if (newSolver>isInteger(iColumn)) { 815 if (value<lower+1.0e6) { 816 nFix++; 817 newUpper=lower; 818 } else if (value>upper1.0e6) { 819 nFix++; 820 newLower=upper; 821 } else { 822 newLower = CoinMax(lower,floor(value)2.0); 823 newUpper = CoinMin(upper,ceil(value)+2.0); 824 } 825 } 826 newSolver>setColLower(iColumn,newLower); 827 newSolver>setColUpper(iColumn,newUpper); 828 } 829 // try branch and bound 830 double * newSolution = new double [numberColumns]; 831 printf("%d fixed after maximizing\n",nFix); 832 int returnCode = smallBranchAndBound(newSolver, 833 numberNodes_,newSolution, 834 solutionValue, 835 solutionValue,"CbcHeuristicNaive1"); 836 if (returnCode<0) 837 returnCode=0; // returned on size 838 if ((returnCode&2)!=0) { 839 // could add cut 840 returnCode &= ~2; 841 } 842 if (returnCode==1) { 843 // solution 844 solutionFound=true; 845 memcpy(betterSolution,newSolution, 846 numberColumns*sizeof(double)); 847 printf("Naive maximizing gave solution of %g\n",solutionValue); 848 cutoff = solutionValue  model_>getCutoffIncrement(); 849 } 850 delete [] newSolution; 851 } 852 } 853 #endif 854 delete newSolver; 855 return solutionFound ? 1 : 0; 856 } 857 // update model 858 void CbcHeuristicNaive::setModel(CbcModel * model) 859 { 860 model_ = model; 861 } 862 863
Note: See TracChangeset
for help on using the changeset viewer.