Bcp 1.4.4
Loading...
Searching...
No Matches
BCP_lp_branch.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_BRANCH_H
4#define _BCP_LP_BRANCH_H
5
6// This file is fully docified.
7
8#include "BCP_math.hpp"
9#include "BCP_enum_branch.hpp"
10#include "BCP_vector.hpp"
11#include "BCP_lp_result.hpp"
12#include "BCP_USER.hpp"
13#include "BCP_var.hpp"
14#include "BCP_cut.hpp"
15#include "BCP_matrix.hpp"
16
18
20
21//#############################################################################
22
33
34//-----------------------------------------------------------------------------
35
45
46//#############################################################################
47// ASSUMPTION
48// ----------
49// All a branching object does are:
50// - add cuts and/or variables
51// - change bounds on cuts and/or variables
52//#############################################################################
53
54// *THINK* : Maybe the methods should be hidden???
55
56// *THINK* : Maybe we should just use vectors instead of pointers to vectors?
57// *THINK* : It'd simplify things and would not be significant extra storage
58// *THINK* : (maybe none at all, depending pon the system operator new...)
59
69
70class BCP_lp_branching_object {
71private:
75 BCP_lp_branching_object(const BCP_lp_branching_object&);
77 BCP_lp_branching_object& operator=(const BCP_lp_branching_object&);
79
80public:
89
114
134
142
144
145public:
153 explicit BCP_lp_branching_object(const int children,
154 BCP_vec<BCP_var*>* const new_vars,
155 BCP_vec<BCP_cut*>* const new_cuts,
156 const BCP_vec<int>* const fvp,
157 const BCP_vec<int>* const fcp,
158 const BCP_vec<double>* const fvb,
159 const BCP_vec<double>* const fcb,
160 const BCP_vec<int>* const ivp,
161 const BCP_vec<int>* const icp,
162 const BCP_vec<double>* const ivb,
163 const BCP_vec<double>* const icb ) :
164 child_num(children),
170 objval_(0), termcode_(0)
171 {
172 if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) ||
173 ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
174 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
175 if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
176 (fcp && (2 * children* fcp->size() != fcb->size())) ||
177 (ivp && (2 * children* ivp->size() != ivb->size())) ||
178 (icp && (2 * children* icp->size() != icb->size())) )
179 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
180
181 if (new_vars) {
182 vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
183 new_vars->clear();
184 }
185 if (new_cuts) {
186 cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
187 new_cuts->clear();
188 }
189
190 if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
191 if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
192 if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
193 if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);
194
195 if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
196 if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
197 if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
198 if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
199 }
201 const int* order);
204 const int* order);
205
206 inline void set_presolve_result(const BCP_vec<double>& objval,
207 const BCP_vec<int>& termcode) {
208 objval_ = new BCP_vec<double>(objval);
209 termcode_ = new BCP_vec<int>(termcode);
210 }
211
212 // NOTE: when the desctructor `delete's vars_to_add and cuts_to_add, it
213 // will just delete the pointers in the BCP_lp_..._sets (see the
214 // destructors of those classes). But this is intentional, because the
215 // vars/cuts will be actually deleted only later, when the unnecessery
216 // ones are deleted from the formulation.
219 delete vars_to_add; delete cuts_to_add;
220 delete forced_var_pos; delete forced_cut_pos;
221 delete forced_var_bd; delete forced_cut_bd;
222 delete implied_var_pos; delete implied_cut_pos;
223 delete implied_var_bd; delete implied_cut_bd;
224 delete objval_; delete termcode_;
225 }
226
227
232 inline int vars_affected() const {
233 return
234 (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
235 (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
236 }
237
239 inline int cuts_affected() const {
240 return
241 (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
242 (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
243 }
244
245 inline int vars_added() const {
246 return vars_to_add ? vars_to_add->size() : 0;
247 }
248
249 inline int cuts_added() const {
250 return cuts_to_add ? cuts_to_add->size() : 0;
251 }
252
256 inline
258 return forced_var_bd->entry(2 * forced_var_pos->size() * index);
259 }
260
264 inline
266 return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
267 }
268
272 inline
274 return implied_var_bd->entry(2 * implied_var_pos->size() * index);
275 }
276
280 inline
282 return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
283 }
284
285
288 // this routine reorders the positions/bounds as well so that the positions
289 // are in increasing order (the vars/cuts are already added to the problem,
290 // no need to reorder those, too)
296 void init_pos_for_added(const int added_vars_start,
297 const int added_cuts_start);
301 void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
304 void print_branching_info(const int orig_varnum,
305 const double* x, const double * obj) const;
307};
308
309//#############################################################################
310
320
321class BCP_presolved_lp_brobj {
322private:
326 BCP_presolved_lp_brobj(const BCP_presolved_lp_brobj&);
328 BCP_presolved_lp_brobj& operator=(const BCP_presolved_lp_brobj&);
330
331private:
336 BCP_lp_branching_object* _candidate;
339 // what to do with each child
343 BCP_vec<BCP_child_action> _child_action;
347 BCP_vec<BCP_user_data*> _user_data;
349 BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
350 BCP_vec< BCP_vec<BCP_row*> > _new_rows;
352
353public:
359 _candidate(candidate),
360 _lpres(),
361 _child_action(candidate->child_num, BCP_ReturnChild),
362 _user_data(candidate->child_num, NULL)
363 {
364 _lpres.reserve(candidate->child_num);
365 for (int i = candidate->child_num; i; --i) {
366 _lpres.unchecked_push_back(new BCP_lp_result);
367 _new_cuts.push_back(BCP_vec<BCP_cut*>());
368 _new_rows.push_back(BCP_vec<BCP_row*>());
369 }
370 }
371
374 purge_ptr_vector(_lpres);
375 purge_ptr_vector(_user_data);
376 for (int i = _new_cuts.size() - 1; i >= 0; --i) {
377 purge_ptr_vector(_new_cuts[i]);
378 purge_ptr_vector(_new_rows[i]);
379 }
380 }
381
382
389 return _candidate;
390 }
391
392 inline const BCP_lp_branching_object* candidate() const {
393 return _candidate;
394 }
395
397 inline const BCP_lp_result& lpres(const int child_ind) const {
398 return *(_lpres[child_ind]);
399 }
400
404 return _child_action;
405 }
406
407 inline const BCP_vec<BCP_child_action>& action() const {
408 return _child_action;
409 }
410
415 return _user_data;
416 }
417
418 inline const BCP_vec<BCP_user_data*>& user_data() const {
419 return _user_data;
420 }
421
424 bool fathomable(const double objval_limit) const;
429
432 inline void initialize_lower_bound(const double val) {
433 for (int i = _candidate->child_num - 1; i >= 0; --i) {
434 _lpres[i]->fake_objective_value(val);
435 }
436 }
437 inline void keep_no_child() {
438 for (int i = _child_action.size() - 1; i >= 0; --i) {
439 _child_action[i] = BCP_ReturnChild;
440 }
441 }
442 inline bool is_pruned() const {
443 for (int i = _child_action.size() - 1; i >= 0; --i) {
444 if (_child_action[i] != BCP_FathomChild)
445 return false;
446 }
447 return true;
448 }
449
451 obj.clear();
452 obj.reserve(_candidate->child_num);
453 const int num_children = _lpres.size();
454 for (int i = 0; i < num_children; ++i)
455 obj.unchecked_push_back(_lpres[i]->objval());
456 }
457
459 inline void set_lower_bounds(const BCP_vec<double>& obj) {
460 const int num_children = _lpres.size();
461 for (int i = 0; i < num_children; ++i)
462 _lpres[i]->fake_objective_value(obj[i]);
463 }
464
467 inline void get_results(OsiSolverInterface& lp, const int child_ind) {
468 _lpres[child_ind]->get_results(lp);
469 }
470
480 void fake_objective_values(const double itlim_objval);
481
486 const BCP_vec<int>& termcode,
487 const double itlim_objval);
488
490 void swap(BCP_presolved_lp_brobj& rhs) {
491 std::swap(_candidate, rhs._candidate);
492 _lpres.swap(rhs._lpres);
493 _child_action.swap(rhs._child_action);
494 _user_data.swap(rhs._user_data);
495 _new_cuts.swap(rhs._new_cuts);
496 _new_rows.swap(rhs._new_rows);
497 }
498 inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
499 inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
501};
502
503#endif
@ BCP_ReturnChild
This child should be returned to the Tree Manager for later processing.
@ BCP_FathomChild
This child should be fathomed.
void purge_ptr_vector(BCP_vec< T * > &pvec, typename BCP_vec< T * >::iterator first, typename BCP_vec< T * >::iterator last)
This function purges the entries [first,last) from the vector of pointers pvec.
Currently there isn't any error handling in BCP.
Definition BCP_error.hpp:20
This class describes a generic branching object.
BCP_lp_branching_object(const int children, BCP_vec< BCP_var * > *const new_vars, BCP_vec< BCP_cut * > *const new_cuts, const BCP_vec< int > *const fvp, const BCP_vec< int > *const fcp, const BCP_vec< double > *const fvb, const BCP_vec< double > *const fcb, const BCP_vec< int > *const ivp, const BCP_vec< int > *const icp, const BCP_vec< double > *const ivb, const BCP_vec< double > *const icb)
The constructor makes a copy of each vector passed to it.
int vars_added() const
Return the number of variables added in the branching.
BCP_vec< double >::const_iterator forced_cut_bd_child(const int index) const
Return a const iterator to the position in the forced cut bound changes where the new bounds for the ...
BCP_vec< BCP_cut * > * cuts_to_add
Cuts to be added to the formulation.
BCP_vec< int > * termcode_
int cuts_added() const
Return the number of cuts added in the branching.
void apply_child_bd(OsiSolverInterface *lp, const int child_ind) const
This method invokes the appropriate methods of lp to apply the forced and implied bound changes of th...
BCP_vec< int > * forced_var_pos
Positions of variables whose bounds change ("forcibly", by branching) in the children.
int child_num
The number of children for this branching object.
BCP_vec< int > * implied_cut_pos
void set_presolve_result(const BCP_vec< double > &objval, const BCP_vec< int > &termcode)
BCP_vec< double >::const_iterator forced_var_bd_child(const int index) const
Return a const iterator to the position in the forced variable bound changes where the new bounds for...
BCP_lp_branching_object(const OsiSolverInterface *osi, const BCP_lp_sos_branching_object &o, const int *order)
BCP_vec< double >::const_iterator implied_cut_bd_child(const int index) const
Return a const iterator to the position in the implied cut bound changes where the new bounds for the...
BCP_vec< int > * forced_cut_pos
Positions of cuts whose bounds change ("forcibly", by branching) in the children.
BCP_vec< double > * objval_
void print_branching_info(const int orig_varnum, const double *x, const double *obj) const
This method prints out some information about the branching object.
int vars_affected() const
Return the number of variables whose bounds are affected by the branching.
BCP_vec< BCP_var * > * vars_to_add
Variables to be added to the formulation.
BCP_vec< double > * implied_cut_bd
BCP_vec< double >::const_iterator implied_var_bd_child(const int index) const
Return a const iterator to the position in the implied variable bound changes where the new bounds fo...
~BCP_lp_branching_object()
The destructor deletes each vector.
BCP_vec< double > * forced_cut_bd
Contains the actual bounds for the cuts indexed by forced_cut_pos.
BCP_vec< int > * implied_var_pos
BCP_vec< double > * forced_var_bd
Contains the actual bounds for the variables indexed by forced_var_pos.
void init_pos_for_added(const int added_vars_start, const int added_cuts_start)
This method "cleans up" the positions and bounds.
BCP_vec< double > * implied_var_bd
int cuts_affected() const
Return the number of cuts whose bounds are affected by the branching.
BCP_lp_branching_object(const BCP_lp_integer_branching_object &o, const int *order)
This class exist only so that we can extract information from OsiIntegerBranchingObject.
BCP_lp_integer_branching_object(const OsiIntegerBranchingObject *o)
const double * childBounds(int i) const
This class holds the results after solving an LP relaxation.
This class exist only so that we can extract information from OsiIntegerBranchingObject.
BCP_lp_sos_branching_object(const OsiSOSBranchingObject *o)
void initialize_lower_bound(const double val)
const BCP_lp_branching_object * candidate() const
Return a const pointer to the candidate.
const BCP_lp_result & lpres(const int child_ind) const
Return a const reference to the presolved results of the child_ind-th child.
void get_lower_bounds(BCP_vec< double > &obj)
Fill up obj with the lower bound on each child.
BCP_vec< BCP_vec< BCP_row * > > & get_new_rows()
bool fathomable(const double objval_limit) const
Return true if every children can be fathomed.
void fake_objective_values(const double itlim_objval)
Examine the termination codes for the children and for those that do not have a valid lower bound fak...
BCP_vec< BCP_child_action > & action()
Return a reference to the actions to be taken.
bool had_numerical_problems() const
Return true if at least one child had numerical difficulties while presolving.
void set_objective_values(const BCP_vec< double > &obj, const BCP_vec< int > &termcode, const double itlim_objval)
Set the appropriate fields of all _lpres to the given termcode and objval if the termcode is "normal"...
void set_lower_bounds(const BCP_vec< double > &obj)
Fill up the lower bounds on the children with the content of obj.
const BCP_vec< BCP_user_data * > & user_data() const
Return a const reference to the user data vector.
~BCP_presolved_lp_brobj()
The destructor simply deletes every member (deletes every lpres in the vector).
BCP_vec< BCP_user_data * > & user_data()
Return a reference to the user data vector.
const BCP_vec< BCP_child_action > & action() const
Return a const reference to the actions to be taken.
BCP_lp_branching_object * candidate()
Return a pointer to the candidate.
void swap(BCP_presolved_lp_brobj &rhs)
swap the two presolved branching object
BCP_presolved_lp_brobj(BCP_lp_branching_object *candidate)
The only one way to construct a presolved branching object is to create it from a regular branching o...
void get_results(OsiSolverInterface &lp, const int child_ind)
Extract the lp results from the LP solver for the child_ind-th child.
BCP_vec< BCP_vec< BCP_cut * > > & get_new_cuts()
The class BCP_vec serves the same purpose as the vector class in the standard template library.
const T * const_iterator
void clear()
Delete every entry.
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
size_t size() const
Return the current number of entries.
void reserve(const size_t n)
Reallocate the object to make space for n entries.