1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 #include "ortools/packing/arc_flow_builder.h"
15
16 #include <algorithm>
17 #include <cstdint>
18
19 #include "absl/container/flat_hash_map.h"
20 #include "absl/strings/str_cat.h"
21 #include "absl/strings/str_join.h"
22 #include "ortools/base/commandlineflags.h"
23 #include "ortools/base/map_util.h"
24 #include "ortools/base/stl_util.h"
25 #include "ortools/graph/topologicalsorter.h"
26
27 namespace operations_research {
28 namespace packing {
29 namespace {
30
31 class ArcFlowBuilder {
32 public:
33 // Same arguments as BuildArcFlowGraph(): see the .h.
34 ArcFlowBuilder(const std::vector<int>& bin_dimensions,
35 const std::vector<std::vector<int>>& item_dimensions_by_type,
36 const std::vector<int>& demand_by_type);
37
38 // Builds the arc-flow graph.
39 ArcFlowGraph BuildVectorBinPackingGraph();
40
41 // For debugging purposes.tring(
42 // Returns the number of states explored in the dynamic programming phase.
43 int64_t NumDpStates() const;
44
45 private:
46 // All items data, regrouped for sorting purposes.
47 struct Item {
48 std::vector<int> dimensions;
49 int demand;
50 int original_index;
51
52 // Used to sort items by relative size.
53 double NormalizedSize(const std::vector<int>& bin_dimensions) const;
54 };
55
56 // State of the dynamic programming algorithm.
57 struct DpState {
58 int cur_item_index;
59 int cur_item_quantity;
60 std::vector<int> used_dimensions;
61 // DP State indices of the states that can be obtained by moving
62 // either "right" to (cur_item_index, cur_item_quantity++) or "up"
63 // to (cur_item_index++, cur_item_quantity=0). -1 if impossible.
64 int right_child;
65 int up_child;
66 };
67
68 // Add item iteratively to create all possible nodes in a forward pass.
69 void ForwardCreationPass(DpState* dp_state);
70 // Scan DP-nodes backward to relabels each nodes by increasing them as much
71 // as possible.
72 void BackwardCompressionPass(int state_index);
73 // Relabel nodes by decreasing them as much as possible.
74 void ForwardCompressionPass(const std::vector<int>& source_node);
75
76 // Can we fit one more item in the bin?
77 bool CanFitNewItem(const std::vector<int>& used_dimensions, int item) const;
78 // Create a new used_dimensions that is used_dimensions + item dimensions.
79 std::vector<int> AddItem(const std::vector<int>& used_dimensions,
80 int item) const;
81
82 // DpState helpers.
83 int LookupOrCreateDpState(int item, int quantity,
84 const std::vector<int>& used_dimensions);
85
86 const std::vector<int> bin_dimensions_;
87 std::vector<Item> items_;
88
89 typedef absl::flat_hash_map<std::vector<int>, int> VectorIntIntMap;
90 int GetOrCreateNode(const std::vector<int>& used_dimensions);
91
92 // We store all DP states in a dense vector, and remember their index
93 // in the dp_state_index_ map (we use a tri-dimensional indexing because
94 // it's faster for the hash part).
95 std::vector<DpState*> dp_states_;
96 std::vector<std::vector<VectorIntIntMap>> dp_state_index_;
97
98 // The ArcFlowGraph will have nodes which will correspond to "some"
99 // of the vector<int> representing the partial bin usages encountered during
100 // the algo. These two data structures map one to the other (note that nodes
101 // are dense integers).
102 absl::flat_hash_map<std::vector<int>, int> node_indices_;
103 std::vector<std::vector<int>> nodes_;
104
105 std::set<ArcFlowGraph::Arc> arcs_;
106 };
107
NormalizedSize(const std::vector<int> & bin_dimensions) const108 double ArcFlowBuilder::Item::NormalizedSize(
109 const std::vector<int>& bin_dimensions) const {
110 double size = 0.0;
111 for (int i = 0; i < bin_dimensions.size(); ++i) {
112 size += static_cast<double>(dimensions[i]) / bin_dimensions[i];
113 }
114 return size;
115 }
116
NumDpStates() const117 int64_t ArcFlowBuilder::NumDpStates() const {
118 int64_t res = 1; // We do not store the initial state.
119 for (const auto& it1 : dp_state_index_) {
120 for (const auto& it2 : it1) {
121 res += it2.size();
122 }
123 }
124 return res;
125 }
126
ArcFlowBuilder(const std::vector<int> & bin_dimensions,const std::vector<std::vector<int>> & item_dimensions_by_type,const std::vector<int> & demand_by_type)127 ArcFlowBuilder::ArcFlowBuilder(
128 const std::vector<int>& bin_dimensions,
129 const std::vector<std::vector<int>>& item_dimensions_by_type,
130 const std::vector<int>& demand_by_type)
131 : bin_dimensions_(bin_dimensions) {
132 // Checks dimensions.
133 for (int i = 0; i < bin_dimensions.size(); ++i) {
134 CHECK_GT(bin_dimensions[i], 0);
135 }
136
137 const int num_items = item_dimensions_by_type.size();
138 items_.resize(num_items);
139 for (int i = 0; i < num_items; ++i) {
140 items_[i].dimensions = item_dimensions_by_type[i];
141 items_[i].demand = demand_by_type[i];
142 items_[i].original_index = i;
143 }
144 std::sort(items_.begin(), items_.end(), [&](const Item& a, const Item& b) {
145 return a.NormalizedSize(bin_dimensions_) >
146 b.NormalizedSize(bin_dimensions_);
147 });
148 }
149
CanFitNewItem(const std::vector<int> & used_dimensions,int item) const150 bool ArcFlowBuilder::CanFitNewItem(const std::vector<int>& used_dimensions,
151 int item) const {
152 for (int d = 0; d < bin_dimensions_.size(); ++d) {
153 if (used_dimensions[d] + items_[item].dimensions[d] > bin_dimensions_[d]) {
154 return false;
155 }
156 }
157 return true;
158 }
159
AddItem(const std::vector<int> & used_dimensions,int item) const160 std::vector<int> ArcFlowBuilder::AddItem(
161 const std::vector<int>& used_dimensions, int item) const {
162 DCHECK(CanFitNewItem(used_dimensions, item));
163 std::vector<int> result = used_dimensions;
164 for (int d = 0; d < bin_dimensions_.size(); ++d) {
165 result[d] += items_[item].dimensions[d];
166 }
167 return result;
168 }
169
GetOrCreateNode(const std::vector<int> & used_dimensions)170 int ArcFlowBuilder::GetOrCreateNode(const std::vector<int>& used_dimensions) {
171 const auto& it = node_indices_.find(used_dimensions);
172 if (it != node_indices_.end()) {
173 return it->second;
174 }
175 const int index = node_indices_.size();
176 node_indices_[used_dimensions] = index;
177 nodes_.push_back(used_dimensions);
178 return index;
179 }
180
BuildVectorBinPackingGraph()181 ArcFlowGraph ArcFlowBuilder::BuildVectorBinPackingGraph() {
182 // Initialize the DP states map.
183 dp_state_index_.resize(items_.size());
184 for (int i = 0; i < items_.size(); ++i) {
185 dp_state_index_[i].resize(items_[i].demand + 1);
186 }
187
188 // Explore all possible DP states (starting from the initial 'empty' state),
189 // and remember their ancestry.
190 std::vector<int> zero(bin_dimensions_.size(), 0);
191 dp_states_.push_back(new DpState({0, 0, zero, -1, -1}));
192 for (int i = 0; i < dp_states_.size(); ++i) {
193 ForwardCreationPass(dp_states_[i]);
194 }
195
196 // We can clear the dp_state_index map as it will not be used anymore.
197 // From now on, we will use the dp_states.used_dimensions to store the new
198 // labels in the backward pass.
199 const int64_t num_dp_states = NumDpStates();
200 dp_state_index_.clear();
201
202 // Backwards pass: "push" the bin dimensions as far as possible.
203 const int num_states = dp_states_.size();
204 std::vector<std::pair<int, int>> flat_deps;
205 for (int i = 0; i < dp_states_.size(); ++i) {
206 if (dp_states_[i]->up_child != -1) {
207 flat_deps.push_back(std::make_pair(dp_states_[i]->up_child, i));
208 }
209 if (dp_states_[i]->right_child != -1) {
210 flat_deps.push_back(std::make_pair(dp_states_[i]->right_child, i));
211 }
212 }
213 const std::vector<int> sorted_work =
214 util::graph::DenseIntStableTopologicalSortOrDie(num_states, flat_deps);
215 for (const int w : sorted_work) {
216 BackwardCompressionPass(w);
217 }
218
219 // ForwardCreationPass again, push the bin dimensions as low as possible.
220 const std::vector<int> source_node = dp_states_[0]->used_dimensions;
221 // We can now delete the states stored in dp_states_.
222 gtl::STLDeleteElements(&dp_states_);
223 ForwardCompressionPass(source_node);
224
225 // We need to connect all nodes that corresponds to at least one item selected
226 // to the sink node.
227 const int sink_node_index = nodes_.size() - 1;
228 for (int node = 1; node < sink_node_index; ++node) {
229 arcs_.insert({node, sink_node_index, -1});
230 }
231
232 ArcFlowGraph result;
233 result.arcs.assign(arcs_.begin(), arcs_.end());
234 result.nodes.assign(nodes_.begin(), nodes_.end());
235 result.num_dp_states = num_dp_states;
236 return result;
237 }
238
LookupOrCreateDpState(int item,int quantity,const std::vector<int> & used_dimensions)239 int ArcFlowBuilder::LookupOrCreateDpState(
240 int item, int quantity, const std::vector<int>& used_dimensions) {
241 VectorIntIntMap& map = dp_state_index_[item][quantity];
242 const int index =
243 map.insert({used_dimensions, dp_states_.size()}).first->second;
244 if (index == dp_states_.size()) {
245 dp_states_.push_back(
246 new DpState({item, quantity, used_dimensions, -1, -1}));
247 }
248 return index;
249 }
250
ForwardCreationPass(DpState * dp_state)251 void ArcFlowBuilder::ForwardCreationPass(DpState* dp_state) {
252 const int item = dp_state->cur_item_index;
253 const int quantity = dp_state->cur_item_quantity;
254 const std::vector<int>& used_dimensions = dp_state->used_dimensions;
255
256 // Explore path up.
257 if (item < items_.size() - 1) {
258 dp_state->up_child = LookupOrCreateDpState(item + 1, 0, used_dimensions);
259 } else {
260 dp_state->up_child = -1;
261 }
262
263 // Explore path right.
264 if (quantity < items_[item].demand && CanFitNewItem(used_dimensions, item)) {
265 const std::vector<int> added = AddItem(used_dimensions, item);
266 dp_state->right_child = LookupOrCreateDpState(item, quantity + 1, added);
267 } else {
268 dp_state->right_child = -1;
269 }
270 }
271
BackwardCompressionPass(int state_index)272 void ArcFlowBuilder::BackwardCompressionPass(int state_index) {
273 // The goal of this function is to fill this.
274 std::vector<int>& result = dp_states_[state_index]->used_dimensions;
275
276 // Inherit our result from the result one step up.
277 const int up_index = dp_states_[state_index]->up_child;
278 const std::vector<int>& result_up =
279 up_index == -1 ? bin_dimensions_ : dp_states_[up_index]->used_dimensions;
280 result = result_up;
281
282 // Adjust our result from the result one step right.
283 const int right_index = dp_states_[state_index]->right_child;
284 if (right_index == -1) return; // We're done.
285 const std::vector<int>& result_right =
286 dp_states_[right_index]->used_dimensions;
287 const Item& item = items_[dp_states_[state_index]->cur_item_index];
288 for (int d = 0; d < bin_dimensions_.size(); ++d) {
289 result[d] = std::min(result[d], result_right[d] - item.dimensions[d]);
290 }
291
292 // Insert the arc from the node to the "right" node.
293 const int node = GetOrCreateNode(result);
294 const int right_node = GetOrCreateNode(result_right);
295 DCHECK_NE(node, right_node);
296 arcs_.insert({node, right_node, item.original_index});
297 // Also insert the 'dotted' arc from the node to the "up" node (if different).
298 if (result != result_up) {
299 const int up_node = GetOrCreateNode(result_up);
300 arcs_.insert({node, up_node, -1});
301 }
302 }
303
304 // Reverse version of the backward pass.
305 // Revisit states forward, and relabel nodes with the longest path in each
306 // dimensions from the source. The only meaningfull difference is that we use
307 // arcs and nodes, instead of dp_states.
ForwardCompressionPass(const std::vector<int> & source_node)308 void ArcFlowBuilder::ForwardCompressionPass(
309 const std::vector<int>& source_node) {
310 const int num_nodes = node_indices_.size();
311 const int num_dims = bin_dimensions_.size();
312 std::set<ArcFlowGraph::Arc> new_arcs;
313 std::vector<std::vector<int>> new_nodes;
314 VectorIntIntMap new_node_indices;
315 std::vector<int> node_remap(num_nodes, -1);
316 // We need to revert the sorting of items as arcs store the original index.
317 std::vector<int> reverse_item_index_map(items_.size(), -1);
318 for (int i = 0; i < items_.size(); ++i) {
319 reverse_item_index_map[items_[i].original_index] = i;
320 }
321
322 std::vector<std::pair<int, int>> forward_deps;
323 std::vector<std::vector<ArcFlowGraph::Arc>> incoming_arcs(num_nodes);
324 for (const ArcFlowGraph::Arc& arc : arcs_) {
325 forward_deps.push_back(std::make_pair(arc.source, arc.destination));
326 incoming_arcs[arc.destination].push_back(arc);
327 }
328
329 const std::vector<int> sorted_work =
330 util::graph::DenseIntStableTopologicalSortOrDie(num_nodes, forward_deps);
331
332 const int old_source_node = GetOrCreateNode(source_node);
333 const int old_sink_node = GetOrCreateNode(bin_dimensions_);
334 CHECK_EQ(sorted_work.front(), old_source_node);
335 CHECK_EQ(sorted_work.back(), old_sink_node);
336
337 // Process nodes in order and remap state to max(previous_state + item
338 // dimensions).
339 for (const int w : sorted_work) {
340 std::vector<int> new_used(num_dims, 0);
341 if (w == sorted_work.back()) { // Do not compress the sink node.
342 new_used = bin_dimensions_;
343 } else {
344 for (const ArcFlowGraph::Arc& arc : incoming_arcs[w]) {
345 const int item =
346 arc.item_index == -1 ? -1 : reverse_item_index_map[arc.item_index];
347 const int prev_node = node_remap[arc.source];
348 const std::vector<int>& prev = new_nodes[prev_node];
349 DCHECK_NE(prev_node, -1);
350 for (int d = 0; d < num_dims; ++d) {
351 if (item != -1) {
352 new_used[d] =
353 std::max(new_used[d], prev[d] + items_[item].dimensions[d]);
354 } else {
355 new_used[d] = std::max(new_used[d], prev[d]);
356 }
357 }
358 }
359 }
360 const auto& it = new_node_indices.find(new_used);
361 if (it != new_node_indices.end()) {
362 node_remap[w] = it->second;
363 } else {
364 const int new_index = new_nodes.size();
365 new_nodes.push_back(new_used);
366 new_node_indices[new_used] = new_index;
367 node_remap[w] = new_index;
368 }
369 }
370 // Remap arcs.
371 for (const ArcFlowGraph::Arc& arc : arcs_) {
372 CHECK_NE(node_remap[arc.source], -1);
373 CHECK_NE(node_remap[arc.destination], -1);
374 // Remove loss arcs between merged nodes.
375 if (arc.item_index == -1 &&
376 node_remap[arc.source] == node_remap[arc.destination])
377 continue;
378 new_arcs.insert(
379 {node_remap[arc.source], node_remap[arc.destination], arc.item_index});
380 }
381 VLOG(1) << "Reduced nodes from " << num_nodes << " to " << new_nodes.size();
382 VLOG(1) << "Reduced arcs from " << arcs_.size() << " to " << new_arcs.size();
383 nodes_ = new_nodes;
384 arcs_ = new_arcs;
385 CHECK_NE(node_remap[old_source_node], -1);
386 CHECK_EQ(0, node_remap[old_source_node]);
387 CHECK_NE(node_remap[old_sink_node], -1);
388 CHECK_EQ(nodes_.size() - 1, node_remap[old_sink_node]);
389 }
390
391 } // namespace
392
operator <(const ArcFlowGraph::Arc & other) const393 bool ArcFlowGraph::Arc::operator<(const ArcFlowGraph::Arc& other) const {
394 if (source != other.source) return source < other.source;
395 if (destination != other.destination) return destination < other.destination;
396 return item_index < other.item_index;
397 }
398
BuildArcFlowGraph(const std::vector<int> & bin_dimensions,const std::vector<std::vector<int>> & item_dimensions_by_type,const std::vector<int> & demand_by_type)399 ArcFlowGraph BuildArcFlowGraph(
400 const std::vector<int>& bin_dimensions,
401 const std::vector<std::vector<int>>& item_dimensions_by_type,
402 const std::vector<int>& demand_by_type) {
403 ArcFlowBuilder afb(bin_dimensions, item_dimensions_by_type, demand_by_type);
404 return afb.BuildVectorBinPackingGraph();
405 }
406
407 } // namespace packing
408 } // namespace operations_research
409