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

Last change on this file since 530 was 530, checked in by ladanyi, 13 years ago

prepare Bcp for changing some LPs into TM storage places. Serial version works, currently debugging parallel version.

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