23#include "absl/base/attributes.h"
24#include "absl/log/check.h"
25#include "absl/strings/str_cat.h"
26#include "absl/strings/string_view.h"
27#include "absl/types/span.h"
51const double kMinCutViolation = 1e-4;
93 IntegerValue
GetMinOverlap(IntegerValue start, IntegerValue end)
const {
127 "DiffnEnergyEvent(x_start_min = ",
x_start_min.value(),
131 ", y_max = ",
y_max.value(),
", y_size = ",
y_size.DebugString(),
141 absl::Span<
const std::vector<LiteralValueValue>> energies,
142 absl::Span<const int> rectangles, absl::string_view cut_name,
Model* model,
146 std::vector<DiffnEnergyEvent> events;
147 const auto& lp_values = manager->
LpValues();
148 for (
const int rect : rectangles) {
149 if (y_helper->
SizeMax(rect) == 0 || x_helper->
SizeMax(rect) == 0) {
173 if (events.empty())
return;
176 double average_d = 0.0;
177 for (
const auto& e : events) {
178 average_d +=
ToDouble(e.y_min + e.y_max);
180 const double average = average_d / 2.0 /
static_cast<double>(events.size());
181 for (
auto& e : events) {
182 e.y_spread = std::abs(
ToDouble(e.y_max) - average) +
183 std::abs(average -
ToDouble(e.y_min));
188 std::sort(events.begin(), events.end(),
190 return std::tie(a.x_start_min, a.y_spread, a.x_end_max) <
191 std::tie(b.x_start_min, b.y_spread, b.x_end_max);
195 double sum_of_all_energies = 0.0;
196 for (
const auto& e : events) {
197 sum_of_all_energies += e.linearized_energy_lp_value;
201 for (
int i1 = 0; i1 + 1 < events.size(); ++i1) {
204 int max_violation_end_index = -1;
205 double max_relative_violation = 1.0 + kMinCutViolation;
206 IntegerValue max_violation_window_start(0);
207 IntegerValue max_violation_window_end(0);
208 IntegerValue max_violation_y_min(0);
209 IntegerValue max_violation_y_max(0);
210 IntegerValue max_violation_area(0);
211 bool max_violation_use_precise_area =
false;
214 double energy_lp = 0.0;
219 capacity_profile.
Clear();
223 std::vector<DiffnEnergyEvent> residual_events(events.begin() + i1,
225 std::sort(residual_events.begin(), residual_events.end(),
227 return std::tie(a.x_end_max, a.y_spread) <
228 std::tie(b.x_end_max, b.y_spread);
232 for (
int i2 = 0; i2 < residual_events.size(); ++i2) {
236 window_max = std::max(window_max, e.
x_end_max);
237 y_min = std::min(y_min, e.
y_min);
238 y_max = std::max(y_max, e.
y_max);
245 if (i2 + 1 < residual_events.size() &&
246 residual_events[i2 + 1].x_start_min >= window_min &&
247 residual_events[i2 + 1].x_end_max <= window_max &&
248 residual_events[i2 + 1].y_min >= y_min &&
249 residual_events[i2 + 1].y_max <= y_max) {
257 bool use_precise_area =
false;
258 IntegerValue precise_area(0);
259 double area_lp = 0.0;
260 const IntegerValue bbox_area =
261 (window_max - window_min) * (y_max - y_min);
263 use_precise_area = precise_area < bbox_area;
264 area_lp =
ToDouble(std::min(precise_area, bbox_area));
266 if (area_lp >= sum_of_all_energies) {
271 const double relative_violation = energy_lp / area_lp;
272 if (relative_violation > max_relative_violation) {
273 max_violation_end_index = i2;
274 max_relative_violation = relative_violation;
275 max_violation_window_start = window_min;
276 max_violation_window_end = window_max;
277 max_violation_y_min = y_min;
278 max_violation_y_max = y_max;
279 max_violation_area = std::min(precise_area, bbox_area);
280 max_violation_use_precise_area = use_precise_area;
284 if (max_violation_end_index == -1)
continue;
288 bool add_opt_to_name =
false;
289 bool add_quadratic_to_name =
false;
290 bool add_energy_to_name =
false;
292 for (
int i2 = 0; i2 <= max_violation_end_index; ++i2) {
295 if (!event.IsPresent()) add_opt_to_name =
true;
296 if (event.energy_is_quadratic) add_quadratic_to_name =
true;
297 if (event.energy_min > event.x_size_min * event.y_size_min) {
298 add_energy_to_name =
true;
301 std::string full_name(cut_name);
302 if (add_opt_to_name) full_name.append(
"_optional");
303 if (add_quadratic_to_name) full_name.append(
"_quadratic");
304 if (add_energy_to_name) full_name.append(
"_energy");
305 if (max_violation_use_precise_area) full_name.append(
"_precise");
306 top_n_cuts.
AddCut(cut.
Build(), full_name, lp_values);
326 const int num_rectangles = helper->
NumBoxes();
327 std::vector<std::vector<LiteralValueValue>> energies(num_rectangles);
329 for (
int i = 0;
i < num_rectangles; ++
i) {
339 std::vector<int> rectangles;
340 rectangles.reserve(num_rectangles);
341 for (
const auto& component :
343 for (
const int rect : component) {
345 if (helper->
IsAbsent(rect))
continue;
355 rectangles.push_back(rect);
358 if (rectangles.size() <= 1)
continue;
361 model, manager, &helper->
x_helper(),
362 &helper->
y_helper(), y_demands_helper);
364 model, manager, &helper->
y_helper(),
365 &helper->
x_helper(), x_demands_helper);
376 return absl::StrCat(
"DiffnCtEvent(x_end = ",
x_end.DebugString(),
381 ", y_max = ",
y_max.value(),
426void GenerateNoOvelap2dCompletionTimeCuts(absl::string_view cut_name,
427 std::vector<DiffnCtEvent> events,
428 bool use_lifting,
Model* model,
433 std::sort(events.begin(), events.end(),
435 return std::tie(e1.x_start_min, e1.y_size_min, e1.x_lp_end) <
436 std::tie(e2.x_start_min, e2.y_size_min, e2.x_lp_end);
438 for (
int start = 0; start + 1 < events.size(); ++start) {
441 events[start].x_start_min == events[start - 1].x_start_min) {
445 const IntegerValue sequence_start_min = events[start].x_start_min;
446 std::vector<DiffnCtEvent> residual_tasks(events.begin() + start,
455 for (
int before = 0; before < start; ++before) {
456 if (events[before].x_start_min + events[before].x_size_min >
457 sequence_start_min) {
459 DiffnCtEvent
event = events[before];
462 event.x_start_min, event.x_start_max, event.x_end_min,
463 event.x_end_max, event.x_size_min, event.y_size_min,
464 event.decomposed_energy, sequence_start_min, event.x_end_max);
466 event.x_size_min +
event.x_start_min - sequence_start_min;
467 event.x_start_min = sequence_start_min;
468 if (event.energy_min > event.x_size_min * event.y_size_min) {
469 event.use_energy =
true;
471 DCHECK_GE(event.energy_min, event.x_size_min * event.y_size_min);
472 if (event.energy_min <= 0)
continue;
473 residual_tasks.push_back(event);
478 std::sort(residual_tasks.begin(), residual_tasks.end(),
480 return e1.x_lp_end < e2.x_lp_end;
485 double best_efficacy = 0.01;
486 IntegerValue best_min_rhs = 0;
487 bool best_use_subset_sum =
false;
490 IntegerValue sum_event_areas = 0;
492 IntegerValue sum_energy = 0;
494 IntegerValue sum_square_energy = 0;
496 double lp_contrib = 0.0;
500 IntegerValue sum_of_y_size_min = 0;
505 for (
int i = 0;
i < residual_tasks.size(); ++
i) {
507 DCHECK_GE(event.x_start_min, sequence_start_min);
509 if (!
AddTo(event.energy_min, &sum_energy))
break;
510 if (!
AddProductTo(event.energy_min, event.x_size_min, &sum_event_areas)) {
513 if (!
AddSquareTo(event.energy_min, &sum_square_energy))
break;
514 if (!
AddTo(event.y_size_min, &sum_of_y_size_min))
break;
516 lp_contrib +=
event.x_lp_end *
ToDouble(event.energy_min);
517 current_start_min = std::min(current_start_min, event.x_start_min);
521 y_min_of_subset = std::min(y_min_of_subset, event.y_min);
522 y_max_of_subset = std::max(y_max_of_subset, event.y_max);
523 if (!event.y_size_is_fixed) use_dp =
false;
526 dp.Reset((y_max_of_subset - y_min_of_subset).value());
529 if (y_max_of_subset - y_min_of_subset > dp.Bound()) {
535 dp.Add(event.y_size_min.value());
538 const IntegerValue reachable_capacity =
539 use_dp ? IntegerValue(dp.CurrentMax())
540 : y_max_of_subset - y_min_of_subset;
543 if (sum_of_y_size_min <= reachable_capacity)
continue;
546 const IntegerValue square_sum_energy =
CapProdI(sum_energy, sum_energy);
548 const IntegerValue rhs_second_term =
549 CeilRatio(square_sum_energy, reachable_capacity);
551 IntegerValue min_rhs =
CapAddI(sum_event_areas, rhs_second_term);
556 if (!
AddProductTo(sum_energy, current_start_min, &min_rhs))
break;
560 const double efficacy = (
ToDouble(min_rhs) - lp_contrib) /
561 std::sqrt(
ToDouble(sum_square_energy));
569 if (efficacy > best_efficacy) {
570 best_efficacy = efficacy;
572 best_min_rhs = min_rhs;
573 best_use_subset_sum =
574 reachable_capacity < y_max_of_subset - y_min_of_subset;
577 if (best_end != -1) {
579 bool is_lifted =
false;
580 bool add_energy_to_name =
false;
581 for (
int i = 0;
i <= best_end; ++
i) {
583 is_lifted |=
event.
lifted;
584 add_energy_to_name |=
event.use_energy;
585 cut.AddTerm(event.x_end, event.energy_min);
587 std::string full_name(cut_name);
588 if (is_lifted) full_name.append(
"_lifted");
589 if (add_energy_to_name) full_name.append(
"_energy");
590 if (best_use_subset_sum) full_name.append(
"_subsetsum");
591 top_n_cuts.AddCut(cut.Build(), full_name, manager->
LpValues());
594 top_n_cuts.TransferToManager(manager);
602 &helper->x_helper(), model, &result.vars,
605 &helper->y_helper(), model, &result.vars,
610 result.generate_cuts = [helper, product_decomposer,
612 if (!helper->SynchronizeAndSetDirection()) {
616 const int num_rectangles = helper->NumBoxes();
617 std::vector<int> rectangles;
618 rectangles.reserve(num_rectangles);
621 for (
const auto& component :
622 helper->connected_components().AsVectorOfSpan()) {
624 if (component.size() <= 1)
continue;
625 for (
int rect : component) {
626 if (!helper->IsPresent(rect))
continue;
627 if (x_helper->SizeMin(rect) == 0 || y_helper->SizeMin(rect) == 0) {
630 rectangles.push_back(rect);
633 auto generate_cuts = [product_decomposer, manager, model, helper,
634 &rectangles](absl::string_view cut_name) {
635 std::vector<DiffnCtEvent> events;
639 const auto& lp_values = manager->LpValues();
640 for (
const int rect : rectangles) {
642 event.x_end = x_helper->Ends()[rect];
643 event.x_lp_end =
event.x_end.LpValue(lp_values);
644 event.y_min = y_helper->StartMin(rect);
645 event.y_max = y_helper->EndMax(rect);
646 event.y_size_min = y_helper->SizeMin(rect);
649 event.energy_min =
event.x_size_min *
event.y_size_min;
650 event.decomposed_energy = product_decomposer->TryToDecompose(
651 x_helper->Sizes()[rect], y_helper->Sizes()[rect]);
652 events.push_back(event);
655 GenerateNoOvelap2dCompletionTimeCuts(cut_name, std::move(events),
660 if (!helper->SynchronizeAndSetDirection(
true,
true,
false)) {
663 generate_cuts(
"NoOverlap2dXCompletionTime");
664 if (!helper->SynchronizeAndSetDirection(
true,
true,
true)) {
667 generate_cuts(
"NoOverlap2dYCompletionTime");
668 if (!helper->SynchronizeAndSetDirection(
false,
false,
false)) {
671 generate_cuts(
"NoOverlap2dXCompletionTime_mirror");
672 if (!helper->SynchronizeAndSetDirection(
false,
false,
true)) {
675 generate_cuts(
"NoOverlap2dYCompletionTime_mirror");
void AddRectangle(IntegerValue x_min, IntegerValue x_max, IntegerValue y_min, IntegerValue y_max)
Adds a rectangle to the current shape.
IntegerValue GetBoundingArea()
std::vector< absl::Span< const V > > AsVectorOfSpan() const
void AddQuadraticLowerBound(AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
LinearExpression BuildExpression()
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff=IntegerValue(1))
void AddLinearExpression(const LinearExpression &expr)
ABSL_MUST_USE_RESULT bool AddDecomposedProduct(absl::Span< const LiteralValueValue > product)
const util_intops::StrongVector< IntegerVariable, double > & LpValues()
To simplify CutGenerator api.
LiteralIndex Index() const
SchedulingConstraintHelper & y_helper() const
const CompactVectorVector< int > & connected_components() const
SchedulingDemandHelper & y_demands_helper()
bool SynchronizeAndSetDirection(bool x_is_forward_after_swap=true, bool y_is_forward_after_swap=true, bool swap_x_and_y=false)
bool IsAbsent(int index) const
SchedulingDemandHelper & x_demands_helper()
SchedulingConstraintHelper & x_helper() const
Helper class to express a product as a linear constraint.
std::vector< LiteralValueValue > TryToDecompose(const AffineExpression &left, const AffineExpression &right)
absl::Span< const AffineExpression > Sizes() const
bool IsPresent(int t) const
Literal PresenceLiteral(int index) const
IntegerValue SizeMax(int t) const
IntegerValue StartMin(int t) const
IntegerValue SizeMin(int t) const
IntegerValue EndMax(int t) const
bool CacheAllEnergyValues()
bool EnergyIsQuadratic(int t) const
IntegerValue EnergyMin(int t) const
void TransferToManager(LinearConstraintManager *manager)
Empty the local pool and add all its content to the manager.
void AddCut(LinearConstraint ct, absl::string_view name, const util_intops::StrongVector< IntegerVariable, double > &lp_solution)
Adds a cut to the local pool.
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
bool AddSquareTo(IntegerValue a, IntegerValue *result)
Computes result += a * a, and return false iff there is an overflow.
bool AddProductTo(IntegerValue a, IntegerValue b, IntegerValue *result)
Computes result += a * b, and return false iff there is an overflow.
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
bool AddTo(IntegerValue a, IntegerValue *result)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
CutGenerator CreateNoOverlap2dEnergyCutGenerator(NoOverlap2DConstraintHelper *helper, Model *model)
const LiteralIndex kNoLiteralIndex(-1)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
void GenerateNoOverlap2dEnergyCut(absl::Span< const std::vector< LiteralValueValue > > energies, absl::Span< const int > rectangles, absl::string_view cut_name, Model *model, LinearConstraintManager *manager, SchedulingConstraintHelper *x_helper, SchedulingConstraintHelper *y_helper, SchedulingDemandHelper *y_demands_helper)
void AddIntegerVariableFromIntervals(const SchedulingConstraintHelper *helper, Model *model, std::vector< IntegerVariable > *vars, int mask)
IntegerValue CapAddI(IntegerValue a, IntegerValue b)
CutGenerator CreateNoOverlap2dCompletionTimeCutGenerator(NoOverlap2DConstraintHelper *helper, Model *model)
bool AtMinOrMaxInt64I(IntegerValue t)
IntegerValue CapProdI(IntegerValue a, IntegerValue b)
Overflows and saturated arithmetic.
double ToDouble(IntegerValue value)
IntegerValue ComputeEnergyMinInWindow(IntegerValue start_min, IntegerValue start_max, IntegerValue end_min, IntegerValue end_max, IntegerValue size_min, IntegerValue demand_min, absl::Span< const LiteralValueValue > filtered_energy, IntegerValue window_start, IntegerValue window_end)
In SWIG mode, we don't want anything besides these top-level includes.
absl::AnyInvocable< bool(LinearConstraintManager *manager)> generate_cuts
std::vector< IntegerVariable > vars
bool only_run_at_level_zero
std::vector< LiteralValueValue > decomposed_energy
IntegerValue x_start_min
Cache of the intervals bound on the x direction.
DiffnBaseEvent(int t, const SchedulingConstraintHelper *x_helper)
IntegerValue y_min
Useful for no_overlap_2d or cumulative.
IntegerValue energy_min
The energy min of this event.
std::string DebugString() const
DiffnCtEvent(int t, const SchedulingConstraintHelper *x_helper)
AffineExpression x_end
The lp value of the end of the x interval.
std::string DebugString() const
AffineExpression y_size
We need this for linearizing the energy in some cases.
DiffnEnergyEvent(int t, const SchedulingConstraintHelper *x_helper)
bool energy_is_quadratic
True if linearized_energy is not exact and a McCormick relaxation.
LiteralIndex presence_literal_index
If set, this event is optional and its presence is controlled by this.
LinearExpression linearized_energy
double y_spread
Used to minimize the increase on the y axis for rectangles.
IntegerValue GetMinOverlap(IntegerValue start, IntegerValue end) const
ABSL_MUST_USE_RESULT bool FillEnergyLp(AffineExpression x_size, const util_intops::StrongVector< IntegerVariable, double > &lp_values, Model *model)
double linearized_energy_lp_value