20#include "absl/container/btree_map.h"
21#include "absl/flags/flag.h"
29 "File to store the solver specific optimization proto.");
35double ConvertVectorBinPackingProblem(
const vbp::VectorBinPackingProblem&
input,
36 ArcFlowGraph* graph) {
39 const int num_items =
input.item_size();
40 const int num_dims =
input.resource_capacity_size();
43 std::vector<std::vector<int>> shapes(num_items);
44 std::vector<int> demands(num_items);
45 std::vector<int> capacities(num_dims);
46 for (
int i = 0; i < num_items; ++i) {
47 shapes[i].assign(
input.item(i).resource_usage().begin(),
48 input.item(i).resource_usage().end());
50 input.item(i).num_copies() +
input.item(i).num_optional_copies();
52 for (
int i = 0;
i < num_dims; ++
i) {
53 capacities[
i] =
input.resource_capacity(i);
57 for (
int i = 0;
i < num_items; ++
i) {
58 const int max_copies =
input.item(i).max_number_of_copies_per_bin();
59 if (max_copies == 0 || max_copies >= demands[i])
continue;
60 capacities.push_back(max_copies);
61 for (
int j = 0; j < num_items; ++j) {
62 shapes[j].push_back(i == j);
67 const double arc_flow_time = timer.
Get();
69 VLOG(1) <<
"The arc-flow grah has " << graph->nodes.size() <<
" nodes, and "
70 << graph->arcs.size() <<
" arcs. It was created by exploring "
71 << graph->num_dp_states
72 <<
" states in the dynamic programming phase in " << arc_flow_time
81 const std::string& mip_params,
double time_limit,
int num_threads,
84 const double arc_flow_time = ConvertVectorBinPackingProblem(problem, &graph);
88 max_num_bins = max_bins;
90 for (
const auto& item : problem.
item()) {
91 max_num_bins += item.num_copies() + item.num_optional_copies();
94 const int num_types = problem.
item_size();
95 std::vector<std::vector<MPVariable*>> incoming_vars(graph.
nodes.size());
96 std::vector<std::vector<MPVariable*>> outgoing_vars(graph.
nodes.size());
97 std::vector<MPVariable*> arc_to_var(graph.
arcs.size());
98 std::vector<std::vector<MPVariable*>> item_to_vars(num_types);
100 MPSolver solver(
"VectorBinPacking", solver_type);
104 for (
int v = 0; v < graph.
arcs.size(); ++v) {
107 solver.
MakeIntVar(0, max_num_bins, absl::StrCat(
"a", v));
109 outgoing_vars[arc.
source].push_back(var);
117 for (
int i = 0; i < num_types; ++i) {
124 for (
MPVariable*
const var : item_to_vars[i]) {
131 for (
int n = 1; n < graph.
nodes.size() - 1; ++n) {
133 for (
MPVariable*
const var : incoming_vars[n]) {
136 for (
MPVariable*
const var : outgoing_vars[n]) {
142 solver.
MakeIntVar(0, max_num_bins,
"num_bins_var");
148 for (
MPVariable*
const var : outgoing_vars[ 0]) {
155 const int sink_node = graph.
nodes.size() - 1;
156 for (
MPVariable*
const var : incoming_vars[sink_node]) {
162 if (!absl::GetFlag(FLAGS_arc_flow_dump_model).empty()) {
176 solution.set_arc_flow_time_in_seconds(arc_flow_time);
191 struct NextCountItem {
196 std::vector<std::vector<NextCountItem>> node_to_next_count_item(
198 for (
int v = 0; v < graph.
arcs.size(); ++v) {
200 static_cast<int>(std::round(arc_to_var[v]->solution_value()));
201 if (count == 0)
continue;
203 node_to_next_count_item[arc.
source].push_back(
212 const auto pop_next_item = [&node_to_next_count_item](
int node) {
213 CHECK(!node_to_next_count_item[node].empty());
214 auto& [next, count, item] = node_to_next_count_item[node].back();
218 const NextItem result{next, item};
220 node_to_next_count_item[node].pop_back();
227 const int start_node = 0;
228 const int end_node = graph.
nodes.size() - 1;
229 while (!node_to_next_count_item[start_node].empty()) {
230 absl::btree_map<int, int> item_count;
231 int current = start_node;
232 while (current != end_node) {
233 const auto [next, item] = pop_next_item(current);
240 for (
const auto& [item, count] : item_count) {
246 for (
const auto& next_counts : node_to_next_count_item) {
247 CHECK(next_counts.empty());
ABSL_FLAG(std::string, arc_flow_dump_model, "", "File to store the solver specific optimization proto.")
void Start()
When Start() is called multiple times, only the most recent is used.
void SetCoefficient(const MPVariable *var, double coeff)
A class to express a linear objective.
void SetCoefficient(const MPVariable *var, double coeff)
void SetOffset(double value)
Sets the constant term in the objective.
double offset() const
Gets the constant term in the objective.
MPVariable * MakeIntVar(double lb, double ub, const std::string &name)
Creates an integer variable.
@ FEASIBLE
feasible, or stopped by limit.
@ INFEASIBLE
proven infeasible.
ResultStatus Solve()
Solves the problem using the default parameter values.
void SetTimeLimit(absl::Duration time_limit)
bool SetSolverSpecificParametersAsString(const std::string ¶meters)
absl::Status SetNumThreads(int num_threads)
-— Solver-specific parameters -—
int64_t wall_time() const
void ExportModelToProto(MPModelProto *output_model) const
Exports model to protocol buffer.
MPObjective * MutableObjective()
Returns the mutable objective object.
void EnableOutput()
Enables solver logging.
MPConstraint * MakeRowConstraint(double lb, double ub)
The class for variables of a Mathematical Programming (MP) model.
double solution_value() const
--— MPVariable --—
::int32_t num_optional_copies() const
double penalty_per_missing_copy() const
::int32_t num_copies() const
void add_item_indices(::int32_t value)
void add_item_copies(::int32_t value)
int item_size() const
repeated .operations_research.packing.vbp.Item item = 4;
const ::operations_research::packing::vbp::Item & item(int index) const
bool has_cost_per_bin() const
optional double cost_per_bin = 6;
double cost_per_bin() const
absl::Status SetTextProto(absl::string_view file_name, const google::protobuf::Message &proto, Options options)
vbp::VectorBinPackingSolution SolveVectorBinPackingWithArcFlow(const vbp::VectorBinPackingProblem &problem, MPSolver::OptimizationProblemType solver_type, const std::string &mip_params, double time_limit, int num_threads, int max_bins)
ArcFlowGraph BuildArcFlowGraph(const std::vector< int > &bin_dimensions, absl::Span< const std::vector< int > > item_dimensions_by_type, absl::Span< const int > demand_by_type)
Main method.
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
static int input(yyscan_t yyscanner)
std::vector< std::vector< int > > nodes