/home/coin/SVN-release/Bcp-1.2.1/Applications/Csp/include/CSP_lp.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2005, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _CSP_LP_H
00004 #define _CSP_LP_H
00005 
00006 #include <cfloat>
00007 #include <map>
00008 #include <vector>
00009 
00010 #include <OsiClpSolverInterface.hpp>
00011 
00012 #include "BCP_parameters.hpp"
00013 #include "BCP_lp_user.hpp"
00014 
00015 #include "CSP_lp_param.hpp"
00016 #include "CSP_var.hpp"
00017 #include "CSP_colgen.hpp"
00018 
00019 class CSP_lp : public BCP_lp_user {
00020   // private data
00021 private:
00022   // this is where we store the 
00023   // columns generated in the compute_lower_bound method
00024   // for use elsewhere in our application. 
00025    std::vector<PATTERN*> improving_patterns_;
00026 
00027   // public data
00028 public:
00029    BCP_parameter_set<CSP_lp_par> par;
00030 
00031   // pointer to the static problem information
00032   // there's only one LP module, so no need to declare this "static"
00033   CSPROBLEM* csproblem;
00034 
00035   CSP_colgen* colgen;
00036 
00037   // public methods
00038 public:
00039   // constructor
00040   CSP_lp() : csproblem(0), colgen(0) {}
00041 
00042   // destructor
00043   ~CSP_lp() {
00044     std::for_each(improving_patterns_.begin(),
00045                   improving_patterns_.end(), DELETEOBJECT());
00046     delete csproblem;
00047     delete colgen;
00048   }
00049 
00050    //==========================================================================
00056   // inherited methods
00057    virtual void
00058    unpack_module_data(BCP_buffer & buf);
00059 
00061    virtual void
00062    pack_var_algo(const BCP_var_algo* var, BCP_buffer& buf) {
00063       CSP_var_pack(var, buf);
00064    }
00065 
00067    virtual BCP_var_algo*
00068    unpack_var_algo(BCP_buffer& buf) {
00069       return CSP_var_unpack(buf);
00070    }
00071       
00072    //==========================================================================
00082    virtual OsiSolverInterface *
00083    initialize_solver_interface();
00084 
00085    //==========================================================================
00102    // *LL* : needs to be written if when we'll do real column generation. Then
00103    // *LL* : we'll need to figure out the previous branching decisions. For
00104    // *LL* : now we just do B&B, so we don't need this.
00105    
00106    virtual void
00107    initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
00108                                    const BCP_vec<BCP_cut*>& cuts,
00109                                    const BCP_vec<BCP_obj_status>& var_status,
00110                                    const BCP_vec<BCP_obj_status>& cut_status,
00111                                    BCP_vec<int>& var_changed_pos,
00112                                    BCP_vec<double>& var_new_bd,
00113                                    BCP_vec<int>& cut_changed_pos,
00114                                    BCP_vec<double>& cut_new_bd);
00115 
00116    //==========================================================================
00123    virtual void
00124    modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching);
00125 
00126    //==========================================================================
00136    virtual double
00137    compute_lower_bound(const double old_lower_bound,
00138                        const BCP_lp_result& lpres,
00139                        const BCP_vec<BCP_var*>& vars,
00140                        const BCP_vec<BCP_cut*>& cuts);
00141    //==========================================================================
00142 
00158    // *LL* : sufficient to test binary-ness, 
00159 #if 0
00160    virtual BCP_solution*
00161    test_feasibility(const BCP_lp_result& lpres,
00162                     const BCP_vec<BCP_var*>& vars,
00163                     const BCP_vec<BCP_cut*>& cuts);
00164 #endif
00165    //==========================================================================
00170    // *LL* : should be written even for B&B (to find good soln's quickly) and
00171    // *LL* : definitely for column generation, but for now it's not an
00172    // *LL* : absolute necessity.
00173 
00174   // This code invokes the default (do nothing) function in BCP
00175   //   virtual BCP_solution*
00176   // generate_heuristic_solution(const BCP_lp_result& lpres,
00177   //                           const BCP_vec<BCP_var*>& vars,
00178   //                           const BCP_vec<BCP_cut*>& cuts) {
00179   //   return BCP_lp_user::generate_heuristic_solution(lpres, vars, cuts);
00180   // }
00181 
00182 
00183   virtual BCP_solution*
00184   generate_heuristic_solution(const BCP_lp_result& lpres,
00185                               const BCP_vec<BCP_var*>& vars,
00186                               const BCP_vec<BCP_cut*>& cuts);
00187   
00188    //==========================================================================
00195   // get one dual ray from the solver, and try to generate columns that cut
00196   // off the  dual ray. 
00197   // RLH: need to write.
00198    virtual void
00199    restore_feasibility(const BCP_lp_result& lpres,
00200                        const std::vector<double*> dual_rays,
00201                        const BCP_vec<BCP_var*>& vars,
00202                        const BCP_vec<BCP_cut*>& cuts,
00203                        BCP_vec<BCP_var*>& vars_to_add,
00204                        BCP_vec<BCP_col*>& cols_to_add);
00205 
00206    //==========================================================================
00227    virtual void
00228    vars_to_cols(const BCP_vec<BCP_cut*>& cuts, // on what to expand
00229                 BCP_vec<BCP_var*>& vars,       // what to expand
00230                 BCP_vec<BCP_col*>& cols,       // the expanded cols
00231                 // things that the user can use for lifting vars if allowed
00232                 const BCP_lp_result& lpres,
00233                 BCP_object_origin origin, bool allow_multiple);
00234 
00235    void
00236    vars_to_cols(BCP_vec<BCP_var*>& vars,
00237                 BCP_vec<BCP_col*>& cols);
00238 
00239    //==========================================================================
00253    // *LL* : for now we don't have cuts, so the default is fine.
00254    virtual void
00255    generate_cuts_in_lp(const BCP_lp_result& lpres,
00256                        const BCP_vec<BCP_var*>& vars,
00257                        const BCP_vec<BCP_cut*>& cuts,
00258                        BCP_vec<BCP_cut*>& new_cuts,
00259                        BCP_vec<BCP_row*>& new_rows) {
00260       BCP_lp_user::generate_cuts_in_lp(lpres, vars, cuts, new_cuts, new_rows);
00261    }
00262 
00263    //==========================================================================
00280    virtual void
00281    generate_vars_in_lp(const BCP_lp_result& lpres,
00282                        const BCP_vec<BCP_var*>& vars,
00283                        const BCP_vec<BCP_cut*>& cuts,
00284                        const bool before_fathom,
00285                        BCP_vec<BCP_var*>& new_vars,
00286                        BCP_vec<BCP_col*>& new_cols);
00287 
00288    //==========================================================================
00296    // *LL* : for now we don't have cuts, so the default is fine.
00297    virtual BCP_object_compare_result
00298    compare_cuts(const BCP_cut* c0, const BCP_cut* c1) {
00299       return BCP_lp_user::compare_cuts(c0, c1);
00300    }
00301 
00302    //==========================================================================
00311    // *LL* : for now we have included every var in the formulation at the root
00312    // *LL* : node, so default is fine. Later we need to write this one.
00313    virtual BCP_object_compare_result
00314    compare_vars(const BCP_var* v0, const BCP_var* v1) {
00315       return BCP_lp_user::compare_vars(v0, v1);
00316    }
00317 
00318    //==========================================================================
00334    // *LL* : This is not a must, but would be nice to add setpacking matrix
00335    // *LL* : reduction techniques eventually. For now use the default.
00336    virtual void
00337    logical_fixing(const BCP_lp_result& lpres,
00338                   const BCP_vec<BCP_var*>& vars,
00339                   const BCP_vec<BCP_cut*>& cuts,
00340                   const BCP_vec<BCP_obj_status>& var_status,
00341                   const BCP_vec<BCP_obj_status>& cut_status,
00342                   const int var_bound_changes_since_logical_fixing,
00343                   BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd) {
00344       BCP_lp_user::logical_fixing(lpres, vars, cuts, var_status, cut_status,
00345                                   var_bound_changes_since_logical_fixing,
00346                                   changed_pos, new_bd);
00347    }
00348 
00349    //==========================================================================
00352    virtual BCP_branching_decision
00353    select_branching_candidates(const BCP_lp_result& lpres,
00354                                const BCP_vec<BCP_var*>& vars,
00355                                const BCP_vec<BCP_cut*>& cuts,
00356                                const BCP_lp_var_pool& local_var_pool,
00357                                const BCP_lp_cut_pool& local_cut_pool,
00358                                BCP_vec<BCP_lp_branching_object*>& cands);
00359    BCP_lp_branching_object*
00360    branch_on_half(const BCP_lp_result& lpres,
00361                   const BCP_vec<BCP_var*>& vars);
00362 
00363    //==========================================================================
00377    // *LL* : Use default for now
00378    // *LL* : Later we can play with integrality based branching
00379    virtual BCP_branching_object_relation
00380    compare_branching_candidates(BCP_presolved_lp_brobj* new_solved,
00381                                 BCP_presolved_lp_brobj* old_solved) {
00382       return BCP_lp_user::compare_branching_candidates(new_solved, old_solved);
00383    }
00384 
00385 
00386    //==========================================================================
00406    // *LL* : The THINK comment above will definitely
00407    // *LL* : apply when we'll do column generation
00408    virtual void
00409    set_actions_for_children(BCP_presolved_lp_brobj* best);
00410       
00411    //==========================================================================
00429    // *LL* : Used only when branching on dynamically generated cuts is
00430    // *LL* : allowed, but we don't generate cuts...
00431    virtual void
00432    purge_slack_pool(const BCP_vec<BCP_cut*>& slack_pool,
00433                     BCP_vec<int>& to_be_purged) {
00434       BCP_lp_user::purge_slack_pool(slack_pool, to_be_purged);
00435    }
00436 
00437 
00438    //==========================================================================
00439 
00440 };
00441 #endif

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