source: trunk/Bonmin/experimental/Bcp/BM_lp_branch.cpp @ 508

Last change on this file since 508 was 508, checked in by pbonami, 13 years ago

Make bcp-bonmin work with new setup

File size: 9.3 KB
Line 
1// (C) Copyright International Business Machines Corporation 2006, 2007
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// Authors :
6// Laszlo Ladanyi, International Business Machines Corporation
7// Pierre Bonami, Carnegie Mellon University
8
9#include "CoinHelperFunctions.hpp"
10#include "BCP_lp_node.hpp"
11#include "BM.hpp"
12#include "BonCurvBranching.hpp"
13#include "BonQPStrongBranching.hpp"
14#include "BonLpStrongBranching.hpp"
15#include "BonOsiTMINLPInterface.hpp"
16
17//#############################################################################
18
19BCP_branching_decision
20BM_lp::select_branching_candidates(const BCP_lp_result& lpres,
21                                   const BCP_vec<BCP_var*>& vars,
22                                   const BCP_vec<BCP_cut*>& cuts,
23                                   const BCP_lp_var_pool& local_var_pool,
24                                   const BCP_lp_cut_pool& local_cut_pool,
25                                   BCP_vec<BCP_lp_branching_object*>& cands)
26{
27    const double objLimit = upper_bound() + cutOffDecrement_;
28
29    if (lower_bound_ >= objLimit) {
30        return BCP_DoNotBranch_Fathomed;
31    }
32
33    if (numNlpFailed_ >= par.entry(BM_par::NumNlpFailureMax)) {
34        printf("WARNING! Too many (%i) NLP failures in a row. Abandoning node.",
35               numNlpFailed_);
36        return BCP_DoNotBranch_Fathomed;
37    }
38
39   
40    OsiBranchingInformation brInfo(bonmin_.nonlinearSolver(), false);
41    brInfo.cutoff_ = objLimit;
42    brInfo.integerTolerance_ = integerTolerance_;
43    brInfo.timeRemaining_ = get_param(BCP_lp_par::MaxRunTime) - CoinCpuTime();
44    brInfo.numberSolutions_ = 0; /*FIXME*/
45    brInfo.numberBranchingSolutions_ = 0; /*FIXME numBranchingSolutions_;*/
46    brInfo.depth_ = current_level();
47
48    BCP_branching_decision brDecision;
49    if (bonmin_.getAlgorithm() == 0) {
50        /* if pure B&B */
51        brDecision = bbBranch(brInfo, cands);
52    } else {
53        brDecision = hybridBranch();
54    }
55
56    return brDecision;
57}
58
59//-----------------------------------------------------------------------------
60
61BCP_branching_decision
62BM_lp::hybridBranch()
63{
64    // FIXME: most of the pureBB stuff should work here.
65    throw BCP_fatal_error("BM_lp: FIXME: make hybrid work...");
66}
67
68//-----------------------------------------------------------------------------
69
70BCP_branching_decision
71BM_lp::bbBranch(OsiBranchingInformation& brInfo,
72                BCP_vec<BCP_lp_branching_object*>& cands)
73{
74    BCP_branching_decision retCode;
75    OsiBranchingObject* brObj = NULL;
76
77    static int cnt = 0;
78    printf("cnt = %i\n", cnt);
79    ++cnt;
80
81    Bonmin::OsiTMINLPInterface& nlp = *bonmin_.nonlinearSolver();
82    const int numCols = nlp.getNumCols();
83    double* clb_old = new double[numCols];
84    double* cub_old = new double[numCols];
85    CoinDisjointCopyN(nlp.getColLower(), numCols, clb_old);
86    CoinDisjointCopyN(nlp.getColUpper(), numCols, cub_old);
87
88    // if we don't have a ChooseVariable object yet, create it now
89    if (!chooseVar_) {
90      switch (varselect_) {
91      case Bonmin::OsiTMINLPInterface::MOST_FRACTIONAL: {
92        // AW: Try to set new chooseVariable object
93        Bonmin::BonCurvBranching* chooseVariable =
94          new Bonmin::BonCurvBranching(&nlp);
95        chooseVariable->setNumberStrong(0);
96        chooseVar_ = chooseVariable;
97        break;
98      }
99      case Bonmin::OsiTMINLPInterface::CURVATURE_ESTIMATOR: {
100        // AW: Try to set new chooseVariable object
101        Bonmin::BonCurvBranching* chooseVariable =
102          new Bonmin::BonCurvBranching(&nlp);
103        chooseVariable->setNumberStrong(numberStrong_);
104        chooseVar_ = chooseVariable;
105        break;
106      }
107      case Bonmin::OsiTMINLPInterface::QP_STRONG_BRANCHING: {
108        Bonmin::BonQPStrongBranching* chooseVariable =
109          new Bonmin::BonQPStrongBranching(&nlp);
110        chooseVariable->setNumberStrong(numberStrong_);
111        chooseVar_ = chooseVariable;
112        break;
113      }
114      case Bonmin::OsiTMINLPInterface::LP_STRONG_BRANCHING: {
115        Bonmin::LpStrongBranching* chooseVariable =
116          new Bonmin::LpStrongBranching(&nlp);
117        chooseVariable->setMaxCuttingPlaneIter(numEcpRounds_);
118        chooseVariable->setNumberStrong(numberStrong_);
119        chooseVar_ = chooseVariable;
120        break;
121      }
122      case Bonmin::OsiTMINLPInterface::NLP_STRONG_BRANCHING: {
123        const bool solve_nlp = true;
124        Bonmin::BonQPStrongBranching* chooseVariable = 
125          new Bonmin::BonQPStrongBranching(&nlp, solve_nlp);
126        chooseVariable->setNumberStrong(numberStrong_);
127        chooseVar_ = chooseVariable;
128        break;
129      }
130      case Bonmin::OsiTMINLPInterface::OSI_SIMPLE: {
131        OsiChooseVariable* chooseVariable = new OsiChooseVariable(&nlp);
132        chooseVar_ = chooseVariable;
133        break;
134      }
135      default:
136        printf("Invalid choice for variable selection!\n");
137        throw -3;
138      }
139    }
140
141    const int brResult = try_to_branch(brInfo, &nlp, chooseVar_, brObj, true);
142
143#if 0
144    if (choose->goodSolution()) {
145        /* yipee! a feasible solution! Check that it's really */
146        const double* sol = choose->goodSolution();
147        BM_solution* bmsol = new BM_solution;
148        //Just copy the solution stored in solver to sol
149        double ptol;
150        nlp_.getDblParam(OsiPrimalTolerance, ptol);
151        for (int i = 0 ; i < numCols ; i++) {
152            if (fabs(sol[i]) > ptol)
153                bmsol->add_entry(i, sol[i]);
154        }
155        bmsol->setObjective(choose->goodObjectiveValue());
156        choose->clearGoodSolution();
157        send_feasible_solution(bmsol);
158        delete bmsol;
159    }
160#endif
161    switch (brResult) {
162    case -2:
163        // when doing strong branching a candidate has proved that the
164        // problem is infeasible
165        retCode = BCP_DoNotBranch_Fathomed;
166        break;
167    case -1:
168        // OsiChooseVariable::chooseVariable() returned 2, 3, or 4
169        if (!brObj) {
170            // just go back and resolve
171            retCode = BCP_DoNotBranch;
172        } else {
173            // otherwise might as well branch. The forced variable is
174            // unlikely to jump up one more (though who knows...)
175            retCode = BCP_DoBranch;
176        }
177        break;
178    case 0:
179        if (!brObj) {
180            // nothing got fixed, yet couldn't find something to branch on
181            throw BCP_fatal_error("BM: Couldn't branch!\n");
182        }
183        // we've got a branching object
184        retCode = BCP_DoBranch;
185        break;
186    default:
187        throw BCP_fatal_error("\
188BM: BCP_lp_user::try_to_branch returned with unknown return code.\n");
189    }
190
191    bool distributedStrongBranching =
192        (retCode == BCP_DoBranch) && (par.entry(BM_par::FullStrongBranch) > 0);
193
194    if (brResult < 0) {
195        // If there were some fixings (brResult < 0) then propagate them
196        // where needed
197
198        // FIXME: This is not nice. Meddling w/ BCP internal data. The BCP
199        // user interface should provide a way to change bounds regardless
200        // whether branching is asked for or not.
201        const double* clb = nlp.getColLower();
202        const double* cub = nlp.getColUpper();
203
204        BCP_lp_prob* p = getLpProblemPointer();
205        BCP_vec<BCP_var*>& vars = p->node->vars;
206        OsiSolverInterface* lp = p->lp_solver;
207        if (distributedStrongBranching) {
208            retCode = retCode;
209        }
210        for (int i = 0; i < numCols; ++i) {
211            if (clb_old[i] != clb[i] || cub_old[i] != cub[i]) {
212                vars[i]->change_bounds(clb[i], cub[i]);
213                lp->setColBounds(i, clb[i], cub[i]);
214            }
215        }
216    }
217
218    if (retCode == BCP_DoBranch) {
219        // all possibilities are 2-way branches
220        int order[2] = {0, 1};
221        // Now interpret the result (at this point we must have a brObj
222        OsiIntegerBranchingObject* intBrObj =
223            dynamic_cast<OsiIntegerBranchingObject*>(brObj);
224        if (intBrObj) {
225            if (intBrObj->firstBranch() == 1) {
226                order[0] = 1;
227                order[1] = 0;
228            }
229            BCP_lp_integer_branching_object o(intBrObj);
230            cands.push_back(new BCP_lp_branching_object(o, order));
231            if (par.entry(BM_par::PrintBranchingInfo)) {
232                printf("BM_lp: branching on variable %i   value: %f\n",
233                       intBrObj->originalObject()->columnNumber(),
234                       intBrObj->value());
235            }
236        }
237        OsiSOSBranchingObject* sosBrObj =
238            dynamic_cast<OsiSOSBranchingObject*>(brObj);
239        if (sosBrObj) {
240            if (sosBrObj->firstBranch() == 1) {
241                order[0] = 1;
242                order[1] = 0;
243            }
244            BCP_lp_sos_branching_object o(sosBrObj);
245            cands.push_back(new BCP_lp_branching_object(&nlp, o, order));
246            if (par.entry(BM_par::PrintBranchingInfo)) {
247                printf("BM_lp: branching on SOS %i   value: %f\n",
248                       sosBrObj->originalObject()->columnNumber(),
249                       sosBrObj->value());
250            }
251        }
252    }
253
254    delete brObj;
255    delete[] clb_old;
256    delete[] cub_old;
257    return retCode;
258}
259
260/****************************************************************************/
261
262void
263BM_lp::set_user_data_for_children(BCP_presolved_lp_brobj* best, 
264                                  const int selected)
265{
266    BM_node* data = NULL;
267    data = new BM_node;
268    data->numNlpFailed_ = numNlpFailed_;
269    best->user_data()[0] = data;
270    data = new BM_node;
271    data->numNlpFailed_ = numNlpFailed_;
272    best->user_data()[1] = data;
273}
274
275//#############################################################################
276
277const BCP_proc_id*
278BM_lp::process_id() const
279{
280}
281
282void
283BM_lp::send_message(const BCP_proc_id* const target, const BCP_buffer& buf)
284{
285}
286
287void
288BM_lp::broadcast_message(const BCP_process_t proc_type, const BCP_buffer& buf)
289{
290}
291
292void
293BM_lp::process_message(BCP_buffer& buf)
294{
295}
296
297/*
298 Ipopt::TMINLP* model = nlp.model();
299 model->get_nlp_info to get nnz_h_lag (pp 16)
300alloc that much space for irow, jcol and values  (passed into eval_h, pp22)
301call eval_h *twice*
302first: values=NULL to get the sparsity structure
303second: irow and jcol are NULL and values will be filled
304the sparsity format is in MA27 format (pp 39 -- but it's symmetric here!)
305(multiple triplets can point to the same location! -- add them up!)
306
307the diagonal of that matrix is the 1-dim quadratic term for each var when the
308others are fixed. Better be nonneg for convex problems)
309*/
Note: See TracBrowser for help on using the repository browser.