 Timestamp:
 Jun 10, 2008 5:43:09 PM (11 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/dynamicbranching/dynamicbranching.cpp
r973 r974 1 /********************************************************************** 2 TODO: 3 4 If we swap two nodes (parent and grandparent) then we should check if anything 5 has been explored under GP after the swap, and if not, just get rid of GP and 6 everything below. 7 8 If strong branching fixed anything in the grandparent we may still swap it 9 with the parent (we don't do it yet, see the test on 10 strong_branching_fixed_vars_), but those fixings must be moved to the parent as 11 well. 12 13 Same thing for locally valid cuts, if GP has them and GP is switched with P 14 then locally valid cuts must be treated as generated in P. 15 16 Same for reduced cost fixing :(. If P has done any then P and GP can't be 17 switched. 18 19 Maybe the best solution is to create local information (strong branching, rc 20 fixing, local cuts, etc.) only every so often, say every 10th level. Then that 21 would block switches, but everywhere else we would be safe. Good question 22 what is worth more: the switches or the local info. 23 24 Alternative solution: Do not add local info to the tree, but keep it in a set 25 of excluded clauses ala Todias Achterberg: Conflict Analysis in Mixed Integer 26 Programming. 27 28 We may want to disable fixing by strong branching completely and if such 29 situation occurs then simply do the branch and one side will be fathomed 30 immediately and we can try to switch. 31 32 Bound modifications when nodes are swapped could be avoided if always start 33 from original bounds and go back to root to apply all branching decisions. On 34 the other hand, reduced cost fixing would be lost. And so would fixings by 35 strong branching. Although both could be stored in an array keeping track of 36 changes implied by the branching decisions. 37 38 ********************************************************************** 39 40 41 **********************************************************************/ 1 42 #include "CoinTime.hpp" 2 43 #include "OsiClpSolverInterface.hpp" … … 6 47 #include <vector> 7 48 #include <map> 49 50 class DBVectorNode; 8 51 9 52 // Trivial class for Branch and Bound … … 33 76 // Also chooses branching variable (if none set to 1) 34 77 DBNodeSimple (OsiSolverInterface &model, 35 36 78 int numberIntegers, int * integer, 79 CoinWarmStart * basis); 37 80 void gutsOfConstructor (OsiSolverInterface &model, 38 39 81 int numberIntegers, int * integer, 82 CoinWarmStart * basis); 40 83 // Copy constructor 41 84 DBNodeSimple ( const DBNodeSimple &); … … 54 97 inline void incrementDescendants() 55 98 { descendants_++;} 99 // Tests if we can switch this node (this is the parent) with its parent 100 bool canSwitchParentWithGrandparent(const int* which, 101 OsiSolverInterface & model, 102 const int * original_lower, 103 const int * original_upper, 104 DBVectorNode & branchingTree); 105 56 106 // Public data 107 // The id of the node 108 int node_id_; 57 109 // Basis (should use tree, but not as wasteful as bounds!) 58 110 CoinWarmStart * basis_; … … 75 127 // Right child 76 128 int child_up_; 129 // Whether strong branching fixed variables when we branched on this node 130 bool strong_branching_fixed_vars_; 131 // Whether reduced cost fixing fixed anything in this node 132 bool reduced_cost_fixed_vars_; 77 133 // Previous in chain 78 134 int previous_; … … 87 143 88 144 DBNodeSimple::DBNodeSimple() : 145 node_id_(1), 89 146 basis_(NULL), 90 147 objectiveValue_(COIN_DBL_MAX), … … 97 154 child_down_(1), 98 155 child_up_(1), 156 strong_branching_fixed_vars_(false), 157 reduced_cost_fixed_vars_(false), 99 158 previous_(1), 100 159 next_(1), … … 104 163 } 105 164 DBNodeSimple::DBNodeSimple(OsiSolverInterface & model, 106 int numberIntegers, int * integer,CoinWarmStart * basis)165 int numberIntegers, int * integer,CoinWarmStart * basis) 107 166 { 108 167 gutsOfConstructor(model,numberIntegers,integer,basis); … … 110 169 void 111 170 DBNodeSimple::gutsOfConstructor(OsiSolverInterface & model, 112 int numberIntegers, int * integer,CoinWarmStart * basis) 113 { 171 int numberIntegers, int * integer,CoinWarmStart * basis) 172 { 173 node_id_ = 1; 114 174 basis_ = basis; 115 175 variable_=1; … … 121 181 child_down_ = 1; 122 182 child_up_ = 1; 183 strong_branching_fixed_vars_ = false; 184 reduced_cost_fixed_vars_ = false; 123 185 previous_ = 1; 124 186 next_ = 1; … … 371 433 DBNodeSimple::DBNodeSimple(const DBNodeSimple & rhs) 372 434 { 435 node_id_=rhs.node_id_; 373 436 if (rhs.basis_) 374 437 basis_=rhs.basis_>clone(); … … 384 447 child_down_ = rhs.child_down_; 385 448 child_up_ = rhs.child_up_; 449 strong_branching_fixed_vars_ = rhs.strong_branching_fixed_vars_; 450 reduced_cost_fixed_vars_ = rhs.reduced_cost_fixed_vars_; 386 451 previous_ = rhs.previous_; 387 452 next_ = rhs.next_; … … 402 467 if (this != &rhs) { 403 468 gutsOfDestructor(); 469 node_id_=rhs.node_id_; 404 470 if (rhs.basis_) 405 471 basis_=rhs.basis_>clone(); … … 413 479 child_down_ = rhs.child_down_; 414 480 child_up_ = rhs.child_up_; 481 strong_branching_fixed_vars_ = rhs.strong_branching_fixed_vars_; 482 reduced_cost_fixed_vars_ = rhs.reduced_cost_fixed_vars_; 415 483 previous_ = rhs.previous_; 416 484 next_ = rhs.next_; … … 446 514 bool 447 515 DBNodeSimple::extension(const DBNodeSimple & other, 448 449 516 const double * originalLower, 517 const double * originalUpper) const 450 518 { 451 519 bool ok=true; … … 465 533 #include <vector> 466 534 #define FUNNY_BRANCHING 1 467 #define FUNNY_TREE 468 #ifndef FUNNY_TREE 469 // Vector of DBNodeSimples 470 typedef std::vector<DBNodeSimple> DBVectorNode; 471 #else 535 472 536 // Must code up by hand 473 537 class DBVectorNode { … … 490 554 { return size_sizeDeferred_;} 491 555 // Push 492 void push_back( const DBNodeSimple & node);556 void push_back(DBNodeSimple & node); // the node_id_ of node will change 493 557 // Last one in (or other criterion) 494 558 DBNodeSimple back() const; … … 497 561 // Works out best one 498 562 int best() const; 499 563 // Rearranges the tree 564 void moveNodeUp(const int* which, 565 OsiSolverInterface& model, DBNodeSimple & node); 566 // It changes the bounds of the descendants of node with node_id 567 void changeDescendantBounds(const int node_id, const bool lower_bd, 568 const int brvar, const int new_bd); 569 500 570 // Public data 501 571 // Maximum size … … 573 643 // Push 574 644 void 575 DBVectorNode::push_back( constDBNodeSimple & node)645 DBVectorNode::push_back(DBNodeSimple & node) 576 646 { 577 647 if (size_==maximumSize_) { … … 597 667 int next = nodes_[firstSpare_].next_; 598 668 nodes_[firstSpare_]=node; 669 nodes_[firstSpare_].node_id_ = firstSpare_; 599 670 if (last_>=0) { 600 671 assert (nodes_[last_].next_==1); … … 677 748 size_; 678 749 } 679 #endif 750 751 static double 752 compute_val_for_ray(const OsiSolverInterface& model) 753 { 754 const std::vector<double*> dual_rays = model.getDualRays(1); 755 if (dual_rays.size() == 0) { 756 printf("WARNING: LP is infeas, but no dual ray is returned!\n"); 757 return 0; 758 } 759 const double* dual_ray = dual_rays[0]; 760 const double direction = model.getObjSense(); 761 const double* rub = model.getRowUpper(); 762 const double* rlb = model.getRowLower(); 763 const double* cub = model.getColUpper(); 764 const double* clb = model.getColLower(); 765 const double* dj = model.getReducedCost(); 766 const double* obj = model.getObjCoefficients(); 767 const int numRows = model.getNumRows(); 768 const int numCols = model.getNumCols(); 769 double yb_plus_rl_minus_su = 0; 770 for (int i = 0; i < numRows; ++i) { 771 const double ray_i = dual_ray[i]; 772 if (ray_i > 1e6) { 773 yb_plus_rl_minus_su += ray_i*rlb[i]; 774 } else if (ray_i < 1e6) { 775 yb_plus_rl_minus_su += ray_i*rub[i]; 776 } 777 } 778 for (int j = 0; j < numCols; ++j) { 779 const double yA_j = dj[j]  obj[j]; 780 if (direction * yA_j > 1e6) { 781 yb_plus_rl_minus_su = yA_j*cub[j]; 782 } else if (direction * yA_j < 1e6) { 783 yb_plus_rl_minus_su = yA_j*clb[j]; 784 } 785 } 786 for (int i = dual_rays.size()1; i >= 0; i) { 787 delete[] dual_rays[i]; 788 } 789 return yb_plus_rl_minus_su; 790 } 680 791 681 792 bool 682 DBNodeSimple::isGrandparentIrrelevant() 683 { 793 DBNodeSimple::canSwitchParentWithGrandparent(const int* which, 794 OsiSolverInterface & model, 795 const int * original_lower, 796 const int * original_upper, 797 DBVectorNode & branchingTree) 798 { 799 /* 800 The current node ('this') is really the parent (P) and the solution in the 801 model represents the child. The grandparent (GP) is this.parent_. Let's have 802 variable names respecting the truth. 803 */ 684 804 #if !defined(FUNNY_BRANCHING) 685 805 return false; 686 806 #endif 687 807 688 if (parent_ == 1) { 808 const int parent_id = node_id_; 809 const DBNodeSimple& parent = branchingTree.nodes_[parent_id]; 810 const int grandparent_id = parent.parent_; 811 812 if (grandparent_id == 1) { 689 813 // can't flip root higher up... 690 814 return false; 691 815 } 816 const DBNodeSimple& grandparent = branchingTree.nodes_[grandparent_id]; 692 817 693 818 if (model.isProvenDualInfeasible()) { … … 695 820 return false; 696 821 } 822 823 if (parent.strong_branching_fixed_vars_  parent.reduced_cost_fixed_vars_  824 grandparent.strong_branching_fixed_vars_) { 825 return false; 826 } 827 828 const double direction = model.getObjSense(); 829 830 const int GP_brvar = grandparent.variable_; 831 const int GP_brvar_fullid = which[GP_brvar]; 832 const bool parent_is_down_child = parent_id == grandparent.child_down_; 833 697 834 if (model.isProvenPrimalInfeasible()) { 698 ...; 835 const int greatgrandparent_id = grandparent.parent_; 836 const int x = GP_brvar_fullid; // for easier reference... we'll use s_x 837 838 /* 839 Now we are going to check that if we relax the GP's branching decision 840 then the child's LP relaxation is still infeasible. The test is done by 841 checking whether the column (or its negative) of the GP's branching 842 variable cuts off the dual ray proving the infeasibility. 843 */ 844 845 const double* dj = model.getReducedCost(); 846 const double* obj = model.getObjCoefficients(); 847 const double yA_x = dj[x]  obj[x]; 848 bool canSwitch = true; 849 850 if (direction > 0) { // minimization problem 851 if (parent_is_down_child) { 852 const double s_x = CoinMax(yA_x, 1e8); 853 if (s_x > 1e6) { // if 0 then canSwitch can stay true 854 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 855 if (yb_plus_rl_minus_su < 1e8) { 856 printf("WARNING: yb_plus_rl_minus_su is not positive!\n"); 857 canSwitch = false; 858 } else { 859 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x]; 860 const double u_x_without_GP = greatgrandparent_id >= 0 ? 861 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] : 862 original_upper[GP_brvar]; 863 canSwitch = max_u_x > u_x_without_GP  1e8; 864 } 865 } 866 } else { 867 const double r_x = CoinMax(yA_x, 1e8); 868 if (r_x > 1e6) { // if 0 then canSwitch can stay true 869 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 870 if (yb_plus_rl_minus_su < 1e8) { 871 printf("WARNING: yb_plus_rl_minus_su is not positive!\n"); 872 canSwitch = false; 873 } else { 874 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x]; 875 const double l_x_without_GP = greatgrandparent_id >= 0 ? 876 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] : 877 original_lower[GP_brvar]; 878 canSwitch = min_l_x < l_x_without_GP + 1e8; 879 } 880 } 881 } 882 } else { // maximization problem 883 if (parent_is_down_child) { 884 const double s_x = CoinMin(yA_x, 1e8); 885 if (s_x < 1e6) { // if 0 then canSwitch can stay true 886 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 887 if (yb_plus_rl_minus_su > 1e8) { 888 printf("WARNING: yb_plus_rl_minus_su is not negative!\n"); 889 canSwitch = false; 890 } else { 891 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x]; 892 const double u_x_without_GP = greatgrandparent_id >= 0 ? 893 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] : 894 original_upper[GP_brvar]; 895 canSwitch = max_u_x > u_x_without_GP  1e8; 896 } 897 } 898 } else { 899 const double r_x = CoinMin(yA_x, 1e8); 900 if (r_x > 1e6) { // if 0 then canSwitch can stay true 901 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 902 if (yb_plus_rl_minus_su > 1e8) { 903 printf("WARNING: yb_plus_rl_minus_su is not negative!\n"); 904 canSwitch = false; 905 } else { 906 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x]; 907 const double l_x_without_GP = greatgrandparent_id >= 0 ? 908 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] : 909 original_lower[GP_brvar]; 910 canSwitch = min_l_x < l_x_without_GP + 1e8; 911 } 912 } 913 } 914 } 915 916 return canSwitch; 699 917 } 700 918 // Both primal and dual feasible, and in this case we don't care how we have … … 702 920 // etc.), we can just look at the reduced costs to figure out if the 703 921 // grandparent is irrelevant. Remember, we are using dual simplex! 704 const DBNodeSimple& parent = branchingTree.nodes_[parent_]; 705 const int iColumn = which[parent.variable_]; 706 double djValue = model.getReducedCost()[iColumn]*direction; 707 const bool down_child = branchingTree.nodeIndex(node) == parent.child_down_; 708 if (djValue>1.0e6) { 922 double djValue = model.getReducedCost()[GP_brvar_fullid]*direction; 923 if (djValue > 1.0e6) { 709 924 // wants to go down 710 if ( down_child) {925 if (parent_is_down_child) { 711 926 return true; 712 927 } 713 const double up_lower = std::floor(parent.value_); 714 if (model.getColLower()[iColumn] > up_lower) { 928 if (model.getColLower()[GP_brvar_fullid] > std::ceil(grandparent.value_)) { 715 929 return true; 716 930 } 717 931 return false; 932 } else if (djValue < 1.0e6) { 933 // wants to go up 934 if (! parent_is_down_child) { 935 return true; 936 } 937 if (model.getColUpper()[GP_brvar_fullid] < std::floor(grandparent.value_)) { 938 return true; 939 } 940 return false; 941 } 942 return false; 943 } 944 945 void 946 DBVectorNode::moveNodeUp(const int* which, 947 OsiSolverInterface& model, DBNodeSimple & node) 948 { 949 /* 950 The current node ('this') is really the parent (P) and the solution in the 951 model represents the child. The grandparent (GP) is this.parent_. Let's have 952 variable names respecting the truth. 953 */ 954 const int parent_id = node.node_id_; 955 DBNodeSimple& parent = nodes_[parent_id]; 956 const int grandparent_id = parent.parent_; 957 assert(grandparent_id != 1); 958 DBNodeSimple& grandparent = nodes_[grandparent_id]; 959 const int greatgrandparent_id = grandparent.parent_; 960 961 const bool parent_is_down_child = parent_id == grandparent.child_down_; 962 963 // First hang the nodes where they belong. 964 parent.parent_ = greatgrandparent_id; 965 grandparent.parent_ = parent_id; 966 const bool down_child_stays_with_parent = parent.way_ & DBNodeSimple::DOWN_CURRENT; 967 int& child_to_move = 968 down_child_stays_with_parent ? parent.child_up_ : parent.child_down_; 969 if (parent_is_down_child) { 970 grandparent.child_down_ = child_to_move; 718 971 } else { 719 // wants to go up 720 if (!down_child) { 721 return true; 722 } 723 const double down_upper = std::ceil(parent.value_); 724 if (model.getColUpper()[iColumn] < down_upper) { 725 return true; 726 } 727 return false; 728 } 729 return false; 972 grandparent.child_up_ = child_to_move; 973 } 974 if (child_to_move >= 0) { 975 nodes_[child_to_move].parent_ = grandparent_id; 976 } 977 child_to_move = grandparent_id; 978 if (greatgrandparent_id >= 0) { 979 DBNodeSimple& greatgrandparent = nodes_[greatgrandparent_id]; 980 if (grandparent_id == greatgrandparent.child_down_) { 981 greatgrandparent.child_down_ = parent_id; 982 } else { 983 greatgrandparent.child_up_ = parent_id; 984 } 985 } 986 987 // Now modify bounds 988 989 // First, get rid of GP's bound change of its branching variable in the 990 // bound list of P. Note: If greatgrandparent_id is < 0 then GP is the root 991 // so its bounds are the original bounds. 992 const int GP_brvar = grandparent.variable_; 993 if (parent_is_down_child) { 994 const int old_upper = greatgrandparent_id >= 0 ? 995 nodes_[greatgrandparent_id].upper_[GP_brvar] : 996 grandparent.upper_[GP_brvar]; 997 parent.upper_[GP_brvar] = old_upper; 998 model.setColUpper(which[GP_brvar], old_upper); 999 } else { 1000 const int old_lower = greatgrandparent_id >= 0 ? 1001 nodes_[greatgrandparent_id].lower_[GP_brvar] : 1002 grandparent.lower_[GP_brvar]; 1003 parent.lower_[GP_brvar] = old_lower; 1004 model.setColLower(which[GP_brvar], old_lower); 1005 } 1006 // THINK: this might not be necessary 1007 model.resolve(); 1008 1009 // Now add the branching var bound change of P to GP and all of its 1010 // descendant 1011 const int P_brvar = parent.variable_; 1012 const double P_value = parent.value_; 1013 int new_bd; 1014 if (down_child_stays_with_parent) { 1015 // Former up child of P is now the down child of GP, so we need to change 1016 // bounds of GP, its up child and descendants of that one. 1017 new_bd = (int)std::ceil(P_value); 1018 grandparent.lower_[P_brvar] = new_bd; 1019 changeDescendantBounds(grandparent.child_up_, 1020 true /*lower bd*/, P_brvar, new_bd); 1021 } else { 1022 // Former down child of P is now the up child of GP, so we need to change 1023 // bounds of GP, its down child and descendants of that one. 1024 new_bd = (int)floor(P_value); 1025 grandparent.upper_[P_brvar] = new_bd; 1026 changeDescendantBounds(grandparent.child_down_, 1027 false /*lower bd*/, P_brvar, new_bd); 1028 } 730 1029 } 731 1030 732 1031 void 733 DBVectorNode::moveNodeUp() 734 { 735 assert(parent != 1); 736 const int parent_id = node.parent_; 737 const DBNodeSimple& parent = branchingTree.nodes_[parent_id]; 738 const int node_id = branchingTree.nodeIndex(node); 739 const bool node_is_down_child = node_id == parent.child_down_; 740 const int grandparent_id = parent.parent_; 741 742 // First hang the nodes where they belong. 743 node.parent_ = grandparent_id; 744 parent.parent_ = node_id; 745 #if 1 746 int& child_to_move = (node.way_ & DOWN_CURRENT) ? node.child_up_ : node.child_down_; 747 if (node_is_down_child) { 748 parent.child_down_ = child_to_move; 1032 DBVectorNode::changeDescendantBounds(const int node_id, const bool lower_bd, 1033 const int brvar, const int new_bd) 1034 { 1035 if (node_id == 1) { 1036 return; 1037 } 1038 changeDescendantBounds(nodes_[node_id].child_down_, lower_bd, brvar, new_bd); 1039 changeDescendantBounds(nodes_[node_id].child_up_, lower_bd, brvar, new_bd); 1040 if (lower_bd) { 1041 nodes_[node_id].lower_[brvar] = new_bd; 749 1042 } else { 750 parent.child_up_ = child_to_move; 751 } 752 if (child_to_move >= 0) { 753 branchingTree.nodes_[child_to_move].parent_ = parent_id; 754 } 755 child_to_move = parent_id; 756 #else 757 if (node.way_ & DOWN_CURRENT) { 758 if (node_is_down_child) { 759 parent.child_down_ = node.child_up_; 760 } else { 761 parent.child_up_ = node.child_up_; 762 } 763 if (node.child_up_ >= 0) { 764 branchingTree.nodes_[node.child_up_].parent_ = parent_id; 765 } 766 node.child_up_ = parent_id; 767 } else { // must be UP_CURRENT 768 if (node_is_down_child) { 769 parent.child_down_ = node.child_down_; 770 } else { 771 parent.child_up_ = node.child_down_; 772 } 773 if (node.child_down_ >= 0) { 774 branchingTree.nodes_[node.child_down_].parent_ = parent_id; 775 } 776 node.child_down_ = parent_id; 777 } 778 #endif 779 if (grandparent_id >= 0) { 780 if (parent_id == branchingTree.nodes_[grandparent_id].child_down_) { 781 branchingTree.nodes_[grandparent_id].child_down_ = node_id; 782 } else { 783 branchingTree.nodes_[grandparent_id].child_up_ = node_id; 784 } 785 } 786 787 // Now modify bounds 788 789 // THINK: could be avoided if always start from original bounds and go back 790 // to root to apply all branching decisions. On the other hand, reduced cost 791 // fixing would be lost. And so would fixings by strong branching. Actually, 792 // what we'd ideally need to do is to apply flipping when strong branching 793 // fixes a variable. 794 } 795 796 797 798 799 800 bool moveNodes(OsiSolverInterface & model, 801 DBVectorNode & branchingTree, 802 int kNode) 803 { 804 805 DBNodeSimple & node = branchingTree[kNode]; 806 DBNodeSimple & grandParent = branchingTree[node.parent_]; 807 int grandParentVariable = grandParent.variable_; 808 // check if branching constraint of grandparent is tight 809 bool canMoveNodes = checkGrandparent(); 810 811 if(!canMoveNodes) 812 return false; 813 814 node.parent_ = grandParent.parent_; 815 grandParent.parent_ = kNode; 816 // change bounds of grandParent 817 grandParent.lower_[ 818 819 820 } 1043 nodes_[node_id].upper_[brvar] = new_bd; 1044 } 1045 } 1046 821 1047 822 1048 // Invoke solver's builtin enumeration algorithm … … 881 1107 int numberIterations=0; 882 1108 int numberNodes =0; 883 int nRedundantUp=0;884 int nRedundantDown=0;885 int nRedundantUp2=0;886 int nRedundantDown2=0;887 1109 DBNodeSimple bestNode; 888 1110 ////// Start main while of branch and bound … … 907 1129 bool down_branch = true; 908 1130 switch (node.way_) { 909 case WAY_UNSET:910 case D OWN_UP__BOTH_DONE:911 case UP_DOWN__BOTH_DONE:1131 case DBNodeSimple::WAY_UNSET: 1132 case DBNodeSimple::DOWN_UP__BOTH_DONE: 1133 case DBNodeSimple::UP_DOWN__BOTH_DONE: 912 1134 abort(); 913 case D OWN_UP__NOTHING_DONE:914 node.way_ = D OWN_UP__DOWN_DONE;1135 case DBNodeSimple::DOWN_UP__NOTHING_DONE: 1136 node.way_ = DBNodeSimple::DOWN_UP__DOWN_DONE; 915 1137 break; 916 case D OWN_UP__DOWN_DONE:917 node.way_ = D OWN_UP__BOTH_DONE:1138 case DBNodeSimple::DOWN_UP__DOWN_DONE: 1139 node.way_ = DBNodeSimple::DOWN_UP__BOTH_DONE; 918 1140 down_branch = false; 919 1141 break; 920 case UP_DOWN__NOTHING_DONE:921 node.way_ = UP_DOWN__UP_DONE:1142 case DBNodeSimple::UP_DOWN__NOTHING_DONE: 1143 node.way_ = DBNodeSimple::UP_DOWN__UP_DONE; 922 1144 down_branch = false; 923 1145 break; 924 case UP_DOWN__UP_DONE:925 node.way_ = UP_DOWN__BOTH_DONE;1146 case DBNodeSimple::UP_DOWN__UP_DONE: 1147 node.way_ = DBNodeSimple::UP_DOWN__BOTH_DONE; 926 1148 break; 927 1149 } … … 947 1169 model.getDblParam(OsiDualObjectiveLimit,cutoff); 948 1170 double gap=(cutoffmodel.getObjValue())*direction+1.0e4; 949 // double gap=(cutoffmodelPtr_>objectiveValue())*direction+1.0e4; 1171 // double 1172 // gap=(cutoffmodelPtr_>objectiveValue())*direction+1.0e4; 1173 bool did_reduced_cost_fixing_for_child = false; 950 1174 if (gap<1.0e10&&model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) { 951 1175 const double * dj = model.getReducedCost(); … … 967 1191 } 968 1192 } 969 //if (nFixed0+nFixed1) 970 //printf("%d fixed to lower, %d fixed to upper\n",nFixed0,nFixed1); 971 } 972 if (model.isAbandoned()) { 973 // THINK: What the heck should we do??? 974 abort(); 975 } 976 while (node.isGrandparentIrrelevant()) { 977 branchingTree.moveNodeUp(node); 978 } 979 980 981 982 983 if (!model.isIterationLimitReached()) { 984 if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) { 985 #if FUNNY_BRANCHING 986 // See if branched variable off bounds 987 const double * dj = model.getReducedCost(); 988 const double * lower = model.getColLower(); 989 const double * upper = model.getColUpper(); 990 const double * solution = model.getColSolution(); 991 // Better to use "natural" value  need flag to say fixed 992 for (i=0;i<numberIntegers;i++) { 993 iColumn=which[i]; 994 relaxedLower[i]=originalLower[i]; 995 relaxedUpper[i]=originalUpper[i]; 996 double djValue = dj[iColumn]*direction; 997 if (djValue>1.0e6) { 998 // wants to go down 999 if (lower[iColumn]>originalLower[i]) { 1000 // Lower bound active 1001 relaxedLower[i]=(int) lower[iColumn]; 1002 } 1003 if (upper[iColumn]<originalUpper[i]) { 1004 // Upper bound NOT active 1005 } 1006 } else if (djValue<1.0e6) { 1007 // wants to go up 1008 if (lower[iColumn]>originalLower[i]) { 1009 // Lower bound NOT active 1010 } 1011 if (upper[iColumn]<originalUpper[i]) { 1012 // Upper bound active 1013 relaxedUpper[i]=(int) upper[iColumn]; 1014 } 1193 if (nFixed0+nFixed1) { 1194 // printf("%d fixed to lower, %d fixed to upper\n", 1195 // nFixed0,nFixed1); 1196 did_reduced_cost_fixing_for_child = true; 1197 } 1198 if (model.isAbandoned()) { 1199 // THINK: What the heck should we do??? 1200 abort(); 1201 } 1202 while (node.canSwitchParentWithGrandparent(which, model, 1203 originalLower, 1204 originalUpper, 1205 branchingTree)) { 1206 branchingTree.moveNodeUp(which, model, node); 1207 } 1208 if (!model.isIterationLimitReached()) { 1209 if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) { 1210 if ((numberNodes%1000)==0) 1211 printf("%d nodes, tree size %d\n", 1212 numberNodes,branchingTree.size()); 1213 if (CoinCpuTime()time1>3600.0) { 1214 printf("stopping after 3600 seconds\n"); 1215 exit(77); 1015 1216 } 1016 } 1017 // See if can do anything 1018 { 1019 /* 1020 If kNode is on second branch then 1021 a) If other feasible could free up as well 1022 b) If other infeasible could do something clever. 1023 For now  we have to give up 1024 */ 1025 int jNode=branchingTree.nodes_[kNode].parent_; 1026 bool canDelete = (branchingTree.nodes_[kNode].descendants_<2); 1027 while (jNode>=0) { 1028 DBNodeSimple & node = branchingTree.nodes_[jNode]; 1029 int next = node.parent_; 1030 if (node.descendants_<2) { 1031 int variable = node.variable_; 1032 iColumn=which[variable]; 1033 double value = node.value_; 1034 double djValue = dj[iColumn]*direction; 1035 assert (node.way_==2node.way_==2); 1036 // we don't know which branch it was  look at current bounds 1037 if (upper[iColumn]<value&&node.lower_[variable]<upper[iColumn]) { 1038 // must have been down branch 1039 if (djValue>1.0e3solution[iColumn]<upper[iColumn]1.0e5) { 1040 if (canDelete) { 1041 nRedundantDown++; 1042 #if 1 1043 printf("%d redundant branch down with value %g current upper %g solution %g dj %g\n", 1044 variable,node.value_,upper[iColumn],solution[iColumn],djValue); 1045 #endif 1046 node.descendants_=2; // ignore 1047 branchingTree.sizeDeferred_++; 1048 int newUpper = originalUpper[variable]; 1049 if (next>=0) { 1050 DBNodeSimple & node2 = branchingTree.nodes_[next]; 1051 newUpper = node2.upper_[variable]; 1052 } 1053 if (branchingTree.nodes_[jNode].parent_!=next) 1054 assert (newUpper>upper[iColumn]); 1055 model.setColUpper(iColumn,newUpper); 1056 int kNode2=next; 1057 int jNode2=branchingTree.nodes_[kNode].parent_; 1058 assert (newUpper>branchingTree.nodes_[kNode].upper_[variable]); 1059 branchingTree.nodes_[kNode].upper_[variable]= newUpper; 1060 while (jNode2!=kNode2) { 1061 DBNodeSimple & node2 = branchingTree.nodes_[jNode2]; 1062 int next = node2.parent_; 1063 if (next!=kNode2) 1064 assert (newUpper>node2.upper_[variable]); 1065 node2.upper_[variable]= newUpper; 1066 jNode2=next; 1067 } 1068 } else { 1069 // can't delete but can add other way to jNode 1070 nRedundantDown2++; 1071 DBNodeSimple & node2 = branchingTree.nodes_[kNode]; 1072 assert (node2.way_==2node2.way_==2); 1073 double value2 = node2.value_; 1074 int variable2 = node2.variable_; 1075 int iColumn2 = which[variable2]; 1076 if (variable != variable2) { 1077 if (node2.way_==2&&upper[iColumn2]<value2) { 1078 // must have been down branch which was done  carry over 1079 int newUpper = (int) floor(value2); 1080 assert (newUpper<node.upper_[variable2]); 1081 node.upper_[variable2]=newUpper; 1082 } else if (node2.way_==2&&lower[iColumn2]>value2) { 1083 // must have been up branch which was done  carry over 1084 int newLower = (int) ceil(value2); 1085 assert (newLower>node.lower_[variable2]); 1086 node.lower_[variable2]=newLower; 1087 } 1088 if (node.lower_[variable2]>node.upper_[variable2]) { 1089 // infeasible 1090 node.descendants_=2; // ignore 1091 branchingTree.sizeDeferred_++; 1092 } 1093 } 1094 } 1095 break; 1096 } 1097 // we don't know which branch it was  look at current bounds 1098 } else if (lower[iColumn]>value&&node.upper_[variable]>lower[iColumn]) { 1099 // must have been up branch 1100 if (djValue<1.0e3solution[iColumn]>lower[iColumn]+1.0e5) { 1101 if (canDelete) { 1102 nRedundantUp++; 1103 #if 1 1104 printf("%d redundant branch up with value %g current lower %g solution %g dj %g\n", 1105 variable,node.value_,lower[iColumn],solution[iColumn],djValue); 1106 #endif 1107 node.descendants_=2; // ignore 1108 branchingTree.sizeDeferred_++; 1109 int newLower = originalLower[variable]; 1110 if (next>=0) { 1111 DBNodeSimple & node2 = branchingTree.nodes_[next]; 1112 newLower = node2.lower_[variable]; 1113 } 1114 if (branchingTree.nodes_[jNode].parent_!=next) 1115 assert (newLower<lower[iColumn]); 1116 model.setColLower(iColumn,newLower); 1117 int kNode2=next; 1118 int jNode2=branchingTree.nodes_[kNode].parent_; 1119 assert (newLower<branchingTree.nodes_[kNode].lower_[variable]); 1120 branchingTree.nodes_[kNode].lower_[variable]= newLower; 1121 while (jNode2!=kNode2) { 1122 DBNodeSimple & node2 = branchingTree.nodes_[jNode2]; 1123 int next = node2.parent_; 1124 if (next!=kNode2) 1125 assert (newLower<node2.lower_[variable]); 1126 node2.lower_[variable]=newLower; 1127 jNode2=next; 1128 } 1129 } else { 1130 // can't delete but can add other way to jNode 1131 nRedundantUp2++; 1132 DBNodeSimple & node2 = branchingTree.nodes_[kNode]; 1133 assert (node2.way_==2node2.way_==2); 1134 double value2 = node2.value_; 1135 int variable2 = node2.variable_; 1136 int iColumn2 = which[variable2]; 1137 if (variable != variable2) { 1138 if (node2.way_==2&&upper[iColumn2]<value2) { 1139 // must have been down branch which was done  carry over 1140 int newUpper = (int) floor(value2); 1141 assert (newUpper<node.upper_[variable2]); 1142 node.upper_[variable2]=newUpper; 1143 } else if (node2.way_==2&&lower[iColumn2]>value2) { 1144 // must have been up branch which was done  carry over 1145 int newLower = (int) ceil(value2); 1146 assert (newLower>node.lower_[variable2]); 1147 node.lower_[variable2]=newLower; 1148 } 1149 if (node.lower_[variable2]>node.upper_[variable2]) { 1150 // infeasible 1151 node.descendants_=2; // ignore 1152 branchingTree.sizeDeferred_++; 1153 } 1154 } 1155 } 1156 break; 1157 } 1158 } 1159 } else { 1160 break; 1161 } 1162 jNode=next; 1217 DBNodeSimple newNode(model,numberIntegers,which,ws); 1218 // something extra may have been fixed by strong branching 1219 // if so go round again 1220 while (newNode.variable_==numberIntegers) { 1221 model.resolve(); 1222 newNode = DBNodeSimple(model,numberIntegers,which,model.getWarmStart()); 1223 newNode.strong_branching_fixed_vars_ = true; 1163 1224 } 1164 } 1165 // solve 1166 //resolve(); 1167 //assert(!getIterationCount()); 1168 if ((numberNodes%1000)==0) 1169 printf("%d nodes, redundant down %d (%d) up %d (%d) tree size %d\n", 1170 numberNodes,nRedundantDown,nRedundantDown2,nRedundantUp,nRedundantUp2,branchingTree.size()); 1171 #else 1172 if ((numberNodes%1000)==0) 1173 printf("%d nodes, tree size %d\n", 1174 numberNodes,branchingTree.size()); 1175 #endif 1176 if (CoinCpuTime()time1>3600.0) { 1177 printf("stopping after 3600 seconds\n"); 1178 exit(77); 1179 } 1180 DBNodeSimple newNode(model,numberIntegers,which,ws); 1181 // something extra may have been fixed by strong branching 1182 // if so go round again 1183 while (newNode.variable_==numberIntegers) { 1184 model.resolve(); 1185 newNode = DBNodeSimple(model,numberIntegers,which,model.getWarmStart()); 1186 } 1187 if (newNode.objectiveValue_<1.0e100) { 1188 if (newNode.variable_>=0) 1189 assert (fabs(newNode.value_floor(newNode.value_+0.5))>1.0e6); 1190 newNode.parent_ = kNode; 1191 // push on stack 1192 branchingTree.push_back(newNode); 1193 if(branchingTree.nodes_[kNode].child_down_ < 0) 1194 branchingTree.nodes_[kNode].child_down_ = branchingTree.last_; 1195 else 1196 branchingTree.nodes_[kNode].child_up_ = branchingTree.last_; 1225 newNode.reduced_cost_fixed_vars_ = did_reduced_cost_fixing_for_child; 1226 if (newNode.objectiveValue_<1.0e100) { 1227 if (newNode.variable_>=0) 1228 assert (fabs(newNode.value_floor(newNode.value_+0.5))>1.0e6); 1229 newNode.parent_ = kNode; 1230 // push on stack 1231 branchingTree.push_back(newNode); 1232 if(branchingTree.nodes_[kNode].child_down_ < 0) 1233 branchingTree.nodes_[kNode].child_down_ = branchingTree.last_; 1234 else 1235 branchingTree.nodes_[kNode].child_up_ = branchingTree.last_; 1197 1236 #if 0 1198 1237 } else { … … 1205 1244 <<" found after "<<numberIterations 1206 1245 <<" iterations and "<<numberNodes<<" nodes" 1207 1246 <<std::endl; 1208 1247 } 1209 1248 #endif
Note: See TracChangeset
for help on using the changeset viewer.