Bcp 1.4.4
Loading...
Searching...
No Matches
BCP_tm.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_TM_H
4#define _BCP_TM_H
5
6#include <queue>
7#include <map>
8
9#include "CoinSearchTree.hpp"
10#include "CoinSmartPtr.hpp"
11
12#include "BCP_math.hpp"
13#include "BCP_buffer.hpp"
14#include "BCP_enum.hpp"
16#include "BCP_tm_node.hpp"
17
18#include "BCP_tm_param.hpp"
19#include "BCP_lp_param.hpp"
20#include "BCP_cg_param.hpp"
21#include "BCP_vg_param.hpp"
22//#include "BCP_cp_param.hpp"
23//#include "BCP_vp_param.hpp"
24#include "BCP_parameters.hpp"
25#include "BCP_tmstorage.hpp"
26
27#include "BCP_buffer.hpp"
28#include "BCP_message.hpp"
29#include "BCP_process.hpp"
30
31#include "BCP_var.hpp"
32#include "BCP_cut.hpp"
33
34//#############################################################################
35class BCP_warmstart;
36class BCP_solution;
37
38class BCP_tm_user;
39class BCP_user_pack;
40
41//class BCP_var;
42//class BCP_cut;
43
45
48
50
51//#############################################################################
52
53#define BCP_ONLY_LP_PROCESS_HANDLING_WORKS
54
62 // BCP_parameter_set<BCP_cp_par> cp;
63 // BCP_parameter_set<BCP_vp_par> vp;
68};
69
70//-----------------------------------------------------------------------------
71
78 bool root_pricing_unpacked; // set if the result of root pricing is already
79 // unpacked. important in a single process
80 // environment, so we don't unpack things twice
81};
82
83//-----------------------------------------------------------------------------
84
86private:
87 int num_lp;
88 // An array whose i-th entry indicates what was the totel wait time when
89 // exactly i LP processes were working
90 double* wait_time;
91 // An array whose i-th entry indicates what was the totel queue length when
92 // exactly i LP processes were working
93 double* sumQueueLength;
94 // An array whose i-th entry indicates how many times we have sampled the
95 // queue length when exactly i LP processes were working
96 int* numQueueLength;
97 int cnt; // how many times we have printed stats
98public:
100 num_lp(0),
101 wait_time(NULL),
102 sumQueueLength(NULL),
103 numQueueLength(NULL),
104 cnt(0) {}
106 delete[] wait_time;
107 delete[] sumQueueLength;
108 delete[] numQueueLength;
109 }
110 void set_num_lp(int num) {
111 delete[] wait_time;
112 delete[] sumQueueLength;
113 delete[] numQueueLength;
114 num_lp = num;
115 wait_time = new double[num+1];
116 sumQueueLength = new double[num+1];
117 numQueueLength = new int[num+1];
118 for (int i = 0; i <= num_lp; ++i) {
119 wait_time[i] = 0;
120 sumQueueLength[i] = 0;
121 numQueueLength[i] = 0;
122 }
123 }
124 void update_wait_time(int i, double t) { wait_time[i] += t; }
125 void update_queue_length(int i, int len) {
126 sumQueueLength[i] += len;
127 ++numQueueLength[i];
128 }
129 void print(bool final, double t);
130};
131
132//-----------------------------------------------------------------------------
133
136class BCP_tm_prob : public BCP_process {
137private:
141 BCP_tm_prob(const BCP_tm_prob&);
143 BCP_tm_prob& operator=(const BCP_tm_prob&);
146 //-------------------------------------------------------------------------
147public: // Data members
154
161
164
175 // flags to signal various things
185 std::vector<int> ts_procs;
186 std::vector<int> lp_procs;
195 //-------------------------------------------------------------------------
198 static double lb_multiplier;
199 std::multiset<double> lower_bounds;
204 //-------------------------------------------------------------------------
214 int phase;
217
218 // *FIXME*: maybe hash_map better for the next four?
220 std::map<int, Coin::SmartPtr<BCP_var> > vars_local;
222 std::map<int, int> vars_remote;
224 std::map<int, Coin::SmartPtr<BCP_cut> > cuts_local;
226 std::map<int, int> cuts_remote;
227
232
233 //-------------------------------------------------------------------------
235 std::map<int, int> ts_space;
236
237 //-------------------------------------------------------------------------
241 std::map<int, BCP_tm_node*> active_nodes;
244
246 std::map<int, BCP_tm_node_to_send*> nodes_to_send;
247
248 // BCP_node_queue candidates;
253
254 //-------------------------------------------------------------------------
264 //-------------------------------------------------------------------------
266
267public:
273 virtual ~BCP_tm_prob();
276public:
280 void pack_var(const BCP_var& var);
286 void pack_cut(const BCP_cut& cut);
292 //-------------------------------------------------------------------------
293
297 inline char
298 param(BCP_tm_par::chr_params key) const { return par.entry(key); }
300 inline int
301 param(BCP_tm_par::int_params key) const { return par.entry(key); }
303 inline double
304 param(BCP_tm_par::dbl_params key) const { return par.entry(key); }
306 inline const BCP_string&
307 param(BCP_tm_par::str_params key) const { return par.entry(key); }
309 inline const BCP_vec<BCP_string>&
310 param(BCP_tm_par::str_array_params key) const { return par.entry(key); }
311
313 inline double granularity() const {
315 }
316
317 //-------------------------------------------------------------------------
319 inline bool has_ub() const { return upper_bound < BCP_DBL_MAX / 10; }
321 inline double ub() const { return upper_bound; }
323 inline bool ub(double new_ub) {
324 if (new_ub < upper_bound){
325 upper_bound = new_ub;
326 return true;
327 }
328 return false;
329 }
331 inline bool over_ub(const double lb) const {
333 }
335 //-------------------------------------------------------------------------
336 virtual BCP_buffer& get_message_buffer() { return msg_buf; }
337 virtual void process_message();
338};
339
340//#############################################################################
341
342#endif
343
BCP_column_generation
This enumerative constant describes what to do when a search tree node becomes fathomable for the cur...
Definition: BCP_enum.hpp:65
#define BCP_DBL_MAX
Definition: BCP_math.hpp:6
This class describes the message buffer used for all processes of BCP.
Definition: BCP_buffer.hpp:39
Abstract base class that defines members common to all types of cuts.
Definition: BCP_cut.hpp:29
NO OLD DOC.
Definition: BCP_lp.hpp:56
This is an abstract base class that describes the message passing environment.
Definition: BCP_message.hpp:30
This class stores data about how an object set (set of vars or set of cuts) changes.
This is the class serves as a holder for a set of parameters.
char entry(const chr_params key) const
This class describes changes in the core of the problem.
This class describes the core of the MIP problem, the variables/cuts in it as well as the matrix corr...
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.
Definition: BCP_string.hpp:13
NO OLD DOC.
Definition: BCP_tm.hpp:136
BCP_solution * feas_sol
Definition: BCP_tm.hpp:163
bool over_ub(const double lb) const
Definition: BCP_tm.hpp:331
virtual void process_message()
char param(BCP_tm_par::chr_params key) const
Definition: BCP_tm.hpp:298
std::multiset< double > lower_bounds
Definition: BCP_tm.hpp:199
std::map< int, BCP_tm_node_to_send * > nodes_to_send
Definition: BCP_tm.hpp:246
std::map< int, BCP_tm_node * > active_nodes
A map from the process ids to the nodes (what they work on)
Definition: BCP_tm.hpp:241
std::map< int, Coin::SmartPtr< BCP_cut > > cuts_local
Definition: BCP_tm.hpp:224
double upper_bound
Definition: BCP_tm.hpp:201
BCP_buffer msg_buf
Definition: BCP_tm.hpp:183
int param(BCP_tm_par::int_params key) const
Definition: BCP_tm.hpp:301
static double lb_multiplier
The lower bounds of the unexplored search tree nodes.
Definition: BCP_tm.hpp:198
int unpack_var()
virtual ~BCP_tm_prob()
int next_var_index_set_start
Definition: BCP_tm.hpp:231
bool need_a_TS
Definition: BCP_tm.hpp:234
double ub() const
Definition: BCP_tm.hpp:321
std::map< int, int > ts_space
Definition: BCP_tm.hpp:235
BCP_problem_core * core
Definition: BCP_tm.hpp:208
BCP_tm_flags flags
Definition: BCP_tm.hpp:177
void pack_var(const BCP_var &var)
int unpack_cut()
double root_node_received_
Definition: BCP_tm.hpp:192
int next_cut_index_set_start
Definition: BCP_tm.hpp:229
const BCP_vec< BCP_string > & param(BCP_tm_par::str_array_params key) const
Definition: BCP_tm.hpp:310
BCP_parameter_set< BCP_tm_par > par
Definition: BCP_tm.hpp:168
std::map< int, int > vars_remote
Definition: BCP_tm.hpp:222
std::vector< int > lp_procs
Definition: BCP_tm.hpp:186
bool has_ub() const
Definition: BCP_tm.hpp:319
BCP_user_pack * packer
A class that holds the methods about how to pack things.
Definition: BCP_tm.hpp:153
bool ub(double new_ub)
Definition: BCP_tm.hpp:323
BCP_var * unpack_var_without_bcpind(BCP_buffer &buf)
double param(BCP_tm_par::dbl_params key) const
Definition: BCP_tm.hpp:304
BCP_scheduler lp_scheduler
Definition: BCP_tm.hpp:188
BCP_tm_user * user
Definition: BCP_tm.hpp:151
BCP_message_environment * msg_env
Definition: BCP_tm.hpp:156
double start_time
Definition: BCP_tm.hpp:203
std::map< int, Coin::SmartPtr< BCP_var > > vars_local
Definition: BCP_tm.hpp:220
double granularity() const
Definition: BCP_tm.hpp:313
BCP_lp_statistics * lp_stat
Definition: BCP_tm.hpp:160
CoinSearchTreeManager candidate_list
Definition: BCP_tm.hpp:243
std::map< int, int > cuts_remote
Definition: BCP_tm.hpp:226
std::vector< int > ts_procs
Definition: BCP_tm.hpp:185
virtual BCP_buffer & get_message_buffer()
Definition: BCP_tm.hpp:336
BCP_tm_stat stat
Definition: BCP_tm.hpp:265
BCP_problem_core_change * core_as_change
Definition: BCP_tm.hpp:210
BCP_cut * unpack_cut_without_bcpind(BCP_buffer &buf)
BCP_vec< std::pair< int, int > > leaves_per_vp
Definition: BCP_tm.hpp:261
BCP_slave_params slave_pars
Definition: BCP_tm.hpp:170
BCP_vec< std::pair< int, int > > leaves_per_cp
Definition: BCP_tm.hpp:259
BCP_tree search_tree
Definition: BCP_tm.hpp:239
BCP_vec< BCP_tm_node * > next_phase_nodes
a vector of nodes to be processed in the next phase
Definition: BCP_tm.hpp:250
double root_node_sent_
members to measure how long it took to process the root node.
Definition: BCP_tm.hpp:191
BCP_vec< BCP_tm_node * > nodes_to_free
Definition: BCP_tm.hpp:252
void pack_cut(const BCP_cut &cut)
const BCP_string & param(BCP_tm_par::str_params key) const
Definition: BCP_tm.hpp:307
BCP_column_generation current_phase_colgen
Definition: BCP_tm.hpp:216
void print(bool final, double t)
void update_wait_time(int i, double t)
Definition: BCP_tm.hpp:124
~BCP_tm_stat()
Definition: BCP_tm.hpp:105
void set_num_lp(int num)
Definition: BCP_tm.hpp:110
BCP_tm_stat()
Definition: BCP_tm.hpp:99
void update_queue_length(int i, int len)
Definition: BCP_tm.hpp:125
The BCP_tm_user class is the base class from which the user can derive a problem specific class to be...
Definition: BCP_tm_user.hpp:58
NO OLD DOC.
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.
Definition: BCP_vector.hpp:24
Warmstarting information for the LP solver.
NO OLD DOC.
Definition: BCP_tm.hpp:57
BCP_parameter_set< BCP_cg_par > cg
Definition: BCP_tm.hpp:65
BCP_parameter_set< BCP_lp_par > lp
Definition: BCP_tm.hpp:61
BCP_parameter_set< BCP_vg_par > vg
Definition: BCP_tm.hpp:67
BCP_parameter_set< BCP_ts_par > ts
Definition: BCP_tm.hpp:59
NO OLD DOC.
Definition: BCP_tm.hpp:74
bool root_pricing_unpacked
Set to true if the result of root pricing is already unpacked.
Definition: BCP_tm.hpp:78
str_params
String parameters.
chr_params
Character parameters.
dbl_params
Double parameters.
@ Granularity
??? Values: Default:
int_params
Integer parameters.