Changeset 996 for branches


Ignore:
Timestamp:
Jul 1, 2008 2:38:20 PM (11 years ago)
Author:
ladanyi
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r995 r996  
    983983    return false;
    984984  }
    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.0e-6) {
    991       // wants to go down
    992       return (parent_is_down_child);
    993     } else if (djValue < -1.0e-6) {
    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...
    997996    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_ + 1e-8) {
    1006998      double djValue = lpres.getReducedCost[GP_brvar_fullid]*direction;
    1007999      if (djValue > 1.0e-6) {
     
    10221014        }
    10231015      }
    1024       return false;
    1025     }
     1016    }
     1017    return false;
    10261018  }
    10271019
     
    14141406  // solve LP
    14151407  model.initialSolve();
     1408  model.setLogLevel(0);
    14161409
    14171410  if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) {
     
    15891582        }
    15901583
    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 = (cutoff-node.objectiveValue_)*direction + 1.0e-4;
     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();
    16241601          }
    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
    16341612#if defined(DEBUG_DYNAMIC_BRANCHING)
    16351613          if (dyn_debug >= 1) {
     
    16371615          }
    16381616#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...
    16491648#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);
    16591679          }
    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            }
    16641694          }
    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()));
    16781695#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        }
    16971697        if ((numberNodes%10)==0)
    16981698          printf("%d nodes, tree size %d\n",
Note: See TracChangeset for help on using the changeset viewer.