Changeset 996
 Timestamp:
 Jul 1, 2008 2:38:20 PM (12 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/dynamicbranching/dynamicbranching.cpp
r995 r996 983 983 return false; 984 984 } 985 986 if (lpres.isProvenOptimal && !lpres.isDualObjectiveLimitReached) { 987 // THINK: should we do anything? like: 988 #if 0 989 double djValue = lpres.getReducedCost[GP_brvar_fullid]*direction; 990 if (djValue > 1.0e6) { 991 // wants to go down 992 return (parent_is_down_child); 993 } else if (djValue < 1.0e6) { 994 return (! parent_is_down_child); 995 } 996 #endif 985 986 // At this point the only flags of interest are isProvenOptimal, 987 // isDualObjectiveLimitReached and isProvenPrimalInfeasible. 988 // Note that isDualObjectiveLimitReached can't be true alone (search for 989 // mustResolve). 990 991 if (lpres.isProvenOptimal) { 992 // May or may not be over the dual obj limit. If the obj val of parent is 993 // higher than that of the grandparent then we allow switching. 994 // NOTE: grandparent's obj val can;t be 1e100 since then parent would not 995 // exist... 997 996 return false; 998 } 999 1000 if (lpres.isDualObjectiveLimitReached) { 1001 // Dual feasible, Because of reswolving (search for mustResolve) the 1002 // problem here is either optimal or infeasible. If infeasible then we 1003 // just need to fall out of this, if optimal then we test the reduced 1004 // cost. 1005 if (lpres.isProvenOptimal) { 997 if (lpres.getObjValue > grandparent.objectiveValue_ + 1e8) { 1006 998 double djValue = lpres.getReducedCost[GP_brvar_fullid]*direction; 1007 999 if (djValue > 1.0e6) { … … 1022 1014 } 1023 1015 } 1024 return false;1025 }1016 } 1017 return false; 1026 1018 } 1027 1019 … … 1414 1406 // solve LP 1415 1407 model.initialSolve(); 1408 model.setLogLevel(0); 1416 1409 1417 1410 if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) { … … 1589 1582 } 1590 1583 1591 const bool mustResolve = 1592 model.isDualObjectiveLimitReached() && !model.isProvenOptimal(); 1593 double oldlimit = 0; 1594 1595 if (mustResolve) { 1596 // THINK: Something faster would be better... 1597 model.getDblParam(OsiDualObjectiveLimit, oldlimit); 1598 model.setDblParam(OsiDualObjectiveLimit, 1e100); 1599 model.resolve(); 1600 } 1601 LPresult lpres(model); 1602 if (mustResolve) { 1603 lpres.isDualObjectiveLimitReached = true; 1604 model.setDblParam(OsiDualObjectiveLimit, oldlimit); 1605 } 1606 1607 bool canSwitch = node.canSwitchParentWithGrandparent(which, lpres, 1608 originalLower, 1609 originalUpper, 1610 branchingTree); 1611 int cnt = 0; 1612 1613 #if defined(DEBUG_DYNAMIC_BRANCHING) 1614 if (dyn_debug >= 1) { 1615 branchingTree.checkTree(); 1616 } 1617 #endif 1618 1619 #if defined(DEBUG_DYNAMIC_BRANCHING) 1620 std::string tree0; 1621 if (dyn_debug >= 10) { 1622 if (canSwitch) { 1623 tree0 = getTree(branchingTree); 1584 const double parentGap = (cutoffnode.objectiveValue_)*direction + 1.0e4; 1585 assert (parentGap >= 0); 1586 const bool smallGap = false; // parentGap / fabs(cutoff) < 0.05; 1587 1588 // We are not going to do any switching unless the gap is small 1589 if (smallGap) { 1590 // THINK: If goes over the dual obj limit then clp sets dual obj limit 1591 // reached *AND* poven primal infeas. So we need to run it to 1592 // completition to know whether it's really infeas or just over the 1593 // bound. Something faster would be better... 1594 const bool mustResolve = 1595 model.isDualObjectiveLimitReached() && !model.isProvenOptimal(); 1596 double oldlimit = 0; 1597 if (mustResolve) { 1598 model.getDblParam(OsiDualObjectiveLimit, oldlimit); 1599 model.setDblParam(OsiDualObjectiveLimit, 1e100); 1600 model.resolve(); 1624 1601 } 1625 } 1626 #endif 1627 1628 while (canSwitch) { 1629 branchingTree.moveNodeUp(which, model, node); 1630 canSwitch = node.canSwitchParentWithGrandparent(which, lpres, 1631 originalLower, 1632 originalUpper, 1633 branchingTree); 1602 LPresult lpres(model); 1603 if (mustResolve) { 1604 lpres.isDualObjectiveLimitReached = true; 1605 model.setDblParam(OsiDualObjectiveLimit, oldlimit); 1606 } 1607 bool canSwitch = 1608 node.canSwitchParentWithGrandparent(which, lpres, originalLower, 1609 originalUpper, branchingTree); 1610 int cnt = 0; 1611 1634 1612 #if defined(DEBUG_DYNAMIC_BRANCHING) 1635 1613 if (dyn_debug >= 1) { … … 1637 1615 } 1638 1616 #endif 1639 ++cnt; 1640 } 1641 if (cnt > 0) { 1642 printf("Before switch: opt: %c inf: %c dual_bd: %c\n", 1643 lpres.isProvenOptimal ? 'T' : 'F', 1644 lpres.isProvenPrimalInfeasible ? 'T' : 'F', 1645 lpres.isDualObjectiveLimitReached ? 'T' : 'F'); 1646 model.resolve(); 1647 // This is horribly looking... Get rid of it when properly 1648 // debugged... 1617 1618 #if defined(DEBUG_DYNAMIC_BRANCHING) 1619 std::string tree0; 1620 if (dyn_debug >= 10) { 1621 if (canSwitch) { 1622 tree0 = getTree(branchingTree); 1623 } 1624 } 1625 #endif 1626 1627 while (canSwitch) { 1628 branchingTree.moveNodeUp(which, model, node); 1629 canSwitch = node.canSwitchParentWithGrandparent(which, lpres, 1630 originalLower, 1631 originalUpper, 1632 branchingTree); 1633 #if defined(DEBUG_DYNAMIC_BRANCHING) 1634 if (dyn_debug >= 1) { 1635 branchingTree.checkTree(); 1636 } 1637 #endif 1638 ++cnt; 1639 } 1640 if (cnt > 0) { 1641 printf("Before switch: opt: %c inf: %c dual_bd: %c\n", 1642 lpres.isProvenOptimal ? 'T' : 'F', 1643 lpres.isProvenPrimalInfeasible ? 'T' : 'F', 1644 lpres.isDualObjectiveLimitReached ? 'T' : 'F'); 1645 model.resolve(); 1646 // This is horribly looking... Get rid of it when properly 1647 // debugged... 1649 1648 #if 1 1650 const bool mustResolve = 1651 model.isDualObjectiveLimitReached() && !model.isProvenOptimal(); 1652 double oldlimit = 0; 1653 1654 if (mustResolve) { 1655 // THINK: Something faster would be better... 1656 model.getDblParam(OsiDualObjectiveLimit, oldlimit); 1657 model.setDblParam(OsiDualObjectiveLimit, 1e100); 1658 model.resolve(); 1649 const bool mustResolve = 1650 model.isDualObjectiveLimitReached() && !model.isProvenOptimal(); 1651 double oldlimit = 0; 1652 1653 if (mustResolve) { 1654 // THINK: Something faster would be better... 1655 model.getDblParam(OsiDualObjectiveLimit, oldlimit); 1656 model.setDblParam(OsiDualObjectiveLimit, 1e100); 1657 model.resolve(); 1658 } 1659 LPresult lpres1(model); 1660 if (mustResolve) { 1661 lpres.isDualObjectiveLimitReached = true; 1662 model.setDblParam(OsiDualObjectiveLimit, oldlimit); 1663 } 1664 printf("After resolve: opt: %c inf: %c dual_bd: %c\n", 1665 lpres1.isProvenOptimal ? 'T' : 'F', 1666 lpres1.isProvenPrimalInfeasible ? 'T' : 'F', 1667 lpres1.isDualObjectiveLimitReached ? 'T' : 'F'); 1668 assert(lpres.isAbandoned == model.isAbandoned()); 1669 assert(lpres.isDualObjectiveLimitReached == model.isDualObjectiveLimitReached()); 1670 assert(lpres.isDualObjectiveLimitReached  1671 (lpres.isProvenOptimal == model.isProvenOptimal())); 1672 assert(lpres.isDualObjectiveLimitReached  1673 (lpres.isProvenPrimalInfeasible == model.isProvenPrimalInfeasible())); 1674 assert(!lpres.isProvenOptimal  ! model.isProvenOptimal()  1675 (lpres.isProvenOptimal && model.isProvenOptimal() && 1676 lpres.getObjValue == model.getObjValue())); 1677 #endif 1678 printf("Finished moving node %d up by %i levels.\n", node.node_id_, cnt); 1659 1679 } 1660 LPresult lpres1(model); 1661 if (mustResolve) { 1662 lpres.isDualObjectiveLimitReached = true; 1663 model.setDblParam(OsiDualObjectiveLimit, oldlimit); 1680 1681 #if defined(DEBUG_DYNAMIC_BRANCHING) 1682 if (dyn_debug >= 10) { 1683 if (cnt > 0) { 1684 std::string tree1 = getTree(branchingTree); 1685 printf("=====================================\n"); 1686 printf("It can move node %i up. way_: 0x%x brvar: %i\n", 1687 node.node_id_, node.way_, node.variable_); 1688 printTree(tree0, cnt+10); 1689 printf("=====================================\n"); 1690 printf("Finished moving the node up by %i levels.\n", cnt); 1691 printTree(tree1, cnt+10); 1692 printf("=====================================\n"); 1693 } 1664 1694 } 1665 printf("After resolve: opt: %c inf: %c dual_bd: %c\n",1666 lpres1.isProvenOptimal ? 'T' : 'F',1667 lpres1.isProvenPrimalInfeasible ? 'T' : 'F',1668 lpres1.isDualObjectiveLimitReached ? 'T' : 'F');1669 assert(lpres.isAbandoned == model.isAbandoned());1670 assert(lpres.isDualObjectiveLimitReached == model.isDualObjectiveLimitReached());1671 assert(lpres.isDualObjectiveLimitReached 1672 (lpres.isProvenOptimal == model.isProvenOptimal()));1673 assert(lpres.isDualObjectiveLimitReached 1674 (lpres.isProvenPrimalInfeasible == model.isProvenPrimalInfeasible()));1675 assert(!lpres.isProvenOptimal  ! model.isProvenOptimal() 1676 (lpres.isProvenOptimal && model.isProvenOptimal() &&1677 lpres.getObjValue == model.getObjValue()));1678 1695 #endif 1679 printf("Finished moving node %d up by %i levels.\n", node.node_id_, cnt); 1680 } 1681 1682 #if defined(DEBUG_DYNAMIC_BRANCHING) 1683 if (dyn_debug >= 10) { 1684 if (cnt > 0) { 1685 std::string tree1 = getTree(branchingTree); 1686 printf("=====================================\n"); 1687 printf("It can move node %i up. way_: 0x%x brvar: %i\n", 1688 node.node_id_, node.way_, node.variable_); 1689 printTree(tree0, cnt+10); 1690 printf("=====================================\n"); 1691 printf("Finished moving the node up by %i levels.\n", cnt); 1692 printTree(tree1, cnt+10); 1693 printf("=====================================\n"); 1694 } 1695 } 1696 #endif 1696 } 1697 1697 if ((numberNodes%10)==0) 1698 1698 printf("%d nodes, tree size %d\n",
Note: See TracChangeset
for help on using the changeset viewer.