idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
Optimizers_BranchAndBound.h
1//
2// Created by henri on 13/03/23.
3//
4
5#ifndef IDOL_OPTIMIZERS_BRANCHANDBOUND_H
6#define IDOL_OPTIMIZERS_BRANCHANDBOUND_H
7
8#include "idol/mixed-integer/optimizers/branch-and-bound/nodes/NodeSet.h"
9#include "idol/general/optimizers/Algorithm.h"
10#include "idol/mixed-integer/optimizers/branch-and-bound/branching-rules/factories/BranchingRuleFactory.h"
11#include "idol/mixed-integer/optimizers/branch-and-bound/node-selection-rules/factories/NodeSelectionRuleFactory.h"
12#include "idol/mixed-integer/optimizers/branch-and-bound/branching-rules/impls/BranchingRule.h"
13#include "idol/mixed-integer/optimizers/branch-and-bound/node-selection-rules/impls/NodeSelectionRule.h"
14#include "idol/mixed-integer/optimizers/branch-and-bound/nodes/Node.h"
15#include "idol/mixed-integer/optimizers/branch-and-bound/nodes/NodeUpdator.h"
16#include "idol/mixed-integer/optimizers/branch-and-bound/callbacks/AbstractBranchAndBoundCallbackI.h"
17#include "idol/general/optimizers/OptimizerFactory.h"
18#include "idol/mixed-integer/modeling/models/Model.h"
19#include "idol/mixed-integer/optimizers/branch-and-bound/logs/Factory.h"
20
21#include <memory>
22#include <cassert>
23#include <fstream>
24
25namespace idol::Optimizers {
26 template<class NodeInfoT> class BranchAndBound;
27}
28
29template<class NodeInfoT>
33
34 std::unique_ptr<OptimizerFactory> m_relaxation_optimizer_factory;
35
36 unsigned int m_n_threads = 1;
37 std::vector<std::unique_ptr<Model>> m_relaxations;
38 std::vector<std::unique_ptr<NodeUpdator<NodeInfoT>>> m_node_updators;
39
40 std::unique_ptr<BranchingRule<NodeInfoT>> m_branching_rule;
41 std::unique_ptr<NodeSelectionRule<NodeInfoT>> m_node_selection_rule;
42 std::unique_ptr<typename Logs::BranchAndBound::Factory<NodeInfoT>::Strategy> m_logger;
43
44 std::unique_ptr<AbstractBranchAndBoundCallbackI<NodeInfoT>> m_callback;
45
46 bool m_has_integer_objective = false;
47 std::vector<unsigned int> m_steps = { std::numeric_limits<unsigned int>::max(), 0, 0 };
48 unsigned int m_n_created_nodes = 0;
49 unsigned int m_n_solved_nodes = 0;
50 unsigned int m_n_active_nodes = 0;
51 double m_root_node_best_bound = -Inf;
52 double m_root_node_best_obj = +Inf;
53
54 std::optional<TreeNode> m_incumbent;
55protected:
56 void build() override;
57 void hook_before_optimize() override;
58 void hook_optimize() override;
59 void hook_after_optimize() override;
60 void add(const Var &t_var) override;
61 void add(const Ctr &t_ctr) override;
62 void add(const QCtr &t_ctr) override;
63 void remove(const Var &t_var) override;
64 void remove(const Ctr &t_ctr) override;
65 void remove(const QCtr &t_ctr) override;
66 void update() override;
67 void write(const std::string &t_name) override;
68
69 void detect_integer_objective();
70 void create_relaxations();
71 Node<NodeInfoT> create_root_node();
72 void explore(TreeNode& t_node, unsigned int t_relaxation_id, SetOfActiveNodes& t_active_nodes, unsigned int t_step);
73 void analyze(const TreeNode& t_node, unsigned int t_relaxation_id, bool* t_explore_children_flag, bool* t_reoptimize_flag);
74 Node<NodeInfoT> select_node_for_branching(SetOfActiveNodes& t_active_nodes);
75 std::vector<TreeNode> create_child_nodes(const TreeNode& t_node);
76 void backtrack(SetOfActiveNodes& t_actives_nodes, SetOfActiveNodes& t_sub_active_nodes);
77 void set_as_incumbent(const TreeNode& t_node);
78 [[nodiscard]] bool gap_is_closed() const;
79 void prune_nodes_by_bound(SetOfActiveNodes& t_active_nodes);
80 void update_lower_bound(const SetOfActiveNodes& t_active_nodes);
81 bool is_valid(const TreeNode& t_node) const;
82
83 void log_node_after_solve(const Node<NodeInfoT>& t_node);
84 void log_after_termination();
85
86 SideEffectRegistry call_callbacks(CallbackEvent t_event, const TreeNode& t_node, unsigned int t_relaxation_id);
87 void update_obj_sense() override;
88 void update_obj() override;
89 void update_rhs() override;
90 void update_obj_constant() override;
91 void update_mat_coeff(const Ctr &t_ctr, const Var &t_var) override;
92 void update_ctr_type(const Ctr &t_ctr) override;
93 void update_ctr_rhs(const Ctr &t_ctr) override;
94 void update_var_type(const Var &t_var) override;
95 void update_var_lb(const Var &t_var) override;
96 void update_var_ub(const Var &t_var) override;
97
98 void update_var_obj(const Var &t_var) override;
99 void set_status(SolutionStatus t_status) override;
100 void set_reason(SolutionReason t_reason) override;
101 void set_best_bound(double t_value) override;
102 void set_best_obj(double t_value) override;
103public:
104 explicit BranchAndBound(const Model& t_model,
105 const OptimizerFactory& t_node_optimizer,
106 const BranchingRuleFactory<NodeInfoT>& t_branching_rule_factory,
107 const NodeSelectionRuleFactory<NodeInfoT>& t_node_selection_rule_factory,
109 const Logs::BranchAndBound::Factory<NodeInfoT>& t_logger_factory);
110
111 [[nodiscard]] std::string name() const override { return "Branch-and-Bound"; }
112
113 void solve(TreeNode& t_node, unsigned int t_relaxation_id) const;
114
115 virtual void set_subtree_depth(unsigned int t_depth) { m_steps.at(1) = t_depth; }
116
117 [[nodiscard]] unsigned int subtree_depth() const { return m_steps.at(1); }
118
119 virtual void add_callback(BranchAndBoundCallback<NodeInfoT>* t_cb);
120
121 void submit_heuristic_solution(NodeInfoT* t_info);
122
123 void submit_lower_bound(double t_lower_bound);
124
125 [[nodiscard]] unsigned int n_created_nodes() const { return m_n_created_nodes; }
126
127 [[nodiscard]] unsigned int n_solved_nodes() const { return m_n_solved_nodes; }
128
129 [[nodiscard]] unsigned int n_active_nodes() const { return m_n_active_nodes; }
130
131 [[nodiscard]] const Model& relaxation() const { return *m_relaxations.front(); }
132
133 [[nodiscard]] Model& relaxation() { return *m_relaxations.front(); }
134
135 [[nodiscard]] double root_node_best_bound() const { return m_root_node_best_bound; }
136
137 [[nodiscard]] double root_node_best_obj() const { return m_root_node_best_obj; }
138
139 BranchingRule<NodeInfoT>& branching_rule() { return *m_branching_rule; }
140
141 const BranchingRule<NodeInfoT>& branching_rule() const { return *m_branching_rule; }
142
143 [[nodiscard]] bool has_incumbent() const { return m_incumbent.has_value(); }
144
145 const TreeNode& incumbent() const { return m_incumbent.value(); }
146
147 [[nodiscard]] double get_var_primal(const Var &t_var) const override;
148
149 [[nodiscard]] double get_var_reduced_cost(const Var &t_var) const override;
150
151 [[nodiscard]] double get_var_ray(const Var &t_var) const override;
152
153 [[nodiscard]] double get_ctr_dual(const Ctr &t_ctr) const override;
154
155 [[nodiscard]] double get_ctr_farkas(const Ctr &t_ctr) const override;
156
157 [[nodiscard]] unsigned int get_n_solutions() const override;
158
159 [[nodiscard]] unsigned int get_solution_index() const override;
160
161 void set_solution_index(unsigned int t_index) override;
162
163 void terminate() override;
164};
165
166template<class NodeInfoT>
168 for (auto& relaxation : m_relaxations) {
169 relaxation->remove(t_ctr);
170 }
171}
172
173template<class NodeInfoT>
175 for (auto& relaxation : m_relaxations) {
176 relaxation->add(t_ctr);
177 }
178}
179
180template<class NodeInfoT>
181bool idol::Optimizers::BranchAndBound<NodeInfoT>::is_valid(const TreeNode &t_node) const {
182 bool result;
183#pragma omp critical
184 result = m_branching_rule->is_valid(t_node);
185 return result;
186}
187
188template<class NodeInfoT>
190#pragma omp critical
191 Optimizer::terminate();
192}
193
194template<class NodeInfoT>
196 const auto& src_model = parent();
197 const auto& objective = src_model.get_obj_expr();
198
199 if (!is_integer(objective.affine().constant(), Tolerance::Integer)) {
200 m_has_integer_objective = false;
201 return;
202 }
203
204 for (const auto& [var, val] : objective.affine().linear()) {
205 if (src_model.get_var_type(var) == Continuous || !is_integer(val, Tolerance::Integer)) {
206 m_has_integer_objective = false;
207 return;
208 }
209 }
210
211 m_has_integer_objective = true;
212}
213
214template<class NodeInfoT>
216 if (m_n_solved_nodes > 1) {
217 throw Exception("Reduced cost not available.");
218 }
219 return m_relaxations.front()->get_var_reduced_cost(t_var);
220}
221
222template<class NodeInfoT>
224
225 if (!get_param_logs()) {
226 return;
227 }
228
229 if (m_callback) {
230 m_callback->log_after_termination();
231 }
232
233 m_logger->log_after_termination();
234
235}
236
237template<class NodeInfoT>
239 m_logger->log_node_after_solve(t_node);
240}
241
242template<class NodeInfoT>
244 if (t_index != 0) {
245 throw Exception("Solution index out of bounds.");
246 }
247}
248
249template<class NodeInfoT>
251 return 0;
252}
253
254template<class NodeInfoT>
256 return m_incumbent.has_value();
257}
258
259template<class NodeInfoT>
261 for (auto& relaxation : m_relaxations) {
262 relaxation->set_obj_expr(parent().get_obj_expr());
263 }
264}
265
266template<class NodeInfoT>
268 for (auto& relaxation : m_relaxations) {
269 relaxation->set_rhs_expr(parent().get_rhs_expr());
270 }
271}
272
273template<class NodeInfoT>
275 for (auto& relaxation : m_relaxations) {
276 relaxation->set_obj_const(parent().get_obj_expr().affine().constant());
277 }
278}
279
280template<class NodeInfoT>
281void idol::Optimizers::BranchAndBound<NodeInfoT>::update_mat_coeff(const Ctr &t_ctr, const Var &t_var) {
282 for (auto& relaxation : m_relaxations) {
283 relaxation->set_mat_coeff(t_ctr, t_var, parent().get_mat_coeff(t_ctr, t_var));
284 }
285}
286
287template<class NodeInfoT>
289 for (auto& relaxation : m_relaxations) {
290 relaxation->set_ctr_type(t_ctr, parent().get_ctr_type(t_ctr));
291 }
292}
293
294template<class NodeInfoT>
296 for (auto& relaxation : m_relaxations) {
297 relaxation->set_ctr_rhs(t_ctr, parent().get_ctr_rhs(t_ctr));
298 }
299}
300
301template<class NodeInfoT>
303 for (auto& relaxation : m_relaxations) {
304 relaxation->set_var_type(t_var, parent().get_var_type(t_var));
305 }
306}
307
308template<class NodeInfoT>
310 for (auto& relaxation : m_relaxations) {
311 relaxation->set_var_lb(t_var, parent().get_var_lb(t_var));
312 }
313}
314
315template<class NodeInfoT>
317 for (auto& relaxation : m_relaxations) {
318 relaxation->set_var_ub(t_var, parent().get_var_ub(t_var));
319 }
320}
321
322template<class NodeInfoT>
324 for (auto& relaxation : m_relaxations) {
325 relaxation->set_var_obj(t_var, parent().get_var_obj(t_var));
326 }
327}
328
329template<class NodeInfoT>
331 throw Exception("Not implemented");
332}
333
334template<class NodeInfoT>
336 if (m_n_solved_nodes > 1) {
337 throw Exception("Accessing Farkas certificate for MIP is not available after the root node.");
338 }
339 return m_relaxations.front()->get_ctr_farkas(t_ctr);
340}
341
342template<class NodeInfoT>
344 if (m_n_solved_nodes > 1) {
345 throw Exception("Accessing dual values for MIP is not available after the root node.");
346 }
347 return m_relaxations.front()->get_ctr_dual(t_ctr);
348}
349
350template<class NodeInfoT>
352 if (m_n_solved_nodes > 1) {
353 throw Exception("Ray not available.");
354 }
355 return m_relaxations.front()->get_var_ray(t_var);
356}
357
358template<class NodeInfoT>
360
361 if (!m_incumbent.has_value()){
362 throw Exception("Trying to access primal values while no incumbent was found.");
363 }
364
365 return m_incumbent->info().primal_solution().get(t_var);
366}
367
368template<class NodeInfoT>
370 if (t_lower_bound > get_best_obj()) {
371 set_status(Fail);
372 set_reason(NotSpecified);
373 terminate();
374 return;
375 }
376 if (t_lower_bound > get_best_bound()) {
377 set_best_bound(t_lower_bound);
378 // New best LB
379 }
380}
381
382template<class NodeInfoT>
384
385 auto t_node = Node<NodeInfoT>::create_detached_node(t_info);
386
387 if (t_node.info().objective_value() < get_best_obj()) {
388
389 //if (m_branching_rule->is_valid(t_node)) {
390 set_as_incumbent(t_node);
391 // New incumbent by submission
392 //} else {
393 // idol_Log(Trace, "Ignoring submitted heuristic solution, solution is not valid.");
394 //}
395
396 } else {
397 // idol_Log(Trace, "Ignoring submitted heuristic solution, objective value is " << t_node.info().objective_value() << " while best obj is " << get_best_obj() << '.');
398 }
399
400}
401
402template<class NodeInfoT>
404idol::Optimizers::BranchAndBound<NodeInfoT>::call_callbacks(CallbackEvent t_event, const Optimizers::BranchAndBound<NodeInfoT>::TreeNode &t_node, unsigned int t_relaxation_id) {
405
406 if (!m_callback) {
407 return {};
408 }
409
410 return m_callback->operator()(this, t_event, t_node, m_relaxations[t_relaxation_id].get());
411}
412
413template<class NodeInfoT>
414void idol::Optimizers::BranchAndBound<NodeInfoT>::add_callback(BranchAndBoundCallback<NodeInfoT> *t_cb) {
415 m_callback->add_callback(t_cb);
416}
417
418template<class NodeInfoT>
420
421}
422
423template<class NodeInfoT>
425 const OptimizerFactory& t_node_optimizer,
426 const BranchingRuleFactory<NodeInfoT>& t_branching_rule_factory,
427 const NodeSelectionRuleFactory<NodeInfoT>& t_node_selection_rule_factory,
428 AbstractBranchAndBoundCallbackI<NodeInfoT>* t_callback,
429 const Logs::BranchAndBound::Factory<NodeInfoT>& t_logger_factory)
430 : Algorithm(t_model),
431 m_relaxation_optimizer_factory(t_node_optimizer.clone()),
432 m_branching_rule(t_branching_rule_factory(*this)),
433 m_node_selection_rule(t_node_selection_rule_factory(*this)),
434 m_callback(t_callback),
435 m_logger(t_logger_factory.operator()(*this)) {
436
437 create_relaxations();
438
439}
440
441template<class NodeInfoT>
443
444 const auto &original_model = parent();
445
446 m_relaxations.clear();
447 m_relaxations.reserve(m_n_threads);
448
449 m_node_updators.clear();
450 m_node_updators.reserve(m_n_threads);
451
452 for (unsigned int i = 0 ; i < m_n_threads ; ++i) {
453 auto* relaxation = original_model.clone();
454 relaxation->use(*m_relaxation_optimizer_factory);
455 m_relaxations.emplace_back(relaxation);
456 m_node_updators.emplace_back(dynamic_cast<NodeUpdator<NodeInfoT>*>(NodeInfoT::create_updator(parent(), *relaxation)));
457 }
458
459}
460
461template<class NodeInfoT>
463
464 auto root_node = Node<NodeInfoT>::create_root_node();
465 assert(root_node.id() == 0);
466 ++m_n_created_nodes;
467
468 return root_node;
469
470}
471
472template<class NodeInfoT>
474 Algorithm::hook_before_optimize();
475
476 // Reset solution
477 set_best_bound(std::max(-Inf, get_param_best_obj_stop()));
478 set_best_obj(std::min(+Inf, get_param_best_bound_stop()));
479 m_incumbent.reset();
480
481 detect_integer_objective();
482
483 m_n_created_nodes = 0;
484 m_n_solved_nodes = 0;
485 m_n_active_nodes = 0;
486
487 m_root_node_best_bound = -Inf;
488 m_root_node_best_obj = Inf;
489
490 m_branching_rule->initialize();
491 for (auto& node_updator : m_node_updators) {
492 node_updator->initialize();
493 }
494 m_callback->initialize(this);
495
496 m_logger->initialize();
497}
498
499template<class NodeInfoT>
501
502 auto root_node = create_root_node();
503
504 SetOfActiveNodes active_nodes;
505
506 explore(root_node, 0, active_nodes, 0);
507
508 if (active_nodes.empty()) {
509 set_best_bound(get_best_obj());
510 }
511
512 m_node_updators[0]->clear();
513
514 if (get_status() == Fail) {
515 return;
516 }
517
518 if (!m_incumbent.has_value()) {
519
520 if (is_pos_inf(get_best_obj())) {
521 set_status(Infeasible);
522 return;
523 }
524
525 if (is_neg_inf(get_best_obj())) {
526 set_status(Unbounded);
527 return;
528 }
529
530 }
531
532 set_status(Feasible);
533
534 if (gap_is_closed()) {
535 set_status(Optimal);
536 set_reason(Proved);
537 return;
538 }
539
540}
541
542template<class NodeInfoT>
544
545 Optimizer::hook_after_optimize();
546
547 log_after_termination();
548
549}
550
551template<class NodeInfoT>
553 TreeNode &t_node,
554 unsigned int t_relaxation_id,
555 SetOfActiveNodes & t_active_nodes,
556 unsigned int t_step) {
557
558 if (is_terminated() || gap_is_closed()) { return; }
559
560 bool reoptimize_flag;
561 bool explore_children_flag;
562
563 do {
564
565 solve(t_node, t_relaxation_id);
566
567 analyze(t_node, t_relaxation_id, &explore_children_flag, &reoptimize_flag);
568
569 log_node_after_solve(t_node);
570
571 } while (reoptimize_flag);
572
573#pragma omp atomic
574 ++m_n_solved_nodes;
575
576 if (is_terminated() || gap_is_closed()) { return; }
577
578 if (!explore_children_flag) { return; }
579
580 t_active_nodes.emplace(t_node);
581
582 const unsigned int max_levels = m_steps.at(t_step);
583
584 for (unsigned int level = 0 ; level < max_levels ; ++level) {
585
586 prune_nodes_by_bound(t_active_nodes);
587
588 if (t_step == 0) {
589 update_lower_bound(t_active_nodes);
590 m_n_active_nodes = t_active_nodes.size();
591 }
592
593 if (t_active_nodes.empty()) { break; }
594
595 if (is_terminated() || gap_is_closed()) { break; }
596
597 auto selected_node = select_node_for_branching(t_active_nodes);
598
599 auto children = create_child_nodes(selected_node);
600
601 const unsigned int n_children = children.size();
602
603 std::vector<SetOfActiveNodes> active_nodes(n_children);
604
605 if (m_n_threads > 1 && t_step == 0) {
606
607 std::vector<std::vector<unsigned int>> to_explore(m_n_threads);
608
609 for (unsigned int q = 0 ; q < n_children ; ++q) {
610 const unsigned int relaxation_id = q % m_n_threads;
611 to_explore[relaxation_id].emplace_back(q);
612 }
613
614#pragma omp parallel for num_threads(m_n_threads)
615 for (unsigned int k = 0 ; k < m_n_threads ; ++k) {
616 for (unsigned int j = 0, n_tasks = to_explore[k].size() ; j < n_tasks ; ++j) {
617 const unsigned int q = to_explore[k][j];
618 explore(children[q], k, active_nodes[q], t_step + 1);
619 }
620 }
621
622 } else {
623
624 for (unsigned int q = 0 ; q < n_children ; ++q) {
625 explore(children[q], t_relaxation_id, active_nodes[q], t_step + 1);
626 }
627
628 }
629
630 for (unsigned int q = 0 ; q < n_children ; ++q) {
631 backtrack(t_active_nodes, active_nodes[q]);
632 }
633
634 }
635
636}
637
638template<class NodeInfoT>
640 unsigned int t_relaxation_id) const {
641
642 auto& node_updator = *m_node_updators[t_relaxation_id];
643 auto& relaxation = *m_relaxations[t_relaxation_id];
644
645 relaxation.optimizer().set_param_best_bound_stop(std::min(get_best_obj(), get_param_best_bound_stop()));
646 relaxation.optimizer().set_param_time_limit(get_remaining_time());
647
648 node_updator.prepare(t_node);
649
650 /*
651 for (const auto& var : parent().vars()) {
652 const double lb = relaxation.get_var_lb(var);
653 const double ub = relaxation.get_var_ub(var);
654 if (lb > ub + Tolerance::Integer) {
655 std::cerr << "Inconsistent bounds for variable " << var << ": " << lb << " > " << ub << std::endl;
656 }
657 }
658 */
659
660 relaxation.optimize();
661
662 t_node.info().save(parent(), relaxation);
663
664 m_branching_rule->on_node_solved(t_node);
665
666}
667
668template<class NodeInfoT>
669void idol::Optimizers::BranchAndBound<NodeInfoT>::analyze(const BranchAndBound::TreeNode &t_node, unsigned int t_relaxation_id, bool* t_explore_children_flag, bool* t_reoptimize_flag) {
670
671 *t_explore_children_flag = false;
672 *t_reoptimize_flag = false;
673
674 if (get_best_bound() > get_best_obj()) {
675 set_status(Fail);
676 set_reason(NotSpecified);
677 terminate();
678 return;
679 }
680
681 const auto& status = t_node.info().status();
682 const auto& reason = t_node.info().reason();
683
684 if (get_remaining_time() == 0 || reason == TimeLimit) {
685 set_reason(TimeLimit);
686 terminate();
687 return;
688 }
689
690 if (status == Unbounded) {
691 set_reason(Proved);
692 set_best_obj(-Inf);
693 terminate();
694 return;
695 }
696
697 if (status == Infeasible || status == InfOrUnbnd) {
698
699 if (t_node.level() == 0) {
700 set_status(status);
701 }
702
703 call_callbacks(PrunedSolution, t_node, t_relaxation_id);
704 return;
705 }
706
707 if (status == Feasible && reason == ObjLimit) {
708 call_callbacks(PrunedSolution, t_node, t_relaxation_id);
709 return;
710 }
711
712 if (status == Fail || status == Loaded) {
713
714 set_status(Fail);
715 set_reason(NotSpecified);
716 terminate();
717 call_callbacks(PrunedSolution, t_node, t_relaxation_id);
718 return;
719 }
720
721 if (t_node.level() == 0) {
722 m_root_node_best_bound = t_node.info().objective_value();
723 }
724
725 if (t_node.info().objective_value() < get_best_obj()) {
726
727 if (is_valid(t_node)) {
728
729 auto side_effects = call_callbacks(IncumbentSolution, t_node, t_relaxation_id);
730
731 if (side_effects.n_added_user_cuts > 0 || side_effects.n_added_lazy_cuts > 0) {
732 *t_reoptimize_flag = true;
733 return;
734 }
735
736 set_as_incumbent(t_node);
737 return;
738
739 }
740
741 } else {
742
743 call_callbacks(PrunedSolution, t_node, t_relaxation_id);
744 return;
745
746 }
747
748 auto side_effects = call_callbacks(InvalidSolution, t_node, t_relaxation_id);
749
750 if (t_node.level() == 0) {
751 m_root_node_best_obj = get_best_obj();
752 }
753
754 if (side_effects.n_added_lazy_cuts > 0 || side_effects.n_added_user_cuts > 0 || side_effects.n_added_local_variable_branching > 0) {
755 *t_reoptimize_flag = true;
756 return;
757 }
758
759 *t_explore_children_flag = true;
760
761}
762
763template<class NodeInfoT>
764void idol::Optimizers::BranchAndBound<NodeInfoT>::set_as_incumbent(const BranchAndBound::TreeNode &t_node) {
765#pragma omp critical
766 m_incumbent = t_node;
767 set_best_obj(t_node.info().objective_value());
768 set_status(Feasible);
769}
770
771template<class NodeInfoT>
772void idol::Optimizers::BranchAndBound<NodeInfoT>::update_lower_bound(const BranchAndBound::SetOfActiveNodes &t_active_nodes) {
773
774 if (t_active_nodes.empty()) { return; }
775
776 auto& lowest_node = *t_active_nodes.by_objective_value().begin();
777 const double raw_lower_bound = lowest_node.info().objective_value();
778 const double lower_bound = m_has_integer_objective && !is_integer(raw_lower_bound, Tolerance::Integer) ? std::ceil(raw_lower_bound) : raw_lower_bound;
779 if (lower_bound > get_best_bound()) {
780 set_best_bound(lower_bound);
781 }
782
783}
784
785template<class NodeInfoT>
786void idol::Optimizers::BranchAndBound<NodeInfoT>::prune_nodes_by_bound(BranchAndBound::SetOfActiveNodes& t_active_nodes) {
787
788 const double upper_bound = get_best_obj();
789
790 auto it = t_active_nodes.by_objective_value().begin();
791 auto end = t_active_nodes.by_objective_value().end();
792
793 while (it != end) {
794
795 const auto& node = *it;
796 const double raw_lower_bound = node.info().objective_value();
797 const double lower_bound = m_has_integer_objective && !is_integer(raw_lower_bound, Tolerance::Integer) ? std::ceil(raw_lower_bound) : raw_lower_bound;
798
799 if (lower_bound >= upper_bound - get_tol_mip_absolute_gap()) {
800 it = t_active_nodes.erase(it);
801 end = t_active_nodes.by_objective_value().end();
802 } else {
803 break;
804 }
805
806 }
807
808}
809
810template<class NodeInfoT>
812idol::Optimizers::BranchAndBound<NodeInfoT>::select_node_for_branching(BranchAndBound::SetOfActiveNodes &t_active_nodes) {
813 auto iterator = m_node_selection_rule->operator()(t_active_nodes);
814 auto result = *iterator;
815 t_active_nodes.erase(iterator);
816 return result;
817}
818
819template<class NodeInfoT>
820void idol::Optimizers::BranchAndBound<NodeInfoT>::write(const std::string &t_name) {
821 m_relaxations.front()->write(t_name);
822}
823
824template<class NodeInfoT>
825std::vector<idol::Node<NodeInfoT>> idol::Optimizers::BranchAndBound<NodeInfoT>::create_child_nodes(const BranchAndBound::TreeNode &t_node) {
826
827 auto children_info = m_branching_rule->create_child_nodes(t_node);
828
829 std::vector<Node<NodeInfoT>> result;
830 result.reserve(children_info.size());
831
832 for (auto* ptr_to_info : children_info) {
833 result.emplace_back(ptr_to_info, m_n_created_nodes++, t_node);
834 }
835
836 m_branching_rule->on_nodes_have_been_created();
837
838 return result;
839}
840
841template<class NodeInfoT>
843 return get_relative_gap() <= get_tol_mip_relative_gap()
844 || get_absolute_gap() <= get_tol_mip_absolute_gap();
845}
846
847template<class NodeInfoT>
848void idol::Optimizers::BranchAndBound<NodeInfoT>::backtrack(BranchAndBound::SetOfActiveNodes &t_actives_nodes,
849 SetOfActiveNodes &t_sub_active_nodes) {
850
851 t_actives_nodes.merge(std::move(t_sub_active_nodes));
852
853}
854
855template<class NodeInfoT>
857 for (auto& relaxation : m_relaxations) {
858 relaxation->update();
859 }
860}
861
862template<class NodeInfoT>
864 for (auto& relaxation : m_relaxations) {
865 relaxation->remove(t_ctr);
866 }
867}
868
869template<class NodeInfoT>
871 for (auto& relaxation : m_relaxations) {
872 relaxation->remove(t_var);
873 }
874}
875
876template<class NodeInfoT>
878 for (auto& relaxation : m_relaxations) {
879 relaxation->add(t_ctr);
880 }
881}
882
883template<class NodeInfoT>
885 for (auto& relaxation : m_relaxations) {
886 relaxation->add(t_var);
887 }
888}
889
890template<class NodeInfoT>
892#pragma omp critical
893 Algorithm::set_best_obj(t_value);
894}
895
896template<class NodeInfoT>
898#pragma omp critical
899 Algorithm::set_best_bound(t_value);
900}
901
902template<class NodeInfoT>
903void idol::Optimizers::BranchAndBound<NodeInfoT>::set_reason(idol::SolutionReason t_reason) {
904#pragma omp critical
905 Algorithm::set_reason(t_reason);
906}
907
908template<class NodeInfoT>
909void idol::Optimizers::BranchAndBound<NodeInfoT>::set_status(idol::SolutionStatus t_status) {
910#pragma omp critical
911 Algorithm::set_status(t_status);
912}
913
914#endif //IDOL_OPTIMIZERS_BRANCHANDBOUND_H
static double Integer
Definition numericals.h:73