Ignore:
Timestamp:
Jan 16, 2013 1:41:25 PM (7 years ago)
Author:
forrest
Message:

multiple root solvers, stronger strong branching and cutoff as constraint

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcNode.cpp

    r1802 r1839  
    1010
    1111#include "CbcConfig.h"
    12 
     12//#define DEBUG_SOLUTION
     13#ifdef DEBUG_SOLUTION
     14#define COIN_DETAIL
     15#endif
    1316#include <string>
    1417//#define CBC_DEBUG 1
     
    14411444            }
    14421445            delete ws;
    1443             int numberNodes = model->getNodeCount();
     1446            //int numberNodes = model->getNodeCount();
    14441447            // update number of strong iterations etc
    14451448            model->incrementStrongInfo(numberStrongDone, numberStrongIterations,
     
    14731476                //if (smallestNumberInfeasibilities>=numberIntegerInfeasibilities)
    14741477                //numberNodes=1000000; // switch off search for better solution
    1475                 numberNodes = 1000000; // switch off anyway
     1478                int numberNodes = 1000000; // switch off anyway
    14761479                averageCostPerIteration /= totalNumberIterations;
    14771480                // all feasible - choose best bet
     
    19341937    int numberStrongInfeasible = 0;
    19351938    int numberStrongIterations = 0;
     1939    int strongType=0;
     1940#define DO_ALL_AT_ROOT
     1941#ifdef DO_ALL_AT_ROOT
     1942    int saveSatisfiedVariables=0;
     1943    int saveNumberToDo=0;
     1944#endif
    19361945    // so we can save lots of stuff
    19371946    CbcStrongInfo choice;
     
    19431952    choice.possibleBranch = choiceObject;
    19441953    numberPassesLeft = CoinMax(numberPassesLeft, 2);
     1954    //#define DEBUG_SOLUTION
     1955#ifdef DEBUG_SOLUTION
     1956    bool onOptimalPath=false;
     1957    if ((model->specialOptions()&1) != 0) {
     1958      const OsiRowCutDebugger *debugger = model->continuousSolver()->getRowCutDebugger() ;
     1959      if (debugger) {
     1960        const OsiRowCutDebugger *debugger2 = model->solver()->getRowCutDebugger() ;
     1961        printf("On optimal in CbcNode %s\n",debugger2 ? "" : "but bad cuts");
     1962        onOptimalPath=true;
     1963      }
     1964    }
     1965#endif
    19451966    while (!finished) {
    19461967        numberPassesLeft--;
     
    24032424        // But adjust depending on ratio of iterations
    24042425        if (searchStrategy > 0) {
    2405             if (numberBeforeTrust >= 5 && numberBeforeTrust <= 10) {
     2426          if (numberBeforeTrust >= /*5*/ 10 && numberBeforeTrust <= 10) {
    24062427                if (searchStrategy != 2) {
    24072428                    assert (searchStrategy == 1);
     
    24732494                solver->setHintParam(OsiDoInBranchAndCut, true, OsiHintDo, &easy) ;
    24742495            int iDo;
     2496#define RESET_BOUNDS
    24752497#ifdef RANGING
    24762498            bool useRanging = model->allDynamic() && !skipAll;
     
    25102532                        osiclp->setSpecialOptions(save | 256);
    25112533                        solver->markHotStart();
     2534#ifdef RESET_BOUNDS
     2535                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     2536                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     2537#endif
    25122538                        osiclp->setSpecialOptions(save);
    25132539                    } else {
    25142540                        solver->markHotStart();
     2541#ifdef RESET_BOUNDS
     2542                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     2543                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     2544#endif
    25152545                    }
    25162546                    doneHotStart = true;
     
    25682598                            sort[j] = - min1;
    25692599                        }
    2570                         if (CoinMax(downPenalty, upPenalty) > gap) {
     2600                        // seems unreliable
     2601                        if (false&&CoinMax(downPenalty, upPenalty) > gap) {
    25712602                            COIN_DETAIL_PRINT(printf("gap %g object %d has down range %g, up %g\n",
    25722603                                                     gap, i, downPenalty, upPenalty));
     
    26012632                        objectiveValue_ = CoinMax(objectiveValue_,newObjValue);
    26022633                        solver->markHotStart();
     2634#ifdef RESET_BOUNDS
     2635                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     2636                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     2637#endif
    26032638                        problemFeasible = solver->isProvenOptimal();
    26042639                    }
     
    26412676                    if (20*numberInfeasible + 4*numberFixed < numberNodes) {
    26422677                        // Say never do
    2643                         skipAll = -1;
     2678                        if (numberBeforeTrust == 5)
     2679                          skipAll = -1;
    26442680                    }
    26452681                }
     
    27272763            if (skipAll < 0)
    27282764                numberToDo = 1;
     2765            strongType=0;
    27292766#ifdef DO_ALL_AT_ROOT
    2730             if (!numberNodes) {
    2731                 printf("DOX %d test %d unsat %d - nobj %d\n",
    2732                        numberToDo, numberTest, numberUnsatisfied_,
    2733                        numberObjects);
     2767            if (model->strongStrategy()) {
     2768              int iStrategy=model->strongStrategy();
     2769              int kDepth = iStrategy/100;
     2770              if (kDepth)
     2771                iStrategy -= 100*kDepth;
     2772              else
     2773                kDepth=5;
     2774              double objValue = solver->getObjSense()*solver->getObjValue();
     2775              double bestPossible = model->getBestPossibleObjValue();
     2776              bestPossible += 1.0e-7*(1.0+fabs(bestPossible));
     2777              int jStrategy = iStrategy/10;
     2778              if (jStrategy) {
     2779                if ((jStrategy&1)!=0&&!depth_)
     2780                  strongType=2;
     2781                else if ((jStrategy&2)!=0&&depth_<=kDepth)
     2782                  strongType=2;
     2783                else if ((jStrategy&4)!=0&&objValue<bestPossible)
     2784                  strongType=2;
     2785                iStrategy-=10*jStrategy;
     2786              }
     2787              if (!strongType) {
     2788                if ((iStrategy&1)!=0&&!depth_)
     2789                  strongType=1;
     2790                else if ((iStrategy&2)!=0&&depth_<=kDepth)
     2791                  strongType=1;
     2792                else if ((iStrategy&4)!=0&&objValue<bestPossible)
     2793                  strongType=1;
     2794              }
     2795              saveNumberToDo=numberToDo;
     2796              if (strongType==2) {
     2797                // add in satisfied
     2798                const int * integerVariable = model->integerVariable();
     2799                int numberIntegers = model->numberIntegers();
     2800                if (numberIntegers==numberObjects) {
     2801                  numberToDo=0;
     2802                  for (int i=0;i<numberIntegers;i++) {
     2803                    int iColumn=integerVariable[i];
     2804                    if (saveUpper[iColumn]>saveLower[iColumn]) {
     2805                      whichObject [numberToDo++]=i;
     2806                    }
     2807                  }
     2808                  saveSatisfiedVariables=numberToDo-saveNumberToDo;
     2809                } else {
     2810                  strongType=1;
     2811                }
     2812              }
     2813              if (strongType) {
    27342814                numberTest = numberToDo;
    2735             }
     2815                numberStrong=numberToDo;
     2816                skipAll=false;
     2817                searchStrategy=0;
     2818                solver->setIntParam(OsiMaxNumIterationHotStart, 100000);
     2819              }
     2820            }
    27362821#endif
    27372822            for ( iDo = 0; iDo < numberToDo; iDo++) {
     
    27442829                double infeasibility = object->infeasibility(&usefulInfo, preferredWay);
    27452830                // may have become feasible
    2746                 if (!infeasibility)
     2831                if (!infeasibility) {
     2832                  if(strongType!=2||solver->getColLower()[iColumn]==solver->getColUpper()[iColumn])
    27472833                    continue;
     2834                }
    27482835#ifndef NDEBUG
    27492836                if (iColumn < numberColumns) {
     
    27712858                choice.numIntInfeasUp = numberUnsatisfied_;
    27722859                choice.numIntInfeasDown = numberUnsatisfied_;
    2773                 choice.upMovement = upEstimate[iObject];
    2774                 choice.downMovement = downEstimate[iObject];
    2775                 assert (choice.upMovement >= 0.0);
    2776                 assert (choice.downMovement >= 0.0);
     2860                if (strongType!=2) {
     2861                  choice.upMovement = upEstimate[iObject];
     2862                  choice.downMovement = downEstimate[iObject];
     2863                } else {
     2864                  choice.upMovement = 0.1;
     2865                  choice.downMovement = 0.1;
     2866                }
     2867                  assert (choice.upMovement >= 0.0);
     2868                  assert (choice.downMovement >= 0.0);
    27772869                choice.fix = 0; // say not fixed
    27782870                // see if can skip strong branching
     
    27802872                if ((numberTest <= 0 || skipAll)) {
    27812873                    if (iDo > 20) {
    2782 #ifdef DO_ALL_AT_ROOT
    2783                         if (!numberNodes)
    2784                             printf("DOY test %d - iDo %d\n",
    2785                                    numberTest, iDo);
    2786 #endif
    27872874                        if (!choiceObject) {
    27882875                            delete choice.possibleBranch;
     
    27962883                if (skipAll < 0)
    27972884                    canSkip = true;
     2885                if (strongType)
     2886                  canSkip=false;
    27982887                if (!canSkip) {
    27992888                    if (!doneHotStart) {
     
    28012890                        doneHotStart = true;
    28022891                        solver->markHotStart();
     2892#ifdef RESET_BOUNDS
     2893                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     2894                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     2895#endif
    28032896                        if (!solver->isProvenOptimal()) {
    28042897                          skipAll=-2;
     
    28442937                    } else {
    28452938                        iStatus = 1; // infeasible
     2939#ifdef CONFLICT_CUTS
     2940# ifdef COIN_HAS_CLP
     2941                        if (osiclp&&(model->moreSpecialOptions()&4194304)!=0) {
     2942                          const CbcFullNodeInfo * topOfTree =
     2943                            model->topOfTree();
     2944                          if (topOfTree) {
     2945                            OsiRowCut * cut = osiclp->smallModelCut(topOfTree->lower(),
     2946                                                                    topOfTree->upper(),
     2947                                                                    model->numberRowsAtContinuous(),
     2948                                                                    model->whichGenerator());
     2949                            if (cut) {
     2950                              printf("XXXXXX found conflict cut in strong branching\n");
     2951                              //cut->print();
     2952                              if ((model->specialOptions()&1) != 0) {
     2953                                const OsiRowCutDebugger *debugger = model->continuousSolver()->getRowCutDebugger() ;
     2954                                if (debugger) {
     2955                                  if (debugger->invalidCut(*cut)) {
     2956                                    model->continuousSolver()->applyRowCuts(1,cut);
     2957                                    model->continuousSolver()->writeMps("bad");
     2958                                  }
     2959                                  CoinAssert (!debugger->invalidCut(*cut));
     2960                                }
     2961                              }
     2962                              model->makeGlobalCut(cut) ;
     2963                            }
     2964                          }
     2965                        }
     2966#endif
     2967#endif
    28462968                    }
    28472969                    if (iStatus != 2 && solver->getIterationCount() >
     
    29633085                        }
    29643086                        solver->markHotStart();
    2965                     }
    2966 #ifdef DO_ALL_AT_ROOT
    2967                     if (!numberNodes)
     3087#ifdef RESET_BOUNDS
     3088                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     3089                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     3090#endif
     3091                    }
     3092#if 0 //def DO_ALL_AT_ROOT
     3093                    if (strongType)
    29683094                        printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
    29693095                               choice.objectNumber, iStatus, newObjectiveValue, choice.numItersDown,
     
    29913117                    } else {
    29923118                        iStatus = 1; // infeasible
     3119#ifdef CONFLICT_CUTS
     3120# ifdef COIN_HAS_CLP
     3121                        if (osiclp&&(model->moreSpecialOptions()&4194304)!=0) {
     3122                          const CbcFullNodeInfo * topOfTree =
     3123                            model->topOfTree();
     3124                          if (topOfTree) {
     3125                            OsiRowCut * cut = osiclp->smallModelCut(topOfTree->lower(),
     3126                                                                    topOfTree->upper(),
     3127                                                                    model->numberRowsAtContinuous(),
     3128                                                                    model->whichGenerator());
     3129                            if (cut) {
     3130                              printf("XXXXXX found conflict cut in strong branching\n");
     3131                              //cut->print();
     3132                              if ((model->specialOptions()&1) != 0) {
     3133                                const OsiRowCutDebugger *debugger = model->continuousSolver()->getRowCutDebugger() ;
     3134                                if (debugger) {
     3135                                  if (debugger->invalidCut(*cut)) {
     3136                                    model->continuousSolver()->applyRowCuts(1,cut);
     3137                                    model->continuousSolver()->writeMps("bad");
     3138                                  }
     3139                                  CoinAssert (!debugger->invalidCut(*cut));
     3140                                }
     3141                              }
     3142                              model->makeGlobalCut(cut) ;
     3143                            }
     3144                          }
     3145                        }
     3146#endif
     3147#endif
    29933148                    }
    29943149                    if (iStatus != 2 && solver->getIterationCount() >
     
    31183273                        }
    31193274                        solver->markHotStart();
    3120                     }
    3121 
    3122 #ifdef DO_ALL_AT_ROOT
    3123                     if (!numberNodes)
     3275#ifdef RESET_BOUNDS
     3276                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     3277                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     3278#endif
     3279                    }
     3280
     3281#if 0 //def DO_ALL_AT_ROOT
     3282                    if (strongType)
    31243283                        printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
    31253284                               choice.objectNumber, iStatus, newObjectiveValue, choice.numItersUp,
     
    31663325                            << CoinMessageEol;
    31673326                        }
    3168                         int betterWay;
    3169                         {
     3327                        int betterWay=0;
     3328                        // If was feasible (extra strong branching) skip
     3329                        if (infeasibility) {
    31703330                            CbcBranchingObject * branchObj =
    31713331                                dynamic_cast <CbcBranchingObject *>(branch_) ;
     
    32623422                        bool goneInfeasible = (!solver->isProvenOptimal()||solver->isDualObjectiveLimitReached());
    32633423                        solver->markHotStart();
     3424#ifdef RESET_BOUNDS
     3425                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     3426                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     3427#endif
    32643428                        // may be infeasible (if other way stopped on iterations)
    32653429                        if (goneInfeasible) {
     
    33053469                        bool goneInfeasible = (!solver->isProvenOptimal()||solver->isDualObjectiveLimitReached());
    33063470                        solver->markHotStart();
     3471#ifdef RESET_BOUNDS
     3472                        memcpy(saveLower,solver->getColLower(),solver->getNumCols()*sizeof(double));
     3473                        memcpy(saveUpper,solver->getColUpper(),solver->getNumCols()*sizeof(double));
     3474#endif
    33073475                        // may be infeasible (if other way stopped on iterations)
    33083476                        if (goneInfeasible) {
     
    34903658    // Set guessed solution value
    34913659    guessedObjectiveValue_ = objectiveValue_ + estimatedDegradation;
    3492 
     3660#ifdef DO_ALL_AT_ROOT
     3661    if (strongType) {
     3662      char general[200];
     3663      if (strongType==1)
     3664        sprintf(general,"Strong branching on all %d unsatisfied, %d iterations (depth %d)\n",
     3665                saveNumberToDo,numberStrongIterations,depth_);
     3666      else
     3667        sprintf(general,"Strong branching on all %d unfixed variables (%d unsatisfied), %d iterations (depth %d)\n",
     3668                saveNumberToDo+saveSatisfiedVariables,saveNumberToDo,numberStrongIterations,depth_);
     3669      model->messageHandler()->message(CBC_FPUMP2,model->messages())
     3670        << general << CoinMessageEol ;
     3671    }
     3672#endif
     3673#ifdef DEBUG_SOLUTION
     3674    if(onOptimalPath&&anyAction==-2) {
     3675      printf("Gone off optimal path in CbcNode\n");
     3676      assert(!onOptimalPath||anyAction!=-2);
     3677    }
     3678#endif
    34933679    /*
    34943680      Cleanup, then we're finished
Note: See TracChangeset for help on using the changeset viewer.