00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef _BM_H
00011 #define _BM_H
00012
00013 #include "BCP_USER.hpp"
00014 #include "BCP_parameters.hpp"
00015 #include "BCP_tm_user.hpp"
00016 #include "BCP_lp_user.hpp"
00017
00018 #include "BB_cut.hpp"
00019
00020 #include "BonIpoptWarmStart.hpp"
00021
00022 #define BM_DISREGARD_SOS
00023
00024
00025
00026 class BM_node : public BCP_user_data {
00027 public:
00032 int numNlpFailed_;
00033 public:
00034 BM_node() : numNlpFailed_(0) {}
00035 BM_node(BCP_buffer& buf) : numNlpFailed_(0) {
00036 buf.unpack(numNlpFailed_);
00037 }
00038 ~BM_node() {}
00039
00040 inline void pack(BCP_buffer& buf) const {
00041 buf.pack(numNlpFailed_);
00042 }
00043 };
00044
00045
00046
00047 enum BM_message {
00048 BM_StrongBranchRequest,
00049 BM_StrongBranchResult,
00050 BM_PseudoCostUpdate
00051 };
00052
00053 enum BM_BoundChange {
00054 BM_Var_DownBranch,
00055 BM_Var_UpBranch
00056 };
00057
00058
00059
00060 class BM_par {
00061 public:
00062 enum chr_params {
00063
00064 DisregardPriorities,
00065 PrintBranchingInfo,
00066 end_of_chr_params
00067 };
00068 enum int_params {
00069
00070 UsePseudoCosts,
00071 DecreasingSortInSetupList,
00072 PreferHighCombinationInBranching,
00073 NumNlpFailureMax,
00074
00075
00076
00077 SBNumBranchesInRoot,
00078
00079 SBNumBranchesInTree,
00080
00081
00082
00083 SBMaxLevel,
00084
00085 end_of_int_params
00086 };
00087 enum dbl_params {
00088 dummy_dbl_param,
00089
00090 end_of_dbl_params
00091 };
00092 enum str_params {
00093 NL_filename,
00094 IpoptParamfile,
00095
00096 end_of_str_params
00097 };
00098 enum str_array_params {
00099 dummy_str_array_param,
00100
00101 end_of_str_array_params
00102 };
00103 };
00104
00105
00106
00107 class BM_stats {
00108 public:
00109 BM_stats() :
00110 numberNodeSolves_(0),
00111 numberSbSolves_(0),
00112 numberFixed_(0),
00113 numberStrongBranching_(0),
00114 sumStrongBranchingListIndices_(0),
00115 sumStrongBranchingListPositions_(0.)
00116 {}
00117
00118 ~BM_stats();
00119
00120 inline void incNumberNodeSolves() {
00121 numberNodeSolves_++;
00122 }
00123 inline void incNumberSbSolves(int cnt) {
00124 numberSbSolves_ += cnt;
00125 }
00126 inline void incNumberFixed() {
00127 numberFixed_++;
00128 }
00129 inline void updateStrongBrachingInfo(int chosenIndex, int listLength) {
00130 numberStrongBranching_++;
00131 sumStrongBranchingListIndices_ += chosenIndex;
00132 sumStrongBranchingListPositions_ +=
00133 (double)(listLength-chosenIndex)/(double)listLength;
00134 }
00135 private:
00137 int numberNodeSolves_;
00139 int numberSbSolves_;
00141 int numberFixed_;
00143 int numberStrongBranching_;
00145 int sumStrongBranchingListIndices_;
00147 double sumStrongBranchingListPositions_;
00148 };
00149
00150
00151
00152
00153
00154 struct BM_BranchData {
00155
00156 int changeType;
00157 int objInd;
00158 int colInd;
00159 double solval;
00160 double bd;
00161
00162 int status;
00163 double objval;
00164 int iter;
00165 double time;
00166 };
00167
00168
00169
00170 class BM_tm : public BCP_tm_user {
00171
00172 public:
00173
00175 BCP_string ipopt_file_content;
00176 BCP_string nl_file_content;
00177 BCP_parameter_set<BM_par> par;
00178 OsiPseudoCosts pseudoCosts_;
00179
00180 public:
00181
00184
00185 BM_tm() {}
00186
00188 virtual ~BM_tm() {}
00190
00193 virtual void pack_module_data(BCP_buffer& buf, BCP_process_t ptype);
00194
00196
00198 virtual void initialize_core(BCP_vec<BCP_var_core*>& vars,
00199 BCP_vec<BCP_cut_core*>& cuts,
00200 BCP_lp_relax*& matrix);
00201
00208 virtual void
00209 create_root(BCP_vec<BCP_var*>& added_vars,
00210 BCP_vec<BCP_cut*>& added_cuts,
00211 BCP_user_data*& user_data);
00212
00214 virtual void display_feasible_solution(const BCP_solution* sol);
00215
00218 virtual void
00219 process_message(BCP_buffer& buf);
00220
00221 void receive_pseudo_cost_update(BCP_buffer& buf);
00222 void pack_pseudo_costs(BCP_buffer& buf);
00223
00225 virtual void display_final_information(const BCP_lp_statistics& lp_stat);
00226
00227 virtual void init_new_phase(int phase,
00228 BCP_column_generation& colgen,
00229 CoinSearchTreeBase*& candidates);
00230
00231 void readIpopt();
00232
00233 private:
00234
00236 void write_AMPL_solution(const BCP_solution* sol,
00237 bool write_file, bool write_screen);
00238
00239 };
00240
00241
00242
00243 struct BM_SB_result
00244 {
00246 int branchEval;
00247 int objInd;
00248 int colInd;
00249 int status[2];
00250 int iter[2];
00251 double objval[2];
00252 double varChange[2];
00253 double time[2];
00254 };
00255
00256
00257
00258 #include <OsiAuxInfo.hpp>
00259 #include <OsiCuts.hpp>
00260 #include "CglGomory.hpp"
00261 #include "CglProbing.hpp"
00262 #include "CglKnapsackCover.hpp"
00263 #include "CglMixedIntegerRounding.hpp"
00264 #include "BonOaFeasChecker.hpp"
00265 #include "BonOaNlpOptim.hpp"
00266 #include "BonEcpCuts.hpp"
00267 #include "BonOACutGenerator2.hpp"
00268
00269 #include "BCP_lp_user.hpp"
00270 #include "BonAmplSetup.hpp"
00271 #include "BonChooseVariable.hpp"
00272
00273 class BM_lp : public BCP_lp_user
00274 {
00275
00276
00277
00278 int in_strong;
00279
00280 BCP_string ipopt_file_content;
00281 BCP_string nl_file_content;
00282 BCP_parameter_set<BM_par> par;
00283 BCP_buffer bm_buf;
00284
00287 Bonmin::BonminAmplSetup bonmin_;
00288
00289 double integerTolerance_;
00290
00295 int numNlpFailed_;
00296
00297 OsiCuts cuts_;
00298
00302 int* objInd_;
00303 int objNum_;
00304
00313 int* infInd_;
00314 double* infUseful_;
00315 int infNum_;
00316 int* feasInd_;
00317 double* feasUseful_;
00318 int feasNum_;
00319
00322 BM_SB_result* sbResult_;
00324 BM_SB_result* bestSbResult_;
00325
00327 double node_start_time;
00328
00330 BM_stats bm_stats;
00331
00332 public:
00333 BM_lp();
00334 virtual ~BM_lp();
00335
00336 inline int& numNlpFailed() {
00337 return (dynamic_cast<BM_node*>(get_user_data()))->numNlpFailed_;
00338 }
00339
00340 virtual void
00341 unpack_module_data(BCP_buffer& buf);
00342
00345 virtual void
00346 process_message(BCP_buffer& buf);
00347
00348 virtual OsiSolverInterface *
00349 initialize_solver_interface();
00350
00351 virtual void
00352 load_problem(OsiSolverInterface& osi, BCP_problem_core* core,
00353 BCP_var_set& vars, BCP_cut_set& cuts);
00354
00355 virtual void
00356 modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching);
00357
00358 virtual BCP_solution*
00359 test_feasibility(const BCP_lp_result& lp_result,
00360 const BCP_vec<BCP_var*>& vars,
00361 const BCP_vec<BCP_cut*>& cuts);
00362 BCP_solution* test_feasibility_BB(const BCP_lp_result& lp_result,
00363 const BCP_vec<BCP_var*>& vars);
00364 BCP_solution* test_feasibility_hybrid(const BCP_lp_result& lp_result,
00365 const BCP_vec<BCP_var*>& vars,
00366 const BCP_vec<BCP_cut*>& cuts);
00367
00368 virtual void
00369 generate_cuts_in_lp(const BCP_lp_result& lpres,
00370 const BCP_vec<BCP_var*>& vars,
00371 const BCP_vec<BCP_cut*>& cuts,
00372 BCP_vec<BCP_cut*>& new_cuts,
00373 BCP_vec<BCP_row*>& new_rows);
00374 virtual void
00375 cuts_to_rows(const BCP_vec<BCP_var*>& vars,
00376 BCP_vec<BCP_cut*>& cuts,
00377 BCP_vec<BCP_row*>& rows,
00378
00379 const BCP_lp_result& lpres,
00380 BCP_object_origin origin, bool allow_multiple);
00381 virtual double
00382 compute_lower_bound(const double old_lower_bound,
00383 const BCP_lp_result& lpres,
00384 const BCP_vec<BCP_var*>& vars,
00385 const BCP_vec<BCP_cut*>& cuts);
00386
00387 virtual void
00388 initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
00389 const BCP_vec<BCP_cut*>& cuts,
00390 const BCP_vec<BCP_obj_status>& vs,
00391 const BCP_vec<BCP_obj_status>& cs,
00392 BCP_vec<int>& var_changed_pos,
00393 BCP_vec<double>& var_new_bd,
00394 BCP_vec<int>& cut_changed_pos,
00395 BCP_vec<double>& cut_new_bd);
00396
00397 virtual BCP_branching_decision
00398 select_branching_candidates(const BCP_lp_result& lpres,
00399 const BCP_vec<BCP_var*>& vars,
00400 const BCP_vec<BCP_cut*>& cuts,
00401 const BCP_lp_var_pool& local_var_pool,
00402 const BCP_lp_cut_pool& local_cut_pool,
00403 BCP_vec<BCP_lp_branching_object*>& cans,
00404 bool force_branch = false);
00405
00406 BCP_branching_decision bbBranch(OsiBranchingInformation& brInfo,
00407 BCP_vec<BCP_lp_branching_object*>& cands);
00408 BCP_branching_decision hybridBranch();
00409
00411 void send_pseudo_cost_update(OsiBranchingInformation& branchInfo);
00412 void unpack_pseudo_costs(BCP_buffer& buf);
00413 int sort_objects(OsiBranchingInformation& branchInfo,
00414 Bonmin::BonChooseVariable* choose, int& branchNum);
00415 void clear_SB_results();
00416 void collect_branch_data(OsiBranchingInformation& branchInfo,
00417 OsiSolverInterface* solver,
00418 const int branchNum,
00419 BM_BranchData* branchData);
00420 void do_distributed_SB(OsiBranchingInformation& branchInfo,
00421 OsiSolverInterface* solver,
00422 const CoinWarmStart* cws,
00423 const int branchNum,
00424 const int* pids, const int pidNum);
00425 bool isBranchFathomable(int status, double obj);
00426 int process_SB_results(OsiBranchingInformation& branchInfo,
00427 OsiSolverInterface* solver,
00428 Bonmin::BonChooseVariable* choose,
00429 OsiBranchingObject*& branchObject);
00430 int try_to_branch(OsiBranchingInformation& branchInfo,
00431 OsiSolverInterface* solver,
00432 Bonmin::BonChooseVariable* choose,
00433 OsiBranchingObject*& branchObject,
00434 bool allowVarFix);
00435
00436 virtual void
00437 set_user_data_for_children(BCP_presolved_lp_brobj* best,
00438 const int selected);
00439
00440 };
00441
00442
00443
00444 #include "BCP_USER.hpp"
00445
00446 class BM_pack : public BCP_user_pack {
00447 public:
00448 virtual ~BM_pack() {}
00449
00450 virtual void pack_user_data(const BCP_user_data* ud, BCP_buffer& buf);
00451 virtual BCP_user_data* unpack_user_data(BCP_buffer& buf);
00452
00453 virtual void pack_cut_algo(const BCP_cut_algo* cut, BCP_buffer& buf);
00454 virtual BCP_cut_algo* unpack_cut_algo(BCP_buffer& buf);
00455
00456 };
00457
00458
00459
00460 class BM_init : public USER_initialize {
00461
00462 public:
00463
00464 virtual BCP_tm_user * tm_init(BCP_tm_prob& p,
00465 const int argnum,
00466 const char * const * arglist);
00467
00468 virtual BCP_lp_user * lp_init(BCP_lp_prob& p);
00469
00470 virtual BCP_user_pack * packer_init(BCP_user_class* p);
00471 };
00472
00473 #endif