Changeset 30


Ignore:
Timestamp:
Aug 28, 2006 10:37:15 AM (13 years ago)
Author:
ladanyi
Message:

sos1 works

Location:
trunk/Bonmin/experimental/Bcp
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Bonmin/experimental/Bcp/BM.cpp

    r28 r30  
    5252                             BCP_parameter(BCP_CharPar, PrintBranchingInfo)));
    5353    keys.push_back(make_pair(BCP_string("CombinedDistanceAndPriority"),
    54                              BCP_parameter(BCP_CharPar, CombinedDistanceAndPriority)));
    55     keys.push_back(make_pair(BCP_string("LowPriorityImportant"),
    56                              BCP_parameter(BCP_CharPar, LowPriorityImportant)));
     54                             BCP_parameter(BCP_CharPar,
     55                                           CombinedDistanceAndPriority)));
     56    keys.push_back(make_pair(BCP_string("SosWithLowPriorityMoreImportant"),
     57                             BCP_parameter(BCP_CharPar,
     58                                           SosWithLowPriorityMoreImportant)));
     59    keys.push_back(make_pair(BCP_string("VarWithLowPriorityMoreImportant"),
     60                             BCP_parameter(BCP_CharPar,
     61                                           VarWithLowPriorityMoreImportant)));
    5762    keys.push_back(make_pair(BCP_string("NumNlpFailureMax"),
    5863                             BCP_parameter(BCP_IntPar, NumNlpFailureMax)));
     
    6974    set_entry(PrintBranchingInfo, true);
    7075    set_entry(CombinedDistanceAndPriority, true);
    71     set_entry(LowPriorityImportant, true);
     76    set_entry(SosWithLowPriorityMoreImportant, true);
     77    set_entry(SosWithLowPriorityMoreImportant, true);
     78    set_entry(VarWithLowPriorityMoreImportant, true);
    7279    set_entry(NumNlpFailureMax, 5);
    7380    set_entry(NL_filename, "");
     
    285292BM_lp::BM_lp() :
    286293    BCP_lp_user(),
     294    sos(),
    287295    babSolver_(3),
    288296    nlp(),
    289     sos(),
    290297    feasChecker_(NULL),
    291298    in_strong(0)
     
    302309    delete[] primal_solution_;
    303310    delete[] branching_priority_;
     311    for (int i = sos.size() - 1; i >= 0; --i) {
     312        delete sos[i];
     313    }
    304314}
    305315
     
    330340                                       BCP_vec<double>& cut_new_bd)
    331341{
     342    int i;
    332343    // First copy the bounds into nlp. That way all the branching decisions
    333344    // will be transferred over.
     345    for (i = sos.size() - 1; i >= 0; --i) {
     346        sos[i]->first = 0;
     347        sos[i]->last = sos[i]->length;
     348    }
    334349    OsiSolverInterface * osi = getLpProblemPointer()->lp_solver;
    335     const int numCols = nlp.getNumCols();
     350    const int numCols = osi->getNumCols();
    336351    const double* clb = osi->getColLower();
    337352    const double* cub = osi->getColUpper();
    338     for (int i = 0; i < numCols; ++i) {
     353    for (i = 0; i < numCols; ++i) {
    339354        const BCP_var_core* v =
    340355            dynamic_cast<const BCP_var_core*>(vars[i]);
     
    349364            const int ind = bv->sos_index;
    350365            const int split = bv->split;
    351             const int len = sos.lengths[ind];
    352             const char type = sos.types[ind];
    353             const int *indices = sos.indices[ind];
     366            const char type = sos[ind]->type;
     367            const int *indices = sos[ind]->indices;
    354368            if (bv->ub() == 0.0) {
    355                 for (int j = split + type; j < len; ++j) {
     369                const int last = sos[ind]->last;
     370                for (int j = split + type; j < last; ++j) {
    356371                    nlp.setColLower(indices[j], 0.0);
    357372                    nlp.setColUpper(indices[j], 0.0);
    358373                }
     374                sos[ind]->last = split + type;
    359375            } else {
    360                 for (int j = 0; j < split; ++j) {
     376                const int first = sos[ind]->first;
     377                for (int j = first; j < split; ++j) {
    361378                    nlp.setColLower(indices[j], 0.0);
    362379                    nlp.setColUpper(indices[j], 0.0);
    363380                }
     381                sos[ind]->first = split;
    364382            }
    365383            continue;
     
    404422        nlp.initialSolve();
    405423        if (nlp.isProvenOptimal()) {
     424            const int numCols = nlp.getNumCols();
    406425            lower_bound_ = nlp.getObjValue();
    407             CoinDisjointCopyN(nlp.getColSolution(), vars.size(),
    408                               primal_solution_);
     426            CoinDisjointCopyN(nlp.getColSolution(), numCols, primal_solution_);
    409427            numNlpFailed_ = 0;
    410428            Ipopt::SmartPtr<Ipopt::OptionsList> options = nlp.retrieve_options();
     
    412430            options->GetNumericValue("integer_tolerance",intTol,"bonmin.");
    413431
    414             const int numCols = nlp.getNumCols();
    415432            int i;
    416433            for (i = 0; i < numCols; ++i) {
     
    440457            lower_bound_ = 1e200;
    441458            numNlpFailed_ = 0;
     459            printf("\
     460BM_lp: At node %i : will fathom because of infeasibility\n",
     461                   current_index());
    442462        }
    443463        else if (nlp.isAbandoned()) {
     
    465485        nlp.retrieve_options()->GetNumericValue("integer_tolerance",
    466486                                                integerTolerance,"bonmin.");
    467         nlp.retrieve_options()->GetNumericValue("cutoff_incr",
     487        /* FIXME: cutoff_decr was called cutoff_incr??? */
     488        nlp.retrieve_options()->GetNumericValue("cutoff_decr",
    468489                                                cutOffIncrement,"bonmin.");
    469490        OsiSolverInterface * osi = getLpProblemPointer()->lp_solver;
     
    607628    double cutoffIncr;
    608629    options->GetNumericValue("integer_tolerance", intTol, "bonmin.");
    609     options->GetNumericValue("cutoff_incr", cutoffIncr, "bonmin.");
     630    options->GetNumericValue("cutoff_decr", cutoffIncr, "bonmin.");
    610631
    611632    if (lower_bound_ >= upper_bound() + cutoffIncr) {
     
    619640    }
    620641
    621     if (par.entry(BM_par::BranchOnSos) && sos.num > 0) {
     642    if (par.entry(BM_par::BranchOnSos) && sos.size() > 0) {
    622643        double bestval = 2.0;
    623644        int bestsos = -1;
    624645        int bestsplit = -1;
    625646        int bestprio = 0;
    626         for (int i = 0; i < sos.num; ++i) {
    627             const int ind = sos.priority_order[i];
    628             const int prio = sos.priorities[ind];
     647        for (size_t ind = 0; ind < sos.size(); ++ind) {
     648            const BmSosInfo& sosi = *sos[ind];
     649            const int prio = sosi.priority;
     650            const int type = sosi.type;
     651            if ((type == 0 && par.entry(BM_par::BranchOnSos) == 2) ||
     652                (type == 1 && par.entry(BM_par::BranchOnSos) == 1))
     653                continue;
    629654            if (bestsos >= 0 && prio != bestprio)
    630655                break;
    631             const int len = sos.lengths[ind];
    632             const int *indices = sos.indices[ind];
     656            const int first = sosi.first;
     657            const int last = sosi.last;
     658            const int *indices = sosi.indices;
    633659            // First count how many nonzeros are there
    634660            int cnt = 0;
    635             for (int j = 0; j < len; ++j) {
     661            for (int j = first; j < last; ++j) {
    636662                const double prim_i = primal_solution_[indices[j]];
    637663                if (prim_i > intTol && prim_i < 1-intTol) {
     
    641667            // For type1 there can be at most 1, for type2 at most 2 nonzeros
    642668            // Find the next sos if this is satisfied.
    643             const int type = sos.types[ind];
    644669            if (cnt <= 1+type)
    645670                continue;
     
    649674            double val = 0.0;
    650675            double primal = 0.0;
    651             for (half = 0; half < len; ++half) {
     676            for (half = first; half < last; ++half) {
    652677                val = primal_solution_[indices[half]];
    653678                primal += val;
     
    664689
    665690            /* The branches will be as follows:
    666                type1 : [0,half) and [half,len)
    667                type2 : [0,half) and (half,len)
    668                So if half==0 then it must be incremented,
    669                and also for type 2 if half==len-1 then it must be decremented.
     691               type1 : [first,half) and [half,last)
     692               type2 : [first,half) and (half,last)
     693               So if half==first then it must be incremented,
     694               and also for type 2 if half==last-1 then it must be decremented.
    670695            */
    671             if (half == 0)
     696            if (half == first)
    672697                ++half;
    673             if (type == 1 && half == len-1)
     698            if (type == 1 && half == last-1)
    674699                --half;
    675700
     
    700725                                                        NULL,NULL,NULL,NULL));
    701726            if (par.entry(BM_par::PrintBranchingInfo)) {
    702                 printf("BM_lp: branching on SOS #%i (type %i)  split at: %i\n",
    703                        bestsos, sos.types[bestsos]+1, bestsplit);
     727                printf("\
     728BM_lp: At node %i branching on SOS%i set %i  split at: %i with val: %f\n",
     729                       current_index(), sos[bestsos]->type+1,
     730                       bestsos, bestsplit, bestval);
    704731            }
    705732            return BCP_DoBranch;;
     
    773800//#############################################################################
    774801
    775 BM_lp::BmSosInfo::~BmSosInfo()
    776 {
    777     if (num > 0) {
    778         for (int i = 0; i < num; ++i) {
    779             delete[] indices[i];
    780             delete[] weights[i];
    781         }
    782         delete[] indices;
    783         delete[] weights;
    784         delete[] types;
    785         delete[] lengths;
    786         delete[] priority_order;
    787     }
    788 }
    789 
     802BM_lp::BmSosInfo::BmSosInfo(const TMINLP::SosInfo * sosinfo, int i)
     803{
     804    priority = sosinfo->priorities ? sosinfo->priorities[i] : 0;
     805    length   = sosinfo->starts[i+1] - sosinfo->starts[i];
     806    type     = sosinfo->types[i] == 1 ? 0 : 1;
     807    indices  = new int[length];
     808    weights  = new double[length];
     809    first    = 0;
     810    last     = length;
     811    CoinDisjointCopyN(sosinfo->indices+sosinfo->starts[i], length, indices);
     812    CoinDisjointCopyN(sosinfo->weights+sosinfo->starts[i], length, weights);
     813    CoinSort_2(weights, weights+length, indices);
     814}
     815   
    790816/*---------------------------------------------------------------------------*/
    791817
    792 void BM_lp::BmSosInfo::setFrom(const TMINLP::SosInfo * sos)
    793 {
    794     if (!sos || sos->num == 0)
     818void BM_lp::setSosFrom(const TMINLP::SosInfo * sosinfo)
     819{
     820    if (!sosinfo || sosinfo->num == 0)
    795821        return;
    796822
    797823    //we have some sos constraints
    798     num = sos->num;
    799     priority_order = new int[num];
    800     CoinIotaN(priority_order, num, 0);
    801     priorities = new int[num];
    802     if (sos->priorities) {
    803         CoinDisjointCopyN(sos->priorities, num, priorities);
     824    sos.reserve(sosinfo->num);
     825    for (int i = 0; i < sosinfo->num; ++i) {
     826        sos.push_back(new BmSosInfo(sosinfo, i));
     827    }
     828
     829    if (sosinfo->priorities) {
     830        int * priorities = new int[sosinfo->num];
     831        CoinDisjointCopyN(sosinfo->priorities, sosinfo->num, priorities);
    804832        /* FIXME: we may need to go down in order! */
    805         CoinSort_2(priorities, priorities+num, priority_order);
    806     } else {
    807         CoinFillN(priorities, num, 0);
    808     }
    809 
    810     lengths = new int[num];
    811     types   = new int[num];
    812     indices = new int*[num];
    813     weights = new double*[num];
    814 
    815     for (int i = 0; i < num; ++i) {
    816         lengths[i] = sos->starts[i+1] - sos->starts[i];
    817         types[i] = sos->types[i] == 1 ? 0 : 1;;
    818         indices[i] = new int[lengths[i]];
    819         weights[i] = new double[lengths[i]];
    820         CoinDisjointCopyN(sos->indices+sos->starts[i], lengths[i], indices[i]);
    821         CoinDisjointCopyN(sos->weights+sos->starts[i], lengths[i], weights[i]);
    822         CoinSort_2(weights[i], weights[i]+lengths[i], indices[i]);
     833        if (par.entry(BM_par::SosWithLowPriorityMoreImportant)) {
     834            CoinSort_2(priorities, priorities+sosinfo->num, &sos[0],
     835                       std::less<int>());
     836        } else {
     837            CoinSort_2(priorities, priorities+sosinfo->num, &sos[0],
     838                       std::greater<int>());
     839        }
     840        delete[] priorities;
    823841    }
    824842}
     
    826844/*---------------------------------------------------------------------------*/
    827845
     846#if 0
    828847void BM_lp::BmSosInfo::shuffle()
    829848{
     
    841860    }
    842861}
     862#endif
    843863
    844864//#############################################################################
  • trunk/Bonmin/experimental/Bcp/BM.hpp

    r28 r30  
    4949        PureBranchAndBound,
    5050        PrintBranchingInfo,
    51         LowPriorityImportant,
     51        SosWithLowPriorityMoreImportant,
     52        VarWithLowPriorityMoreImportant,
    5253        end_of_chr_params
    5354    };
     
    156157{
    157158    struct BmSosInfo {
    158         int num;
    159         int *priority_order;
    160         int *lengths;
    161         int *types; // 0: type 1  ---- 1: type 2
    162         int *priorities;
    163         int **indices;
    164         double **weights;
    165         BmSosInfo() : num(0) {}
    166         ~BmSosInfo();
    167         void setFrom(const TMINLP::SosInfo * sos);
    168         void shuffle();
    169     };
     159        int length;
     160        int type; // 0: type 1  ---- 1: type 2
     161        int priority;
     162        int *indices;
     163        double *weights;
     164        int first;
     165        int last;
     166        BmSosInfo(const TMINLP::SosInfo * sosinfo, int i);
     167        ~BmSosInfo() {
     168            delete[] indices;
     169            delete[] weights;
     170        }
     171    };
     172    std::vector<BmSosInfo*> sos;
     173    void setSosFrom(const TMINLP::SosInfo * sosinfo);
    170174               
    171175    BCP_string ipopt_file_content;
     
    175179    OsiBabSolver babSolver_;
    176180    BonminAmplInterface nlp;
    177     BmSosInfo sos;
    178181
    179182    double lower_bound_;
  • trunk/Bonmin/experimental/Bcp/BM_pack.cpp

    r1 r30  
    7878    double bm_cutoffIncr; // could be negative
    7979    options->GetNumericValue("integer_tolerance",bm_intTol,"bonmin.");
    80     options->GetNumericValue("cutoff_incr",bm_cutoffIncr,"bonmin.");
     80    options->GetNumericValue("cutoff_decr",bm_cutoffIncr,"bonmin.");
    8181
    8282    BCP_lp_prob* bcp_lp = getLpProblemPointer();
     
    121121    /* SOS constraints */
    122122    if (par.entry(BM_par::BranchOnSos)) {
    123         sos.setFrom(nlp.model()->sosConstraints());
     123        setSosFrom(nlp.model()->sosConstraints());
    124124    }
    125125
     
    134134    if (prio == NULL) {
    135135        // No. Just sett all of them uniformly to 1.0
    136         for (i = 0; i < numCols; ++i)
    137             {
    138                 branching_priority_[i] = 1.0;
    139             }
    140     }
    141     else {
     136        for (i = 0; i < numCols; ++i) {
     137            branching_priority_[i] = 1.0;
     138        }
     139    } else {
    142140        /* Yes! the lower the number the earlier we want to branch on it.
    143141           Let's see how many different numbers there are */
    144142        std::set<int> numbers;
    145         for (i = 0; i < numCols; ++i)
    146             {
    147                 numbers.insert(prio[i]);
    148             }
     143        for (i = 0; i < numCols; ++i) {
     144            numbers.insert(prio[i]);
     145        }
    149146        if (numbers.size() > 15) {
    150             /* Sigh... too many... We just have to trust the user's knowledge */
     147            /* Sigh... too many... We just have to trust the user's
     148               knowledge */
    151149            if (par.entry(BM_par::CombinedDistanceAndPriority) == true) {
    152150                printf("WARNING!\n");
     
    166164                                        1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14};
    167165            const double* powers =
    168                 par.entry(BM_par::LowPriorityImportant) ? powerup : powerdo;
    169             for (i = 0; i < numCols; ++i)
    170                 {
    171                     const int pos = coinDistance(numbers.begin(), numbers.find(prio[i]));
    172                     assert (pos >= 0 && pos < 15);
    173                     branching_priority_[i] = powers[pos];
     166                par.entry(BM_par::VarWithLowPriorityMoreImportant) ? powerup : powerdo;
     167            for (i = 0; i < numCols; ++i) {
     168                const int pos = coinDistance(numbers.begin(), numbers.find(prio[i]));
     169                assert (pos >= 0 && pos < 15);
     170                branching_priority_[i] = powers[pos];
     171            }
     172        } else {
     173            if (par.entry(BM_par::VarWithLowPriorityMoreImportant)) {
     174                const double maxprio = *numbers.rbegin();
     175                for (i = 0; i < numCols; ++i) {
     176                    branching_priority_[i] = maxprio - prio[i];
    174177                }
    175         }
    176         else {
    177             if (par.entry(BM_par::LowPriorityImportant)) {
    178                 const double maxprio = *numbers.rbegin();
    179                 for (i = 0; i < numCols; ++i)
    180                     {
    181                         branching_priority_[i] = maxprio - prio[i];
    182                     }
    183             }
    184             else {
    185                 for (i = 0; i < numCols; ++i)
    186                     {
    187                         branching_priority_[i] = prio[i];
    188                     }
     178            } else {
     179                for (i = 0; i < numCols; ++i) {
     180                    branching_priority_[i] = prio[i];
     181                }
    189182            }
    190183        }
Note: See TracChangeset for help on using the changeset viewer.