CSP_lp.hpp

Go to the documentation of this file.

// Copyright (C) 2005, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef _CSP_LP_H
#define _CSP_LP_H

#include <cfloat>
#include <map>
#include <vector>

#include <OsiClpSolverInterface.hpp>

#include "BCP_parameters.hpp"
#include "BCP_lp_user.hpp"

#include "CSP_lp_param.hpp"
#include "CSP_var.hpp"
#include "CSP_colgen.hpp"

class CSP_lp : public BCP_lp_user {
  // private data
private:
  // this is where we store the 
  // columns generated in the compute_lower_bound method
  // for use elsewhere in our application. 
   std::vector<PATTERN*> improving_patterns_;

  // public data
public:
   BCP_parameter_set<CSP_lp_par> par;

  // pointer to the static problem information
  // there's only one LP module, so no need to declare this "static"
  CSPROBLEM* csproblem;

  CSP_colgen* colgen;

  // public methods
public:
  // constructor
  CSP_lp() : csproblem(0), colgen(0) {}

  // destructor
  ~CSP_lp() {
    std::for_each(improving_patterns_.begin(),
                  improving_patterns_.end(), DELETEOBJECT());
    delete csproblem;
    delete colgen;
  }

   //==========================================================================
  // inherited methods
   virtual void
   unpack_module_data(BCP_buffer & buf);

   virtual void
   pack_var_algo(const BCP_var_algo* var, BCP_buffer& buf) {
      CSP_var_pack(var, buf);
   }

   virtual BCP_var_algo*
   unpack_var_algo(BCP_buffer& buf) {
      return CSP_var_unpack(buf);
   }
      
   //==========================================================================
   virtual OsiSolverInterface *
   initialize_solver_interface();

   //==========================================================================
   // *LL* : needs to be written if when we'll do real column generation. Then
   // *LL* : we'll need to figure out the previous branching decisions. For
   // *LL* : now we just do B&B, so we don't need this.
   
   virtual void
   initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
                                   const BCP_vec<BCP_cut*>& cuts,
                                   const BCP_vec<BCP_obj_status>& var_status,
                                   const BCP_vec<BCP_obj_status>& cut_status,
                                   BCP_vec<int>& var_changed_pos,
                                   BCP_vec<double>& var_new_bd,
                                   BCP_vec<int>& cut_changed_pos,
                                   BCP_vec<double>& cut_new_bd);

   //==========================================================================
   virtual void
   modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching);

   //==========================================================================
   virtual double
   compute_lower_bound(const double old_lower_bound,
                       const BCP_lp_result& lpres,
                       const BCP_vec<BCP_var*>& vars,
                       const BCP_vec<BCP_cut*>& cuts);
   //==========================================================================

   // *LL* : sufficient to test binary-ness, 
#if 0
   virtual BCP_solution*
   test_feasibility(const BCP_lp_result& lpres,
                    const BCP_vec<BCP_var*>& vars,
                    const BCP_vec<BCP_cut*>& cuts);
#endif
   //==========================================================================
   // *LL* : should be written even for B&B (to find good soln's quickly) and
   // *LL* : definitely for column generation, but for now it's not an
   // *LL* : absolute necessity.

  // This code invokes the default (do nothing) function in BCP
  //   virtual BCP_solution*
  // generate_heuristic_solution(const BCP_lp_result& lpres,
  //                           const BCP_vec<BCP_var*>& vars,
  //                           const BCP_vec<BCP_cut*>& cuts) {
  //   return BCP_lp_user::generate_heuristic_solution(lpres, vars, cuts);
  // }


  virtual BCP_solution*
  generate_heuristic_solution(const BCP_lp_result& lpres,
                              const BCP_vec<BCP_var*>& vars,
                              const BCP_vec<BCP_cut*>& cuts);
  
   //==========================================================================
  // get one dual ray from the solver, and try to generate columns that cut
  // off the  dual ray. 
  // RLH: need to write.
   virtual void
   restore_feasibility(const BCP_lp_result& lpres,
                       const std::vector<double*> dual_rays,
                       const BCP_vec<BCP_var*>& vars,
                       const BCP_vec<BCP_cut*>& cuts,
                       BCP_vec<BCP_var*>& vars_to_add,
                       BCP_vec<BCP_col*>& cols_to_add);

   //==========================================================================
   virtual void
   vars_to_cols(const BCP_vec<BCP_cut*>& cuts, // on what to expand
                BCP_vec<BCP_var*>& vars,       // what to expand
                BCP_vec<BCP_col*>& cols,       // the expanded cols
                // things that the user can use for lifting vars if allowed
                const BCP_lp_result& lpres,
                BCP_object_origin origin, bool allow_multiple);

   void
   vars_to_cols(BCP_vec<BCP_var*>& vars,
                BCP_vec<BCP_col*>& cols);

   //==========================================================================
   // *LL* : for now we don't have cuts, so the default is fine.
   virtual void
   generate_cuts_in_lp(const BCP_lp_result& lpres,
                       const BCP_vec<BCP_var*>& vars,
                       const BCP_vec<BCP_cut*>& cuts,
                       BCP_vec<BCP_cut*>& new_cuts,
                       BCP_vec<BCP_row*>& new_rows) {
      BCP_lp_user::generate_cuts_in_lp(lpres, vars, cuts, new_cuts, new_rows);
   }

   //==========================================================================
   virtual void
   generate_vars_in_lp(const BCP_lp_result& lpres,
                       const BCP_vec<BCP_var*>& vars,
                       const BCP_vec<BCP_cut*>& cuts,
                       const bool before_fathom,
                       BCP_vec<BCP_var*>& new_vars,
                       BCP_vec<BCP_col*>& new_cols);

   //==========================================================================
   // *LL* : for now we don't have cuts, so the default is fine.
   virtual BCP_object_compare_result
   compare_cuts(const BCP_cut* c0, const BCP_cut* c1) {
      return BCP_lp_user::compare_cuts(c0, c1);
   }

   //==========================================================================
   // *LL* : for now we have included every var in the formulation at the root
   // *LL* : node, so default is fine. Later we need to write this one.
   virtual BCP_object_compare_result
   compare_vars(const BCP_var* v0, const BCP_var* v1) {
      return BCP_lp_user::compare_vars(v0, v1);
   }

   //==========================================================================
   // *LL* : This is not a must, but would be nice to add setpacking matrix
   // *LL* : reduction techniques eventually. For now use the default.
   virtual void
   logical_fixing(const BCP_lp_result& lpres,
                  const BCP_vec<BCP_var*>& vars,
                  const BCP_vec<BCP_cut*>& cuts,
                  const BCP_vec<BCP_obj_status>& var_status,
                  const BCP_vec<BCP_obj_status>& cut_status,
                  const int var_bound_changes_since_logical_fixing,
                  BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd) {
      BCP_lp_user::logical_fixing(lpres, vars, cuts, var_status, cut_status,
                                  var_bound_changes_since_logical_fixing,
                                  changed_pos, new_bd);
   }

   //==========================================================================
   virtual BCP_branching_decision
   select_branching_candidates(const BCP_lp_result& lpres,
                               const BCP_vec<BCP_var*>& vars,
                               const BCP_vec<BCP_cut*>& cuts,
                               const BCP_lp_var_pool& local_var_pool,
                               const BCP_lp_cut_pool& local_cut_pool,
                               BCP_vec<BCP_lp_branching_object*>& cands);
   BCP_lp_branching_object*
   branch_on_half(const BCP_lp_result& lpres,
                  const BCP_vec<BCP_var*>& vars);

   //==========================================================================
   // *LL* : Use default for now
   // *LL* : Later we can play with integrality based branching
   virtual BCP_branching_object_relation
   compare_branching_candidates(BCP_presolved_lp_brobj* new_solved,
                                BCP_presolved_lp_brobj* old_solved) {
      return BCP_lp_user::compare_branching_candidates(new_solved, old_solved);
   }


   //==========================================================================
   // *LL* : The THINK comment above will definitely
   // *LL* : apply when we'll do column generation
   virtual void
   set_actions_for_children(BCP_presolved_lp_brobj* best);
      
   //==========================================================================
   // *LL* : Used only when branching on dynamically generated cuts is
   // *LL* : allowed, but we don't generate cuts...
   virtual void
   purge_slack_pool(const BCP_vec<BCP_cut*>& slack_pool,
                    BCP_vec<int>& to_be_purged) {
      BCP_lp_user::purge_slack_pool(slack_pool, to_be_purged);
   }


   //==========================================================================

};
#endif