source: trunk/Bonmin/experimental/Bcp/BM.hpp @ 508

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

Make bcp-bonmin work with new setup

  • Property svn:eol-style set to native
  • Property svn:keywords set to "Author Date Id Revision"
File size: 11.5 KB
Line 
1// (C) Copyright International Business Machines Corporation and Carnegie Mellon University 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// Date : 03/15/2006
10#ifndef _BM_H
11#define _BM_H
12
13#include "BonCbcParam.hpp"
14
15#include "BCP_USER.hpp"
16#include "BCP_tm_user.hpp"
17#include "BCP_lp_user.hpp"
18
19#include "BB_cut.hpp"
20
21//#############################################################################
22
23class BM_node : public BCP_user_data {
24public:
25    /** A counter for how many times in a row did the NLP code fail. When the
26        NLP fails we branch; hopefully it'll be OK in the children. If it
27        fails too many times in a row then we fathom the node: it's hopelessly
28        difficult. */
29    int numNlpFailed_;
30public:
31    BM_node() : numNlpFailed_(0) {}
32    BM_node(BCP_buffer& buf) : numNlpFailed_(0) {
33        buf.unpack(numNlpFailed_);
34    }
35    ~BM_node() {}
36
37    inline void pack(BCP_buffer& buf) const {
38        buf.pack(numNlpFailed_);
39    }
40};
41
42//#############################################################################
43   
44enum BM_WarmStartStrategy {
45    WarmStartNone,
46    WarmStartFromRoot,
47    WarmStartFromParent
48};
49
50// This needs to be the same as enum VarSelectStra_Enum in
51// BonOsiTMINLPInterface.hpp
52enum BM_BranchingStrategy {
53    BM_MostFractional=0,
54    BM_StrongBranching,
55    BM_ReliabilityBranching,
56    BM_CurvatureEstimator,
57    BM_QpStrongBranching,
58    BM_LpStrongBranching,
59    BM_NlpStrongBranching,
60    BM_OsiChooseVariable,
61    BM_OsiChooseStrong
62};
63
64enum BM_message {
65    StrongBranchRequest,
66    StrongBranchResult,
67    FreeToBusyRatio
68};
69
70//#############################################################################
71   
72class BM_par {
73public:
74    enum chr_params {
75        //
76        CombinedDistanceAndPriority,
77        PrintBranchingInfo,
78        SosWithLowPriorityMoreImportant,
79        VarWithLowPriorityMoreImportant,
80        end_of_chr_params
81    };
82    enum int_params {
83        //
84        BranchingStrategy,
85        FullStrongBranch,
86        NumNlpFailureMax,
87        WarmStartStrategy,
88        end_of_int_params
89    };
90    enum dbl_params {
91        //
92        end_of_dbl_params
93    };
94    enum str_params {
95        NL_filename,
96        IpoptParamfile,
97        //
98        end_of_str_params
99    };
100    enum str_array_params {
101        //
102        end_of_str_array_params
103    };
104};
105
106//#############################################################################
107
108class BM_tm : public BCP_tm_user {
109
110public:
111
112    /**@name Private data member */
113    BCP_string ipopt_file_content;
114    BCP_string nl_file_content;
115    BCP_parameter_set<BM_par> par;
116    Bonmin::BonminCbcParam minlpParams_;
117
118public:
119
120    /**@name Constructors and destructors */
121    //@{
122    /// Default constructor
123    BM_tm() {}
124
125    /// Default destructor
126    virtual ~BM_tm() {}
127    //@}
128
129    /**@name Packing and unpacking methods */
130    //@{
131    virtual void pack_module_data(BCP_buffer& buf, BCP_process_t ptype);
132
133    virtual void pack_cut_algo(const BCP_cut_algo* cut, BCP_buffer& buf) {
134        BB_pack_cut(cut, buf);
135    }
136    virtual BCP_cut_algo* unpack_cut_algo(BCP_buffer& buf) {
137        return BB_unpack_cut(buf);
138    }
139
140    virtual BCP_solution* unpack_feasible_solution(BCP_buffer& buf);
141
142    /// Packing of user data
143    virtual void pack_user_data(const BCP_user_data* ud, BCP_buffer& buf);
144
145    /// Unpacking of user_data
146    virtual BCP_user_data* unpack_user_data(BCP_buffer& buf);
147    //@}
148
149    /// Pass the core constraints and core variables to bcp
150    virtual void initialize_core(BCP_vec<BCP_var_core*>& vars,
151                                 BCP_vec<BCP_cut_core*>& cuts,
152                                 BCP_lp_relax*& matrix);
153
154    /** Create the set of extra variables and cuts that should be added to the
155        formulation in the root node. Also decide how variable pricing shuld be
156        done, that is, if column generation is requested in the
157        init_new_phase() method of this class then column
158        generation should be performed according to \c pricing_status.
159    */
160    virtual void
161    create_root(BCP_vec<BCP_var*>& added_vars,
162                BCP_vec<BCP_cut*>& added_cuts,
163                BCP_user_data*& user_data);
164
165    /// Print a feasible solution
166    virtual void display_feasible_solution(const BCP_solution* sol);
167
168    /** What is the process id of the current process */
169    const BCP_proc_id*
170    process_id() const;
171    /** Send a message to a particular process */
172    void
173    send_message(const BCP_proc_id* const target, const BCP_buffer& buf);
174    /** Broadcast the message to all processes of the given type */
175    void
176    broadcast_message(const BCP_process_t proc_type, const BCP_buffer& buf);
177    /** Process a message that has been sent by another process' user part to
178        this process' user part. */
179    virtual void
180    process_message(BCP_buffer& buf);
181
182    /// Output the final solution
183    virtual void display_final_information(const BCP_lp_statistics& lp_stat);
184
185    virtual void init_new_phase(int phase,
186                                BCP_column_generation& colgen,
187                                CoinSearchTreeBase*& candidates);
188
189    void readIpopt();
190
191  private:
192
193  /// auxilliary method for handling output for AMPL
194  void write_AMPL_solution(const BCP_solution* sol,
195                           bool write_file, bool write_screen);
196
197};
198
199//#############################################################################
200
201#include <OsiAuxInfo.hpp>
202#include <OsiCuts.hpp>
203#include "CglGomory.hpp"
204#include "CglProbing.hpp"
205#include "CglKnapsackCover.hpp"
206#include "CglMixedIntegerRounding.hpp"
207#include "BonOaFeasChecker.hpp"
208#include "BonOaNlpOptim.hpp"
209#include "BonEcpCuts.hpp"
210#include "BonOACutGenerator2.hpp"
211
212#include "BCP_lp_user.hpp"
213#include "BonAmplSetup.hpp"
214
215class BM_lp : public BCP_lp_user
216{
217    BCP_string ipopt_file_content;
218    BCP_string nl_file_content;
219    BCP_parameter_set<BM_par> par;
220
221    OsiBabSolver babSolver_;
222    /** PIERRE: This contains the setup for running Bonmin in particular nlp solver, continuous solver,
223      cut generators,...*/
224    Bonmin::BonminAmplSetup bonmin_;
225
226    CoinWarmStart* ws_;
227    OsiChooseVariable* chooseVar_;
228    int numEcpRounds_;
229    int numberStrong_;
230    int minReliability_;
231    int varselect_;
232    double integerTolerance_;
233    double cutOffDecrement_;
234
235#if 0
236    /* A couple of cut generators to be used in the hybrid method */
237    CglGomory miGGen_;
238    CglProbing probGen_;
239    CglKnapsackCover knapsackGen_;
240    CglMixedIntegerRounding mixedGen_;
241    Bonmin::OaNlpOptim oaGen_;
242    Bonmin::EcpCuts ecpGen_;
243    Bonmin::OACutGenerator2 oaDec_;
244    Bonmin::OaFeasibilityChecker feasCheck_;
245#endif
246    /* FIXME: gross cheating. works only for serial mode. Store the warmstart
247       informations in the lp process, do not send them over in user data or
248       anywhere. MUST be fixed. The map is indexed by the node index. */
249    std::map<int, CoinWarmStart*> warmStart;
250
251    double lower_bound_;
252    double* primal_solution_;
253
254    /** A counter for how many times in a row did the NLP code fail. When the
255        NLP fails we branch; hopefully it'll be OK in the children. If it
256        fails too many times in a row then we fathom the node: it's hopelessly
257        difficult. */
258    int numNlpFailed_;
259
260    OsiCuts cuts_;
261
262    /** The last free-to-busy ratio (among the LP processes) that the TM has
263        sent over. It is used to decide whether we want distributed strong
264        branching */
265    double freeToBusyRatio_;
266
267public:
268    BM_lp();
269    virtual ~BM_lp();
270
271    inline int& numNlpFailed() {
272        return (dynamic_cast<BM_node*>(get_user_data()))->numNlpFailed_;
273    }
274
275    virtual void
276    unpack_module_data(BCP_buffer& buf);
277
278    virtual void pack_cut_algo(const BCP_cut_algo* cut, BCP_buffer& buf) {
279        BB_pack_cut(cut, buf);
280    }
281    virtual BCP_cut_algo* unpack_cut_algo(BCP_buffer& buf) {
282        return BB_unpack_cut(buf);
283    }
284
285    virtual void
286    pack_feasible_solution(BCP_buffer& buf, const BCP_solution* sol);
287
288    virtual void
289    pack_user_data(const BCP_user_data* ud, BCP_buffer& buf);
290    virtual BCP_user_data*
291    unpack_user_data(BCP_buffer& buf);
292
293    /** What is the process id of the current process */
294    const BCP_proc_id*
295    process_id() const;
296    /** Send a message to a particular process */
297    void
298    send_message(const BCP_proc_id* const target, const BCP_buffer& buf);
299    /** Broadcast the message to all processes of the given type */
300    void
301    broadcast_message(const BCP_process_t proc_type, const BCP_buffer& buf);
302    /** Process a message that has been sent by another process' user part to
303        this process' user part. */
304    virtual void
305    process_message(BCP_buffer& buf);
306
307    virtual OsiSolverInterface *
308    initialize_solver_interface();
309
310    virtual BCP_solution*
311    test_feasibility(const BCP_lp_result& lp_result,
312                     const BCP_vec<BCP_var*>& vars,
313                     const BCP_vec<BCP_cut*>& cuts);
314    BCP_solution* test_feasibility_BB(const BCP_vec<BCP_var*>& vars);
315    BCP_solution* test_feasibility_hybrid(const BCP_lp_result& lp_result,
316                                          const BCP_vec<BCP_var*>& vars,
317                                          const BCP_vec<BCP_cut*>& cuts);
318
319    virtual void
320    generate_cuts_in_lp(const BCP_lp_result& lpres,
321                        const BCP_vec<BCP_var*>& vars,
322                        const BCP_vec<BCP_cut*>& cuts,
323                        BCP_vec<BCP_cut*>& new_cuts,
324                        BCP_vec<BCP_row*>& new_rows);
325    virtual void
326    cuts_to_rows(const BCP_vec<BCP_var*>& vars, // on what to expand
327                 BCP_vec<BCP_cut*>& cuts,       // what to expand
328                 BCP_vec<BCP_row*>& rows,       // the expanded rows
329                 // things that the user can use for lifting cuts if allowed
330                 const BCP_lp_result& lpres,
331                 BCP_object_origin origin, bool allow_multiple);
332    virtual double
333    compute_lower_bound(const double old_lower_bound,
334                        const BCP_lp_result& lpres,
335                        const BCP_vec<BCP_var*>& vars,
336                        const BCP_vec<BCP_cut*>& cuts);
337
338    virtual void 
339    initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
340                                    const BCP_vec<BCP_cut*>& cuts,
341                                    const BCP_vec<BCP_obj_status>& vs,
342                                    const BCP_vec<BCP_obj_status>& cs,
343                                    BCP_vec<int>& var_changed_pos,
344                                    BCP_vec<double>& var_new_bd,
345                                    BCP_vec<int>& cut_changed_pos,
346                                    BCP_vec<double>& cut_new_bd);
347
348    virtual BCP_branching_decision
349    select_branching_candidates(const BCP_lp_result& lpres,
350                                const BCP_vec<BCP_var*>& vars,
351                                const BCP_vec<BCP_cut*>& cuts,
352                                const BCP_lp_var_pool& local_var_pool,
353                                const BCP_lp_cut_pool& local_cut_pool,
354                                BCP_vec<BCP_lp_branching_object*>& cans);
355
356    BCP_branching_decision bbBranch(OsiBranchingInformation& brInfo,
357                                    BCP_vec<BCP_lp_branching_object*>& cands);
358    BCP_branching_decision hybridBranch();
359
360    virtual void
361    set_user_data_for_children(BCP_presolved_lp_brobj* best, 
362                               const int selected);
363
364    virtual void
365    modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching);
366
367private:
368    /* There's no totalTime_ and nodeTime_. Look at the top of BM.cpp */
369    //   double totalTime_;
370    //   double nodeTime_;
371    int in_strong;
372
373};
374
375//#############################################################################
376
377#include "BCP_USER.hpp"
378
379class BM_init : public USER_initialize {
380
381public:
382
383    virtual BCP_tm_user * tm_init(BCP_tm_prob& p,
384                                  const int argnum,
385                                  const char * const * arglist);
386
387    virtual BCP_lp_user * lp_init(BCP_lp_prob& p);
388};
389
390//#############################################################################
391
392class BM_solution : public BCP_solution { 
393public:
394    double _objective;
395    BCP_vec<int> _ind;
396    BCP_vec<double> _values;
397
398public:
399    BM_solution() : _objective(0), _ind(), _values() {}
400    virtual ~BM_solution() {}
401
402    inline virtual double objective_value() const { return _objective; }
403    inline void setObjective(double obj) { _objective = obj; }
404
405    void add_entry(int i, double value) {
406        _ind.push_back(i);
407        _values.push_back(value);
408    }
409};
410
411#endif
Note: See TracBrowser for help on using the repository browser.