MC_lp Class Reference

#include <MC_lp.hpp>

Inheritance diagram for MC_lp:

Inheritance graph
[legend]
Collaboration diagram for MC_lp:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 MC_lp ()
 ~MC_lp ()
virtual void unpack_module_data (BCP_buffer &buf)
 Unpack the initial information sent to the LP process by the Tree Manager.
virtual void pack_cut_algo (const BCP_cut_algo *cut, BCP_buffer &buf)
virtual BCP_cut_algounpack_cut_algo (BCP_buffer &buf)
virtual OsiSolverInterfaceinitialize_solver_interface ()
 Create LP solver environment.
virtual void modify_lp_parameters (OsiSolverInterface *lp, bool in_strong_branching)
 Modify parameters of the LP solver before optimization.
virtual BCP_solutiontest_feasibility (const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 Evaluate and return MIP feasibility of the current solution.
virtual BCP_solutiongenerate_heuristic_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 Try to generate a heuristic solution (or return one generated during cut/variable generation.
MC_solutionmc_generate_heuristic_solution (const double *x, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 A local helper function.
virtual void pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol)
 Pack a MIP feasible solution into a buffer.
virtual void cuts_to_rows (const BCP_vec< BCP_var * > &vars, BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_row * > &rows, const BCP_lp_result &lpres, BCP_object_origin origin, bool allow_multiple)
 Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation.
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)
 Generate cuts within the LP process.
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)
 Compare two generated cuts.
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)
 This method provides an opportunity for the user to tighten the bounds of variables.
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
OsiSolverInterfacesolveToOpt (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)
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)
 Decide which branching object is preferred for branching.
virtual void set_actions_for_children (BCP_presolved_lp_brobj *best)
 Decide what to do with the children of the selected branching object.
 MC_lp ()
 ~MC_lp ()
virtual void unpack_module_data (BCP_buffer &buf)
 Unpack the initial information sent to the LP process by the Tree Manager.
virtual void pack_cut_algo (const BCP_cut_algo *cut, BCP_buffer &buf)
virtual BCP_cut_algounpack_cut_algo (BCP_buffer &buf)
virtual OsiSolverInterfaceinitialize_solver_interface ()
 Create LP solver environment.
virtual void modify_lp_parameters (OsiSolverInterface *lp, bool in_strong_branching)
 Modify parameters of the LP solver before optimization.
virtual BCP_solutiontest_feasibility (const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 Evaluate and return MIP feasibility of the current solution.
virtual BCP_solutiongenerate_heuristic_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 Try to generate a heuristic solution (or return one generated during cut/variable generation.
MC_solutionmc_generate_heuristic_solution (const double *x, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
 A local helper function.
virtual void pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol)
 Pack a MIP feasible solution into a buffer.
virtual void cuts_to_rows (const BCP_vec< BCP_var * > &vars, BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_row * > &rows, const BCP_lp_result &lpres, BCP_object_origin origin, bool allow_multiple)
 Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation.
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)
 Generate cuts within the LP process.
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)
 Compare two generated cuts.
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)
 This method provides an opportunity for the user to tighten the bounds of variables.
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
OsiSolverInterfacesolveToOpt (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)
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)
 Decide which branching object is preferred for branching.
virtual void set_actions_for_children (BCP_presolved_lp_brobj *best)
 Decide what to do with the children of the selected branching object.

Public Attributes

BCP_parameter_set< MC_lp_parpar
MC_problem mc
int hist_len
double * objhist
MC_solutionsoln
bool started_exact
bool tried_hard_cuts_in_prev_major_iter
double obj_shift
BCP_presolved_lp_brobjbest_presolved
BCP_parameter_set< MC_lp_parpar
double * objhist
MC_solutionsoln
BCP_presolved_lp_brobjbest_presolved

Private Member Functions

 MC_lp (const MC_lp &)
MC_lpoperator= (const MC_lp &)
 MC_lp (const MC_lp &)
MC_lpoperator= (const MC_lp &)

Detailed Description

Definition at line 16 of file MC_lp.hpp.


Constructor & Destructor Documentation

MC_lp::MC_lp ( const MC_lp  )  [private]

MC_lp::MC_lp (  )  [inline]

Definition at line 43 of file MC_lp.hpp.

MC_lp::~MC_lp (  )  [inline]

Definition at line 45 of file MC_lp.hpp.

References objhist, and soln.

MC_lp::MC_lp ( const MC_lp  )  [private]

MC_lp::MC_lp (  )  [inline]

Definition at line 43 of file MC_lp.hpp.

MC_lp::~MC_lp (  )  [inline]

Definition at line 45 of file MC_lp.hpp.

References objhist, and soln.


Member Function Documentation

MC_lp& MC_lp::operator= ( const MC_lp  )  [private]

virtual void MC_lp::unpack_module_data ( BCP_buffer buf  )  [virtual]

Unpack the initial information sent to the LP process by the Tree Manager.

This information was packed by the method BCP_tm_user::pack_module_data() invoked with BCP_ProcessType_LP as the third (target process type) argument.

Default: empty method.

Reimplemented from BCP_lp_user.

virtual void MC_lp::pack_cut_algo ( const BCP_cut_algo cut,
BCP_buffer buf 
) [virtual]

virtual BCP_cut_algo* MC_lp::unpack_cut_algo ( BCP_buffer buf  )  [virtual]

virtual OsiSolverInterface* MC_lp::initialize_solver_interface (  )  [virtual]

Create LP solver environment.

Create the LP solver class that will be used for solving the LP relaxations. The default implementation picks up which COIN_USE_XXX is defined and initializes an lp solver of that type. This is probably OK for most users. The only reason to override this method is to be able to choose at runtime which lp solver to instantiate (maybe even different solvers on different processors). In this case she should probably also override the pack_warmstart() and unpack_warmstart() methods in this class and in the BCP_tm_user class.

Reimplemented from BCP_lp_user.

virtual void MC_lp::modify_lp_parameters ( OsiSolverInterface lp,
bool  in_strong_branching 
) [virtual]

Modify parameters of the LP solver before optimization.

This method provides an opportunity for the user to change parameters of the LP solver before optimization in the LP solver starts. The second argument indicates whether the optimization is a "regular" optimization or it will take place in strong branching. Default: empty method.

Reimplemented from BCP_lp_user.

virtual BCP_solution* MC_lp::test_feasibility ( const BCP_lp_result lp_result,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
) [virtual]

Evaluate and return MIP feasibility of the current solution.

If the solution is MIP feasible, return a solution object otherwise return a NULL pointer. The useris also welcome to heuristically generate a solution and return a pointer to that solution (although the user will have another chance (after cuts and variables are generated) to return/create heuristically generated solutions. (After all, it's quite possible that solutions are generated during cut/variable generation.)

Default: test feasibility based on the FeeasibilityTest parameter in BCP_lp_par which defults to BCP_FullTest_Feasible.

Parameters:
lp_result the result of the most recent LP optimization
vars variables currently in the formulation
cuts variables currently in the formulation

Reimplemented from BCP_lp_user.

virtual BCP_solution* MC_lp::generate_heuristic_solution ( const BCP_lp_result lpres,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
) [virtual]

Try to generate a heuristic solution (or return one generated during cut/variable generation.

Reimplemented from BCP_lp_user.

MC_solution* MC_lp::mc_generate_heuristic_solution ( const double *  x,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
)

A local helper function.

virtual void MC_lp::pack_feasible_solution ( BCP_buffer buf,
const BCP_solution sol 
) [virtual]

Pack a MIP feasible solution into a buffer.

The solution will be unpacked in the Tree Manager by the BCP_tm_user::unpack_feasible_solution() method.

Default: The default implementation assumes that sol is a BCP_solution_generic object (containing variables at nonzero level) and packs it.

Parameters:
buf (OUT) the buffer to pack into
sol (IN) the solution to be packed

Reimplemented from BCP_lp_user.

virtual void MC_lp::cuts_to_rows ( const BCP_vec< BCP_var * > &  vars,
BCP_vec< BCP_cut * > &  cuts,
BCP_vec< BCP_row * > &  rows,
const BCP_lp_result lpres,
BCP_object_origin  origin,
bool  allow_multiple 
) [virtual]

Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation.

Converting means computing for each cut the coefficients corresponding to each variable and creating BCP_row objects that can be added to the formulation.

This method has different purposes depending on the value of the last argument. If multiple expansion is not allowed then the user must generate a unique row for each cut. This unique row must always be the same for any given cut. This kind of operation is needed so that an LP relaxation can be exactly recreated.

On the other hand if multiple expansion is allowed then the user has (almost) free reign over what she returns. She can delete some of the cuts or append new ones (e.g., lifted ones) to the end. The result of the LP relaxation and the origin of the cuts are there to help her to make a decision about what to do. For example, she might want to lift cuts coming from the Cut Generator, but not those coming from the Cut Pool. The only requirement is that when this method returns the number of cuts and rows must be the same and the i-th row must be the unique row corresponding to the i-th cut.

Parameters:
vars the variables currently in the relaxation (IN)
cuts the cuts to be converted (IN/OUT)
rows the rows into which the cuts are converted (OUT)
lpres solution to the current LP relaxation (IN)
origin where the cuts come from (IN)
allow_multiple whether multiple expansion, i.e., lifting, is allowed (IN)
Default: throw an exception (if this method is invoked then the user must have generated cuts and BCP has no way to know how to convert them).

Reimplemented from BCP_lp_user.

virtual void MC_lp::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 
) [virtual]

Generate cuts within the LP process.

Sometimes too much information would need to be transmitted for cut generation (e.g., the full tableau for Gomory cuts) or the cut generation is so fast that transmitting the info would take longer than generating the cuts. In such cases it might better to generate the cuts locally. This routine provides the opportunity.
Default: empty for now. To be interfaced to Cgl.

Parameters:
lpres solution to the current LP relaxation (IN)
vars the variabless currently in the relaxation (IN)
cuts the cuts currently in the relaxation (IN)
new_cuts the vector of generated cuts (OUT)
new_rows the correspontding rows(OUT)

Reimplemented from BCP_lp_user.

void MC_lp::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 MC_lp::unique_cycle_cuts ( BCP_vec< BCP_cut * > &  new_cuts,
BCP_vec< BCP_row * > &  new_rows 
)

void MC_lp::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 MC_lp::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 MC_lp::getMaxLpViol (  ) 

virtual BCP_object_compare_result MC_lp::compare_cuts ( const BCP_cut c0,
const BCP_cut c1 
) [virtual]

Compare two generated cuts.

Cuts are generated in different iterations, they come from the Cut Pool, etc. There is a very real possibility that the LP process receives several cuts that are either identical or one of them is better then another (cuts off everything the other cuts off). This routine is used to decide which one to keep if not both.
Default: Return BCP_DifferentObjs.

Reimplemented from BCP_lp_user.

virtual void MC_lp::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 
) [virtual]

This method provides an opportunity for the user to tighten the bounds of variables.

The method is invoked after reduced cost fixing. The results are returned in the last two parameters.
Default: empty method.

Parameters:
lpres the result of the most recent LP optimization,
vars the variables in the current formulation,
status the stati of the variables as known to the system,
var_bound_changes_since_logical_fixing the number of variables whose bounds have changed (by reduced cost fixing) since the most recent invocation of this method that has actually forced changes returned something in the last two arguments,
changed_pos the positions of the variables whose bounds should be changed
new_bd the new bounds (lb/ub pairs) of these variables.

Reimplemented from BCP_lp_user.

bool MC_lp::is_gap_tailoff_rel ( const int  k,
const double  minimp,
const double  objval 
) const

bool MC_lp::is_lb_tailoff_abs ( const int  k,
const double  minimp,
const double  objval 
) const

bool MC_lp::is_lb_tailoff_rel ( const int  k,
const double  minimp,
const double  objval 
) const

void MC_lp::tailoff_test ( bool &  tailoff_gap_rel,
bool &  tailoff_lb_abs,
bool &  tailoff_lb_rel,
const double  objval 
) const

OsiSolverInterface* MC_lp::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 MC_lp::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 
) [virtual]

void MC_lp::perform_strong_branching ( const BCP_lp_result lpres,
OsiSolverInterface exact_solver,
BCP_vec< BCP_lp_branching_object * > &  cands 
)

void MC_lp::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 MC_lp::compare_branching_candidates ( BCP_presolved_lp_brobj new_presolved,
BCP_presolved_lp_brobj old_presolved 
) [virtual]

Decide which branching object is preferred for branching.

Based on the member fields of the two presolved candidate branching objects decide which one should be preferred for really branching on it. Possible return values are: BCP_OldPresolvedIsBetter, BCP_NewPresolvedIsBetter and BCP_NewPresolvedIsBetter_BranchOnIt. This last value (besides specifying which candidate is preferred) also indicates that no further candidates should be examined, branching should be done on this candidate.

Default: The behavior of this method is governed by the BranchingObjectComparison parameter in BCP_lp_par.

Reimplemented from BCP_lp_user.

virtual void MC_lp::set_actions_for_children ( BCP_presolved_lp_brobj best  )  [virtual]

Decide what to do with the children of the selected branching object.

Fill out the _child_action field in best. This will specify for every child what to do with it. Possible values for each individual child are BCP_FathomChild, BCP_ReturnChild and BCP_KeepChild. There can be at most child with this last action specified. It means that in case of diving this child will be processed by this LP process as the next search tree node.

Default: Every action is BCP_ReturnChild. However, if BCP dives then one child will be mark with BCP_KeepChild. The decision which child to keep is based on the ChildPreference parameter in BCP_lp_par. Also, if a child has a presolved lower bound that is higher than the current upper bound then that child is mark as BCP_FathomChild.

THINK*: Should those children be sent back for processing in the next phase?

Reimplemented from BCP_lp_user.

MC_lp& MC_lp::operator= ( const MC_lp  )  [private]

virtual void MC_lp::unpack_module_data ( BCP_buffer buf  )  [virtual]

Unpack the initial information sent to the LP process by the Tree Manager.

This information was packed by the method BCP_tm_user::pack_module_data() invoked with BCP_ProcessType_LP as the third (target process type) argument.

Default: empty method.

Reimplemented from BCP_lp_user.

virtual void MC_lp::pack_cut_algo ( const BCP_cut_algo cut,
BCP_buffer buf 
) [virtual]

virtual BCP_cut_algo* MC_lp::unpack_cut_algo ( BCP_buffer buf  )  [virtual]

virtual OsiSolverInterface* MC_lp::initialize_solver_interface (  )  [virtual]

Create LP solver environment.

Create the LP solver class that will be used for solving the LP relaxations. The default implementation picks up which COIN_USE_XXX is defined and initializes an lp solver of that type. This is probably OK for most users. The only reason to override this method is to be able to choose at runtime which lp solver to instantiate (maybe even different solvers on different processors). In this case she should probably also override the pack_warmstart() and unpack_warmstart() methods in this class and in the BCP_tm_user class.

Reimplemented from BCP_lp_user.

virtual void MC_lp::modify_lp_parameters ( OsiSolverInterface lp,
bool  in_strong_branching 
) [virtual]

Modify parameters of the LP solver before optimization.

This method provides an opportunity for the user to change parameters of the LP solver before optimization in the LP solver starts. The second argument indicates whether the optimization is a "regular" optimization or it will take place in strong branching. Default: empty method.

Reimplemented from BCP_lp_user.

virtual BCP_solution* MC_lp::test_feasibility ( const BCP_lp_result lp_result,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
) [virtual]

Evaluate and return MIP feasibility of the current solution.

If the solution is MIP feasible, return a solution object otherwise return a NULL pointer. The useris also welcome to heuristically generate a solution and return a pointer to that solution (although the user will have another chance (after cuts and variables are generated) to return/create heuristically generated solutions. (After all, it's quite possible that solutions are generated during cut/variable generation.)

Default: test feasibility based on the FeeasibilityTest parameter in BCP_lp_par which defults to BCP_FullTest_Feasible.

Parameters:
lp_result the result of the most recent LP optimization
vars variables currently in the formulation
cuts variables currently in the formulation

Reimplemented from BCP_lp_user.

virtual BCP_solution* MC_lp::generate_heuristic_solution ( const BCP_lp_result lpres,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
) [virtual]

Try to generate a heuristic solution (or return one generated during cut/variable generation.

Reimplemented from BCP_lp_user.

MC_solution* MC_lp::mc_generate_heuristic_solution ( const double *  x,
const BCP_vec< BCP_var * > &  vars,
const BCP_vec< BCP_cut * > &  cuts 
)

A local helper function.

virtual void MC_lp::pack_feasible_solution ( BCP_buffer buf,
const BCP_solution sol 
) [virtual]

Pack a MIP feasible solution into a buffer.

The solution will be unpacked in the Tree Manager by the BCP_tm_user::unpack_feasible_solution() method.

Default: The default implementation assumes that sol is a BCP_solution_generic object (containing variables at nonzero level) and packs it.

Parameters:
buf (OUT) the buffer to pack into
sol (IN) the solution to be packed

Reimplemented from BCP_lp_user.

virtual void MC_lp::cuts_to_rows ( const BCP_vec< BCP_var * > &  vars,
BCP_vec< BCP_cut * > &  cuts,
BCP_vec< BCP_row * > &  rows,
const BCP_lp_result lpres,
BCP_object_origin  origin,
bool  allow_multiple 
) [virtual]

Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation.

Converting means computing for each cut the coefficients corresponding to each variable and creating BCP_row objects that can be added to the formulation.

This method has different purposes depending on the value of the last argument. If multiple expansion is not allowed then the user must generate a unique row for each cut. This unique row must always be the same for any given cut. This kind of operation is needed so that an LP relaxation can be exactly recreated.

On the other hand if multiple expansion is allowed then the user has (almost) free reign over what she returns. She can delete some of the cuts or append new ones (e.g., lifted ones) to the end. The result of the LP relaxation and the origin of the cuts are there to help her to make a decision about what to do. For example, she might want to lift cuts coming from the Cut Generator, but not those coming from the Cut Pool. The only requirement is that when this method returns the number of cuts and rows must be the same and the i-th row must be the unique row corresponding to the i-th cut.

Parameters:
vars the variables currently in the relaxation (IN)
cuts the cuts to be converted (IN/OUT)
rows the rows into which the cuts are converted (OUT)
lpres solution to the current LP relaxation (IN)
origin where the cuts come from (IN)
allow_multiple whether multiple expansion, i.e., lifting, is allowed (IN)
Default: throw an exception (if this method is invoked then the user must have generated cuts and BCP has no way to know how to convert them).

Reimplemented from BCP_lp_user.

virtual void MC_lp::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 
) [virtual]

Generate cuts within the LP process.

Sometimes too much information would need to be transmitted for cut generation (e.g., the full tableau for Gomory cuts) or the cut generation is so fast that transmitting the info would take longer than generating the cuts. In such cases it might better to generate the cuts locally. This routine provides the opportunity.
Default: empty for now. To be interfaced to Cgl.

Parameters:
lpres solution to the current LP relaxation (IN)
vars the variabless currently in the relaxation (IN)
cuts the cuts currently in the relaxation (IN)
new_cuts the vector of generated cuts (OUT)
new_rows the correspontding rows(OUT)

Reimplemented from BCP_lp_user.

void MC_lp::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 MC_lp::unique_cycle_cuts ( BCP_vec< BCP_cut * > &  new_cuts,
BCP_vec< BCP_row * > &  new_rows 
)

void MC_lp::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 MC_lp::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 MC_lp::getMaxLpViol (  ) 

virtual BCP_object_compare_result MC_lp::compare_cuts ( const BCP_cut c0,
const BCP_cut c1 
) [virtual]

Compare two generated cuts.

Cuts are generated in different iterations, they come from the Cut Pool, etc. There is a very real possibility that the LP process receives several cuts that are either identical or one of them is better then another (cuts off everything the other cuts off). This routine is used to decide which one to keep if not both.
Default: Return BCP_DifferentObjs.

Reimplemented from BCP_lp_user.

virtual void MC_lp::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 
) [virtual]

This method provides an opportunity for the user to tighten the bounds of variables.

The method is invoked after reduced cost fixing. The results are returned in the last two parameters.
Default: empty method.

Parameters:
lpres the result of the most recent LP optimization,
vars the variables in the current formulation,
status the stati of the variables as known to the system,
var_bound_changes_since_logical_fixing the number of variables whose bounds have changed (by reduced cost fixing) since the most recent invocation of this method that has actually forced changes returned something in the last two arguments,
changed_pos the positions of the variables whose bounds should be changed
new_bd the new bounds (lb/ub pairs) of these variables.

Reimplemented from BCP_lp_user.

bool MC_lp::is_gap_tailoff_rel ( const int  k,
const double  minimp,
const double  objval 
) const

bool MC_lp::is_lb_tailoff_abs ( const int  k,
const double  minimp,
const double  objval 
) const

bool MC_lp::is_lb_tailoff_rel ( const int  k,
const double  minimp,
const double  objval 
) const

void MC_lp::tailoff_test ( bool &  tailoff_gap_rel,
bool &  tailoff_lb_abs,
bool &  tailoff_lb_rel,
const double  objval 
) const

OsiSolverInterface* MC_lp::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 MC_lp::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 
) [virtual]

void MC_lp::perform_strong_branching ( const BCP_lp_result lpres,
OsiSolverInterface exact_solver,
BCP_vec< BCP_lp_branching_object * > &  cands 
)

void MC_lp::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 MC_lp::compare_branching_candidates ( BCP_presolved_lp_brobj new_presolved,
BCP_presolved_lp_brobj old_presolved 
) [virtual]

Decide which branching object is preferred for branching.

Based on the member fields of the two presolved candidate branching objects decide which one should be preferred for really branching on it. Possible return values are: BCP_OldPresolvedIsBetter, BCP_NewPresolvedIsBetter and BCP_NewPresolvedIsBetter_BranchOnIt. This last value (besides specifying which candidate is preferred) also indicates that no further candidates should be examined, branching should be done on this candidate.

Default: The behavior of this method is governed by the BranchingObjectComparison parameter in BCP_lp_par.

Reimplemented from BCP_lp_user.

virtual void MC_lp::set_actions_for_children ( BCP_presolved_lp_brobj best  )  [virtual]

Decide what to do with the children of the selected branching object.

Fill out the _child_action field in best. This will specify for every child what to do with it. Possible values for each individual child are BCP_FathomChild, BCP_ReturnChild and BCP_KeepChild. There can be at most child with this last action specified. It means that in case of diving this child will be processed by this LP process as the next search tree node.

Default: Every action is BCP_ReturnChild. However, if BCP dives then one child will be mark with BCP_KeepChild. The decision which child to keep is based on the ChildPreference parameter in BCP_lp_par. Also, if a child has a presolved lower bound that is higher than the current upper bound then that child is mark as BCP_FathomChild.

THINK*: Should those children be sent back for processing in the next phase?

Reimplemented from BCP_lp_user.


Member Data Documentation

BCP_parameter_set<MC_lp_par> MC_lp::par

Definition at line 21 of file MC_lp.hpp.

MC_problem MC_lp::mc

Definition at line 22 of file MC_lp.hpp.

int MC_lp::hist_len

Definition at line 26 of file MC_lp.hpp.

double* MC_lp::objhist

Definition at line 27 of file MC_lp.hpp.

Referenced by ~MC_lp().

MC_solution* MC_lp::soln

Definition at line 30 of file MC_lp.hpp.

Referenced by ~MC_lp().

bool MC_lp::started_exact

Definition at line 32 of file MC_lp.hpp.

bool MC_lp::tried_hard_cuts_in_prev_major_iter

Definition at line 33 of file MC_lp.hpp.

double MC_lp::obj_shift

Definition at line 38 of file MC_lp.hpp.

BCP_presolved_lp_brobj* MC_lp::best_presolved

Definition at line 40 of file MC_lp.hpp.

BCP_parameter_set<MC_lp_par> MC_lp::par

Definition at line 21 of file MC_lp.hpp.

double* MC_lp::objhist

Definition at line 27 of file MC_lp.hpp.

MC_solution* MC_lp::soln

Definition at line 30 of file MC_lp.hpp.

BCP_presolved_lp_brobj* MC_lp::best_presolved

Definition at line 40 of file MC_lp.hpp.


The documentation for this class was generated from the following files:
Generated on Thu Jan 15 03:03:23 2009 for coin-Bcp by  doxygen 1.4.7