25#include "absl/log/check.h"
26#include "absl/log/log.h"
27#include "absl/log/vlog_is_on.h"
28#include "absl/numeric/bits.h"
29#include "absl/random/distributions.h"
30#include "absl/types/span.h"
42 if (!VLOG_IS_ON(1))
return;
43 std::vector<std::pair<std::string, int64_t>> stats;
45 {
"OrthogonalPackingInfeasibilityDetector/called", num_calls_});
47 {
"OrthogonalPackingInfeasibilityDetector/conflicts", num_conflicts_});
48 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/dff0_conflicts",
49 num_conflicts_dff0_});
50 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/dff2_conflicts",
51 num_conflicts_dff2_});
52 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/trivial_conflicts",
53 num_trivial_conflicts_});
54 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/conflicts_two_items",
55 num_conflicts_two_items_});
56 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/no_energy_conflict",
57 num_scheduling_possible_});
58 stats.push_back({
"OrthogonalPackingInfeasibilityDetector/brute_force_calls",
59 num_brute_force_calls_});
61 {
"OrthogonalPackingInfeasibilityDetector/brute_force_conflicts",
62 num_brute_force_conflicts_});
64 {
"OrthogonalPackingInfeasibilityDetector/brute_force_relaxations",
65 num_brute_force_relaxation_});
67 shared_stats_->AddStats(stats);
71std::optional<std::pair<int, int>> FindPairwiseConflict(
72 absl::Span<const IntegerValue> sizes_x,
73 absl::Span<const IntegerValue> sizes_y,
74 std::pair<IntegerValue, IntegerValue> bounding_box_size,
75 absl::Span<const int> index_by_decreasing_x_size,
76 absl::Span<const int> index_by_decreasing_y_size) {
81 while (x_idx < index_by_decreasing_x_size.size() &&
82 y_idx < index_by_decreasing_y_size.size()) {
83 if (index_by_decreasing_x_size[x_idx] ==
84 index_by_decreasing_y_size[y_idx]) {
85 if (sizes_x[index_by_decreasing_x_size[x_idx]] >
86 sizes_y[index_by_decreasing_x_size[x_idx]]) {
93 const bool overlap_on_x = (sizes_x[index_by_decreasing_x_size[x_idx]] +
94 sizes_x[index_by_decreasing_y_size[y_idx]] >
95 bounding_box_size.first);
96 const bool overlap_on_y = (sizes_y[index_by_decreasing_x_size[x_idx]] +
97 sizes_y[index_by_decreasing_y_size[y_idx]] >
98 bounding_box_size.second);
99 if (overlap_on_x && overlap_on_y) {
100 return std::make_pair(index_by_decreasing_x_size[x_idx],
101 index_by_decreasing_y_size[y_idx]);
102 }
else if (overlap_on_x) {
104 }
else if (overlap_on_y) {
113IntegerValue RoundingLowestInverse(IntegerValue y, IntegerValue c_k,
114 IntegerValue max_x, IntegerValue k) {
116 DCHECK_LE(y, 2 * c_k);
117 IntegerValue ret = std::numeric_limits<IntegerValue>::max();
120 if (y <= c_k && (max_x.value() & 1) == 0) {
121 const IntegerValue inverse_mid = max_x / 2;
122 ret = std::min(ret, inverse_mid);
123 if (y == c_k && y.value() & 1) {
133 const IntegerValue inverse_high = max_x - k * (c_k - y / 2);
134 if (2 * inverse_high > max_x) {
138 const IntegerValue lowest_inverse_high =
139 std::max(max_x / 2 + 1, inverse_high - k + 1);
140 ret = std::min(ret, lowest_inverse_high);
144 const IntegerValue inverse_low = k * y / 2;
145 if (2 * inverse_low < max_x) {
146 ret = std::min(ret, inverse_low);
153 return RoundingLowestInverse(y, c_k_, max_x_, k_);
157 IntegerValue y)
const {
158 return RoundingLowestInverse(y, c_k_, max_x_, IntegerValue(1) << log2_k_);
175 absl::Span<const IntegerValue> sizes_x,
176 absl::Span<const IntegerValue> sizes_y,
177 absl::Span<const int> index_by_decreasing_x_size,
178 absl::Span<const IntegerValue> g_x, IntegerValue g_max,
179 IntegerValue x_bb_size, IntegerValue total_energy, IntegerValue bb_area,
180 IntegerValue* best_k) {
184 int num_items = sizes_x.size();
185 auto build_result = [&sizes_x, &sizes_y, num_items, &x_bb_size, &bb_area,
186 &g_max, &g_x](
const IntegerValue k) {
187 std::vector<std::pair<int, IntegerValue>> index_to_energy;
188 index_to_energy.reserve(num_items);
189 for (
int i = 0;
i < num_items;
i++) {
190 IntegerValue point_value;
191 if (sizes_x[
i] > x_bb_size - k) {
193 }
else if (sizes_x[
i] < k) {
196 point_value = g_x[
i];
198 index_to_energy.push_back({
i, point_value * sizes_y[
i]});
200 std::sort(index_to_energy.begin(), index_to_energy.end(),
201 [](
const std::pair<int, IntegerValue>& a,
202 const std::pair<int, IntegerValue>&
b) {
203 return a.second > b.second;
205 IntegerValue recomputed_energy = 0;
206 for (
int i = 0;
i < index_to_energy.size();
i++) {
207 recomputed_energy += index_to_energy[
i].second;
208 if (recomputed_energy > bb_area) {
209 OrthogonalPackingResult result(
211 result.conflict_type_ = OrthogonalPackingResult::ConflictType::DFF_F0;
212 result.items_participating_on_conflict_.resize(
i + 1);
213 for (
int j = 0; j <=
i; j++) {
214 const int index = index_to_energy[j].first;
215 result.items_participating_on_conflict_[j] = {
217 .size_x = sizes_x[index],
218 .size_y = sizes_y[index]};
224 LOG(FATAL) <<
"build_result called with no conflict";
234 IntegerValue current_energy = total_energy;
235 OrthogonalPackingResult best_result;
236 if (current_energy > bb_area) {
237 best_result = build_result(0);
242 int removing_item_index = index_by_decreasing_x_size.size() - 1;
243 int enlarging_item_index = 0;
244 while (enlarging_item_index < index_by_decreasing_x_size.size()) {
245 int index = index_by_decreasing_x_size[enlarging_item_index];
246 IntegerValue size = sizes_x[index];
250 const IntegerValue k = x_bb_size - size + 1;
251 if (2 * k > x_bb_size) {
258 index = index_by_decreasing_x_size[enlarging_item_index];
259 size = sizes_x[index];
260 current_energy += (g_max - g_x[index]) * sizes_y[index];
261 enlarging_item_index++;
262 }
while (enlarging_item_index < index_by_decreasing_x_size.size() &&
263 sizes_x[index_by_decreasing_x_size[enlarging_item_index]] == size);
267 while (removing_item_index >= 0 &&
268 sizes_x[index_by_decreasing_x_size[removing_item_index]] < k) {
269 const int remove_idx = index_by_decreasing_x_size[removing_item_index];
270 current_energy -= g_x[remove_idx] * sizes_y[remove_idx];
271 removing_item_index--;
274 if (current_energy > bb_area) {
275 OrthogonalPackingResult current_result = build_result(k);
276 if (current_result.IsBetterThan(best_result)) {
277 best_result = current_result;
309bool FindHeuristicSchedulingSolution(
310 absl::Span<const IntegerValue> sizes,
311 absl::Span<const IntegerValue> demands,
312 absl::Span<const int> heuristic_order, IntegerValue global_end_max,
313 IntegerValue capacity_max,
314 std::vector<std::pair<IntegerValue, IntegerValue>>& profile,
315 std::vector<std::pair<IntegerValue, IntegerValue>>& new_profile) {
322 for (
int i = 0;
i < heuristic_order.size();
i++) {
323 const IntegerValue event_size = sizes[heuristic_order[
i]];
324 const IntegerValue event_demand = demands[heuristic_order[
i]];
325 const IntegerValue event_start_min = 0;
326 const IntegerValue event_start_max = global_end_max - event_size;
327 const IntegerValue start_min =
328 std::max(event_start_min, start_of_previous_task);
333 while (profile[current + 1].first <= start_min ||
334 profile[current].second < event_demand) {
338 const IntegerValue actual_start =
339 std::max(start_min, profile[current].first);
340 start_of_previous_task = actual_start;
343 if (actual_start > event_start_max)
return false;
345 const IntegerValue actual_end = actual_start + event_size;
348 if (
i == heuristic_order.size() - 1)
break;
352 new_profile.push_back(
353 {actual_start, profile[current].second - event_demand});
356 while (profile[current].first < actual_end) {
357 new_profile.push_back(
358 {profile[current].first, profile[current].second - event_demand});
362 if (profile[current].first > actual_end) {
363 new_profile.push_back(
364 {actual_end, new_profile.back().second + event_demand});
366 while (current < profile.size()) {
367 new_profile.push_back(profile[current]);
370 profile.swap(new_profile);
398void OrthogonalPackingInfeasibilityDetector::GetAllCandidatesForKForDff2(
399 absl::Span<const IntegerValue> sizes, IntegerValue bb_size,
400 IntegerValue sqrt_bb_size, Bitset64<IntegerValue>& candidates) {
402 candidates.ClearAndResize(bb_size / 2 + 2);
405 for (IntegerValue
i = 2;
i <= sqrt_bb_size;
i++) {
408 for (
int i = 1;
i <= sqrt_bb_size;
i++) {
409 const ::util::math::ConstantDivisor<uint16_t> div(
i);
411 candidates.Set(bb_size.value() / div);
413 for (
int k = 0; k < sizes.size(); k++) {
414 IntegerValue size = sizes[k];
415 if (2 * size > bb_size && size < bb_size) {
416 candidates.Set((bb_size.value() - size.value() + 1) / div);
417 }
else if (2 * size < bb_size) {
418 candidates.Set(size.value() / div);
436 candidates.Resize(bb_size / 4 + 1);
437 candidates.Resize(bb_size / 3 + 2);
438 candidates.Set(bb_size / 4 + 1);
440 candidates.Set(bb_size / 3 + 1);
455OrthogonalPackingInfeasibilityDetector::CheckFeasibilityWithDualFunction2(
456 absl::Span<const IntegerValue> sizes_x,
457 absl::Span<const IntegerValue> sizes_y,
458 absl::Span<const int> index_by_decreasing_x_size, IntegerValue x_bb_size,
459 IntegerValue y_bb_size,
int max_number_of_parameters_to_check) {
460 if (x_bb_size == 1) {
461 return OrthogonalPackingResult();
463 std::vector<IntegerValue> sizes_x_rescaled;
464 if (x_bb_size >= std::numeric_limits<uint16_t>::max()) {
469 absl::bit_width(
static_cast<uint64_t
>(x_bb_size.value() + 1)) - 16 + 1;
470 const RoundingDualFeasibleFunctionPowerOfTwo dff(x_bb_size, log2_k);
471 sizes_x_rescaled.resize(sizes_x.size());
472 for (
int i = 0;
i < sizes_x.size();
i++) {
473 sizes_x_rescaled[
i] = dff(sizes_x[
i]);
475 x_bb_size = dff(x_bb_size);
476 CHECK_LT(x_bb_size, std::numeric_limits<uint16_t>::max());
477 sizes_x = sizes_x_rescaled;
480 Bitset64<IntegerValue> candidates;
482 int num_items = sizes_x.size();
483 const IntegerValue max_possible_number_of_parameters =
484 std::min(x_bb_size / 4 + 1, sqrt_bb_size * num_items);
485 if (5ull * max_number_of_parameters_to_check <
486 max_possible_number_of_parameters) {
490 candidates.Resize(x_bb_size / 4 + 1);
491 int num_candidates = 0;
492 while (num_candidates < max_number_of_parameters_to_check) {
493 const IntegerValue pick =
494 absl::Uniform(random_, 1, x_bb_size.value() / 4);
495 if (!candidates.IsSet(pick)) {
496 candidates.Set(pick);
501 GetAllCandidatesForKForDff2(sizes_x, x_bb_size, sqrt_bb_size, candidates);
503 if (max_number_of_parameters_to_check < max_possible_number_of_parameters) {
507 for (
auto it = candidates.begin(); it != candidates.end(); ++it) {
510 if (count > max_number_of_parameters_to_check) {
511 std::vector<IntegerValue> sampled_candidates(
512 max_number_of_parameters_to_check);
513 std::sample(candidates.begin(), candidates.end(),
514 sampled_candidates.begin(),
515 max_number_of_parameters_to_check, random_);
516 candidates.ClearAll();
517 for (
const IntegerValue k : sampled_candidates) {
523 OrthogonalPackingResult best_result;
526 std::vector<IntegerValue> modified_sizes(num_items);
527 for (
const IntegerValue k : candidates) {
528 const RoundingDualFeasibleFunction dff(x_bb_size, k);
529 IntegerValue energy = 0;
530 for (
int i = 0;
i < num_items;
i++) {
531 modified_sizes[
i] = dff(sizes_x[
i]);
532 energy += modified_sizes[
i] * sizes_y[
i];
534 const IntegerValue modified_x_bb_size = dff(x_bb_size);
537 GetDffConflict(sizes_x, sizes_y, index_by_decreasing_x_size,
538 modified_sizes, modified_x_bb_size, x_bb_size, energy,
539 modified_x_bb_size * y_bb_size, &dff0_k);
543 DFFComposedF2F0 composed_dff(x_bb_size, dff0_k, k);
544 dff0_res.conflict_type_ = OrthogonalPackingResult::ConflictType::DFF_F2;
545 for (
auto& item : dff0_res.items_participating_on_conflict_) {
547 composed_dff.LowestInverse(composed_dff(sizes_x[item.index]));
551 DCHECK_EQ(composed_dff(item.size_x), composed_dff(sizes_x[item.index]));
552 DCHECK_LE(item.size_x, sizes_x[item.index]);
554 item.size_y = sizes_y[item.index];
556 if (dff0_res.IsBetterThan(best_result)) {
557 best_result = dff0_res;
564bool OrthogonalPackingInfeasibilityDetector::RelaxConflictWithBruteForce(
566 std::pair<IntegerValue, IntegerValue> bounding_box_size,
567 int brute_force_threshold) {
568 const int num_items_originally =
569 result.items_participating_on_conflict_.size();
570 if (num_items_originally > 2 * brute_force_threshold) {
574 std::vector<IntegerValue> sizes_x;
575 std::vector<IntegerValue> sizes_y;
576 std::vector<int> indexes;
577 std::vector<bool> to_be_removed(num_items_originally,
false);
579 sizes_x.reserve(num_items_originally - 1);
580 sizes_y.reserve(num_items_originally - 1);
581 for (
int i = 0;
i < num_items_originally;
i++) {
585 for (
int j = 0; j < num_items_originally; j++) {
586 if (
i == j || to_be_removed[j]) {
589 sizes_x.push_back(result.items_participating_on_conflict_[j].size_x);
590 sizes_y.push_back(result.items_participating_on_conflict_[j].size_y);
593 sizes_x, sizes_y, bounding_box_size, brute_force_threshold);
596 to_be_removed[
i] =
true;
599 if (!std::any_of(to_be_removed.begin(), to_be_removed.end(),
600 [](
bool b) { return b; })) {
603 OrthogonalPackingResult original = result;
605 result.conflict_type_ = OrthogonalPackingResult::ConflictType::BRUTE_FORCE;
607 result.items_participating_on_conflict_.clear();
608 for (
int i = 0;
i < num_items_originally;
i++) {
609 if (to_be_removed[
i]) {
612 result.items_participating_on_conflict_.push_back(
613 original.items_participating_on_conflict_[
i]);
619OrthogonalPackingInfeasibilityDetector::TestFeasibilityImpl(
620 absl::Span<const IntegerValue> sizes_x,
621 absl::Span<const IntegerValue> sizes_y,
622 std::pair<IntegerValue, IntegerValue> bounding_box_size,
624 using ConflictType = OrthogonalPackingResult::ConflictType;
626 const int num_items = sizes_x.size();
627 DCHECK_EQ(num_items, sizes_y.size());
628 const IntegerValue bb_area =
629 bounding_box_size.first * bounding_box_size.second;
630 IntegerValue total_energy = 0;
632 auto make_item = [sizes_x, sizes_y](
int i) {
633 return OrthogonalPackingResult::Item{
634 .index =
i, .size_x = sizes_x[
i], .size_y = sizes_y[
i]};
637 index_by_decreasing_x_size_.resize(num_items);
638 index_by_decreasing_y_size_.resize(num_items);
639 for (
int i = 0;
i < num_items;
i++) {
640 total_energy += sizes_x[
i] * sizes_y[
i];
641 index_by_decreasing_x_size_[
i] =
i;
642 index_by_decreasing_y_size_[
i] =
i;
643 if (sizes_x[
i] > bounding_box_size.first ||
644 sizes_y[
i] > bounding_box_size.second) {
645 OrthogonalPackingResult result(
647 result.conflict_type_ = ConflictType::TRIVIAL;
648 result.items_participating_on_conflict_ = {make_item(
i)};
653 if (num_items <= 1) {
657 std::sort(index_by_decreasing_x_size_.begin(),
658 index_by_decreasing_x_size_.end(),
659 [&sizes_x, &sizes_y](
int a,
int b) {
661 return std::tie(sizes_x[a], sizes_y[a]) >
662 std::tie(sizes_x[b], sizes_y[b]);
664 std::sort(index_by_decreasing_y_size_.begin(),
665 index_by_decreasing_y_size_.end(),
666 [&sizes_y, &sizes_x](
int a,
int b) {
667 return std::tie(sizes_y[a], sizes_x[a]) >
668 std::tie(sizes_y[b], sizes_x[b]);
672 if (options.use_pairwise) {
673 if (
auto pair = FindPairwiseConflict(sizes_x, sizes_y, bounding_box_size,
674 index_by_decreasing_x_size_,
675 index_by_decreasing_y_size_);
677 OrthogonalPackingResult result(
679 result.conflict_type_ = ConflictType::PAIRWISE;
680 result.items_participating_on_conflict_ = {
681 make_item(pair.value().first), make_item(pair.value().second)};
684 if (num_items == 2) {
690 if (total_energy > bb_area) {
691 result.conflict_type_ = ConflictType::TRIVIAL;
693 std::vector<std::pair<int, IntegerValue>> index_to_energy;
694 index_to_energy.reserve(num_items);
695 for (
int i = 0;
i < num_items;
i++) {
696 index_to_energy.push_back({
i, sizes_x[
i] * sizes_y[
i]});
698 std::sort(index_to_energy.begin(), index_to_energy.end(),
699 [](
const std::pair<int, IntegerValue>& a,
700 const std::pair<int, IntegerValue>&
b) {
701 return a.second > b.second;
703 IntegerValue recomputed_energy = 0;
704 for (
int i = 0;
i < index_to_energy.size();
i++) {
705 recomputed_energy += index_to_energy[
i].second;
706 if (recomputed_energy > bb_area) {
707 result.items_participating_on_conflict_.resize(
i + 1);
708 for (
int j = 0; j <=
i; j++) {
709 result.items_participating_on_conflict_[j] =
710 make_item(index_to_energy[j].first);
712 result.slack_ = recomputed_energy - bb_area - 1;
718 const int minimum_conflict_size = options.use_pairwise ? 3 : 2;
719 if (result.items_participating_on_conflict_.size() == minimum_conflict_size) {
723 if (options.use_dff_f0) {
732 GetDffConflict(sizes_x, sizes_y, index_by_decreasing_x_size_, sizes_x,
733 bounding_box_size.first, bounding_box_size.first,
734 total_energy, bb_area, &best_k);
735 if (conflict.IsBetterThan(result)) {
740 GetDffConflict(sizes_y, sizes_x, index_by_decreasing_y_size_, sizes_y,
741 bounding_box_size.second, bounding_box_size.second,
742 total_energy, bb_area, &best_k);
743 for (
auto& item : conflict.items_participating_on_conflict_) {
744 std::swap(item.size_x, item.size_y);
746 if (conflict.IsBetterThan(result)) {
751 if (result.items_participating_on_conflict_.size() == minimum_conflict_size) {
755 bool found_scheduling_solution =
false;
756 if (options.use_dff_f2) {
760 if (FindHeuristicSchedulingSolution(
761 sizes_x, sizes_y, index_by_decreasing_x_size_,
762 bounding_box_size.first, bounding_box_size.second,
763 scheduling_profile_, new_scheduling_profile_) ||
764 FindHeuristicSchedulingSolution(
765 sizes_y, sizes_x, index_by_decreasing_y_size_,
766 bounding_box_size.second, bounding_box_size.first,
767 scheduling_profile_, new_scheduling_profile_)) {
768 num_scheduling_possible_++;
770 found_scheduling_solution =
true;
774 if (!found_scheduling_solution && options.use_dff_f2) {
777 auto conflict = CheckFeasibilityWithDualFunction2(
778 sizes_x, sizes_y, index_by_decreasing_x_size_, bounding_box_size.first,
779 bounding_box_size.second,
780 options.dff2_max_number_of_parameters_to_check);
781 if (conflict.IsBetterThan(result)) {
785 if (result.items_participating_on_conflict_.size() ==
786 minimum_conflict_size) {
789 conflict = CheckFeasibilityWithDualFunction2(
790 sizes_y, sizes_x, index_by_decreasing_y_size_, bounding_box_size.second,
791 bounding_box_size.first,
792 options.dff2_max_number_of_parameters_to_check);
793 for (
auto& item : conflict.items_participating_on_conflict_) {
794 std::swap(item.size_x, item.size_y);
796 if (conflict.IsBetterThan(result)) {
803 sizes_x, sizes_y, bounding_box_size, options.brute_force_threshold);
804 num_brute_force_calls_ +=
807 result.conflict_type_ = ConflictType::BRUTE_FORCE;
809 result.items_participating_on_conflict_.resize(num_items);
810 for (
int i = 0;
i < num_items;
i++) {
811 result.items_participating_on_conflict_[
i] = make_item(
i);
819 num_brute_force_relaxation_ += RelaxConflictWithBruteForce(
820 result, bounding_box_size, options.brute_force_threshold);
827 absl::Span<const IntegerValue> sizes_x,
828 absl::Span<const IntegerValue> sizes_y,
829 std::pair<IntegerValue, IntegerValue> bounding_box_size,
831 using ConflictType = OrthogonalPackingResult::ConflictType;
835 TestFeasibilityImpl(sizes_x, sizes_y, bounding_box_size, options);
839 switch (result.conflict_type_) {
840 case ConflictType::DFF_F0:
841 num_conflicts_dff0_++;
843 case ConflictType::DFF_F2:
844 num_conflicts_dff2_++;
846 case ConflictType::PAIRWISE:
847 num_conflicts_two_items_++;
849 case ConflictType::TRIVIAL:
851 num_trivial_conflicts_++;
853 case ConflictType::BRUTE_FORCE:
854 num_brute_force_conflicts_++;
856 case ConflictType::NO_CONFLICT:
857 LOG(FATAL) <<
"Should never happen";
865 int i,
Coord coord, IntegerValue lower_bound) {
866 Item& item = items_participating_on_conflict_[
i];
868 const IntegerValue orthogonal_size =
871 if (size <= lower_bound || orthogonal_size > slack_) {
874 const IntegerValue new_size =
875 std::max(lower_bound, size - slack_ / orthogonal_size);
876 slack_ -= (size - new_size) * orthogonal_size;
877 DCHECK_NE(size, new_size);
878 DCHECK_GE(slack_, 0);
OrthogonalPackingResult TestFeasibility(absl::Span< const IntegerValue > sizes_x, absl::Span< const IntegerValue > sizes_y, std::pair< IntegerValue, IntegerValue > bounding_box_size, const OrthogonalPackingOptions &options=OrthogonalPackingOptions())
~OrthogonalPackingInfeasibilityDetector()
bool TryUseSlackToReduceItemSize(int i, Coord coord, IntegerValue lower_bound=0)
IntegerValue LowestInverse(IntegerValue y) const
IntegerValue LowestInverse(IntegerValue y) const
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
int64_t FloorSquareRoot(int64_t a)
The argument must be non-negative.
BruteForceResult BruteForceOrthogonalPacking(absl::Span< const IntegerValue > sizes_x, absl::Span< const IntegerValue > sizes_y, std::pair< IntegerValue, IntegerValue > bounding_box_size, int max_complexity)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid