MC_lp.hpp

Go to the documentation of this file.

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

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

#include "MC.hpp"
#include "MC_solution.hpp"
#include "MC_lp_param.hpp"

class OsiVolSolverInterface;
class OsiSolverInterface;

class MC_lp : public BCP_lp_user {
private:
  MC_lp(const MC_lp&);
  MC_lp& operator=(const MC_lp&);
public:
  BCP_parameter_set<MC_lp_par> par;
  MC_problem mc;

  // hold a history of objective values (for tailing off, until it's
  // implemented in BCP
  int hist_len;
  double* objhist;
  // hold the solution generated during cycle cut generation and return it in
  // generate_heuristic_solution()
  MC_solution* soln;
  // Whether we have started to solve the problems to optimality
  bool started_exact;
  bool tried_hard_cuts_in_prev_major_iter;

  // When using the volume alg in general, but solving to optimality with
  // simplex using the reduced costs wrt. the duals of the volume, obj_shift
  // is constant term after the cost transformation
  double obj_shift;
  // the presolved best candidate
  BCP_presolved_lp_brobj* best_presolved;

public:
  MC_lp() : par(), mc(), objhist(0), soln(0), started_exact(false),
            tried_hard_cuts_in_prev_major_iter(false), best_presolved(0) {}
  ~MC_lp() {
    delete[] objhist;
    delete soln;
  }

  //--------------------------------------------------------------------------
  // unpack the module data for the appropriate process
  virtual void
  unpack_module_data(BCP_buffer & buf);
  //--------------------------------------------------------------------------
  // Override the initializer so that we can choose between vol and simplex
  // at runtime.
  virtual OsiSolverInterface *
  initialize_solver_interface();
   
  //--------------------------------------------------------------------------
  // Opportunity to reset things before optimization
  virtual void
  modify_lp_parameters(OsiSolverInterface* lp, const int changeType,
                       bool in_strong_branching);
  //--------------------------------------------------------------------------
  // Feasibility testing
  virtual BCP_solution*
  test_feasibility(const BCP_lp_result& lp_result,
                   const BCP_vec<BCP_var*>& vars,
                   const BCP_vec<BCP_cut*>& cuts);
  virtual BCP_solution*
  generate_heuristic_solution(const BCP_lp_result& lpres,
                              const BCP_vec<BCP_var*>& vars,
                              const BCP_vec<BCP_cut*>& cuts);
  MC_solution*
  mc_generate_heuristic_solution(const double* x,
                                 const BCP_vec<BCP_var*>& vars,
                                 const BCP_vec<BCP_cut*>& cuts);
  //--------------------------------------------------------------------------
  // feasible solution packing
  virtual void
  pack_feasible_solution(BCP_buffer& buf, const BCP_solution* sol);
  //--------------------------------------------------------------------------
  // Convert the user generated cuts into rows
  virtual void
  cuts_to_rows(const BCP_vec<BCP_var*>& vars, // on what to expand
               BCP_vec<BCP_cut*>& cuts,       // what to expand
               BCP_vec<BCP_row*>& rows,       // the expanded rows
               // things that the user can use for lifting cuts if allowed
               const BCP_lp_result& lpres,
               BCP_object_origin origin, bool allow_multiple);
  //--------------------------------------------------------------------------
  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);
  void
  generate_cuts_in_lp(const double* x, const double* lhs,
                      const double objval,
                      const BCP_vec<BCP_var*>& vars,
                      const BCP_vec<BCP_cut*>& cuts,
                      BCP_vec<BCP_cut*>& new_cuts,
                      BCP_vec<BCP_row*>& new_rows);
  void
  unique_cycle_cuts(BCP_vec<BCP_cut*>& new_cuts,
                    BCP_vec<BCP_row*>& new_rows);
  void
  generate_mst_cuts(const double* x, const double* lhs,
                    const double objval,
                    const BCP_vec<BCP_var*>& vars,
                    const BCP_vec<BCP_cut*>& cuts,
                    BCP_vec<BCP_cut*>& new_cuts,
                    BCP_vec<BCP_row*>& new_rows);
  void
  generate_sp_cuts(const double* x, const double* lhs,
                   const double objval,
                   const BCP_vec<BCP_var*>& vars,
                   const BCP_vec<BCP_cut*>& cuts,
                   BCP_vec<BCP_cut*>& new_cuts,
                   BCP_vec<BCP_row*>& new_rows);
  double
  getMaxLpViol();
  //--------------------------------------------------------------------------
  virtual BCP_object_compare_result
  compare_cuts(const BCP_cut* c0, const BCP_cut* c1);
  //--------------------------------------------------------------------------
  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);
  //--------------------------------------------------------------------------
  // Helper functions to check if there has been a tailing off in the past k
  // iterations
  //--------------------------------------------------------------------------
  bool
  is_gap_tailoff_rel(const int k, const double minimp,
                     const double objval) const;
  bool
  is_lb_tailoff_abs(const int k, const double minimp,
                    const double objval) const;
  bool
  is_lb_tailoff_rel(const int k, const double minimp,
                    const double objval) const;
  void
  tailoff_test(bool& tailoff_gap_rel, bool& tailoff_lb_abs,
               bool& tailoff_lb_rel, const double objval) const;
  //--------------------------------------------------------------------------
  OsiSolverInterface* 
  solveToOpt(OsiVolSolverInterface* vollp,
             const BCP_lp_result& lpres,
             const BCP_vec<BCP_var*>& vars,
             const BCP_vec<BCP_cut*>& cuts,
             double& exact_obj);
  //--------------------------------------------------------------------------
  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*>& candidates,
                              bool force_branch = false);
  void
  perform_strong_branching(const BCP_lp_result& lpres,
                           OsiSolverInterface* exact_solver,
                           BCP_vec<BCP_lp_branching_object*>& cands);
  void
  choose_branching_vars(const BCP_vec<BCP_var*>& vars, const double * x,
                        const int cand_num,
                        BCP_vec<BCP_lp_branching_object*>& cands);
  //--------------------------------------------------------------------------
  virtual BCP_branching_object_relation
  compare_branching_candidates(BCP_presolved_lp_brobj* new_presolved,
                               BCP_presolved_lp_brobj* old_presolved);
  virtual void
  set_actions_for_children(BCP_presolved_lp_brobj* best);
};

#endif