|
// 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
|
||
|
|
//
|
||
|
|
// This file contains a solver for the Two-Dimensional Constrained
|
||
|
|
// Guillotine Cutting Problem. The problem requires cutting a plane
|
||
|
|
// rectangle into smaller rectangular pieces of given sizes and values
|
||
|
|
// in order to maximize the sum of the values of the cut pieces in which
|
||
|
|
// there is a constraint on the maximum number of each type of piece that
|
||
|
|
// is to be produced and all cuts go from one edge of the rectangle to be
|
||
|
|
// cut to the opposite edge.
|
||
|
|
//
|
||
|
|
// If cgc_time_limit_in_ms is defined, it provides the best value
|
||
|
|
// achieved in that amount of time.
|
||
|
|
//
|
||
|
|
// Example usage:
|
||
|
|
//
|
||
|
|
// std::unique_ptr<operations_research::ConstrainedGuillotineCuttingData>
|
||
|
|
// data(new operations_research::ConstrainedGuillotineCuttingData());
|
||
|
|
// data->LoadFromFile(file_path);
|
||
|
|
// operations_research::ConstrainedGuillotineCutting cgc(std::move(data));
|
||
|
|
// cgc.Solve(absl::Milliseconds(absl::GetFlag(FLAGS_time_limit_in_ms)));
|
||
|
|
// if (cgc.Solved()) {
|
||
|
|
// cgc.PrintSolution();
|
||
|
|
// }
|
||
|
|
|
||
|
|
#ifndef ORTOOLS_EXAMPLES_CGC_H_
|
||
|
|
#define ORTOOLS_EXAMPLES_CGC_H_
|
||
|
|
|
||
|
|
#include <algorithm>
|
||
|
|
#include <memory>
|
||
|
|
#include <string>
|
||
|
|
#include <utility>
|
||
|
|
#include <vector>
|
||
|
|
|
||
|
|
#include "examples/cpp/cgc_data.h"
|
||
|
|
#include "ortools/constraint_solver/constraint_solver.h"
|
||
|
|
|
||
|
|
namespace operations_research {
|
||
|
|
|
||
|
|
class ConstrainedGuillotineCutting {
|
||
|
|
public:
|
||
|
|
struct CutRectangle {
|
||
|
|
CutRectangle(int parent_index, int length, int width)
|
||
|
|
: parent_index(parent_index), length(length), width(width) {}
|
||
|
|
|
||
|
|
int parent_index;
|
||
|
|
int length;
|
||
|
|
int width;
|
||
|
|
};
|
||
|
|
|
||
|
|
explicit ConstrainedGuillotineCutting(
|
||
|
|
std::unique_ptr<ConstrainedGuillotineCuttingData> data)
|
||
|
|
: data_(std::move(data)),
|
||
|
|
solver_("ConstrainedGuillotineCutting"),
|
||
|
|
solved_(false),
|
||
|
|
maximum_value_(0) {}
|
||
|
|
|
||
|
|
int MaximumValue() const {
|
||
|
|
DCHECK(solved_);
|
||
|
|
return maximum_value_;
|
||
|
|
}
|
||
|
|
bool Solved() const { return solved_; }
|
||
|
|
|
||
|
|
void PrintSolution() const;
|
||
|
|
void Solve(absl::Duration time_limit);
|
||
|
|
|
||
|
|
private:
|
||
|
|
// Contains the problem parameters.
|
||
|
|
std::unique_ptr<ConstrainedGuillotineCuttingData> data_;
|
||
|
|
Solver solver_;
|
||
|
|
|
||
|
|
bool solved_;
|
||
|
|
int maximum_value_;
|
||
|
|
std::vector<CutRectangle> solution_;
|
||
|
|
};
|
||
|
|
|
||
|
|
} // namespace operations_research
|
||
|
|
|
||
|
|
#endif // ORTOOLS_EXAMPLES_CGC_H_
|