Bcp 1.4.4
Loading...
Searching...
No Matches
BCP_lp_user.hpp
Go to the documentation of this file.
1// Copyright (C) 2000, International Business Machines
2// Corporation and others. All Rights Reserved.
3#ifndef _BCP_LP_USER_H
4#define _BCP_LP_USER_H
5
6// This file is fully prepared for doxygen.
7
8#include <vector>
9
11#include "OsiAuxInfo.hpp"
13#include "OsiChooseVariable.hpp"
14
15#include "BCP_USER.hpp"
16
17#include "BCP_buffer.hpp"
18#include "BCP_vector.hpp"
19#include "BCP_string.hpp"
20#include "BCP_warmstart.hpp"
21#include "BCP_solution.hpp"
22#include "BCP_var.hpp"
23#include "BCP_cut.hpp"
24#include "BCP_matrix.hpp"
25
26#include "BCP_enum.hpp"
27#include "BCP_enum_branch.hpp"
29#include "BCP_lp_param.hpp"
30#include "BCP_lp_result.hpp"
31#include "BCP_lp_pool.hpp"
32#include "BCP_lp_branch.hpp"
33
34//#############################################################################
35
36class BCP_lp_prob;
38
39//#############################################################################
40
41// All these functions are defined in BCP_lp_user.cpp, except for those that
42// have no counterparts in p.defaults, i.e., for those that have no builtin
43// pairs.
44
45//#############################################################################
46
76private:
78 BCP_lp_user& operator=(const BCP_lp_user&);
79
80private:
81 bool using_deprecated_set_user_data_for_children;
82 BCP_lp_prob * p;
83 OsiBabSolver* babSolver_;
84
85public:
93 void setLpProblemPointer(BCP_lp_prob * ptr) { p = ptr; }
98 void setOsiBabSolver(OsiBabSolver* ptr) { babSolver_ = ptr; }
99 OsiBabSolver* getOsiBabSolver() { return babSolver_; }
100
104 double upper_bound() const;
107 bool over_ub(double lb) const;
109 int current_phase() const;
111 int current_level() const;
113 int current_index() const;
115 int current_iteration() const;
117 double start_time() const;
123 void print(const bool ifprint, const char * format, ...) const;
124
128 char get_param(const BCP_lp_par::chr_params key) const;
130 int get_param(const BCP_lp_par::int_params key) const;
132 double get_param(const BCP_lp_par::dbl_params key) const;
135
137 void set_param(const BCP_lp_par::chr_params key, const bool val);
139 void set_param(const BCP_lp_par::chr_params key, const char val);
141 void set_param(const BCP_lp_par::int_params key, const int val);
143 void set_param(const BCP_lp_par::dbl_params key, const double val);
145 void set_param(const BCP_lp_par::str_params key, const char * val);
151 //=========================================================================
154 BCP_lp_user() : p(0), babSolver_(0) {}
157 virtual ~BCP_lp_user() {}
160 //=========================================================================
168 void
169 select_nonzeros(const double * first, const double * last,
170 const double etol, BCP_vec<int>& nonzeros) const;
173 void
174 select_zeros(const double * first, const double * last,
175 const double etol, BCP_vec<int>& zeros) const;
178 void
179 select_positives(const double * first, const double * last,
180 const double etol, BCP_vec<int>& positives) const;
183 void
184 select_fractions(const double * first, const double * last,
185 const double etol, BCP_vec<int>& fractions) const;
188 //=========================================================================
197 virtual void
199
202 //=========================================================================
204 int process_id() const;
206 int parent() const;
208 void
209 send_message(const int target, const BCP_buffer& buf,
212 void
213 receive_message(const int sender, BCP_buffer& buf,
216 void
217 broadcast_message(const BCP_process_t proc_type, const BCP_buffer& buf);
220 virtual void
222 //=========================================================================
233 virtual OsiSolverInterface *
235
236 //=========================================================================
241 virtual void
242 initialize_int_and_sos_list(std::vector<OsiObject *>& intAndSosObjects);
243
244 //=========================================================================
262 virtual void
264 const BCP_vec<BCP_cut*>& cuts,
265 const BCP_vec<BCP_obj_status>& var_status,
266 const BCP_vec<BCP_obj_status>& cut_status,
267 BCP_vec<int>& var_changed_pos,
268 BCP_vec<double>& var_new_bd,
269 BCP_vec<int>& cut_changed_pos,
270 BCP_vec<double>& cut_new_bd);
271
272 //=========================================================================
277 virtual void
279 BCP_var_set& vars, BCP_cut_set& cuts);
280
281 //=========================================================================
295 virtual void
296 modify_lp_parameters(OsiSolverInterface* lp, const int changeType,
297 bool in_strong_branching);
298
299 //===========================================================================
326 virtual void
328 const BCP_vec<BCP_var*>& vars,
329 const BCP_vec<BCP_cut*>& cuts,
330 const double old_lower_bound,
331 double& true_lower_bound,
332 BCP_solution*& sol,
333 BCP_vec<BCP_cut*>& new_cuts,
334 BCP_vec<BCP_row*>& new_rows,
335 BCP_vec<BCP_var*>& new_vars,
336 BCP_vec<BCP_col*>& new_cols);
337
338 //=========================================================================
350 virtual double
351 compute_lower_bound(const double old_lower_bound,
352 const BCP_lp_result& lpres,
353 const BCP_vec<BCP_var*>& vars,
354 const BCP_vec<BCP_cut*>& cuts);
355
356 //=========================================================================
377 virtual BCP_solution*
379 const BCP_vec<BCP_var*>& vars,
380 const BCP_vec<BCP_cut*>& cuts);
397 test_binary(const BCP_lp_result& lpres, const BCP_vec<BCP_var*>& vars,
398 const double etol) const;
403 const double etol) const;
406 test_full(const BCP_lp_result& lpres, const BCP_vec<BCP_var*>& vars,
407 const double etol) const;
416 virtual BCP_solution*
418 const BCP_vec<BCP_var*>& vars,
419 const BCP_vec<BCP_cut*>& cuts);
422 //=========================================================================
437 virtual void
439
440 //-------------------------------------------------------------------------
462 virtual void
464 const BCP_lp_result& lp_result,
465 const BCP_vec<BCP_var*>& vars,
466 const BCP_vec<BCP_cut*>& cuts);
467 //-------------------------------------------------------------------------
489 virtual void
491 const BCP_lp_result& lp_result,
492 const BCP_vec<BCP_var*>& vars,
493 const BCP_vec<BCP_cut*>& cuts);
496 //=========================================================================
517 virtual void
519 const BCP_vec<BCP_var*>& vars,
520 const BCP_vec<BCP_cut*>& cuts,
521 const bool final_lp_solution);
524 //=========================================================================
531 virtual void
533 const std::vector<double*> dual_rays,
534 const BCP_vec<BCP_var*>& vars,
535 const BCP_vec<BCP_cut*>& cuts,
536 BCP_vec<BCP_var*>& vars_to_add,
537 BCP_vec<BCP_col*>& cols_to_add);
538
539 //=========================================================================
575 virtual void
576 cuts_to_rows(const BCP_vec<BCP_var*>& vars, // on what to expand
577 BCP_vec<BCP_cut*>& cuts, // what to expand
578 BCP_vec<BCP_row*>& rows, // the expanded rows
579 // things that the user can use for lifting cuts if allowed
580 const BCP_lp_result& lpres,
581 BCP_object_origin origin, bool allow_multiple);
582 //-------------------------------------------------------------------------
603 virtual void
604 vars_to_cols(const BCP_vec<BCP_cut*>& cuts, // on what to expand
605 BCP_vec<BCP_var*>& vars, // what to expand
606 BCP_vec<BCP_col*>& cols, // the expanded cols
607 // things that the user can use for lifting vars if allowed
608 const BCP_lp_result& lpres,
609 BCP_object_origin origin, bool allow_multiple);
612 //=========================================================================
628 virtual void
630 const BCP_vec<BCP_var*>& vars,
631 const BCP_vec<BCP_cut*>& cuts,
632 BCP_vec<BCP_cut*>& new_cuts,
633 BCP_vec<BCP_row*>& new_rows);
634 //-------------------------------------------------------------------------
651 virtual void
653 const BCP_vec<BCP_var*>& vars,
654 const BCP_vec<BCP_cut*>& cuts,
655 const bool before_fathom,
656 BCP_vec<BCP_var*>& new_vars,
657 BCP_vec<BCP_col*>& new_cols);
658 //-------------------------------------------------------------------------
667 compare_cuts(const BCP_cut* c0, const BCP_cut* c1);
668 //-------------------------------------------------------------------------
678 compare_vars(const BCP_var* v0, const BCP_var* v1);
681 //=========================================================================
682 virtual void
684 const BCP_vec<BCP_var*>& vars,
685 const BCP_vec<BCP_cut*>& cuts,
686 const bool before_fathom,
687 BCP_vec<int>& deletable);
688 virtual void
690 const BCP_vec<BCP_var*>& vars,
691 const BCP_vec<BCP_cut*>& cuts,
692 const bool before_fathom,
693 BCP_vec<int>& deletable);
694 //=========================================================================
712 virtual void
714 const BCP_vec<BCP_var*>& vars,
715 const BCP_vec<BCP_cut*>& cuts,
716 const BCP_vec<BCP_obj_status>& var_status,
717 const BCP_vec<BCP_obj_status>& cut_status,
718 const int var_bound_changes_since_logical_fixing,
719 BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd);
724 void
725 reduced_cost_fixing(const double* dj, const double* x, const double gap,
726 BCP_vec<BCP_var*>& vars, int& newly_changed);
727
728 //=========================================================================
770 const BCP_vec<BCP_var*>& vars,
771 const BCP_vec<BCP_cut*>& cuts,
772 const BCP_lp_var_pool& local_var_pool,
773 const BCP_lp_cut_pool& local_cut_pool,
775 bool force_branch = false);
778 virtual int
780 OsiSolverInterface* solver,
781 OsiChooseVariable* choose,
782 OsiBranchingObject*& branchObject,
783 bool allowVarFix);
788 void
790 const BCP_vec<BCP_var*>& vars,
791 const int to_be_selected,
792 const double etol,
798 void
800 const BCP_vec<BCP_var*>& vars,
801 const int to_be_selected,
802 const double etol,
808 void
809 append_branching_vars(const double* x,
810 const BCP_vec<BCP_var*>& vars,
811 const BCP_vec<int>& select_pos,
831 BCP_presolved_lp_brobj* old_solved);
851 virtual void
853
862 virtual void
864 const int selected);
868 virtual void
872 //=========================================================================
873 // purging the slack cut pool (candidates for branching on cut)
895 virtual void
897 BCP_vec<int>& to_be_purged);
899};
900
901//#############################################################################
902
903#endif
BCP_object_compare_result
This enumerative constant describes the possible outcomes when comparing two objects (variables or cu...
Definition BCP_enum.hpp:276
BCP_object_origin
This enumerative constant describes the origin (originating process) of an object (variable or cut).
Definition BCP_enum.hpp:249
BCP_branching_decision
This enumerative constant is the return value of the select_branching_candidates() method in \URL[BCP...
BCP_branching_object_relation
This enumerative constant is the return value of the compare_presolved_branching_objects() method in ...
BCP_process_t
This enumerative constant describes the various process types.
BCP_message_tag
This enumerative constant describes the message tags different processes of BCP understand.
@ BCP_Msg_User
Used by the user to send a message to the user portion of the other process.
This class describes the message buffer used for all processes of BCP.
This class is just a collection of pointers to cuts with a number of methods to manipulate these cuts...
Definition BCP_cut.hpp:279
Abstract base class that defines members common to all types of cuts.
Definition BCP_cut.hpp:29
NO OLD DOC.
Definition BCP_lp.hpp:102
This class holds the results after solving an LP relaxation.
The BCP_lp_user class is the base class from which the user can derive a problem specific class to be...
virtual BCP_solution * test_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 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)
Initializing a new search tree node.
virtual OsiSolverInterface * initialize_solver_interface()
Create LP solver environment.
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.
virtual void modify_lp_parameters(OsiSolverInterface *lp, const int changeType, bool in_strong_branching)
Modify parameters of the LP solver before optimization.
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)
Restoring feasibility.
virtual void set_user_data_for_children(BCP_presolved_lp_brobj *best)
Deprecated version of the previos method (it does not pass the index of the selected branching candid...
BCP_lp_prob * getLpProblemPointer()
Get the pointer.
virtual void process_message(BCP_buffer &buf)
Process a message that has been sent by another process' user part to this process' user part.
void setLpProblemPointer(BCP_lp_prob *ptr)
Set the pointer.
void setOsiBabSolver(OsiBabSolver *ptr)
void print(const bool ifprint, const char *format,...) const
A method to print a message with the process id.
void append_branching_vars(const double *x, const BCP_vec< BCP_var * > &vars, const BCP_vec< int > &select_pos, BCP_vec< BCP_lp_branching_object * > &candidates)
This helper method creates branching variable candidates and appends them to cans.
virtual void vars_to_cols(const BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_var * > &vars, BCP_vec< BCP_col * > &cols, const BCP_lp_result &lpres, BCP_object_origin origin, bool allow_multiple)
Convert a set of variables into corresponding columns for the current LP relaxation.
virtual void pack_primal_solution(BCP_buffer &buf, const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
Pack the information necessary for cut generation into the buffer.
virtual void load_problem(OsiSolverInterface &osi, BCP_problem_core *core, BCP_var_set &vars, BCP_cut_set &cuts)
Load the problem specified by core, vars, and cuts into the solver interface.
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.
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, bool force_branch=false)
Decide whether to branch or not and select a set of branching candidates if branching is decided upon...
int process_id() const
What is the process id of the current process.
void set_param(const BCP_lp_par::str_params key, const char *val)
virtual void set_actions_for_children(BCP_presolved_lp_brobj *best)
Decide what to do with the children of the selected branching object.
virtual void unpack_module_data(BCP_buffer &buf)
Unpack the initial information sent to the LP process by the Tree Manager.
virtual void purge_slack_pool(const BCP_vec< BCP_cut * > &slack_pool, BCP_vec< int > &to_be_purged)
Selectively purge the list of slack cuts.
virtual ~BCP_lp_user()
Being virtual, the destructor invokes the destructor for the real type of the object being deleted.
void broadcast_message(const BCP_process_t proc_type, const BCP_buffer &buf)
Broadcast the message to all processes of the given type.
BCP_solution_generic * test_integral(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
Test whether all variables are integer.
virtual BCP_object_compare_result compare_vars(const BCP_var *v0, const BCP_var *v1)
Compare two generated variables.
void reduced_cost_fixing(const double *dj, const double *x, const double gap, BCP_vec< BCP_var * > &vars, int &newly_changed)
Reduced cost fixing.
virtual BCP_object_compare_result compare_cuts(const BCP_cut *c0, const BCP_cut *c1)
Compare two generated cuts.
void send_message(const int target, const BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User)
Send a message to a particular process.
virtual void pack_feasible_solution(BCP_buffer &buf, const BCP_solution *sol)
Pack a MIP feasible solution into a buffer.
void branch_close_to_one(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const int to_be_selected, const double etol, BCP_vec< BCP_lp_branching_object * > &candidates)
Select the "close-to-one" variables for strong branching.
virtual BCP_solution * generate_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.
void select_positives(const double *first, const double *last, const double etol, BCP_vec< int > &positives) const
Select all positive entries.
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)
Compute a true lower bound for the subproblem.
OsiBabSolver * getOsiBabSolver()
const BCP_string & get_param(const BCP_lp_par::str_params key) const
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 set_user_data_for_children(BCP_presolved_lp_brobj *best, const int selected)
For each child create a user data object and put it into the appropriate entry in best->user_data().
char get_param(const BCP_lp_par::chr_params key) const
int current_iteration() const
Return the iteration count within the search tree node being processed.
BCP_solution_generic * test_full(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
Test whether the variables specified as integers are really integer.
double get_param(const BCP_lp_par::dbl_params key) const
int get_param(const BCP_lp_par::int_params key) const
BCP_solution_generic * test_binary(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
Test whether all variables are 0/1.
virtual void select_cuts_to_delete(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool before_fathom, BCP_vec< int > &deletable)
void send_feasible_solution(const BCP_solution *sol)
virtual void display_lp_solution(const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool final_lp_solution)
Display the result of most recent LP optimization.
void receive_message(const int sender, BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User)
Wait for a message and receive it.
double upper_bound() const
Return what is the best known upper bound (might be BCP_DBL_MAX)
void select_zeros(const double *first, const double *last, const double etol, BCP_vec< int > &zeros) const
Select all zero entries.
virtual int try_to_branch(OsiBranchingInformation &branchInfo, OsiSolverInterface *solver, OsiChooseVariable *choose, OsiBranchingObject *&branchObject, bool allowVarFix)
void set_param(const BCP_lp_par::chr_params key, const char val)
virtual BCP_branching_object_relation compare_branching_candidates(BCP_presolved_lp_brobj *new_solved, BCP_presolved_lp_brobj *old_solved)
Decide which branching object is preferred for branching.
virtual void select_vars_to_delete(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool before_fathom, BCP_vec< int > &deletable)
BCP_user_data * get_user_data()
Return a pointer to the BCP_user_data structure the user (may have) stored in this node.
virtual void pack_dual_solution(BCP_buffer &buf, const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
Pack the information necessary for variable generation into the buffer.
void set_param(const BCP_lp_par::dbl_params key, const double val)
virtual void initialize_int_and_sos_list(std::vector< OsiObject * > &intAndSosObjects)
Create the list of objects that can be used for branching (simple integer vars and SOS sets).
int current_index() const
Return the internal index of the search tree node being processed.
void branch_close_to_half(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const int to_be_selected, const double etol, BCP_vec< BCP_lp_branching_object * > &candidates)
Select the "close-to-half" variables for strong branching.
double start_time() const
Return when the LP process started.
int parent() const
the process id of the parent
void select_nonzeros(const double *first, const double *last, const double etol, BCP_vec< int > &nonzeros) const
Select all nonzero entries.
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)
Generate variables within the LP process.
int current_phase() const
Return the phase the algorithm is in.
int current_level() const
Return the level of the search tree node being processed.
void set_param(const BCP_lp_par::chr_params key, const bool val)
virtual void process_lp_result(const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const double old_lower_bound, double &true_lower_bound, BCP_solution *&sol, BCP_vec< BCP_cut * > &new_cuts, BCP_vec< BCP_row * > &new_rows, BCP_vec< BCP_var * > &new_vars, BCP_vec< BCP_col * > &new_cols)
Process the result of an iteration.
void select_fractions(const double *first, const double *last, const double etol, BCP_vec< int > &fractions) const
Select all fractional entries.
bool over_ub(double lb) const
Return true / false depending on whether the lb argument is over the current upper bound or not.
void set_param(const BCP_lp_par::int_params key, const int val)
A presolved branching object candidate.
This class describes the core of the MIP problem, the variables/cuts in it as well as the matrix corr...
This class holds a MIP feasible primal solution.
This is the abstract base class for a solution to a Mixed Integer Programming problem.
This class is a very simple impelementation of a constant length string.
This class is just a collection of pointers to variables with a number of methods to manipulate these...
Definition BCP_var.hpp:316
Abstract base class that defines members common to all types of variables.
Definition BCP_var.hpp:28
The class BCP_vec serves the same purpose as the vector class in the standard template library.
dbl_params
Double parameters.
str_params
String parameters.
int_params
Integer parameters.
chr_params
Character parameters.