Changeset 113


Ignore:
Timestamp:
Nov 11, 2006 9:32:35 PM (13 years ago)
Author:
ladanyi
Message:

cbc and bcp based bonmin works almost the same w/ pure b&b

Location:
branches/devel/Bonmin/experimental/Bcp
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/devel/Bonmin/experimental/Bcp/BM.cpp

    r110 r113  
    3434void BCP_parameter_set<BM_par>::create_keyword_list() {
    3535    // Create the list of keywords for parameter file reading
    36     keys.push_back(make_pair(BCP_string("BranchOnSos"),
    37                              BCP_parameter(BCP_CharPar, BranchOnSos)));
     36    keys.push_back(make_pair(BCP_string("BranchingStrategy"),
     37                             BCP_parameter(BCP_IntPar, BranchingStrategy)));
    3838    keys.push_back(make_pair(BCP_string("PureBranchAndBound"),
    3939                             BCP_parameter(BCP_CharPar, PureBranchAndBound)));
     
    6363template <>
    6464void BCP_parameter_set<BM_par>::set_default_entries() {
    65     set_entry(BranchOnSos, true);
     65    set_entry(BranchingStrategy, BM_OsiChooseStrong);
    6666    set_entry(PureBranchAndBound, false);
    6767    set_entry(PrintBranchingInfo, true);
  • branches/devel/Bonmin/experimental/Bcp/BM.hpp

    r110 r113  
    4646};
    4747
     48enum BM_BranchingStrategy {
     49    BM_OsiChooseVariable,
     50    BM_OsiChooseStrong
     51};
     52
    4853class BM_par {
    4954public:
    5055    enum chr_params {
    5156        //
    52         BranchOnSos,
    5357        CombinedDistanceAndPriority,
    5458        PureBranchAndBound,
     
    6064    enum int_params {
    6165        //
     66        BranchingStrategy,
    6267        NumNlpFailureMax,
    6368        WarmStartStrategy,
  • branches/devel/Bonmin/experimental/Bcp/BM_lp.cpp

    r110 r113  
    3636    clp->messageHandler()->setLogLevel(0);
    3737    setOsiBabSolver(dynamic_cast<OsiBabSolver *>(clp->getAuxiliaryInfo()));
    38 
    39     // copy over the OsiObjects from the nlp solver
    40     clp->addObjects(nlp.numberObjects(), nlp.objects());
    4138
    4239    return clp;
     
    6259    nlp.setColUpper(osi->getColUpper());
    6360
    64     // Carry the changes over to the object lists in osi and in nlp
    65     const int numObj = osi->numberObjects();
    66     OsiObject** osiObj = osi->objects();
     61    // Carry the changes over to the object lists in nlp
     62    const int numObj = nlp.numberObjects();
    6763    OsiObject** nlpObj = nlp.objects();
    6864    for (i = 0; i < numObj; ++i) {
    69         OsiSimpleInteger* io = dynamic_cast<OsiSimpleInteger*>(osiObj[i]);
     65        OsiSimpleInteger* io = dynamic_cast<OsiSimpleInteger*>(nlpObj[i]);
    7066        if (io) {
    71             io->resetBounds(osi);
    72             io = dynamic_cast<OsiSimpleInteger*>(nlpObj[i]);
    7367            io->resetBounds(&nlp);
    74             continue;
    75         }
    76         // The rest is OsiSOS where we don't need to do anything
    77         break;
     68        } else {
     69            // The rest is OsiSOS where we don't need to do anything
     70            break;
     71        }
     72    }
     73
     74    // copy over the OsiObjects from the nlp solver if the lp solver is to be
     75    // used at all (i.e., not pure B&B)
     76    if (! par.entry(BM_par::PureBranchAndBound)) {
     77        osi->addObjects(nlp.numberObjects(), nlp.objects());
    7878    }
    7979
  • branches/devel/Bonmin/experimental/Bcp/BM_lp_branch.cpp

    r110 r113  
    3434    // FIXME: for general hybrid algo
    3535    if (par.entry(BM_par::PureBranchAndBound)) {
     36        BCP_branching_decision retCode;
    3637        OsiBranchingObject* brObj = NULL;
    3738        OsiBranchingInformation brInfo(&nlp, false);
     
    5152        CoinDisjointCopyN(nlp.getColLower(), numCols, clb_old);
    5253        CoinDisjointCopyN(nlp.getColUpper(), numCols, cub_old);
    53        
    54         OsiChooseStrong choose(&nlp);
    55         choose.setNumberBeforeTrusted(5); // the default in Cbc
    56         choose.setNumberStrong(5); // the default in Cbc
    57         /** Pseudo Shadow Price mode
    58             0 - off
    59             1 - use and multiply by strong info
    60             2 - use
    61         */
    62         choose.setShadowPriceMode(0);
    63 
    64         const int brResult = try_to_branch(brInfo, &nlp, &choose, brObj, true);
    65 #if 0
    66         /* FIXME:before doing anything check if we have found a new solution */
    67         if (choose->goodSolution()
    68             &&model->problemFeasibility()->feasible(model,-1)>=0) {
    69             // yes
    70             double objValue = choose->goodObjectiveValue();
    71             model->setBestSolution(CBC_STRONGSOL,
    72                                    objValue,
    73                                    choose->goodSolution()) ;
    74             model->setLastHeuristic(NULL);
    75             model->incrementUsed(choose->goodSolution());
     54
     55        OsiChooseVariable* choose = NULL;
     56        switch (par.entry(BM_par::BranchingStrategy)) {
     57        case BM_OsiChooseVariable:
     58            choose = new OsiChooseVariable(&nlp);
     59            choose->setNumberStrong(1);
     60            break;
     61        case BM_OsiChooseStrong:
     62            OsiChooseStrong* strong = new OsiChooseStrong(&nlp);
     63            strong->setNumberBeforeTrusted(5); // the default in Cbc
     64            choose->setNumberStrong(5); // the default in Cbc
     65            /** Pseudo Shadow Price mode
     66                0 - off
     67                1 - use and multiply by strong info
     68                2 - use
     69            */
     70            strong->setShadowPriceMode(0);
     71            choose = strong;
     72            break;
     73        }
     74
     75        const int brResult = try_to_branch(brInfo, &nlp, choose, brObj, true);
     76
     77        if (choose->goodSolution()) {
     78            /* yipee! a feasible solution! */
     79            const double* sol = choose->goodSolution();
     80            BM_solution* bmsol = new BM_solution;
     81            //Just copy the solution stored in solver to sol
     82            double ptol;
     83            nlp.getDblParam(OsiPrimalTolerance, ptol);
     84            for (int i = 0 ; i < numCols ; i++) {
     85                if (fabs(sol[i]) > ptol)
     86                    bmsol->add_entry(i, sol[i]);
     87            }
     88            bmsol->setObjective(choose->goodObjectiveValue());
    7689            choose->clearGoodSolution();
    77         }
    78 #endif
     90            send_feasible_solution(bmsol);
     91            delete bmsol;
     92        }
     93
    7994        switch (brResult) {
    8095        case -2:
    8196            // when doing strong branching a candidate has proved that the
    8297            // problem is infeasible
    83             delete[] clb_old;
    84             delete[] cub_old;
    85             return BCP_DoNotBranch_Fathomed;
     98            retCode = BCP_DoNotBranch_Fathomed;
     99            break;
    86100        case -1:
    87101            // OsiChooseVariable::chooseVariable() returned 2, 3, or 4
    88102            if (!brObj) {
    89103                // just go back and resolve
    90                 delete[] clb_old;
    91                 delete[] cub_old;
    92                 return BCP_DoNotBranch;
    93             }
    94             // otherwise might as well branch. The forced variable is
    95             // unlikely to jump up one more (though who knows...)
     104                retCode = BCP_DoNotBranch;
     105            } else {
     106                // otherwise might as well branch. The forced variable is
     107                // unlikely to jump up one more (though who knows...)
     108                retCode = BCP_DoBranch;
     109            }
    96110            break;
    97111        case 0:
     
    101115            }
    102116            // we've got a branching object
     117            retCode = BCP_DoBranch;
    103118            break;
    104119        default:
     
    107122        }
    108123
    109         // If there were some fixings (brResult < 0) then propagate them where
    110         // needed
    111124        if (brResult < 0) {
    112             const double* clb = nlp.getColLower();
    113             const double* cub = nlp.getColUpper();
    114             BCP_lp_prob* p = getLpProblemPointer();
    115             BCP_vec<BCP_var*>& vars = p->node->vars;
    116             OsiSolverInterface* lp = p->lp_solver;
    117             for (int i = 0; i < numCols; ++i) {
    118                 if (clb_old[i] != clb[i] || cub_old[i] != cub[i]) {
    119                     vars[i]->change_bounds(clb[i], cub[i]);
    120                     lp->setColBounds(i, clb[i], cub[i]);
     125            // If there were some fixings (brResult < 0) then propagate them
     126            // where needed
     127            if (brResult < 0) {
     128                const double* clb = nlp.getColLower();
     129                const double* cub = nlp.getColUpper();
     130                BCP_lp_prob* p = getLpProblemPointer();
     131                BCP_vec<BCP_var*>& vars = p->node->vars;
     132                OsiSolverInterface* lp = p->lp_solver;
     133                for (int i = 0; i < numCols; ++i) {
     134                    if (clb_old[i] != clb[i] || cub_old[i] != cub[i]) {
     135                        vars[i]->change_bounds(clb[i], cub[i]);
     136                        lp->setColBounds(i, clb[i], cub[i]);
     137                    }
    121138                }
    122139            }
    123140        }
     141
     142        if (retCode == BCP_DoBranch) {
     143            // all possibilities are 2-way branches
     144            int order[2] = {0, 1};
     145            if (choose->bestWhichWay() == 1) {
     146                order[0] = 1;
     147                order[1] = 0;
     148            }
     149            // Now interpret the result (at this point we must have a brObj
     150            OsiIntegerBranchingObject* intBrObj =
     151                dynamic_cast<OsiIntegerBranchingObject*>(brObj);
     152            if (intBrObj) {
     153                BCP_lp_integer_branching_object o(intBrObj);
     154                cands.push_back(new BCP_lp_branching_object(o, order));
     155                if (par.entry(BM_par::PrintBranchingInfo)) {
     156                    printf("BM_lp: branching on variable %i   value: %f\n",
     157                           intBrObj->originalObject()->columnNumber(),
     158                           intBrObj->value());
     159                }
     160            }
     161            OsiSOSBranchingObject* sosBrObj =
     162                dynamic_cast<OsiSOSBranchingObject*>(brObj);
     163            if (sosBrObj) {
     164                BCP_lp_sos_branching_object o(sosBrObj);
     165                cands.push_back(new BCP_lp_branching_object(&nlp, o, order));
     166                if (par.entry(BM_par::PrintBranchingInfo)) {
     167                    printf("BM_lp: branching on SOS %i   value: %f\n",
     168                           sosBrObj->originalObject()->columnNumber(),
     169                           sosBrObj->value());
     170                }
     171            }
     172        }
     173
    124174        delete[] clb_old;
    125175        delete[] cub_old;
    126 
    127         // Now interpret the result (at this point we must have a brObj
    128         OsiIntegerBranchingObject* intBrObj =
    129             dynamic_cast<OsiIntegerBranchingObject*>(brObj);
    130         if (intBrObj) {
    131             BCP_lp_integer_branching_object o(intBrObj);
    132             cands.push_back(new BCP_lp_branching_object(o));
    133             if (par.entry(BM_par::PrintBranchingInfo)) {
    134                 printf("BM_lp: branching on variable %i   value: %f\n",
    135                        intBrObj->originalObject()->columnNumber(),
    136                        intBrObj->value());
    137             }
    138         }
    139         OsiSOSBranchingObject* sosBrObj =
    140             dynamic_cast<OsiSOSBranchingObject*>(brObj);
    141         if (sosBrObj) {
    142             BCP_lp_sos_branching_object o(sosBrObj);
    143             cands.push_back(new BCP_lp_branching_object(&nlp, o));
    144             if (par.entry(BM_par::PrintBranchingInfo)) {
    145                 printf("BM_lp: branching on variable %i   value: %f\n",
    146                        sosBrObj->originalObject()->columnNumber(),
    147                        sosBrObj->value());
    148             }
    149         }
    150         return BCP_DoBranch;
     176        delete choose;
     177        return retCode;
    151178
    152179    } else { // not pure B&B
Note: See TracChangeset for help on using the changeset viewer.