00001
00002
00003 #ifndef _MC_LP_H
00004 #define _MC_LP_H
00005
00006 #include "BCP_lp_user.hpp"
00007 #include "BCP_parameters.hpp"
00008
00009 #include "MC.hpp"
00010 #include "MC_solution.hpp"
00011 #include "MC_lp_param.hpp"
00012
00013 class OsiVolSolverInterface;
00014 class OsiSolverInterface;
00015
00016 class MC_lp : public BCP_lp_user {
00017 private:
00018 MC_lp(const MC_lp&);
00019 MC_lp& operator=(const MC_lp&);
00020 public:
00021 BCP_parameter_set<MC_lp_par> par;
00022 MC_problem mc;
00023
00024
00025
00026 int hist_len;
00027 double* objhist;
00028
00029
00030 MC_solution* soln;
00031
00032 bool started_exact;
00033 bool tried_hard_cuts_in_prev_major_iter;
00034
00035
00036
00037
00038 double obj_shift;
00039
00040 BCP_presolved_lp_brobj* best_presolved;
00041
00042 public:
00043 MC_lp() : par(), mc(), objhist(0), soln(0), started_exact(false),
00044 tried_hard_cuts_in_prev_major_iter(false), best_presolved(0) {}
00045 ~MC_lp() {
00046 delete[] objhist;
00047 delete soln;
00048 }
00049
00050
00051
00052 virtual void
00053 unpack_module_data(BCP_buffer & buf);
00054
00055
00056
00057 virtual OsiSolverInterface *
00058 initialize_solver_interface();
00059
00060
00061
00062 virtual void
00063 modify_lp_parameters(OsiSolverInterface* lp, const int changeType,
00064 bool in_strong_branching);
00065
00066
00067 virtual BCP_solution*
00068 test_feasibility(const BCP_lp_result& lp_result,
00069 const BCP_vec<BCP_var*>& vars,
00070 const BCP_vec<BCP_cut*>& cuts);
00073 virtual BCP_solution*
00074 generate_heuristic_solution(const BCP_lp_result& lpres,
00075 const BCP_vec<BCP_var*>& vars,
00076 const BCP_vec<BCP_cut*>& cuts);
00078 MC_solution*
00079 mc_generate_heuristic_solution(const double* x,
00080 const BCP_vec<BCP_var*>& vars,
00081 const BCP_vec<BCP_cut*>& cuts);
00082
00083
00084 virtual void
00085 pack_feasible_solution(BCP_buffer& buf, const BCP_solution* sol);
00086
00087
00088 virtual void
00089 cuts_to_rows(const BCP_vec<BCP_var*>& vars,
00090 BCP_vec<BCP_cut*>& cuts,
00091 BCP_vec<BCP_row*>& rows,
00092
00093 const BCP_lp_result& lpres,
00094 BCP_object_origin origin, bool allow_multiple);
00095
00096 virtual void
00097 generate_cuts_in_lp(const BCP_lp_result& lpres,
00098 const BCP_vec<BCP_var*>& vars,
00099 const BCP_vec<BCP_cut*>& cuts,
00100 BCP_vec<BCP_cut*>& new_cuts,
00101 BCP_vec<BCP_row*>& new_rows);
00102 void
00103 generate_cuts_in_lp(const double* x, const double* lhs,
00104 const double objval,
00105 const BCP_vec<BCP_var*>& vars,
00106 const BCP_vec<BCP_cut*>& cuts,
00107 BCP_vec<BCP_cut*>& new_cuts,
00108 BCP_vec<BCP_row*>& new_rows);
00109 void
00110 unique_cycle_cuts(BCP_vec<BCP_cut*>& new_cuts,
00111 BCP_vec<BCP_row*>& new_rows);
00112 void
00113 generate_mst_cuts(const double* x, const double* lhs,
00114 const double objval,
00115 const BCP_vec<BCP_var*>& vars,
00116 const BCP_vec<BCP_cut*>& cuts,
00117 BCP_vec<BCP_cut*>& new_cuts,
00118 BCP_vec<BCP_row*>& new_rows);
00119 void
00120 generate_sp_cuts(const double* x, const double* lhs,
00121 const double objval,
00122 const BCP_vec<BCP_var*>& vars,
00123 const BCP_vec<BCP_cut*>& cuts,
00124 BCP_vec<BCP_cut*>& new_cuts,
00125 BCP_vec<BCP_row*>& new_rows);
00126 double
00127 getMaxLpViol();
00128
00129 virtual BCP_object_compare_result
00130 compare_cuts(const BCP_cut* c0, const BCP_cut* c1);
00131
00132 virtual void
00133 logical_fixing(const BCP_lp_result& lpres,
00134 const BCP_vec<BCP_var*>& vars,
00135 const BCP_vec<BCP_cut*>& cuts,
00136 const BCP_vec<BCP_obj_status>& var_status,
00137 const BCP_vec<BCP_obj_status>& cut_status,
00138 const int var_bound_changes_since_logical_fixing,
00139 BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd);
00140
00141
00142
00143
00144 bool
00145 is_gap_tailoff_rel(const int k, const double minimp,
00146 const double objval) const;
00147 bool
00148 is_lb_tailoff_abs(const int k, const double minimp,
00149 const double objval) const;
00150 bool
00151 is_lb_tailoff_rel(const int k, const double minimp,
00152 const double objval) const;
00153 void
00154 tailoff_test(bool& tailoff_gap_rel, bool& tailoff_lb_abs,
00155 bool& tailoff_lb_rel, const double objval) const;
00156
00157 OsiSolverInterface*
00158 solveToOpt(OsiVolSolverInterface* vollp,
00159 const BCP_lp_result& lpres,
00160 const BCP_vec<BCP_var*>& vars,
00161 const BCP_vec<BCP_cut*>& cuts,
00162 double& exact_obj);
00163
00164 virtual BCP_branching_decision
00165 select_branching_candidates(const BCP_lp_result& lpres,
00166 const BCP_vec<BCP_var*>& vars,
00167 const BCP_vec<BCP_cut*>& cuts,
00168 const BCP_lp_var_pool& local_var_pool,
00169 const BCP_lp_cut_pool& local_cut_pool,
00170 BCP_vec<BCP_lp_branching_object*>& candidates,
00171 bool force_branch = false);
00172 void
00173 perform_strong_branching(const BCP_lp_result& lpres,
00174 OsiSolverInterface* exact_solver,
00175 BCP_vec<BCP_lp_branching_object*>& cands);
00176 void
00177 choose_branching_vars(const BCP_vec<BCP_var*>& vars, const double * x,
00178 const int cand_num,
00179 BCP_vec<BCP_lp_branching_object*>& cands);
00180
00181 virtual BCP_branching_object_relation
00182 compare_branching_candidates(BCP_presolved_lp_brobj* new_presolved,
00183 BCP_presolved_lp_brobj* old_presolved);
00184 virtual void
00185 set_actions_for_children(BCP_presolved_lp_brobj* best);
00186 };
00187
00188 #endif