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
56
62 // BCP_parameter_set<BCP_cp_par> cp;
63 // BCP_parameter_set<BCP_vp_par> vp;
68};
69
70//-----------------------------------------------------------------------------
71
73
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
135
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&);
145
146 //-------------------------------------------------------------------------
147public: // Data members
154
158
161
164
172
175 // flags to signal various things
179
185 std::vector<int> ts_procs;
186 std::vector<int> lp_procs;
194
195 //-------------------------------------------------------------------------
198 static double lb_multiplier;
199 std::multiset<double> lower_bounds;
204 //-------------------------------------------------------------------------
212
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 //-------------------------------------------------------------------------
263
264 //-------------------------------------------------------------------------
266
267public:
273 virtual ~BCP_tm_prob();
275
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 }
330
331 inline bool over_ub(const double lb) const {
333 }
334
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.
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.
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.
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...
BCP_process(int self, int my_parent)
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.
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
void set_num_lp(int num)
Definition BCP_tm.hpp:110
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...
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.
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.
int_params
Integer parameters.