/home/coin/SVN-release/Bcp-1.2.1/Applications/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    // Pack an algorithmic cut
00056    virtual void
00057    pack_cut_algo(const BCP_cut_algo* cut, BCP_buffer& buf);
00058    //--------------------------------------------------------------------------
00059    // Unpack an algorithmic cut
00060    virtual BCP_cut_algo*
00061    unpack_cut_algo(BCP_buffer& buf);
00062    //--------------------------------------------------------------------------
00063    // Override the initializer so that we can choose between vol and simplex
00064    // at runtime.
00065    virtual OsiSolverInterface *
00066    initialize_solver_interface();
00067    
00068    //--------------------------------------------------------------------------
00069    // Opportunity to reset things before optimization
00070    virtual void
00071    modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching);
00072    //--------------------------------------------------------------------------
00073    // Feasibility testing
00074    virtual BCP_solution*
00075    test_feasibility(const BCP_lp_result& lp_result,
00076                     const BCP_vec<BCP_var*>& vars,
00077                     const BCP_vec<BCP_cut*>& cuts);
00080    virtual BCP_solution*
00081    generate_heuristic_solution(const BCP_lp_result& lpres,
00082                                const BCP_vec<BCP_var*>& vars,
00083                                const BCP_vec<BCP_cut*>& cuts);
00085    MC_solution*
00086    mc_generate_heuristic_solution(const double* x,
00087                                   const BCP_vec<BCP_var*>& vars,
00088                                   const BCP_vec<BCP_cut*>& cuts);
00089    //--------------------------------------------------------------------------
00090    // feasible solution packing
00091    virtual void
00092    pack_feasible_solution(BCP_buffer& buf, const BCP_solution* sol);
00093    //--------------------------------------------------------------------------
00094    // Convert the user generated cuts into rows
00095    virtual void
00096    cuts_to_rows(const BCP_vec<BCP_var*>& vars, // on what to expand
00097                 BCP_vec<BCP_cut*>& cuts,       // what to expand
00098                 BCP_vec<BCP_row*>& rows,       // the expanded rows
00099                 // things that the user can use for lifting cuts if allowed
00100                 const BCP_lp_result& lpres,
00101                 BCP_object_origin origin, bool allow_multiple);
00102    //--------------------------------------------------------------------------
00103    virtual void
00104    generate_cuts_in_lp(const BCP_lp_result& lpres,
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    generate_cuts_in_lp(const double* x, const double* lhs,
00111                        const double objval,
00112                        const BCP_vec<BCP_var*>& vars,
00113                        const BCP_vec<BCP_cut*>& cuts,
00114                        BCP_vec<BCP_cut*>& new_cuts,
00115                        BCP_vec<BCP_row*>& new_rows);
00116    void
00117    unique_cycle_cuts(BCP_vec<BCP_cut*>& new_cuts,
00118                      BCP_vec<BCP_row*>& new_rows);
00119    void
00120    generate_mst_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    void
00127    generate_sp_cuts(const double* x, const double* lhs,
00128                     const double objval,
00129                     const BCP_vec<BCP_var*>& vars,
00130                     const BCP_vec<BCP_cut*>& cuts,
00131                     BCP_vec<BCP_cut*>& new_cuts,
00132                     BCP_vec<BCP_row*>& new_rows);
00133    double
00134    getMaxLpViol();
00135    //--------------------------------------------------------------------------
00136       virtual BCP_object_compare_result
00137    compare_cuts(const BCP_cut* c0, const BCP_cut* c1);
00138    //--------------------------------------------------------------------------
00139    virtual void
00140    logical_fixing(const BCP_lp_result& lpres,
00141                   const BCP_vec<BCP_var*>& vars,
00142                   const BCP_vec<BCP_cut*>& cuts,
00143                   const BCP_vec<BCP_obj_status>& var_status,
00144                   const BCP_vec<BCP_obj_status>& cut_status,
00145                   const int var_bound_changes_since_logical_fixing,
00146                   BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd);
00147    //--------------------------------------------------------------------------
00148    // Helper functions to check if there has been a tailing off in the past k
00149    // iterations
00150    //--------------------------------------------------------------------------
00151    bool
00152    is_gap_tailoff_rel(const int k, const double minimp,
00153                       const double objval) const;
00154    bool
00155    is_lb_tailoff_abs(const int k, const double minimp,
00156                      const double objval) const;
00157    bool
00158    is_lb_tailoff_rel(const int k, const double minimp,
00159                      const double objval) const;
00160    void
00161    tailoff_test(bool& tailoff_gap_rel, bool& tailoff_lb_abs,
00162                 bool& tailoff_lb_rel, const double objval) const;
00163    //--------------------------------------------------------------------------
00164    OsiSolverInterface* 
00165    solveToOpt(OsiVolSolverInterface* vollp,
00166               const BCP_lp_result& lpres,
00167               const BCP_vec<BCP_var*>& vars,
00168               const BCP_vec<BCP_cut*>& cuts,
00169               double& exact_obj);
00170    //--------------------------------------------------------------------------
00171    virtual BCP_branching_decision
00172    select_branching_candidates(const BCP_lp_result& lpres,
00173                                const BCP_vec<BCP_var*>& vars,
00174                                const BCP_vec<BCP_cut*>& cuts,
00175                                const BCP_lp_var_pool& local_var_pool,
00176                                const BCP_lp_cut_pool& local_cut_pool,
00177                                BCP_vec<BCP_lp_branching_object*>& candidates);
00178    void
00179    perform_strong_branching(const BCP_lp_result& lpres,
00180                             OsiSolverInterface* exact_solver,
00181                             BCP_vec<BCP_lp_branching_object*>& cands);
00182    void
00183    choose_branching_vars(const BCP_vec<BCP_var*>& vars, const double * x,
00184                          const int cand_num,
00185                          BCP_vec<BCP_lp_branching_object*>& cands);
00186    //--------------------------------------------------------------------------
00187    virtual BCP_branching_object_relation
00188    compare_branching_candidates(BCP_presolved_lp_brobj* new_presolved,
00189                                 BCP_presolved_lp_brobj* old_presolved);
00190    virtual void
00191    set_actions_for_children(BCP_presolved_lp_brobj* best);
00192 };
00193 
00194 #endif

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7