/home/coin/SVN-release/OS-2.4.0/Bcp/examples/MaxCut/include/MC_lp.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
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   // hold a history of objective values (for tailing off, until it's
00025   // implemented in BCP
00026   int hist_len;
00027   double* objhist;
00028   // hold the solution generated during cycle cut generation and return it in
00029   // generate_heuristic_solution()
00030   MC_solution* soln;
00031   // Whether we have started to solve the problems to optimality
00032   bool started_exact;
00033   bool tried_hard_cuts_in_prev_major_iter;
00034 
00035   // When using the volume alg in general, but solving to optimality with
00036   // simplex using the reduced costs wrt. the duals of the volume, obj_shift
00037   // is constant term after the cost transformation
00038   double obj_shift;
00039   // the presolved best candidate
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   // unpack the module data for the appropriate process
00052   virtual void
00053   unpack_module_data(BCP_buffer & buf);
00054   //--------------------------------------------------------------------------
00055   // Override the initializer so that we can choose between vol and simplex
00056   // at runtime.
00057   virtual OsiSolverInterface *
00058   initialize_solver_interface();
00059    
00060   //--------------------------------------------------------------------------
00061   // Opportunity to reset things before optimization
00062   virtual void
00063   modify_lp_parameters(OsiSolverInterface* lp, const int changeType,
00064                        bool in_strong_branching);
00065   //--------------------------------------------------------------------------
00066   // Feasibility testing
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   // feasible solution packing
00084   virtual void
00085   pack_feasible_solution(BCP_buffer& buf, const BCP_solution* sol);
00086   //--------------------------------------------------------------------------
00087   // Convert the user generated cuts into rows
00088   virtual void
00089   cuts_to_rows(const BCP_vec<BCP_var*>& vars, // on what to expand
00090                BCP_vec<BCP_cut*>& cuts,       // what to expand
00091                BCP_vec<BCP_row*>& rows,       // the expanded rows
00092                // things that the user can use for lifting cuts if allowed
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   // Helper functions to check if there has been a tailing off in the past k
00142   // iterations
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

Generated on Thu Sep 22 03:05:50 2011 by  doxygen 1.4.7