Morph MORPH
SIGN IN SIGN UP
google / or-tools UNCLAIMED

Google's Operations Research tools:

0 0 643 C++
Normal View History Raw
Use new bintest framework (#4928)
2025-12-01 10:22:54 +01:00
// Copyright 2010-2025 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Two-Dimensional Constrained Guillotine Cutting
#include "examples/cpp/cgc.h"
#include <algorithm>
#include <cstdint>
#include <string>
#include <vector>
#include "absl/container/btree_set.h"
examples: rework logging usage
2026-02-20 16:40:19 +01:00
#include "absl/log/check.h"
Use new bintest framework (#4928)
2025-12-01 10:22:54 +01:00
#include "absl/strings/str_format.h"
#include "absl/strings/str_split.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "examples/cpp/cgc_data.h"
#include "ortools/base/helpers.h"
#include "ortools/base/options.h"
#include "ortools/constraint_solver/constraint_solver.h"
#include "re2/re2.h"
namespace operations_research {
bool ConstrainedGuillotineCuttingData::LoadFromFile(
const std::string& input_file) {
std::string buffer;
if (!file::GetContents(input_file, &buffer, file::Defaults()).ok()) {
LOG(ERROR) << "Could not read from file " << input_file;
return false;
}
const std::vector<std::string> lines =
absl::StrSplit(buffer, '\n', absl::SkipEmpty());
if (lines.empty()) {
LOG(ERROR) << "Empty file: " << input_file;
return false;
}
int num_pieces;
if (!RE2::FullMatch(lines[0], "\\s*(\\d+)\\s*", &num_pieces)) {
LOG(ERROR) << "Could not parse number of pieces";
return false;
}
if (0 >= num_pieces) {
LOG(ERROR) << "There are no pieces in the problem specification";
return false;
}
if (lines.size() != num_pieces + 2) {
LOG(ERROR) << "File: " << input_file << " does not respect the format";
return false;
}
if (!RE2::FullMatch(lines[1], "\\s*(\\d+)\\s+(\\d+)\\s*", &root_length_,
&root_width_)) {
LOG(ERROR) << "Could not parse the size of the main rectangle";
return false;
}
pieces_.resize(num_pieces);
for (int i = 0; i < num_pieces; ++i) {
if (!RE2::FullMatch(lines[i + 2],
"\\s*(\\d+)\\s+(\\d+)\\s+(\\d+)\\s+(\\d+)\\s*",
&pieces_[i].length, &pieces_[i].width,
&pieces_[i].max_appearances, &pieces_[i].value)) {
LOG(ERROR) << "Could not parse piece on line " << lines[i + 2]
<< ", line number " << i + 3;
return false;
}
}
return true;
}
namespace {
// Depending on the part that was cut, returns an IntVar representing
// if the cut that was made on the (index / 2 + 1) rectangle is
// a guillotine cut.
IntVar* IsAGuillotineCut(int index,
const std::vector<IntVar*>& size_currently_cut,
const std::vector<IntVar*>& size_not_cut,
const std::vector<IntVar*>& parent_index,
const std::vector<int>& pieces_size, Solver* solver) {
CHECK(solver != nullptr);
// The size of the cut must be >= 1 in order for the cut to be a valid one.
IntVar* const condition_var =
solver->MakeIsGreaterOrEqualCstVar(size_currently_cut[index], 1);
// The part that is not cut should remain the same.
IntVar* const same_uncut_size_as_sibling =
solver->MakeIsEqualVar(size_not_cut[index], size_not_cut[index + 1]);
// The part that is not cut should remain the same with the parent.
IntVar* const same_uncut_size_as_parent = solver->MakeIsEqualVar(
size_not_cut[index],
solver->MakeElement(size_not_cut, parent_index[index / 2 + 1]));
// We make a cut if the size of the cut matches at least one of the pieces.
IntVar* const cut_equals_piece_size = solver->MakeIsEqualCstVar(
solver->MakeElement(pieces_size, size_currently_cut[index]), 1);
// The sum of the sizes that were cut should equal the parent size.
IntVar* const sum_of_sizes = solver->MakeIsEqualVar(
solver->MakeSum(size_currently_cut[index], size_currently_cut[index + 1]),
solver->MakeElement(size_currently_cut, parent_index[index / 2 + 1]));
const std::vector<IntVar*> cut_implications = {
same_uncut_size_as_sibling, same_uncut_size_as_parent,
cut_equals_piece_size, sum_of_sizes};
return solver
->MakeConditionalExpression(
condition_var,
solver->MakeIsEqualCstVar(solver->MakeSum(cut_implications),
cut_implications.size()),
0)
->Var();
}
// Sets initial variables:
// stores piece sizes related variables and sets maximum value
// and maximum number of elements in a cutting path.
void SetInitialElements(const ConstrainedGuillotineCuttingData& data,
std::vector<int>* sizes_to_pieces,
std::vector<int>* piece_length,
std::vector<int>* piece_width, int* maximum_value,
int* maximum_elements) {
CHECK(sizes_to_pieces != nullptr);
CHECK(piece_length != nullptr);
CHECK(piece_width != nullptr);
CHECK(maximum_value != nullptr);
CHECK(maximum_elements != nullptr);
sizes_to_pieces->resize((data.root_length() + 1) * (data.root_width() + 1),
data.pieces().size());
piece_length->resize(data.root_length() + 1, 0);
piece_width->resize(data.root_width() + 1, 0);
const int main_rectangle_area = data.root_length() * data.root_width();
// Number of elements in the path should dependent on the number
// of end pieces. Considering that at every point we could in 2 cuts
// get to an end piece, which means maximum 4 new pieces,
// a limit of 4 * number_of_end_pieces should fit the path.
static const int kMultiplyNumOfEndPiecesBy = 4;
*maximum_value = 0;
*maximum_elements = 1;
int index = 0;
for (const ConstrainedGuillotineCuttingData::Piece& piece : data.pieces()) {
if (piece.length <= data.root_length() &&
piece.width <= data.root_width()) {
(*sizes_to_pieces)[piece.length * data.root_width() + piece.width] =
index;
(*piece_length)[piece.length] = 1;
(*piece_width)[piece.width] = 1;
}
const int number_of_appearances =
std::min(piece.max_appearances,
main_rectangle_area / (piece.length * piece.width));
*maximum_value += piece.value * number_of_appearances;
*maximum_elements += kMultiplyNumOfEndPiecesBy * number_of_appearances;
index++;
}
// TODO(user): a better upper bound for value and for
// maximum_elements.
}
void SetRectanglesVariablesAndAddConstraints(
const std::vector<int>& piece_length, const std::vector<int>& piece_width,
const int maximum_elements, const int root_length, const int root_width,
std::vector<IntVar*>* parent_index, std::vector<IntVar*>* rectangle_length,
std::vector<IntVar*>* rectangle_width, Solver* solver) {
CHECK(parent_index != nullptr);
CHECK(rectangle_length != nullptr);
CHECK(rectangle_width != nullptr);
CHECK(solver != nullptr);
static const int kMainRectangleIndex = 0;
solver->MakeIntVarArray(maximum_elements / 2 + 2, -1, maximum_elements,
"parent_index_", parent_index);
solver->MakeIntVarArray(maximum_elements, 0, root_length, "length_",
rectangle_length);
solver->MakeIntVarArray(maximum_elements, 0, root_width, "width_",
rectangle_width);
(*parent_index)[kMainRectangleIndex]->SetValue(-1);
(*rectangle_length)[kMainRectangleIndex]->SetValue(root_length);
(*rectangle_width)[kMainRectangleIndex]->SetValue(root_width);
// Any rectangle can be cut just once.
solver->AddConstraint(solver->MakeAllDifferent(*parent_index));
std::vector<IntVar*> x_guillotine_cut;
std::vector<IntVar*> y_guillotine_cut;
// Every 2 consecutive cuts are from the same rectangle starting with
// position 1, since at index 0 we keep information regarding the
// main rectangle.
for (int i = 1; i < maximum_elements; i += 2) {
// The rectangle from which we cut needs to be < i. In case we do not cut
// anything (the elements are all 0) the parent_index will be i.
solver->AddConstraint(
solver->MakeLessOrEqual((*parent_index)[i / 2 + 1], i));
// If one of the sizes is 0, then all are 0 and the parent does not point
// to a real parent, but to itself, since we cannot have a valid cut
// that leaves one size 0.
IntVar* length_is_zero =
solver->MakeIsEqualCstVar((*rectangle_length)[i], 0);
solver->AddConstraint(solver->MakeEquality(
length_is_zero,
solver->MakeIsEqualCstVar((*rectangle_length)[i + 1], 0)));
solver->AddConstraint(solver->MakeEquality(
length_is_zero, solver->MakeIsEqualCstVar((*rectangle_width)[i], 0)));
solver->AddConstraint(solver->MakeEquality(
length_is_zero,
solver->MakeIsEqualCstVar((*rectangle_width)[i + 1], 0)));
solver->AddConstraint(solver->MakeEquality(
length_is_zero,
solver->MakeIsEqualCstVar((*parent_index)[i / 2 + 1], i)));
// Group 0-cuts together at the beginning. So after a normal cut there
// will not be any 0-cuts.
if (i > 1) {
solver->AddConstraint(solver->MakeLessOrEqual(
solver->MakeIsGreaterOrEqualCstVar((*rectangle_length)[i - 1], 1),
solver->MakeIsGreaterOrEqualCstVar((*rectangle_length)[i], 1)));
}
// If it is an x-guillotine cut.
x_guillotine_cut.push_back(IsAGuillotineCut(i, *rectangle_length,
*rectangle_width, *parent_index,
piece_length, solver));
// If it is an y-guillotine cut.
y_guillotine_cut.push_back(
IsAGuillotineCut(i, *rectangle_width, *rectangle_length, *parent_index,
piece_width, solver));
// Every pair of rectangles should correspond to a guillotine cut
// on one of the axis or they could be 0 if there was no cut made.
solver->AddConstraint(solver->MakeEquality(
solver->MakeSum(
length_is_zero,
solver->MakeSum(
solver->MakeIsEqualCstVar(x_guillotine_cut[i / 2], 1),
solver->MakeIsEqualCstVar(y_guillotine_cut[i / 2], 1))),
1));
}
}
void AddAdditionalConstraints(const std::vector<IntVar*>& parent_index,
const std::vector<IntVar*>& rectangle_length,
const std::vector<IntVar*>& rectangle_width,
const std::vector<int>& sizes_to_pieces,
const ConstrainedGuillotineCuttingData& data,
int maximum_elements,
std::vector<IntVar*>* is_end_piece,
std::vector<IntVar*>* was_cut, IntVar* value,
Solver* solver) {
CHECK(is_end_piece != nullptr);
CHECK(was_cut != nullptr);
CHECK(value != nullptr);
CHECK(solver != nullptr);
solver->MakeIntVarArray(maximum_elements, 0, 1, "", was_cut);
for (int i = 0; i < maximum_elements; ++i) {
solver->AddConstraint(solver->MakeCount(parent_index, i, (*was_cut)[i]));
is_end_piece->push_back(
solver
->MakeConditionalExpression(
solver->MakeIsEqualCstVar((*was_cut)[i], 0),
solver->MakeElement(
sizes_to_pieces,
solver
->MakeSum(solver->MakeProd(rectangle_length[i],
data.root_width()),
rectangle_width[i])
->Var()),
data.pieces().size())
->Var());
}
int index = 0;
std::vector<IntVar*> values;
for (const ConstrainedGuillotineCuttingData::Piece& piece : data.pieces()) {
// Number of appearances of every type should be less or equal
// to the maximum number of times a piece can appear.
IntVar* const appearances =
solver->MakeIntVar(0, (data.root_length() * data.root_width()) /
(piece.length * piece.width));
// The number of appearances of every piece should be equal
// to the number of times that piece appears in a path as an end piece.
solver->AddConstraint(solver->MakeCount(*is_end_piece, index, appearances));
// Values will contain for every piece:
// number_of_time_the_piece_appears * its value.
values.push_back(
solver
->MakeProd(solver->MakeMin(appearances, piece.max_appearances),
piece.value)
->Var());
index++;
}
solver->AddConstraint(solver->MakeEquality(value, solver->MakeSum(values)));
}
void CreateAdditionalMonitors(absl::Duration time_limit,
std::vector<SearchMonitor*>* monitors,
OptimizeVar* objective_value, Solver* solver) {
CHECK(monitors != nullptr);
CHECK(objective_value != nullptr);
CHECK(solver != nullptr);
monitors->push_back(objective_value);
static const int kLogFrequency = 100000;
SearchMonitor* const log =
solver->MakeSearchLog(kLogFrequency, objective_value);
monitors->push_back(log);
if (time_limit != absl::InfiniteDuration()) {
SearchLimit* const limit = solver->MakeTimeLimit(time_limit);
monitors->push_back(limit);
}
}
DecisionBuilder* CreateDecisionBuilder(
const std::vector<IntVar*>& parent_index,
const std::vector<IntVar*>& rectangle_length,
const std::vector<IntVar*>& rectangle_width,
const std::vector<IntVar*>& was_cut, Solver* solver) {
CHECK(solver != nullptr);
std::vector<IntVar*> decision_variables;
for (int i = 1; i < rectangle_length.size() / 2 + 1; ++i) {
decision_variables.push_back(parent_index[i]);
decision_variables.push_back(rectangle_length[2 * (i - 1) + 1]);
decision_variables.push_back(rectangle_width[2 * (i - 1) + 1]);
}
for (int i = 0; i < rectangle_length.size(); ++i) {
decision_variables.push_back(was_cut[i]);
}
return solver->MakePhase(decision_variables, Solver::CHOOSE_FIRST_UNBOUND,
Solver::ASSIGN_MAX_VALUE);
}
void FillSolution(
const std::vector<IntVar*>& parent_index,
const std::vector<IntVar*>& rectangle_length,
const std::vector<IntVar*>& rectangle_width,
const SolutionCollector* collector, IntVar* value, int* maximum_value,
std::vector<ConstrainedGuillotineCutting::CutRectangle>* solution) {
CHECK(collector != nullptr);
CHECK(value != nullptr);
CHECK(maximum_value != nullptr);
CHECK(solution != nullptr);
int number_of_zero_cuts = 0;
int parent = -1;
for (int i = 0; i < rectangle_length.size(); ++i) {
if (!collector->Value(0, rectangle_length[i])) {
number_of_zero_cuts++;
continue;
}
if (i % 2 == 1) {
parent = std::max(
collector->Value(0, parent_index[i / 2 + 1]) - number_of_zero_cuts,
int64_t{0});
}
solution->emplace_back(parent, collector->Value(0, rectangle_length[i]),
collector->Value(0, rectangle_width[i]));
}
*maximum_value = collector->Value(0, value);
}
void ValidateSolution(int num_pieces, int root_width,
const std::vector<IntVar*>& parent_index,
const std::vector<IntVar*>& rectangle_length,
const std::vector<IntVar*>& rectangle_width,
const std::vector<IntVar*>& is_end_piece,
absl::Span<const int> sizes_to_pieces,
const SolutionCollector* collector) {
CHECK(collector != nullptr);
absl::btree_set<int> parent_ids;
for (int i = 0; i < parent_index.size(); ++i) {
parent_ids.insert(collector->Value(0, parent_index[i]));
// The rectangle from which the rectangles were cut needs to be
// <= current position. For every pair of rectangles we keep
// their parent index once.
CHECK(collector->Value(0, parent_index[i]) <= i * 2 - 1);
}
// Every piece should be cut just once.
CHECK_EQ(parent_ids.size(), parent_index.size());
bool guillotine_cut = false;
for (int i = 1; i < rectangle_length.size(); i += 2) {
const int parent = collector->Value(0, parent_index[i / 2 + 1]);
const int length_left_rectangle = collector->Value(0, rectangle_length[i]);
const int length_rigth_rectangle =
collector->Value(0, rectangle_length[i + 1]);
const int length_parent = collector->Value(0, rectangle_length[parent]);
const int width_parent = collector->Value(0, rectangle_width[parent]);
const int width_left_rectangle = collector->Value(0, rectangle_width[i]);
const int width_right_rectangle =
collector->Value(0, rectangle_width[i + 1]);
const bool is_a_x_guillotine_cut =
length_left_rectangle + length_rigth_rectangle == length_parent &&
length_left_rectangle && length_rigth_rectangle &&
width_left_rectangle == width_right_rectangle &&
width_left_rectangle == width_parent;
const bool is_a_y_guillotine_cut =
width_left_rectangle + width_right_rectangle == width_parent &&
width_left_rectangle && width_right_rectangle &&
length_left_rectangle == length_rigth_rectangle &&
length_left_rectangle == length_parent;
const bool is_a_zero_cut = !length_left_rectangle &&
!length_rigth_rectangle &&
!width_left_rectangle && !width_right_rectangle;
// Every cut is a guillotine cut or all elements are 0.
CHECK(is_a_x_guillotine_cut || is_a_y_guillotine_cut || is_a_zero_cut);
// Check if it is a piece.
const int it_is_piece1 =
parent_ids.contains(i)
? num_pieces
: sizes_to_pieces[length_left_rectangle * root_width +
width_left_rectangle];
const int it_is_piece2 =
parent_ids.contains(i + 1)
? num_pieces
: sizes_to_pieces[length_rigth_rectangle * root_width +
width_right_rectangle];
CHECK_EQ(it_is_piece1, collector->Value(0, is_end_piece[i]));
CHECK_EQ(it_is_piece2, collector->Value(0, is_end_piece[i + 1]));
// Check that all 0-cuts (both rectangles are 0x0) are grouped together.
CHECK_LE(guillotine_cut, is_a_x_guillotine_cut || is_a_y_guillotine_cut);
guillotine_cut |= is_a_x_guillotine_cut || is_a_y_guillotine_cut;
}
}
} // namespace
void ConstrainedGuillotineCutting::PrintSolution() const {
CHECK(solved_);
absl::PrintF("Maximum value: %d\n", maximum_value_);
absl::PrintF("Main rectangle 0 sizes: %dx%d\n", data_->root_length(),
data_->root_width());
for (int i = 1; i < solution_.size(); ++i) {
if (i % 2 == 1) {
absl::PrintF("\nRectangle %d was cut in: \n", solution_[i].parent_index);
}
absl::PrintF("Rectangle %d sizes: %dx%d\n", i, solution_[i].length,
solution_[i].width);
}
}
void ConstrainedGuillotineCutting::Solve(absl::Duration time_limit) {
const std::vector<ConstrainedGuillotineCuttingData::Piece>& pieces =
data_->pieces();
// Depending on the size of a rectangle, it represents the index of
// the piece to which it corresponds. If it does not correspond to
// any piece, than it will remain pieces.size().
std::vector<int> sizes_to_pieces;
// Depending on the length(width) of a rectangle, it will be 1 if
// there exists a piece that has that length(width).
std::vector<int> piece_length;
std::vector<int> piece_width;
int maximum_value;
int maximum_elements;
SetInitialElements(*data_, &sizes_to_pieces, &piece_length, &piece_width,
&maximum_value, &maximum_elements);
// For every pair of rectangles the index of the rectangle
// that the rectangles were cut of.
std::vector<IntVar*> parent_index;
// sizes of the rectangles
std::vector<IntVar*> rectangle_length;
std::vector<IntVar*> rectangle_width;
SetRectanglesVariablesAndAddConstraints(
piece_length, piece_width, maximum_elements, data_->root_length(),
data_->root_width(), &parent_index, &rectangle_length, &rectangle_width,
&solver_);
// Contains the piece that this rectangle equals to if it is
// an end piece (it was not cut).
std::vector<IntVar*> is_end_piece;
// For every piece it is true if the corresponding rectangle
// was cut.
std::vector<IntVar*> was_cut;
IntVar* const value = solver_.MakeIntVar(0, maximum_value);
AddAdditionalConstraints(parent_index, rectangle_length, rectangle_width,
sizes_to_pieces, *data_, maximum_elements,
&is_end_piece, &was_cut, value, &solver_);
// Objective: maximize the value of the end pieces.
OptimizeVar* const objective_value = solver_.MakeMaximize(value, 1);
DecisionBuilder* const db = CreateDecisionBuilder(
parent_index, rectangle_length, rectangle_width, was_cut, &solver_);
std::vector<SearchMonitor*> monitors;
SolutionCollector* const collector = solver_.MakeLastSolutionCollector();
collector->Add(parent_index);
collector->Add(rectangle_length);
collector->Add(rectangle_width);
collector->Add(is_end_piece);
collector->Add(value);
monitors.push_back(collector);
CreateAdditionalMonitors(time_limit, &monitors, objective_value, &solver_);
const int64_t start_time = solver_.wall_time();
solver_.Solve(db, monitors);
const int64_t end_time = solver_.wall_time();
LOG(INFO) << "The process took: " << (end_time - start_time) / 1000.0
<< " seconds.";
if (collector->solution_count()) {
ValidateSolution(pieces.size(), data_->root_width(), parent_index,
rectangle_length, rectangle_width, is_end_piece,
sizes_to_pieces, collector);
solved_ = true;
FillSolution(parent_index, rectangle_length, rectangle_width, collector,
value, &maximum_value_, &solution_);
}
}
} // namespace operations_research
Reference in New Issue Copy Permalink