OR-Tools  8.2
constraint_solver.h
Go to the documentation of this file.
1// Copyright 2010-2018 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
67
68#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
70
71#include <functional>
72#include <iosfwd>
73#include <memory>
74#include <random>
75#include <string>
76#include <utility>
77#include <vector>
78
79#include "absl/base/macros.h"
80#include "absl/container/flat_hash_map.h"
81#include "absl/container/flat_hash_set.h"
82#include "absl/random/distributions.h"
83#include "absl/random/random.h"
84#include "absl/strings/str_format.h"
86#include "ortools/base/hash.h"
89#include "ortools/base/macros.h"
92#include "ortools/base/timer.h"
93#include "ortools/constraint_solver/routing_parameters.pb.h"
94#include "ortools/constraint_solver/search_stats.pb.h"
95#include "ortools/constraint_solver/solver_parameters.pb.h"
99
100#if !defined(SWIG)
101ABSL_DECLARE_FLAG(int64, cp_random_seed);
102#endif // !defined(SWIG)
103
104class File;
105
106namespace operations_research {
107
108class Assignment;
109class AssignmentProto;
110class BaseObject;
111class CpArgument;
112class CpConstraint;
113class CpIntegerExpression;
114class CpIntervalVariable;
115class CpSequenceVariable;
116class CastConstraint;
117class Constraint;
118class Decision;
119class DecisionBuilder;
120class DecisionVisitor;
121class Demon;
122class DemonProfiler;
123class LocalSearchProfiler;
124class Dimension;
125class DisjunctiveConstraint;
126class ExpressionCache;
127class IntExpr;
128class IntTupleSet;
129class IntVar;
130class IntVarAssignment;
131class IntVarElement;
132class IntervalVar;
133class IntervalVarAssignment;
134class IntervalVarElement;
135class IntVarLocalSearchFilter;
136class LocalSearchFilter;
137class LocalSearchFilterManager;
138class LocalSearchOperator;
139class LocalSearchPhaseParameters;
140class ModelCache;
141class ModelVisitor;
142class OptimizeVar;
143class Pack;
144class PropagationBaseObject;
145class PropagationMonitor;
146class LocalSearchMonitor;
147class Queue;
148class RevBitMatrix;
149class RevBitSet;
150class RegularLimit;
151class RegularLimitParameters;
152class Search;
153class ImprovementSearchLimit;
154class SearchLimit;
155class SearchMonitor;
156class SequenceVar;
157class SequenceVarAssignment;
158class SolutionCollector;
159class SolutionPool;
160class Solver;
161class ConstraintSolverParameters;
162class SymmetryBreaker;
163struct StateInfo;
164struct Trail;
165template <class T>
166class SimpleRevFIFO;
167
169 return absl::GetFlag(FLAGS_cp_random_seed) == -1
170 ? absl::Uniform<int64>(absl::BitGen(), 0, kint64max)
171 : absl::GetFlag(FLAGS_cp_random_seed);
172}
173
178 public:
183 };
184
188 };
189
190 enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };
191
195
198
202
207
212
215
219
222
226
229
232
234};
235
253class Solver {
254 public:
261 : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
262 IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
263 : variable(v), expression(e), maintainer(c) {}
267 };
268
270 static constexpr int kNumPriorities = 3;
271
277
280
285
288
296
304
312
320
326
332
337
342
346
350 };
351 // TODO(user): add HIGHEST_MIN and LOWEST_MAX.
352
358
361
364
367
370
375
379
383 };
384
401
407 };
408
415 };
416
430 };
431
445
461
464
473
484
492
499
507
514
526
535
539
544
554
559
568 };
569
578
586
593 TSPLNS
594 };
595
607 EQ
608 };
609
617
620
623 };
624
630
633
636
639
642
645
648
651
656 };
657
663
666
669
672
675
678
683
688 };
689
699
704
709
713
717 };
718
722
737 };
738
741
743 typedef std::function<int64(int64)> IndexEvaluator1;
744 typedef std::function<int64(int64, int64)> IndexEvaluator2;
745 typedef std::function<int64(int64, int64, int64)> IndexEvaluator3;
746
747 typedef std::function<bool(int64)> IndexFilter1;
748
749 typedef std::function<IntVar*(int64)> Int64ToIntVar;
750
751 typedef std::function<int64(Solver* solver, const std::vector<IntVar*>& vars,
752 int64 first_unbound, int64 last_unbound)>
754
755 typedef std::function<int64(const IntVar* v, int64 id)> VariableValueSelector;
756 typedef std::function<bool(int64, int64, int64)> VariableValueComparator;
757 typedef std::function<DecisionModification()> BranchSelector;
758 // TODO(user): wrap in swig.
759 typedef std::function<void(Solver*)> Action;
760 typedef std::function<void()> Closure;
761
763 explicit Solver(const std::string& name);
764 Solver(const std::string& name, const ConstraintSolverParameters& parameters);
765 ~Solver();
766
768 ConstraintSolverParameters parameters() const { return parameters_; }
770 // TODO(user): Move to constraint_solver_parameters.h.
771 static ConstraintSolverParameters DefaultSolverParameters();
772
774
778 template <class T>
779 void SaveValue(T* o) {
780 InternalSaveValue(o);
781 }
782
795 template <typename T>
796 T* RevAlloc(T* object) {
797 return reinterpret_cast<T*>(SafeRevAlloc(object));
798 }
799
806 template <typename T>
807 T* RevAllocArray(T* object) {
808 return reinterpret_cast<T*>(SafeRevAllocArray(object));
809 }
810
844 void AddConstraint(Constraint* const c);
848 void AddCastConstraint(CastConstraint* const constraint,
849 IntVar* const target_var, IntExpr* const expr);
850
892 bool Solve(DecisionBuilder* const db,
893 const std::vector<SearchMonitor*>& monitors);
894 bool Solve(DecisionBuilder* const db);
895 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1);
896 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
897 SearchMonitor* const m2);
898 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
899 SearchMonitor* const m2, SearchMonitor* const m3);
900 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
901 SearchMonitor* const m2, SearchMonitor* const m3,
902 SearchMonitor* const m4);
904
913
914 void NewSearch(DecisionBuilder* const db,
915 const std::vector<SearchMonitor*>& monitors);
916 void NewSearch(DecisionBuilder* const db);
917 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1);
918 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
919 SearchMonitor* const m2);
920 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
921 SearchMonitor* const m2, SearchMonitor* const m3);
922 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
923 SearchMonitor* const m2, SearchMonitor* const m3,
924 SearchMonitor* const m4);
925
926 bool NextSolution();
927 void RestartSearch();
928 void EndSearch();
930
939 bool SolveAndCommit(DecisionBuilder* const db,
940 const std::vector<SearchMonitor*>& monitors);
941 bool SolveAndCommit(DecisionBuilder* const db);
942 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1);
943 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
944 SearchMonitor* const m2);
945 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
946 SearchMonitor* const m2, SearchMonitor* const m3);
947
949 bool CheckAssignment(Assignment* const solution);
950
954 bool CheckConstraint(Constraint* const ct);
955
957 SolverState state() const { return state_; }
958
960 void Fail();
961
962#if !defined(SWIG)
967 void AddBacktrackAction(Action a, bool fast);
968#endif
969
971 std::string DebugString() const;
972
974 static int64 MemoryUsage();
975
980 absl::Time Now() const;
981
984 int64 wall_time() const;
985
987 int64 branches() const { return branches_; }
988
990 int64 solutions() const;
991
994
996 int64 demon_runs(DemonPriority p) const { return demon_runs_[p]; }
997
999 int64 failures() const { return fails_; }
1000
1002 int64 neighbors() const { return neighbors_; }
1003
1005 int64 filtered_neighbors() const { return filtered_neighbors_; }
1006
1008 int64 accepted_neighbors() const { return accepted_neighbors_; }
1009
1012 uint64 stamp() const;
1013
1015 uint64 fail_stamp() const;
1016
1019 return optimization_direction_;
1020 }
1022 optimization_direction_ = direction;
1023 }
1024
1025 // All factories (MakeXXX methods) encapsulate creation of objects
1026 // through RevAlloc(). Hence, the Solver used for allocating the
1027 // returned object will retain ownership of the allocated memory.
1028 // Destructors are called upon backtrack, or when the Solver is
1029 // itself destructed.
1030
1031 // ----- Int Variables and Constants -----
1032
1034 IntVar* MakeIntVar(int64 min, int64 max, const std::string& name);
1035
1037 IntVar* MakeIntVar(const std::vector<int64>& values, const std::string& name);
1038
1040 IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);
1041
1044
1046 IntVar* MakeIntVar(const std::vector<int64>& values);
1047
1049 IntVar* MakeIntVar(const std::vector<int>& values);
1050
1052 IntVar* MakeBoolVar(const std::string& name);
1053
1056
1058 IntVar* MakeIntConst(int64 val, const std::string& name);
1059
1062
1066 void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1067 const std::string& name, std::vector<IntVar*>* vars);
1070 void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1071 std::vector<IntVar*>* vars);
1073 IntVar** MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1074 const std::string& name);
1075
1079 void MakeBoolVarArray(int var_count, const std::string& name,
1080 std::vector<IntVar*>* vars);
1083 void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
1085 IntVar** MakeBoolVarArray(int var_count, const std::string& name);
1086
1087 // ----- Integer Expressions -----
1088
1090 IntExpr* MakeSum(IntExpr* const left, IntExpr* const right);
1092 IntExpr* MakeSum(IntExpr* const expr, int64 value);
1094 IntExpr* MakeSum(const std::vector<IntVar*>& vars);
1095
1097 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1098 const std::vector<int64>& coefs);
1100 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1101 const std::vector<int>& coefs);
1102
1104 IntExpr* MakeDifference(IntExpr* const left, IntExpr* const right);
1106 IntExpr* MakeDifference(int64 value, IntExpr* const expr);
1108 IntExpr* MakeOpposite(IntExpr* const expr);
1109
1111 IntExpr* MakeProd(IntExpr* const left, IntExpr* const right);
1113 IntExpr* MakeProd(IntExpr* const expr, int64 value);
1114
1116 IntExpr* MakeDiv(IntExpr* const expr, int64 value);
1118 IntExpr* MakeDiv(IntExpr* const numerator, IntExpr* const denominator);
1119
1121 IntExpr* MakeAbs(IntExpr* const expr);
1123 IntExpr* MakeSquare(IntExpr* const expr);
1125 IntExpr* MakePower(IntExpr* const expr, int64 n);
1126
1128 IntExpr* MakeElement(const std::vector<int64>& values, IntVar* const index);
1130 IntExpr* MakeElement(const std::vector<int>& values, IntVar* const index);
1131
1142 IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
1143 IntVar* const index);
1145 IntExpr* MakeElement(IndexEvaluator2 values, IntVar* const index1,
1146 IntVar* const index2);
1147
1149 IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* const index);
1150
1151#if !defined(SWIG)
1153 IntExpr* MakeElement(Int64ToIntVar vars, int64 range_start, int64 range_end,
1154 IntVar* argument);
1155#endif // SWIG
1156
1159 IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64 value);
1160
1162 Constraint* MakeIfThenElseCt(IntVar* const condition,
1163 IntExpr* const then_expr,
1164 IntExpr* const else_expr,
1165 IntVar* const target_var);
1166
1168 IntExpr* MakeMin(const std::vector<IntVar*>& vars);
1170 IntExpr* MakeMin(IntExpr* const left, IntExpr* const right);
1172 IntExpr* MakeMin(IntExpr* const expr, int64 value);
1174 IntExpr* MakeMin(IntExpr* const expr, int value);
1175
1177 IntExpr* MakeMax(const std::vector<IntVar*>& vars);
1179 IntExpr* MakeMax(IntExpr* const left, IntExpr* const right);
1181 IntExpr* MakeMax(IntExpr* const expr, int64 value);
1183 IntExpr* MakeMax(IntExpr* const expr, int value);
1184
1186 IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64 early_cost,
1187 int64 early_date, int64 late_date,
1188 int64 late_cost);
1189
1192 IntExpr* MakeSemiContinuousExpr(IntExpr* const expr, int64 fixed_charge,
1193 int64 step);
1194
1197 // TODO(user): Investigate if we can merge all three piecewise linear
1199#ifndef SWIG
1201 const PiecewiseLinearFunction& f);
1202#endif
1203
1205 IntExpr* MakeModulo(IntExpr* const x, int64 mod);
1206
1208 IntExpr* MakeModulo(IntExpr* const x, IntExpr* const mod);
1209
1211 IntExpr* MakeConditionalExpression(IntVar* const condition,
1212 IntExpr* const expr,
1213 int64 unperformed_value);
1214
1219 Constraint* MakeFalseConstraint(const std::string& explanation);
1220
1223 IntVar* const boolvar);
1227 Constraint* MakeIsEqualCt(IntExpr* const v1, IntExpr* v2, IntVar* const b);
1229 IntVar* MakeIsEqualVar(IntExpr* const v1, IntExpr* v2);
1231 Constraint* MakeEquality(IntExpr* const left, IntExpr* const right);
1233 Constraint* MakeEquality(IntExpr* const expr, int64 value);
1235 Constraint* MakeEquality(IntExpr* const expr, int value);
1236
1239 IntVar* const boolvar);
1243 IntVar* MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2);
1245 Constraint* MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
1246 IntVar* const b);
1248 Constraint* MakeNonEquality(IntExpr* const left, IntExpr* const right);
1252 Constraint* MakeNonEquality(IntExpr* const expr, int value);
1253
1256 IntVar* const boolvar);
1260 IntVar* MakeIsLessOrEqualVar(IntExpr* const left, IntExpr* const right);
1262 Constraint* MakeIsLessOrEqualCt(IntExpr* const left, IntExpr* const right,
1263 IntVar* const b);
1265 Constraint* MakeLessOrEqual(IntExpr* const left, IntExpr* const right);
1269 Constraint* MakeLessOrEqual(IntExpr* const expr, int value);
1270
1273 IntVar* const boolvar);
1277 IntVar* MakeIsGreaterOrEqualVar(IntExpr* const left, IntExpr* const right);
1279 Constraint* MakeIsGreaterOrEqualCt(IntExpr* const left, IntExpr* const right,
1280 IntVar* const b);
1282 Constraint* MakeGreaterOrEqual(IntExpr* const left, IntExpr* const right);
1286 Constraint* MakeGreaterOrEqual(IntExpr* const expr, int value);
1287
1289 Constraint* MakeIsGreaterCstCt(IntExpr* const v, int64 c, IntVar* const b);
1293 IntVar* MakeIsGreaterVar(IntExpr* const left, IntExpr* const right);
1295 Constraint* MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
1296 IntVar* const b);
1298 Constraint* MakeGreater(IntExpr* const left, IntExpr* const right);
1300 Constraint* MakeGreater(IntExpr* const expr, int64 value);
1302 Constraint* MakeGreater(IntExpr* const expr, int value);
1303
1305 Constraint* MakeIsLessCstCt(IntExpr* const v, int64 c, IntVar* const b);
1309 IntVar* MakeIsLessVar(IntExpr* const left, IntExpr* const right);
1311 Constraint* MakeIsLessCt(IntExpr* const left, IntExpr* const right,
1312 IntVar* const b);
1314 Constraint* MakeLess(IntExpr* const left, IntExpr* const right);
1316 Constraint* MakeLess(IntExpr* const expr, int64 value);
1318 Constraint* MakeLess(IntExpr* const expr, int value);
1319
1321 Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64 cst);
1322 Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
1323 int64 cst);
1324 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64 cst);
1325 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars,
1326 IntVar* const var);
1327 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1328 const std::vector<int64>& coefficients,
1329 int64 cst);
1330 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1331 const std::vector<int>& coefficients,
1332 int64 cst);
1333 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1334 const std::vector<int64>& coefficients,
1335 IntVar* const target);
1336 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1337 const std::vector<int>& coefficients,
1338 IntVar* const target);
1339 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1340 const std::vector<int64>& coeffs,
1341 int64 cst);
1342 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1343 const std::vector<int>& coeffs,
1344 int64 cst);
1345 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1346 const std::vector<int64>& coefficients,
1347 int64 cst);
1348 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1349 const std::vector<int>& coefficients,
1350 int64 cst);
1351
1352 Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
1353 IntVar* const min_var);
1354 Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
1355 IntVar* const max_var);
1356
1357 Constraint* MakeElementEquality(const std::vector<int64>& vals,
1358 IntVar* const index, IntVar* const target);
1359 Constraint* MakeElementEquality(const std::vector<int>& vals,
1360 IntVar* const index, IntVar* const target);
1361 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1362 IntVar* const index, IntVar* const target);
1363 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1364 IntVar* const index, int64 target);
1366 Constraint* MakeAbsEquality(IntVar* const var, IntVar* const abs_var);
1371 Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
1372 IntVar* const index, int64 target);
1373
1381#if !defined(SWIG)
1383 Demon* MakeActionDemon(Action action);
1384#endif
1386 Demon* MakeClosureDemon(Closure closure);
1387
1388 // ----- Between and related constraints -----
1389
1391 Constraint* MakeBetweenCt(IntExpr* const expr, int64 l, int64 u);
1392
1397 Constraint* MakeNotBetweenCt(IntExpr* const expr, int64 l, int64 u);
1398
1400 Constraint* MakeIsBetweenCt(IntExpr* const expr, int64 l, int64 u,
1401 IntVar* const b);
1402 IntVar* MakeIsBetweenVar(IntExpr* const v, int64 l, int64 u);
1403
1404 // ----- Member and related constraints -----
1405
1408 Constraint* MakeMemberCt(IntExpr* const expr,
1409 const std::vector<int64>& values);
1410 Constraint* MakeMemberCt(IntExpr* const expr, const std::vector<int>& values);
1411
1413 Constraint* MakeNotMemberCt(IntExpr* const expr,
1414 const std::vector<int64>& values);
1415 Constraint* MakeNotMemberCt(IntExpr* const expr,
1416 const std::vector<int>& values);
1417
1419 Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int64> starts,
1420 std::vector<int64> ends);
1422 Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int> starts,
1423 std::vector<int> ends);
1424#if !defined(SWIG)
1427 SortedDisjointIntervalList intervals);
1428#endif // !defined(SWIG)
1429
1431 Constraint* MakeIsMemberCt(IntExpr* const expr,
1432 const std::vector<int64>& values,
1433 IntVar* const boolvar);
1434 Constraint* MakeIsMemberCt(IntExpr* const expr,
1435 const std::vector<int>& values,
1436 IntVar* const boolvar);
1437 IntVar* MakeIsMemberVar(IntExpr* const expr,
1438 const std::vector<int64>& values);
1439 IntVar* MakeIsMemberVar(IntExpr* const expr, const std::vector<int>& values);
1440
1442 Constraint* MakeAtMost(std::vector<IntVar*> vars, int64 value,
1443 int64 max_count);
1445 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1446 int64 max_count);
1448 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1449 IntVar* const max_count);
1450
1452 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1453 const std::vector<int64>& values,
1454 const std::vector<IntVar*>& cards);
1456 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1457 const std::vector<int>& values,
1458 const std::vector<IntVar*>& cards);
1460 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1461 const std::vector<IntVar*>& cards);
1464 Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64 card_min,
1465 int64 card_max, int64 card_size);
1469 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1470 const std::vector<int64>& card_min,
1471 const std::vector<int64>& card_max);
1475 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1476 const std::vector<int>& card_min,
1477 const std::vector<int>& card_max);
1481 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1482 const std::vector<int64>& values,
1483 const std::vector<int64>& card_min,
1484 const std::vector<int64>& card_max);
1488 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1489 const std::vector<int>& values,
1490 const std::vector<int>& card_min,
1491 const std::vector<int>& card_max);
1492
1497 Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
1498 IntVar* const deviation_var, int64 total_sum);
1499
1502 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);
1503
1507 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
1508 bool stronger_propagation);
1509
1512 Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
1513 int64 escape_value);
1514 // TODO(user): Do we need a version with an array of escape values.
1515
1531 Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
1532 const std::vector<IntVar*>& sorted);
1533 // TODO(user): Add void MakeSortedArray(
1534 // const std::vector<IntVar*>& vars,
1535 // std::vector<IntVar*>* const sorted);
1536
1539 Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
1540 const std::vector<IntVar*>& right);
1541
1544 Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
1545 const std::vector<IntVar*>& right);
1546
1552 const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);
1553
1557 IntVar* index, const std::vector<IntVar*>& vars);
1558
1562 IntVar* index, const std::vector<IntVar*>& vars);
1563
1568 Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
1569 const std::vector<IntVar*>& second_vars);
1570
1576 Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
1577 const std::vector<IntVar*>& second_vars,
1578 int64 escape_value);
1579
1580 // TODO(user): Implement MakeAllNullIntersect taking an array of
1581 // variable vectors.
1582
1592 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1593 const std::vector<IntVar*>& active,
1594 IndexFilter1 sink_handler = nullptr);
1595 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1596 const std::vector<IntVar*>& active,
1597 IndexFilter1 sink_handler, bool assume_paths);
1598
1600 Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);
1601
1604 Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);
1605
1610 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1611 const std::vector<IntVar*>& active,
1612 const std::vector<IntVar*>& cumuls,
1613 const std::vector<IntVar*>& transits);
1616 // TODO(user): Merge with other path-cumuls constraints.
1617 Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1618 const std::vector<IntVar*>& active,
1619 const std::vector<IntVar*>& cumuls,
1620 const std::vector<IntVar*>& transits);
1627 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1628 const std::vector<IntVar*>& active,
1629 const std::vector<IntVar*>& cumuls,
1630 IndexEvaluator2 transit_evaluator);
1631
1638 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1639 const std::vector<IntVar*>& active,
1640 const std::vector<IntVar*>& cumuls,
1641 const std::vector<IntVar*>& slacks,
1642 IndexEvaluator2 transit_evaluator);
1645 // TODO(user): Only does checking on WhenBound events on next variables.
1647 Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1648 std::vector<int64> sources,
1649 std::vector<int64> sinks,
1650 std::vector<IntVar*> status);
1651#ifndef SWIG
1654 // TODO(user): This constraint does not make holes in variable domains;
1658 std::vector<IntVar*> nexts,
1659 const std::vector<std::pair<int, int>>& precedences);
1669 std::vector<IntVar*> nexts,
1670 const std::vector<std::pair<int, int>>& precedences,
1671 const std::vector<int>& lifo_path_starts,
1672 const std::vector<int>& fifo_path_starts);
1676 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1677 const std::vector<std::pair<int, int>>& precedences);
1678#endif // !SWIG
1682 Constraint* MakeMapDomain(IntVar* const var,
1683 const std::vector<IntVar*>& actives);
1684
1689 Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1690 const IntTupleSet& tuples);
1691
1699 Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1700 const IntTupleSet& transition_table,
1701 int64 initial_state,
1702 const std::vector<int64>& final_states);
1703
1711 Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1712 const IntTupleSet& transition_table,
1713 int64 initial_state,
1714 const std::vector<int>& final_states);
1715
1716#if defined(SWIGPYTHON)
1719 const std::vector<IntVar*>& vars,
1720 const std::vector<std::vector<int64> /*keep for swig*/>& raw_tuples) {
1721 IntTupleSet tuples(vars.size());
1722 tuples.InsertAll(raw_tuples);
1723 return MakeAllowedAssignments(vars, tuples);
1724 }
1725
1727 const std::vector<IntVar*>& vars,
1728 const std::vector<std::vector<int64> /*keep for swig*/>& raw_transitions,
1729 int64 initial_state, const std::vector<int>& final_states) {
1730 IntTupleSet transitions(3);
1731 transitions.InsertAll(raw_transitions);
1732 return MakeTransitionConstraint(vars, transitions, initial_state,
1733 final_states);
1734 }
1735#endif
1736
1746 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1747 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1749 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1750 const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1752 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1753 const std::vector<int>& x_size, const std::vector<int>& y_size);
1754
1764 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1765 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1767 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1768 const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1770 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1771 const std::vector<int>& x_size, const std::vector<int>& y_size);
1772
1778 Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);
1779
1785 int64 duration, bool optional,
1786 const std::string& name);
1787
1791 int count, int64 start_min, int64 start_max, int64 duration,
1792 bool optional, const std::string& name,
1793 std::vector<IntervalVar*>* const array);
1794
1797 IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1798 int64 duration,
1799 const std::string& name);
1800
1803 IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1804 int64 duration,
1805 IntVar* const performed_variable,
1806 const std::string& name);
1807
1811 const std::vector<IntVar*>& start_variables, int64 duration,
1812 const std::string& name, std::vector<IntervalVar*>* const array);
1813
1817 const std::vector<IntVar*>& start_variables,
1818 const std::vector<int64>& durations, const std::string& name,
1819 std::vector<IntervalVar*>* const array);
1823 const std::vector<IntVar*>& start_variables,
1824 const std::vector<int>& durations, const std::string& name,
1825 std::vector<IntervalVar*>* const array);
1826
1830 const std::vector<IntVar*>& start_variables,
1831 const std::vector<int64>& durations,
1832 const std::vector<IntVar*>& performed_variables, const std::string& name,
1833 std::vector<IntervalVar*>* const array);
1834
1838 const std::vector<IntVar*>& start_variables,
1839 const std::vector<int>& durations,
1840 const std::vector<IntVar*>& performed_variables, const std::string& name,
1841 std::vector<IntervalVar*>* const array);
1842
1844 IntervalVar* MakeFixedInterval(int64 start, int64 duration,
1845 const std::string& name);
1846
1850 int64 duration_min, int64 duration_max,
1851 int64 end_min, int64 end_max, bool optional,
1852 const std::string& name);
1853
1857 int64 duration_min, int64 duration_max,
1858 int64 end_min, int64 end_max, bool optional,
1859 const std::string& name,
1860 std::vector<IntervalVar*>* const array);
1861
1864 IntervalVar* MakeMirrorInterval(IntervalVar* const interval_var);
1865
1871 IntervalVar* const interval_var, int64 duration, int64 offset);
1872
1878 IntervalVar* const interval_var, int64 duration, int64 offset);
1879
1885 IntervalVar* const interval_var, int64 duration, int64 offset);
1886
1892 IntervalVar* const interval_var, int64 duration, int64 offset);
1893
1911 IntervalVar* MakeIntervalRelaxedMin(IntervalVar* const interval_var);
1912
1930 IntervalVar* MakeIntervalRelaxedMax(IntervalVar* const interval_var);
1931
1934 Constraint* MakeIntervalVarRelation(IntervalVar* const t,
1936
1938 Constraint* MakeIntervalVarRelation(IntervalVar* const t1,
1940 IntervalVar* const t2);
1941
1946 Constraint* MakeIntervalVarRelationWithDelay(IntervalVar* const t1,
1948 IntervalVar* const t2,
1949 int64 delay);
1950
1954 Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1955 IntervalVar* const t2, IntVar* const alt);
1956
1959 Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1960 IntervalVar* const t2);
1961
1964 DisjunctiveConstraint* MakeDisjunctiveConstraint(
1965 const std::vector<IntervalVar*>& intervals, const std::string& name);
1966
1970 DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
1971 const std::vector<IntervalVar*>& intervals, const std::string& name);
1972
1982 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1983 const std::vector<int64>& demands, int64 capacity,
1984 const std::string& name);
1985
1995 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1996 const std::vector<int>& demands, int64 capacity,
1997 const std::string& name);
1998
2008 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2009 const std::vector<int64>& demands,
2010 IntVar* const capacity, const std::string& name);
2011
2021 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2022 const std::vector<int>& demands,
2023 IntVar* const capacity, const std::string& name);
2024
2032 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2033 const std::vector<IntVar*>& demands,
2034 int64 capacity, const std::string& name);
2035
2043 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2044 const std::vector<IntVar*>& demands,
2045 IntVar* const capacity, const std::string& name);
2046
2052 Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
2053 IntervalVar* const target_var);
2054
2056 Constraint* MakeEquality(IntervalVar* const var1, IntervalVar* const var2);
2057
2059 Assignment* MakeAssignment();
2060
2062 Assignment* MakeAssignment(const Assignment* const a);
2063
2065 SolutionCollector* MakeFirstSolutionCollector(
2066 const Assignment* const assignment);
2069 SolutionCollector* MakeFirstSolutionCollector();
2070
2072 SolutionCollector* MakeLastSolutionCollector(
2073 const Assignment* const assignment);
2076 SolutionCollector* MakeLastSolutionCollector();
2077
2082 SolutionCollector* MakeBestValueSolutionCollector(
2083 const Assignment* const assignment, bool maximize);
2089 SolutionCollector* MakeBestValueSolutionCollector(bool maximize);
2090
2094 SolutionCollector* MakeNBestValueSolutionCollector(
2095 const Assignment* const assignment, int solution_count, bool maximize);
2096 SolutionCollector* MakeNBestValueSolutionCollector(int solution_count,
2097 bool maximize);
2098
2100 SolutionCollector* MakeAllSolutionCollector(
2101 const Assignment* const assignment);
2104 SolutionCollector* MakeAllSolutionCollector();
2105
2107 OptimizeVar* MakeMinimize(IntVar* const v, int64 step);
2108
2110 OptimizeVar* MakeMaximize(IntVar* const v, int64 step);
2111
2113 OptimizeVar* MakeOptimize(bool maximize, IntVar* const v, int64 step);
2114
2117 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2118 const std::vector<int64>& weights,
2119 int64 step);
2120
2123 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2124 const std::vector<int>& weights,
2125 int64 step);
2126
2128 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2129 const std::vector<int64>& weights,
2130 int64 step);
2131
2133 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2134 const std::vector<int>& weights,
2135 int64 step);
2136
2138 OptimizeVar* MakeWeightedOptimize(bool maximize,
2139 const std::vector<IntVar*>& sub_objectives,
2140 const std::vector<int64>& weights,
2141 int64 step);
2142
2144 OptimizeVar* MakeWeightedOptimize(bool maximize,
2145 const std::vector<IntVar*>& sub_objectives,
2146 const std::vector<int>& weights,
2147 int64 step);
2148
2150
2166
2167 SearchMonitor* MakeTabuSearch(bool maximize, IntVar* const v, int64 step,
2168 const std::vector<IntVar*>& vars,
2169 int64 keep_tenure, int64 forbid_tenure,
2170 double tabu_factor);
2171
2174 SearchMonitor* MakeGenericTabuSearch(bool maximize, IntVar* const v,
2175 int64 step,
2176 const std::vector<IntVar*>& tabu_vars,
2177 int64 forbid_tenure);
2178
2180 // TODO(user): document behavior
2181 SearchMonitor* MakeSimulatedAnnealing(bool maximize, IntVar* const v,
2182 int64 step, int64 initial_temperature);
2183
2186 SearchMonitor* MakeGuidedLocalSearch(bool maximize, IntVar* const objective,
2187 IndexEvaluator2 objective_function,
2188 int64 step,
2189 const std::vector<IntVar*>& vars,
2190 double penalty_factor);
2192 bool maximize, IntVar* const objective,
2193 IndexEvaluator3 objective_function, int64 step,
2194 const std::vector<IntVar*>& vars,
2195 const std::vector<IntVar*>& secondary_vars, double penalty_factor);
2196
2200 SearchMonitor* MakeLubyRestart(int scale_factor);
2201
2204 SearchMonitor* MakeConstantRestart(int frequency);
2205
2207 RegularLimit* MakeTimeLimit(absl::Duration time);
2208#if !defined(SWIG)
2209 ABSL_DEPRECATED("Use the version taking absl::Duration() as argument")
2210#endif // !defined(SWIG)
2212 return MakeTimeLimit(time_in_ms == kint64max
2213 ? absl::InfiniteDuration()
2214 : absl::Milliseconds(time_in_ms));
2215 }
2216
2220
2224
2228
2231 // timer by estimating the number of remaining calls, and 'cumulative' means
2232 // that the limit applies cumulatively, instead of search-by-search.
2234 int64 solutions, bool smart_time_check = false,
2235 bool cumulative = false);
2237 RegularLimit* MakeLimit(const RegularLimitParameters& proto);
2238
2239#if !defined(SWIG)
2240 ABSL_DEPRECATED("Use other MakeLimit() versions")
2241#endif // !defined(SWIG)
2243 int64 solutions, bool smart_time_check = false,
2244 bool cumulative = false);
2245
2247 RegularLimitParameters MakeDefaultRegularLimitParameters() const;
2248
2252 SearchLimit* MakeLimit(SearchLimit* const limit_1,
2253 SearchLimit* const limit_2);
2254
2260 IntVar* objective_var, bool maximize, double objective_scaling_factor,
2261 double objective_offset, double improvement_rate_coefficient,
2262 int improvement_rate_solutions_distance);
2263
2266 SearchLimit* MakeCustomLimit(std::function<bool()> limiter);
2267
2268 // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).
2269
2272 SearchMonitor* MakeSearchLog(int branch_period);
2273
2275 SearchMonitor* MakeSearchLog(int branch_period, IntVar* const var);
2276
2279 SearchMonitor* MakeSearchLog(int branch_period,
2280 std::function<std::string()> display_callback);
2281
2284 SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
2285 std::function<std::string()> display_callback);
2286
2289 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var);
2290
2293 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var,
2294 std::function<std::string()> display_callback);
2295
2304 IntVar* variable = nullptr;
2308 double scaling_factor = 1.0;
2309 double offset = 0;
2313 std::function<std::string()> display_callback;
2317 };
2319
2322 SearchMonitor* MakeSearchTrace(const std::string& prefix);
2323
2325 SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
2326 SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
2327 SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);
2328
2333#if !defined(SWIG)
2336 absl::flat_hash_map<const IntVar*, int>* const map);
2337#endif // !defined(SWIG)
2338
2341 const std::vector<SymmetryBreaker*>& visitors);
2344 SymmetryBreaker* const v2);
2346 SymmetryBreaker* const v2,
2347 SymmetryBreaker* const v3);
2349 SymmetryBreaker* const v2,
2350 SymmetryBreaker* const v3,
2351 SymmetryBreaker* const v4);
2352
2358 bool start_with_lower_half);
2361 Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
2362 const std::vector<int64>& values);
2364 Decision* MakeDecision(Action apply, Action refute);
2365
2375 DecisionBuilder* const db2);
2377 DecisionBuilder* const db2,
2378 DecisionBuilder* const db3);
2380 DecisionBuilder* const db2,
2381 DecisionBuilder* const db3,
2382 DecisionBuilder* const db4);
2383 DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);
2384
2396 // TODO(user): The search tree can be balanced by using binary
2401 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2);
2402 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2403 DecisionBuilder* const db3);
2404 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2405 DecisionBuilder* const db3, DecisionBuilder* const db4);
2406 DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);
2407
2409 // TODO(user): name each of them differently, and document them (and do that
2411 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2412 IntVarStrategy var_str, IntValueStrategy val_str);
2413 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2414 IndexEvaluator1 var_evaluator,
2415 IntValueStrategy val_str);
2416
2417 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2418 IntVarStrategy var_str,
2419 IndexEvaluator2 value_evaluator);
2420
2423 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2424 IntVarStrategy var_str,
2425 VariableValueComparator var_val1_val2_comparator);
2426
2427 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2428 IndexEvaluator1 var_evaluator,
2429 IndexEvaluator2 value_evaluator);
2430
2431 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2432 IntVarStrategy var_str,
2433 IndexEvaluator2 value_evaluator,
2434 IndexEvaluator1 tie_breaker);
2435
2436 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2437 IndexEvaluator1 var_evaluator,
2438 IndexEvaluator2 value_evaluator,
2439 IndexEvaluator1 tie_breaker);
2440
2441 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
2442 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
2444
2446 DecisionBuilder* MakePhase(IntVar* const v0, IntVarStrategy var_str,
2447 IntValueStrategy val_str);
2448 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2449 IntVarStrategy var_str, IntValueStrategy val_str);
2450 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2451 IntVar* const v2, IntVarStrategy var_str,
2452 IntValueStrategy val_str);
2453 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2454 IntVar* const v2, IntVar* const v3,
2455 IntVarStrategy var_str, IntValueStrategy val_str);
2456
2463 int64* const marker);
2464
2471 int64* const marker);
2472
2475 Decision* MakeRankFirstInterval(SequenceVar* const sequence, int index);
2476
2479 Decision* MakeRankLastInterval(SequenceVar* const sequence, int index);
2480
2486 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2488
2496 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2497 IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2498 EvaluatorStrategy str);
2499
2501 DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
2502 IntervalStrategy str);
2503
2504 DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
2505 SequenceStrategy str);
2506
2510 Assignment* const assignment, DecisionBuilder* const db,
2511 const std::vector<IntVar*>& vars);
2512
2516
2523 SearchMonitor* const monitor1);
2525 SearchMonitor* const monitor1,
2526 SearchMonitor* const monitor2);
2528 SearchMonitor* const monitor1,
2529 SearchMonitor* const monitor2,
2530 SearchMonitor* const monitor3);
2532 SearchMonitor* const monitor1,
2533 SearchMonitor* const monitor2,
2534 SearchMonitor* const monitor3,
2535 SearchMonitor* const monitor4);
2537 const std::vector<SearchMonitor*>& monitors);
2538
2547 Assignment* const solution, bool maximize,
2548 int64 step);
2550 Assignment* const solution, bool maximize,
2551 int64 step,
2552 SearchMonitor* const monitor1);
2554 Assignment* const solution, bool maximize,
2555 int64 step, SearchMonitor* const monitor1,
2556 SearchMonitor* const monitor2);
2558 Assignment* const solution, bool maximize,
2559 int64 step, SearchMonitor* const monitor1,
2560 SearchMonitor* const monitor2,
2561 SearchMonitor* const monitor3);
2563 Assignment* const solution, bool maximize,
2564 int64 step, SearchMonitor* const monitor1,
2565 SearchMonitor* const monitor2,
2566 SearchMonitor* const monitor3,
2567 SearchMonitor* const monitor4);
2569 DecisionBuilder* const db, Assignment* const solution, bool maximize,
2570 int64 step, const std::vector<SearchMonitor*>& monitors);
2571
2575
2579
2581 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2583 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2584 const std::vector<IntVar*>& secondary_vars,
2586 // TODO(user): Make the callback an IndexEvaluator2 when there are no
2587 // secondary variables.
2588 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2589 IndexEvaluator3 evaluator,
2591 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2592 const std::vector<IntVar*>& secondary_vars,
2593 IndexEvaluator3 evaluator,
2595
2603 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2604 int number_of_variables);
2605 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2606 int number_of_variables,
2607 int32 seed);
2608
2615
2623 const std::vector<IntVar*>& variables,
2624 const std::vector<int64>& target_values);
2625
2657 const std::vector<LocalSearchOperator*>& ops);
2659 const std::vector<LocalSearchOperator*>& ops, bool restart);
2661 const std::vector<LocalSearchOperator*>& ops,
2662 std::function<int64(int, int)> evaluator);
2666 const std::vector<LocalSearchOperator*>& ops);
2667
2672 const std::vector<LocalSearchOperator*>& ops, int32 seed);
2673
2682 const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,
2683 double exploration_coefficient, bool maximize);
2684
2691 int64 limit);
2692
2717 // TODO(user): Make a variant which runs a local search after each
2718 // solution found in a DFS.
2719
2721 Assignment* const assignment,
2724 const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2728 const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2729 DecisionBuilder* const first_solution_sub_decision_builder,
2732 const std::vector<SequenceVar*>& vars,
2733 DecisionBuilder* const first_solution,
2735
2738
2741 IntVar* objective, LocalSearchOperator* const ls_operator,
2742 DecisionBuilder* const sub_decision_builder);
2744 IntVar* objective, LocalSearchOperator* const ls_operator,
2745 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2747 IntVar* objective, LocalSearchOperator* const ls_operator,
2748 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2749 LocalSearchFilterManager* filter_manager);
2750
2752 IntVar* objective, SolutionPool* const pool,
2753 LocalSearchOperator* const ls_operator,
2754 DecisionBuilder* const sub_decision_builder);
2756 IntVar* objective, SolutionPool* const pool,
2757 LocalSearchOperator* const ls_operator,
2758 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2760 IntVar* objective, SolutionPool* const pool,
2761 LocalSearchOperator* const ls_operator,
2762 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2763 LocalSearchFilterManager* filter_manager);
2764
2770 const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2771 Solver::LocalSearchFilterBound filter_enum);
2773 const std::vector<IntVar*>& vars,
2774 const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2775 Solver::LocalSearchFilterBound filter_enum);
2776
2779 void TopPeriodicCheck();
2783 int TopProgressPercent();
2784
2788 void PushState();
2789 void PopState();
2790
2793 int SearchDepth() const;
2794
2797 int SearchLeftDepth() const;
2798
2801 int SolveDepth() const;
2802
2805
2808
2810 template <class T>
2811 void SaveAndSetValue(T* adr, T val) {
2812 if (*adr != val) {
2813 InternalSaveValue(adr);
2814 *adr = val;
2815 }
2816 }
2817
2819 template <class T>
2820 void SaveAndAdd(T* adr, T val) {
2821 if (val != 0) {
2822 InternalSaveValue(adr);
2823 (*adr) += val;
2824 }
2825 }
2826
2829 DCHECK_GT(size, 0);
2830 return absl::Uniform<int64>(random_, 0, size);
2831 }
2832
2835 DCHECK_GT(size, 0);
2836 return absl::Uniform<int32>(random_, 0, size);
2837 }
2838
2840 void ReSeed(int32 seed) { random_.seed(seed); }
2841
2845 void ExportProfilingOverview(const std::string& filename);
2846
2848 // TODO(user): Merge demon and local search profiles.
2849 std::string LocalSearchProfile() const;
2850
2851#if !defined(SWIG)
2853 ConstraintSolverStatistics GetConstraintSolverStatistics() const;
2855 LocalSearchStatistics GetLocalSearchStatistics() const;
2856#endif // !defined(SWIG)
2857
2861 bool CurrentlyInSolve() const;
2862
2865 int constraints() const { return constraints_list_.size(); }
2866
2868 void Accept(ModelVisitor* const visitor) const;
2869
2870 Decision* balancing_decision() const { return balancing_decision_.get(); }
2871
2873#if !defined(SWIG)
2874 void set_fail_intercept(std::function<void()> fail_intercept) {
2875 fail_intercept_ = std::move(fail_intercept);
2876 }
2877#endif // !defined(SWIG)
2878 void clear_fail_intercept() { fail_intercept_ = nullptr; }
2880 DemonProfiler* demon_profiler() const { return demon_profiler_; }
2881 // TODO(user): Get rid of the following methods once fast local search is
2884 void SetUseFastLocalSearch(bool use_fast_local_search) {
2885 use_fast_local_search_ = use_fast_local_search;
2886 }
2888 bool UseFastLocalSearch() const { return use_fast_local_search_; }
2890 bool HasName(const PropagationBaseObject* object) const;
2892 Demon* RegisterDemon(Demon* const demon);
2894 IntExpr* RegisterIntExpr(IntExpr* const expr);
2900
2902 Search* ActiveSearch() const;
2904 ModelCache* Cache() const;
2906 bool InstrumentsDemons() const;
2908 bool IsProfilingEnabled() const;
2910 bool IsLocalSearchProfilingEnabled() const;
2912 bool InstrumentsVariables() const;
2914 bool NameAllVariables() const;
2916 std::string model_name() const;
2921 void AddPropagationMonitor(PropagationMonitor* const monitor);
2927 void SetSearchContext(Search* search, const std::string& search_context);
2928 std::string SearchContext() const;
2929 std::string SearchContext(const Search* search) const;
2931 // TODO(user): Investigate if this should be moved to Search.
2934 void ClearLocalSearchState() { local_search_state_.reset(nullptr); }
2935
2940 std::vector<int64> tmp_vector_;
2941
2942 friend class BaseIntExpr;
2943 friend class Constraint;
2944 friend class DemonProfiler;
2945 friend class FindOneNeighbor;
2946 friend class IntVar;
2948 friend class Queue;
2949 friend class SearchMonitor;
2950 friend class SearchLimit;
2951 friend class RoutingModel;
2953
2954#if !defined(SWIG)
2955 friend void InternalSaveBooleanVarValue(Solver* const, IntVar* const);
2956 template <class>
2957 friend class SimpleRevFIFO;
2958 template <class K, class V>
2960
2965 bool IsBooleanVar(IntExpr* const expr, IntVar** inner_var,
2966 bool* is_negated) const;
2967
2972 bool IsProduct(IntExpr* const expr, IntExpr** inner_expr, int64* coefficient);
2973#endif
2974
2977 IntExpr* CastExpression(const IntVar* const var) const;
2978
2980 void FinishCurrentSearch();
2981 void RestartCurrentSearch();
2982
2985 void ShouldFail() { should_fail_ = true; }
2986 void CheckFail() {
2987 if (!should_fail_) return;
2988 should_fail_ = false;
2989 Fail();
2990 }
2991
2992 private:
2993 void Init();
2994 void PushState(MarkerType t, const StateInfo& info);
2996 void PushSentinel(int magic_code);
2997 void BacktrackToSentinel(int magic_code);
2998 void ProcessConstraints();
2999 bool BacktrackOneLevel(Decision** fail_decision);
3000 void JumpToSentinelWhenNested();
3001 void JumpToSentinel();
3002 void check_alloc_state();
3003 void FreezeQueue();
3004 void EnqueueVar(Demon* const d);
3005 void EnqueueDelayedDemon(Demon* const d);
3006 void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3007 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3008 void UnfreezeQueue();
3009 void reset_action_on_fail();
3010 void set_action_on_fail(Action a);
3011 void set_variable_to_clean_on_fail(IntVar* v);
3012 void IncrementUncheckedSolutionCounter();
3013 bool IsUncheckedSolutionLimitReached();
3014
3015 void InternalSaveValue(int* valptr);
3016 void InternalSaveValue(int64* valptr);
3017 void InternalSaveValue(uint64* valptr);
3018 void InternalSaveValue(double* valptr);
3019 void InternalSaveValue(bool* valptr);
3020 void InternalSaveValue(void** valptr);
3021 void InternalSaveValue(int64** valptr) {
3022 InternalSaveValue(reinterpret_cast<void**>(valptr));
3023 }
3024
3025 BaseObject* SafeRevAlloc(BaseObject* ptr);
3026
3027 int* SafeRevAllocArray(int* ptr);
3028 int64* SafeRevAllocArray(int64* ptr);
3029 uint64* SafeRevAllocArray(uint64* ptr);
3030 double* SafeRevAllocArray(double* ptr);
3031 BaseObject** SafeRevAllocArray(BaseObject** ptr);
3032 IntVar** SafeRevAllocArray(IntVar** ptr);
3033 IntExpr** SafeRevAllocArray(IntExpr** ptr);
3034 Constraint** SafeRevAllocArray(Constraint** ptr);
3037 void* UnsafeRevAllocAux(void* ptr);
3038 template <class T>
3039 T* UnsafeRevAlloc(T* ptr) {
3040 return reinterpret_cast<T*>(
3041 UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
3042 }
3043 void** UnsafeRevAllocArrayAux(void** ptr);
3044 template <class T>
3045 T** UnsafeRevAllocArray(T** ptr) {
3046 return reinterpret_cast<T**>(
3047 UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
3048 }
3049
3050 void InitCachedIntConstants();
3051 void InitCachedConstraint();
3052
3056 Search* TopLevelSearch() const { return searches_.at(1); }
3060 Search* ParentSearch() const {
3061 const size_t search_size = searches_.size();
3062 DCHECK_GT(search_size, 1);
3063 return searches_[search_size - 2];
3064 }
3065
3067 std::string GetName(const PropagationBaseObject* object);
3068 void SetName(const PropagationBaseObject* object, const std::string& name);
3069
3072 int GetNewIntVarIndex() { return num_int_vars_++; }
3073
3075 bool IsADifference(IntExpr* expr, IntExpr** const left,
3076 IntExpr** const right);
3077
3078 const std::string name_;
3079 const ConstraintSolverParameters parameters_;
3080 absl::flat_hash_map<const PropagationBaseObject*, std::string>
3081 propagation_object_names_;
3082 absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3083 cast_information_;
3084 absl::flat_hash_set<const Constraint*> cast_constraints_;
3085 const std::string empty_name_;
3086 std::unique_ptr<Queue> queue_;
3087 std::unique_ptr<Trail> trail_;
3088 std::vector<Constraint*> constraints_list_;
3089 std::vector<Constraint*> additional_constraints_list_;
3090 std::vector<int> additional_constraints_parent_list_;
3091 SolverState state_;
3092 int64 branches_;
3093 int64 fails_;
3094 int64 decisions_;
3095 int64 demon_runs_[kNumPriorities];
3096 int64 neighbors_;
3097 int64 filtered_neighbors_;
3098 int64 accepted_neighbors_;
3099 OptimizationDirection optimization_direction_;
3100 std::unique_ptr<ClockTimer> timer_;
3101 std::vector<Search*> searches_;
3102 std::mt19937 random_;
3103 uint64 fail_stamp_;
3104 std::unique_ptr<Decision> balancing_decision_;
3106 std::function<void()> fail_intercept_;
3108 DemonProfiler* const demon_profiler_;
3110 bool use_fast_local_search_;
3112 LocalSearchProfiler* const local_search_profiler_;
3114 std::unique_ptr<Assignment> local_search_state_;
3115
3117 enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3118 IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3119
3121 Constraint* true_constraint_;
3122 Constraint* false_constraint_;
3123
3124 std::unique_ptr<Decision> fail_decision_;
3125 int constraint_index_;
3126 int additional_constraint_index_;
3127 int num_int_vars_;
3128
3129 std::unique_ptr<ModelCache> model_cache_;
3130 std::unique_ptr<PropagationMonitor> propagation_monitor_;
3131 PropagationMonitor* print_trace_;
3132 std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3133 int anonymous_variable_index_;
3134 bool should_fail_;
3135
3137};
3138
3139std::ostream& operator<<(std::ostream& out, const Solver* const s);
3140
3144inline int64 Zero() { return 0; }
3145
3147inline int64 One() { return 1; }
3148
3153 public:
3155 virtual ~BaseObject() {}
3156 virtual std::string DebugString() const { return "BaseObject"; }
3157
3158 private:
3159 DISALLOW_COPY_AND_ASSIGN(BaseObject);
3160};
3161
3162std::ostream& operator<<(std::ostream& out, const BaseObject* o);
3163
3168 public:
3169 explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
3171
3172 std::string DebugString() const override {
3173 if (name().empty()) {
3174 return "PropagationBaseObject";
3175 } else {
3176 return absl::StrFormat("PropagationBaseObject: %s", name());
3177 }
3178 }
3179 Solver* solver() const { return solver_; }
3180
3183 void FreezeQueue() { solver_->FreezeQueue(); }
3184
3187 void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3188
3192 void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
3193 void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
3194 void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3195 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3196
3197#if !defined(SWIG)
3198 // This method sets a callback that will be called if a failure
3199 // happens during the propagation of the queue.
3201 solver_->set_action_on_fail(std::move(a));
3202 }
3203#endif // !defined(SWIG)
3204
3206 void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3207
3210 solver_->set_variable_to_clean_on_fail(v);
3211 }
3212
3214 virtual std::string name() const;
3215 void set_name(const std::string& name);
3217 bool HasName() const;
3219 virtual std::string BaseName() const;
3220
3221 private:
3222 Solver* const solver_;
3223 DISALLOW_COPY_AND_ASSIGN(PropagationBaseObject);
3224};
3225
3228class Decision : public BaseObject {
3229 public:
3231 ~Decision() override {}
3232
3234 virtual void Apply(Solver* const s) = 0;
3235
3237 virtual void Refute(Solver* const s) = 0;
3238
3239 std::string DebugString() const override { return "Decision"; }
3241 virtual void Accept(DecisionVisitor* const visitor) const;
3242
3243 private:
3244 DISALLOW_COPY_AND_ASSIGN(Decision);
3245};
3246
3250 public:
3252 ~DecisionVisitor() override {}
3253 virtual void VisitSetVariableValue(IntVar* const var, int64 value);
3254 virtual void VisitSplitVariableDomain(IntVar* const var, int64 value,
3255 bool start_with_lower_half);
3256 virtual void VisitScheduleOrPostpone(IntervalVar* const var, int64 est);
3257 virtual void VisitScheduleOrExpedite(IntervalVar* const var, int64 est);
3258 virtual void VisitRankFirstInterval(SequenceVar* const sequence, int index);
3259 virtual void VisitRankLastInterval(SequenceVar* const sequence, int index);
3260 virtual void VisitUnknownDecision();
3261
3262 private:
3263 DISALLOW_COPY_AND_ASSIGN(DecisionVisitor);
3264};
3265
3269 public:
3271 ~DecisionBuilder() override {}
3276 virtual Decision* Next(Solver* const s) = 0;
3277 std::string DebugString() const override;
3278#if !defined(SWIG)
3283 virtual void AppendMonitors(Solver* const solver,
3284 std::vector<SearchMonitor*>* const extras);
3285 virtual void Accept(ModelVisitor* const visitor) const;
3286#endif
3287
3288 private:
3289 DISALLOW_COPY_AND_ASSIGN(DecisionBuilder);
3290};
3291
3301class Demon : public BaseObject {
3302 public:
3305 Demon() : stamp_(uint64_t{0}) {}
3306 ~Demon() override {}
3307
3309 virtual void Run(Solver* const s) = 0;
3310
3314 virtual Solver::DemonPriority priority() const;
3315
3316 std::string DebugString() const override;
3317
3320 void inhibit(Solver* const s);
3321
3323 void desinhibit(Solver* const s);
3324
3325 private:
3326 friend class Queue;
3327 void set_stamp(int64 stamp) { stamp_ = stamp; }
3328 uint64 stamp() const { return stamp_; }
3329 uint64 stamp_;
3331};
3332
3334class ModelVisitor : public BaseObject {
3335 public:
3337 static const char kAbs[];
3338 static const char kAbsEqual[];
3339 static const char kAllDifferent[];
3340 static const char kAllowedAssignments[];
3341 static const char kAtMost[];
3342 static const char kIndexOf[];
3343 static const char kBetween[];
3344 static const char kConditionalExpr[];
3345 static const char kCircuit[];
3346 static const char kConvexPiecewise[];
3347 static const char kCountEqual[];
3348 static const char kCover[];
3349 static const char kCumulative[];
3350 static const char kDeviation[];
3351 static const char kDifference[];
3352 static const char kDisjunctive[];
3353 static const char kDistribute[];
3354 static const char kDivide[];
3355 static const char kDurationExpr[];
3356 static const char kElement[];
3357 static const char kElementEqual[];
3358 static const char kEndExpr[];
3359 static const char kEquality[];
3360 static const char kFalseConstraint[];
3361 static const char kGlobalCardinality[];
3362 static const char kGreater[];
3363 static const char kGreaterOrEqual[];
3364 static const char kIntegerVariable[];
3365 static const char kIntervalBinaryRelation[];
3366 static const char kIntervalDisjunction[];
3367 static const char kIntervalUnaryRelation[];
3368 static const char kIntervalVariable[];
3369 static const char kInversePermutation[];
3370 static const char kIsBetween[];
3371 static const char kIsDifferent[];
3372 static const char kIsEqual[];
3373 static const char kIsGreater[];
3374 static const char kIsGreaterOrEqual[];
3375 static const char kIsLess[];
3376 static const char kIsLessOrEqual[];
3377 static const char kIsMember[];
3378 static const char kLess[];
3379 static const char kLessOrEqual[];
3380 static const char kLexLess[];
3381 static const char kLinkExprVar[];
3382 static const char kMapDomain[];
3383 static const char kMax[];
3384 static const char kMaxEqual[];
3385 static const char kMember[];
3386 static const char kMin[];
3387 static const char kMinEqual[];
3388 static const char kModulo[];
3389 static const char kNoCycle[];
3390 static const char kNonEqual[];
3391 static const char kNotBetween[];
3392 static const char kNotMember[];
3393 static const char kNullIntersect[];
3394 static const char kOpposite[];
3395 static const char kPack[];
3396 static const char kPathCumul[];
3397 static const char kDelayedPathCumul[];
3398 static const char kPerformedExpr[];
3399 static const char kPower[];
3400 static const char kProduct[];
3401 static const char kScalProd[];
3402 static const char kScalProdEqual[];
3403 static const char kScalProdGreaterOrEqual[];
3404 static const char kScalProdLessOrEqual[];
3405 static const char kSemiContinuous[];
3406 static const char kSequenceVariable[];
3407 static const char kSortingConstraint[];
3408 static const char kSquare[];
3409 static const char kStartExpr[];
3410 static const char kSum[];
3411 static const char kSumEqual[];
3412 static const char kSumGreaterOrEqual[];
3413 static const char kSumLessOrEqual[];
3414 static const char kTrace[];
3415 static const char kTransition[];
3416 static const char kTrueConstraint[];
3417 static const char kVarBoundWatcher[];
3418 static const char kVarValueWatcher[];
3419
3421 static const char kCountAssignedItemsExtension[];
3422 static const char kCountUsedBinsExtension[];
3423 static const char kInt64ToBoolExtension[];
3424 static const char kInt64ToInt64Extension[];
3425 static const char kObjectiveExtension[];
3426 static const char kSearchLimitExtension[];
3427 static const char kUsageEqualVariableExtension[];
3428
3429 static const char kUsageLessConstantExtension[];
3430 static const char kVariableGroupExtension[];
3433
3435 static const char kActiveArgument[];
3436 static const char kAssumePathsArgument[];
3437 static const char kBranchesLimitArgument[];
3438 static const char kCapacityArgument[];
3439 static const char kCardsArgument[];
3440 static const char kCoefficientsArgument[];
3441 static const char kCountArgument[];
3442 static const char kCumulativeArgument[];
3443 static const char kCumulsArgument[];
3444 static const char kDemandsArgument[];
3445 static const char kDurationMaxArgument[];
3446 static const char kDurationMinArgument[];
3447 static const char kEarlyCostArgument[];
3448 static const char kEarlyDateArgument[];
3449 static const char kEndMaxArgument[];
3450 static const char kEndMinArgument[];
3451 static const char kEndsArgument[];
3452 static const char kExpressionArgument[];
3453 static const char kFailuresLimitArgument[];
3454 static const char kFinalStatesArgument[];
3455 static const char kFixedChargeArgument[];
3456 static const char kIndex2Argument[];
3457 static const char kIndexArgument[];
3458 static const char kInitialState[];
3459 static const char kIntervalArgument[];
3460 static const char kIntervalsArgument[];
3461 static const char kLateCostArgument[];
3462 static const char kLateDateArgument[];
3463 static const char kLeftArgument[];
3464 static const char kMaxArgument[];
3465 static const char kMaximizeArgument[];
3466 static const char kMinArgument[];
3467 static const char kModuloArgument[];
3468 static const char kNextsArgument[];
3469 static const char kOptionalArgument[];
3470 static const char kPartialArgument[];
3471 static const char kPositionXArgument[];
3472 static const char kPositionYArgument[];
3473 static const char kRangeArgument[];
3474 static const char kRelationArgument[];
3475 static const char kRightArgument[];
3476 static const char kSequenceArgument[];
3477 static const char kSequencesArgument[];
3478 static const char kSizeArgument[];
3479 static const char kSizeXArgument[];
3480 static const char kSizeYArgument[];
3481 static const char kSmartTimeCheckArgument[];
3482 static const char kSolutionLimitArgument[];
3483 static const char kStartMaxArgument[];
3484 static const char kStartMinArgument[];
3485 static const char kStartsArgument[];
3486 static const char kStepArgument[];
3487 static const char kTargetArgument[];
3488 static const char kTimeLimitArgument[];
3489 static const char kTransitsArgument[];
3490 static const char kTuplesArgument[];
3491 static const char kValueArgument[];
3492 static const char kValuesArgument[];
3493 static const char kVariableArgument[];
3494 static const char kVarsArgument[];
3495 static const char kEvaluatorArgument[];
3496
3498 static const char kMirrorOperation[];
3499 static const char kRelaxedMaxOperation[];
3500 static const char kRelaxedMinOperation[];
3501 static const char kSumOperation[];
3502 static const char kDifferenceOperation[];
3503 static const char kProductOperation[];
3504 static const char kStartSyncOnStartOperation[];
3505 static const char kStartSyncOnEndOperation[];
3506 static const char kTraceOperation[];
3507
3508 ~ModelVisitor() override;
3509
3511
3513 virtual void BeginVisitModel(const std::string& type_name);
3514 virtual void EndVisitModel(const std::string& type_name);
3515 virtual void BeginVisitConstraint(const std::string& type_name,
3516 const Constraint* const constraint);
3517 virtual void EndVisitConstraint(const std::string& type_name,
3518 const Constraint* const constraint);
3519 virtual void BeginVisitExtension(const std::string& type);
3520 virtual void EndVisitExtension(const std::string& type);
3521 virtual void BeginVisitIntegerExpression(const std::string& type_name,
3522 const IntExpr* const expr);
3523 virtual void EndVisitIntegerExpression(const std::string& type_name,
3524 const IntExpr* const expr);
3525 virtual void VisitIntegerVariable(const IntVar* const variable,
3526 IntExpr* const delegate);
3527 virtual void VisitIntegerVariable(const IntVar* const variable,
3528 const std::string& operation, int64 value,
3529 IntVar* const delegate);
3530 virtual void VisitIntervalVariable(const IntervalVar* const variable,
3531 const std::string& operation, int64 value,
3532 IntervalVar* const delegate);
3533 virtual void VisitSequenceVariable(const SequenceVar* const variable);
3534
3536 virtual void VisitIntegerArgument(const std::string& arg_name, int64 value);
3537 virtual void VisitIntegerArrayArgument(const std::string& arg_name,
3538 const std::vector<int64>& values);
3539 virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
3540 const IntTupleSet& tuples);
3541
3543 virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
3544 IntExpr* const argument);
3545
3547 const std::string& arg_name, const std::vector<IntVar*>& arguments);
3548
3550 virtual void VisitIntervalArgument(const std::string& arg_name,
3551 IntervalVar* const argument);
3552
3553 virtual void VisitIntervalArrayArgument(
3554 const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
3556 virtual void VisitSequenceArgument(const std::string& arg_name,
3557 SequenceVar* const argument);
3558
3559 virtual void VisitSequenceArrayArgument(
3560 const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
3561#if !defined(SWIG)
3564 const std::string& arg_name, const Solver::Int64ToIntVar& arguments);
3565
3569 int64 index_max);
3571 int64 index_min, int64 index_max);
3574 const std::string& arg_name, int64 index_max);
3575#endif // #if !defined(SWIG)
3576};
3577
3585 public:
3587 ~Constraint() override {}
3588
3591 virtual void Post() = 0;
3592
3595 virtual void InitialPropagate() = 0;
3596 std::string DebugString() const override;
3597
3600 void PostAndPropagate();
3601
3603 virtual void Accept(ModelVisitor* const visitor) const;
3604
3606 bool IsCastConstraint() const;
3607
3611 virtual IntVar* Var();
3612
3613 private:
3614 DISALLOW_COPY_AND_ASSIGN(Constraint);
3615};
3616
3621 public:
3624 CHECK(target_var != nullptr);
3625 }
3626 ~CastConstraint() override {}
3627
3628 IntVar* target_var() const { return target_var_; }
3629
3630 protected:
3632};
3633
3636 public:
3637 static constexpr int kNoProgress = -1;
3638
3639 explicit SearchMonitor(Solver* const s) : solver_(s) {}
3640 ~SearchMonitor() override {}
3642 virtual void EnterSearch();
3643
3645 virtual void RestartSearch();
3646
3648 virtual void ExitSearch();
3649
3651 virtual void BeginNextDecision(DecisionBuilder* const b);
3652
3654 virtual void EndNextDecision(DecisionBuilder* const b, Decision* const d);
3655
3657 virtual void ApplyDecision(Decision* const d);
3658
3660 virtual void RefuteDecision(Decision* const d);
3661
3664 virtual void AfterDecision(Decision* const d, bool apply);
3665
3667 virtual void BeginFail();
3668
3670 virtual void EndFail();
3671
3673 virtual void BeginInitialPropagation();
3674
3676 virtual void EndInitialPropagation();
3677
3681 virtual bool AcceptSolution();
3682
3686 virtual bool AtSolution();
3687
3689 virtual void NoMoreSolutions();
3690
3693 virtual bool LocalOptimum();
3694
3696 virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3697
3699 virtual void AcceptNeighbor();
3700
3702 virtual void AcceptUncheckedNeighbor();
3703
3706 virtual bool IsUncheckedSolutionLimitReached() { return false; }
3707
3708 Solver* solver() const { return solver_; }
3709
3711 virtual void PeriodicCheck();
3712
3715 virtual int ProgressPercent() { return kNoProgress; }
3716
3718 virtual void Accept(ModelVisitor* const visitor) const;
3719
3722 virtual void Install();
3723
3724 private:
3725 Solver* const solver_;
3726 DISALLOW_COPY_AND_ASSIGN(SearchMonitor);
3727};
3728
3734template <class T>
3735class Rev {
3736 public:
3737 explicit Rev(const T& val) : stamp_(0), value_(val) {}
3738
3739 const T& Value() const { return value_; }
3740
3741 void SetValue(Solver* const s, const T& val) {
3742 if (val != value_) {
3743 if (stamp_ < s->stamp()) {
3744 s->SaveValue(&value_);
3745 stamp_ = s->stamp();
3746 }
3747 value_ = val;
3748 }
3749 }
3750
3751 private:
3752 uint64 stamp_;
3753 T value_;
3754};
3755
3757template <class T>
3758class NumericalRev : public Rev<T> {
3759 public:
3760 explicit NumericalRev(const T& val) : Rev<T>(val) {}
3761
3762 void Add(Solver* const s, const T& to_add) {
3763 this->SetValue(s, this->Value() + to_add);
3764 }
3765
3766 void Incr(Solver* const s) { Add(s, 1); }
3767
3768 void Decr(Solver* const s) { Add(s, -1); }
3769};
3770
3776template <class T>
3778 public:
3779 RevArray(int size, const T& val)
3780 : stamps_(new uint64[size]), values_(new T[size]), size_(size) {
3781 for (int i = 0; i < size; ++i) {
3782 stamps_[i] = 0;
3783 values_[i] = val;
3784 }
3785 }
3786
3788
3789 int64 size() const { return size_; }
3790
3791 const T& Value(int index) const { return values_[index]; }
3792
3793#if !defined(SWIG)
3794 const T& operator[](int index) const { return values_[index]; }
3795#endif
3796
3797 void SetValue(Solver* const s, int index, const T& val) {
3798 DCHECK_LT(index, size_);
3799 if (val != values_[index]) {
3800 if (stamps_[index] < s->stamp()) {
3801 s->SaveValue(&values_[index]);
3802 stamps_[index] = s->stamp();
3803 }
3804 values_[index] = val;
3805 }
3806 }
3807
3808 private:
3809 std::unique_ptr<uint64[]> stamps_;
3810 std::unique_ptr<T[]> values_;
3811 const int size_;
3812};
3813
3815template <class T>
3816class NumericalRevArray : public RevArray<T> {
3817 public:
3818 NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
3819
3820 void Add(Solver* const s, int index, const T& to_add) {
3821 this->SetValue(s, index, this->Value(index) + to_add);
3822 }
3823
3824 void Incr(Solver* const s, int index) { Add(s, index, 1); }
3825
3826 void Decr(Solver* const s, int index) { Add(s, index, -1); }
3827};
3828
3837 public:
3838 explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
3839 ~IntExpr() override {}
3840
3841 virtual int64 Min() const = 0;
3842 virtual void SetMin(int64 m) = 0;
3843 virtual int64 Max() const = 0;
3844 virtual void SetMax(int64 m) = 0;
3845
3848 virtual void Range(int64* l, int64* u) {
3849 *l = Min();
3850 *u = Max();
3851 }
3853 virtual void SetRange(int64 l, int64 u) {
3854 SetMin(l);
3855 SetMax(u);
3856 }
3857
3859 virtual void SetValue(int64 v) { SetRange(v, v); }
3860
3862 virtual bool Bound() const { return (Min() == Max()); }
3863
3865 virtual bool IsVar() const { return false; }
3866
3868 virtual IntVar* Var() = 0;
3869
3874 IntVar* VarWithName(const std::string& name);
3875
3877 virtual void WhenRange(Demon* d) = 0;
3880 WhenRange(solver()->MakeClosureDemon(std::move(closure)));
3881 }
3882
3883#if !defined(SWIG)
3886 WhenRange(solver()->MakeActionDemon(std::move(action)));
3887 }
3888#endif // SWIG
3889
3891 virtual void Accept(ModelVisitor* const visitor) const;
3892
3893 private:
3894 DISALLOW_COPY_AND_ASSIGN(IntExpr);
3895};
3896
3904
3907
3913
3915 public:
3916 ~IntVarIterator() override {}
3917
3919 virtual void Init() = 0;
3920
3922 virtual bool Ok() const = 0;
3923
3925 virtual int64 Value() const = 0;
3926
3928 virtual void Next() = 0;
3929
3931 std::string DebugString() const override { return "IntVar::Iterator"; }
3932};
3933
3934#ifndef SWIG
3942 public:
3944 : it_(it), begin_was_called_(false) {
3945 it_->Init();
3946 }
3947 struct Iterator;
3949 if (DEBUG_MODE) {
3950 DCHECK(!begin_was_called_);
3951 begin_was_called_ = true;
3952 }
3953 return Iterator::Begin(it_);
3954 }
3955 Iterator end() { return Iterator::End(it_); }
3956
3957 struct Iterator {
3960 return Iterator(it, /*is_end=*/false);
3961 }
3963 return Iterator(it, /*is_end=*/true);
3964 }
3965
3967 DCHECK(it_->Ok());
3968 return it_->Value();
3969 }
3971 DCHECK(it_->Ok());
3972 it_->Next();
3973 return *this;
3974 }
3975 bool operator!=(const Iterator& other) const {
3976 DCHECK(other.it_ == it_);
3977 DCHECK(other.is_end_);
3978 return it_->Ok();
3979 }
3980
3981 private:
3982 Iterator(IntVarIterator* it, bool is_end) : it_(it), is_end_(is_end) {}
3983
3984 IntVarIterator* const it_;
3985 const bool is_end_;
3986 };
3987
3988 private:
3989 IntVarIterator* const it_;
3990 bool begin_was_called_;
3991};
3992#endif // SWIG
3993
3997class IntVar : public IntExpr {
3998 public:
3999 explicit IntVar(Solver* const s);
4000 IntVar(Solver* const s, const std::string& name);
4001 ~IntVar() override {}
4002
4003 bool IsVar() const override { return true; }
4004 IntVar* Var() override { return this; }
4005
4008 virtual int64 Value() const = 0;
4009
4011 virtual void RemoveValue(int64 v) = 0;
4012
4015 virtual void RemoveInterval(int64 l, int64 u) = 0;
4016
4018 virtual void RemoveValues(const std::vector<int64>& values);
4019
4021 virtual void SetValues(const std::vector<int64>& values);
4022
4025 virtual void WhenBound(Demon* d) = 0;
4029 WhenBound(solver()->MakeClosureDemon(std::move(closure)));
4030 }
4031
4032#if !defined(SWIG)
4036 WhenBound(solver()->MakeActionDemon(std::move(action)));
4037 }
4038#endif // SWIG
4039
4042 virtual void WhenDomain(Demon* d) = 0;
4046 WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
4047 }
4048#if !defined(SWIG)
4052 WhenDomain(solver()->MakeActionDemon(std::move(action)));
4053 }
4054#endif // SWIG
4055
4057 virtual uint64 Size() const = 0;
4058
4061 virtual bool Contains(int64 v) const = 0;
4062
4066 virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;
4067
4071 virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;
4072
4074 virtual int64 OldMin() const = 0;
4075
4077 virtual int64 OldMax() const = 0;
4078
4079 virtual int VarType() const;
4080
4082 void Accept(ModelVisitor* const visitor) const override;
4083
4085 virtual IntVar* IsEqual(int64 constant) = 0;
4086 virtual IntVar* IsDifferent(int64 constant) = 0;
4087 virtual IntVar* IsGreaterOrEqual(int64 constant) = 0;
4088 virtual IntVar* IsLessOrEqual(int64 constant) = 0;
4089
4091 int index() const { return index_; }
4092
4093 private:
4094 const int index_;
4095 DISALLOW_COPY_AND_ASSIGN(IntVar);
4096};
4097
4102 public:
4103 SolutionCollector(Solver* const solver, const Assignment* assignment);
4104 explicit SolutionCollector(Solver* const solver);
4105 ~SolutionCollector() override;
4106 std::string DebugString() const override { return "SolutionCollector"; }
4107
4109 void Add(IntVar* const var);
4110 void Add(const std::vector<IntVar*>& vars);
4111 void Add(IntervalVar* const var);
4112 void Add(const std::vector<IntervalVar*>& vars);
4113 void Add(SequenceVar* const var);
4114 void Add(const std::vector<SequenceVar*>& vars);
4115 void AddObjective(IntVar* const objective);
4116
4118 void EnterSearch() override;
4119
4121 int solution_count() const;
4122
4124 Assignment* solution(int n) const;
4125
4127 int64 wall_time(int n) const;
4128
4130 int64 branches(int n) const;
4131
4134 int64 failures(int n) const;
4135
4137 int64 objective_value(int n) const;
4138
4140 int64 Value(int n, IntVar* const var) const;
4141
4143 int64 StartValue(int n, IntervalVar* const var) const;
4144
4146 int64 EndValue(int n, IntervalVar* const var) const;
4147
4149 int64 DurationValue(int n, IntervalVar* const var) const;
4150
4152 int64 PerformedValue(int n, IntervalVar* const var) const;
4153
4157 const std::vector<int>& ForwardSequence(int n, SequenceVar* const var) const;
4161 const std::vector<int>& BackwardSequence(int n, SequenceVar* const var) const;
4164 const std::vector<int>& Unperformed(int n, SequenceVar* const var) const;
4165
4166 protected:
4173 bool operator<(const SolutionData& other) const {
4174 return std::tie(solution, time, branches, failures, objective_value) <
4175 std::tie(other.solution, other.time, other.branches,
4176 other.failures, other.objective_value);
4177 }
4178 };
4179
4181 void PushSolution();
4182 void Push(const SolutionData& data) { solution_data_.push_back(data); }
4184 void PopSolution();
4185 SolutionData BuildSolutionDataForCurrentState();
4187 void check_index(int n) const;
4188
4189 std::unique_ptr<Assignment> prototype_;
4190 std::vector<SolutionData> solution_data_;
4191 std::vector<Assignment*> recycle_solutions_;
4192
4193 private:
4194 DISALLOW_COPY_AND_ASSIGN(SolutionCollector);
4195};
4196
4197// TODO(user): Refactor this into an Objective class:
4198// - print methods for AtNode and AtSolution.
4199// - support for weighted objective and lexicographical objective.
4200
4205 public:
4206 OptimizeVar(Solver* const s, bool maximize, IntVar* const a, int64 step);
4207 ~OptimizeVar() override;
4208
4210 int64 best() const { return best_; }
4211
4213 IntVar* Var() const { return var_; }
4215 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
4216 void EnterSearch() override;
4217 void BeginNextDecision(DecisionBuilder* const db) override;
4218 void RefuteDecision(Decision* const d) override;
4219 bool AtSolution() override;
4220 bool AcceptSolution() override;
4221 virtual std::string Print() const;
4222 std::string DebugString() const override;
4223 void Accept(ModelVisitor* const visitor) const override;
4224
4225 void ApplyBound();
4226
4227 protected:
4228 IntVar* const var_;
4233
4234 private:
4235 DISALLOW_COPY_AND_ASSIGN(OptimizeVar);
4236};
4237
4240 public:
4241 explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
4242 ~SearchLimit() override;
4243
4245 bool crossed() const { return crossed_; }
4246
4251 virtual bool Check() = 0;
4252
4254 virtual void Init() = 0;
4255
4258 virtual void Copy(const SearchLimit* const limit) = 0;
4259
4261 virtual SearchLimit* MakeClone() const = 0;
4262
4264 void EnterSearch() override;
4265 void BeginNextDecision(DecisionBuilder* const b) override;
4266 void PeriodicCheck() override;
4267 void RefuteDecision(Decision* const d) override;
4268 std::string DebugString() const override {
4269 return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
4270 }
4271
4272 private:
4273 void TopPeriodicCheck();
4274
4275 bool crossed_;
4276 DISALLOW_COPY_AND_ASSIGN(SearchLimit);
4277};
4278
4282 public:
4283 RegularLimit(Solver* const s, absl::Duration time, int64 branches,
4284 int64 failures, int64 solutions, bool smart_time_check,
4285 bool cumulative);
4286 ~RegularLimit() override;
4287 void Copy(const SearchLimit* const limit) override;
4288 SearchLimit* MakeClone() const override;
4290 bool Check() override;
4291 void Init() override;
4292 void ExitSearch() override;
4293 void UpdateLimits(absl::Duration time, int64 branches, int64 failures,
4295 absl::Duration duration_limit() const { return duration_limit_; }
4297 return duration_limit_ == absl::InfiniteDuration()
4298 ? kint64max
4299 : absl::ToInt64Milliseconds(duration_limit());
4300 }
4301 int64 branches() const { return branches_; }
4302 int64 failures() const { return failures_; }
4303 int64 solutions() const { return solutions_; }
4304 bool IsUncheckedSolutionLimitReached() override;
4305 int ProgressPercent() override;
4306 std::string DebugString() const override;
4307
4308 absl::Time AbsoluteSolverDeadline() const {
4309 return solver_time_at_limit_start_ + duration_limit_;
4310 }
4311
4312 void Accept(ModelVisitor* const visitor) const override;
4313
4314 private:
4315 bool CheckTime();
4316 absl::Duration TimeElapsed();
4317 static int64 GetPercent(int64 value, int64 offset, int64 total) {
4318 return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
4319 : -1;
4320 }
4321
4322 absl::Duration duration_limit_;
4323 absl::Time solver_time_at_limit_start_;
4324 absl::Duration last_time_elapsed_;
4325 int64 check_count_;
4326 int64 next_check_;
4327 bool smart_time_check_;
4328 int64 branches_;
4329 int64 branches_offset_;
4330 int64 failures_;
4331 int64 failures_offset_;
4332 int64 solutions_;
4333 int64 solutions_offset_;
4341 bool cumulative_;
4342};
4343
4344// Limit based on the improvement rate of 'objective_var'.
4345// This limit proceeds in two stages:
4346// 1) During the phase of the search in which the objective_var is strictly
4347// improving, a threshold value is computed as the minimum improvement rate of
4348// the objective, based on the 'improvement_rate_coefficient' and
4349// 'improvement_rate_solutions_distance' parameters.
4350// 2) Then, if the search continues beyond this phase of strict improvement, the
4351// limit stops the search when the improvement rate of the objective gets below
4352// this threshold value.
4354 public:
4355 ImprovementSearchLimit(Solver* const s, IntVar* objective_var, bool maximize,
4356 double objective_scaling_factor,
4357 double objective_offset,
4358 double improvement_rate_coefficient,
4359 int improvement_rate_solutions_distance);
4360 ~ImprovementSearchLimit() override;
4361 void Copy(const SearchLimit* const limit) override;
4362 SearchLimit* MakeClone() const override;
4363 bool Check() override;
4364 bool AtSolution() override;
4365 void Init() override;
4366
4367 private:
4368 IntVar* objective_var_;
4369 bool maximize_;
4370 double objective_scaling_factor_;
4371 double objective_offset_;
4372 double improvement_rate_coefficient_;
4373 int improvement_rate_solutions_distance_;
4374
4375 double best_objective_;
4376 // clang-format off
4377 std::deque<std::pair<double, int64> > improvements_;
4378 // clang-format on
4379 double threshold_;
4380 bool objective_updated_;
4381 bool gradient_stage_;
4382};
4383
4395 public:
4397 static const int64 kMinValidValue;
4399 static const int64 kMaxValidValue;
4400 IntervalVar(Solver* const solver, const std::string& name)
4402 set_name(name);
4403 }
4404 ~IntervalVar() override {}
4405
4408 virtual int64 StartMin() const = 0;
4409 virtual int64 StartMax() const = 0;
4410 virtual void SetStartMin(int64 m) = 0;
4411 virtual void SetStartMax(int64 m) = 0;
4412 virtual void SetStartRange(int64 mi, int64 ma) = 0;
4413 virtual int64 OldStartMin() const = 0;
4414 virtual int64 OldStartMax() const = 0;
4415 virtual void WhenStartRange(Demon* const d) = 0;
4417 WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4418 }
4419#if !defined(SWIG)
4421 WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4422 }
4423#endif // SWIG
4424 virtual void WhenStartBound(Demon* const d) = 0;
4426 WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4427 }
4428#if !defined(SWIG)
4430 WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4431 }
4432#endif // SWIG
4433
4435 virtual int64 DurationMin() const = 0;
4436 virtual int64 DurationMax() const = 0;
4437 virtual void SetDurationMin(int64 m) = 0;
4438 virtual void SetDurationMax(int64 m) = 0;
4439 virtual void SetDurationRange(int64 mi, int64 ma) = 0;
4440 virtual int64 OldDurationMin() const = 0;
4441 virtual int64 OldDurationMax() const = 0;
4442 virtual void WhenDurationRange(Demon* const d) = 0;
4444 WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4445 }
4446#if !defined(SWIG)
4448 WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4449 }
4450#endif // SWIG
4451 virtual void WhenDurationBound(Demon* const d) = 0;
4453 WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4454 }
4455#if !defined(SWIG)
4457 WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4458 }
4459#endif // SWIG
4460
4462 virtual int64 EndMin() const = 0;
4463 virtual int64 EndMax() const = 0;
4464 virtual void SetEndMin(int64 m) = 0;
4465 virtual void SetEndMax(int64 m) = 0;
4466 virtual void SetEndRange(int64 mi, int64 ma) = 0;
4467 virtual int64 OldEndMin() const = 0;
4468 virtual int64 OldEndMax() const = 0;
4469 virtual void WhenEndRange(Demon* const d) = 0;
4471 WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4472 }
4473#if !defined(SWIG)
4475 WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4476 }
4477#endif // SWIG
4478 virtual void WhenEndBound(Demon* const d) = 0;
4480 WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4481 }
4482#if !defined(SWIG)
4484 WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4485 }
4486#endif // SWIG
4487
4490 virtual bool MustBePerformed() const = 0;
4491 virtual bool MayBePerformed() const = 0;
4492 bool CannotBePerformed() const { return !MayBePerformed(); }
4493 bool IsPerformedBound() const {
4494 return MustBePerformed() || !MayBePerformed();
4495 }
4496 virtual void SetPerformed(bool val) = 0;
4497 virtual bool WasPerformedBound() const = 0;
4498 virtual void WhenPerformedBound(Demon* const d) = 0;
4500 WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4501 }
4502#if !defined(SWIG)
4504 WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4505 }
4506#endif // SWIG
4507
4509 void WhenAnything(Demon* const d);
4512 WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4513 }
4514#if !defined(SWIG)
4517 WhenAnything(solver()->MakeActionDemon(std::move(action)));
4518 }
4519#endif // SWIG
4520
4524 virtual IntExpr* StartExpr() = 0;
4525 virtual IntExpr* DurationExpr() = 0;
4526 virtual IntExpr* EndExpr() = 0;
4527 virtual IntExpr* PerformedExpr() = 0;
4531 virtual IntExpr* SafeStartExpr(int64 unperformed_value) = 0;
4532 virtual IntExpr* SafeDurationExpr(int64 unperformed_value) = 0;
4533 virtual IntExpr* SafeEndExpr(int64 unperformed_value) = 0;
4534
4536 virtual void Accept(ModelVisitor* const visitor) const = 0;
4537
4538 private:
4539 DISALLOW_COPY_AND_ASSIGN(IntervalVar);
4540};
4541
4549 public:
4550 SequenceVar(Solver* const s, const std::vector<IntervalVar*>& intervals,
4551 const std::vector<IntVar*>& nexts, const std::string& name);
4552
4553 ~SequenceVar() override;
4554
4555 std::string DebugString() const override;
4556
4557#if !defined(SWIG)
4560 void DurationRange(int64* const dmin, int64* const dmax) const;
4561
4564 void HorizonRange(int64* const hmin, int64* const hmax) const;
4565
4568 void ActiveHorizonRange(int64* const hmin, int64* const hmax) const;
4569
4571 void ComputeStatistics(int* const ranked, int* const not_ranked,
4572 int* const unperformed) const;
4573#endif // !defined(SWIG)
4574
4577 void RankFirst(int index);
4578
4581 void RankNotFirst(int index);
4582
4585 void RankLast(int index);
4586
4589 void RankNotLast(int index);
4590
4593 void ComputePossibleFirstsAndLasts(std::vector<int>* const possible_firsts,
4594 std::vector<int>* const possible_lasts);
4595
4601 void RankSequence(const std::vector<int>& rank_first,
4602 const std::vector<int>& rank_last,
4603 const std::vector<int>& unperformed);
4604
4613 void FillSequence(std::vector<int>* const rank_first,
4614 std::vector<int>* const rank_last,
4615 std::vector<int>* const unperformed) const;
4616
4618 IntervalVar* Interval(int index) const;
4619
4621 IntVar* Next(int index) const;
4622
4624 int64 size() const { return intervals_.size(); }
4625
4627 virtual void Accept(ModelVisitor* const visitor) const;
4628
4629 private:
4630 int ComputeForwardFrontier();
4631 int ComputeBackwardFrontier();
4632 void UpdatePrevious() const;
4633
4634 const std::vector<IntervalVar*> intervals_;
4635 const std::vector<IntVar*> nexts_;
4636 mutable std::vector<int> previous_;
4637};
4638
4640 public:
4641 AssignmentElement() : activated_(true) {}
4642
4643 void Activate() { activated_ = true; }
4644 void Deactivate() { activated_ = false; }
4645 bool Activated() const { return activated_; }
4646
4647 private:
4648 bool activated_;
4649};
4650
4652 public:
4653 IntVarElement();
4654 explicit IntVarElement(IntVar* const var);
4655 void Reset(IntVar* const var);
4657 void Copy(const IntVarElement& element);
4658 IntVar* Var() const { return var_; }
4659 void Store() {
4660 min_ = var_->Min();
4661 max_ = var_->Max();
4662 }
4663 void Restore() {
4664 if (var_ != nullptr) {
4665 var_->SetRange(min_, max_);
4666 }
4667 }
4668 void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
4669 void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
4670
4671 int64 Min() const { return min_; }
4672 void SetMin(int64 m) { min_ = m; }
4673 int64 Max() const { return max_; }
4674 void SetMax(int64 m) { max_ = m; }
4675 int64 Value() const {
4676 DCHECK_EQ(min_, max_);
4677 // Get the value from an unbound int var assignment element.
4678 return min_;
4679 }
4680 bool Bound() const { return (max_ == min_); }
4681 void SetRange(int64 l, int64 u) {
4682 min_ = l;
4683 max_ = u;
4684 }
4685 void SetValue(int64 v) {
4686 min_ = v;
4687 max_ = v;
4688 }
4689 std::string DebugString() const;
4690
4691 bool operator==(const IntVarElement& element) const;
4692 bool operator!=(const IntVarElement& element) const {
4693 return !(*this == element);
4694 }
4695
4696 private:
4697 IntVar* var_;
4698 int64 min_;
4699 int64 max_;
4700};
4701
4703 public:
4705 explicit IntervalVarElement(IntervalVar* const var);
4706 void Reset(IntervalVar* const var);
4708 void Copy(const IntervalVarElement& element);
4709 IntervalVar* Var() const { return var_; }
4710 void Store();
4711 void Restore();
4712 void LoadFromProto(
4713 const IntervalVarAssignment& interval_var_assignment_proto);
4714 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
4715
4716 int64 StartMin() const { return start_min_; }
4717 int64 StartMax() const { return start_max_; }
4719 CHECK_EQ(start_max_, start_min_);
4720 return start_max_;
4721 }
4722 int64 DurationMin() const { return duration_min_; }
4723 int64 DurationMax() const { return duration_max_; }
4725 CHECK_EQ(duration_max_, duration_min_);
4726 return duration_max_;
4727 }
4728 int64 EndMin() const { return end_min_; }
4729 int64 EndMax() const { return end_max_; }
4730 int64 EndValue() const {
4731 CHECK_EQ(end_max_, end_min_);
4732 return end_max_;
4733 }
4734 int64 PerformedMin() const { return performed_min_; }
4735 int64 PerformedMax() const { return performed_max_; }
4737 CHECK_EQ(performed_max_, performed_min_);
4738 return performed_max_;
4739 }
4740 void SetStartMin(int64 m) { start_min_ = m; }
4741 void SetStartMax(int64 m) { start_max_ = m; }
4743 start_min_ = mi;
4744 start_max_ = ma;
4745 }
4747 start_min_ = v;
4748 start_max_ = v;
4749 }
4750 void SetDurationMin(int64 m) { duration_min_ = m; }
4751 void SetDurationMax(int64 m) { duration_max_ = m; }
4753 duration_min_ = mi;
4754 duration_max_ = ma;
4755 }
4757 duration_min_ = v;
4758 duration_max_ = v;
4759 }
4760 void SetEndMin(int64 m) { end_min_ = m; }
4761 void SetEndMax(int64 m) { end_max_ = m; }
4762 void SetEndRange(int64 mi, int64 ma) {
4763 end_min_ = mi;
4764 end_max_ = ma;
4765 }
4767 end_min_ = v;
4768 end_max_ = v;
4769 }
4770 void SetPerformedMin(int64 m) { performed_min_ = m; }
4771 void SetPerformedMax(int64 m) { performed_max_ = m; }
4773 performed_min_ = mi;
4774 performed_max_ = ma;
4775 }
4777 performed_min_ = v;
4778 performed_max_ = v;
4779 }
4780 bool Bound() const {
4781 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4782 end_min_ == end_max_ && performed_min_ == performed_max_);
4783 }
4784 std::string DebugString() const;
4785 bool operator==(const IntervalVarElement& element) const;
4786 bool operator!=(const IntervalVarElement& element) const {
4787 return !(*this == element);
4788 }
4789
4790 private:
4791 int64 start_min_;
4792 int64 start_max_;
4793 int64 duration_min_;
4794 int64 duration_max_;
4795 int64 end_min_;
4796 int64 end_max_;
4797 int64 performed_min_;
4798 int64 performed_max_;
4799 IntervalVar* var_;
4800};
4801
4816 public:
4818 explicit SequenceVarElement(SequenceVar* const var);
4819 void Reset(SequenceVar* const var);
4821 void Copy(const SequenceVarElement& element);
4822 SequenceVar* Var() const { return var_; }
4823 void Store();
4824 void Restore();
4825 void LoadFromProto(
4826 const SequenceVarAssignment& sequence_var_assignment_proto);
4827 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
4828
4829 const std::vector<int>& ForwardSequence() const;
4830 const std::vector<int>& BackwardSequence() const;
4831 const std::vector<int>& Unperformed() const;
4832 void SetSequence(const std::vector<int>& forward_sequence,
4833 const std::vector<int>& backward_sequence,
4834 const std::vector<int>& unperformed);
4835 void SetForwardSequence(const std::vector<int>& forward_sequence);
4836 void SetBackwardSequence(const std::vector<int>& backward_sequence);
4837 void SetUnperformed(const std::vector<int>& unperformed);
4838 bool Bound() const {
4839 return forward_sequence_.size() + unperformed_.size() == var_->size();
4840 }
4841
4842 std::string DebugString() const;
4843
4844 bool operator==(const SequenceVarElement& element) const;
4845 bool operator!=(const SequenceVarElement& element) const {
4846 return !(*this == element);
4847 }
4848
4849 private:
4850 bool CheckClassInvariants();
4851
4852 SequenceVar* var_;
4853 std::vector<int> forward_sequence_;
4854 std::vector<int> backward_sequence_;
4855 std::vector<int> unperformed_;
4856};
4857
4858template <class V, class E>
4860 public:
4862 E* Add(V* var) {
4863 CHECK(var != nullptr);
4864 int index = -1;
4865 if (!Find(var, &index)) {
4866 return FastAdd(var);
4867 } else {
4868 return &elements_[index];
4869 }
4870 }
4872 E* FastAdd(V* var) {
4873 DCHECK(var != nullptr);
4874 elements_.emplace_back(var);
4875 return &elements_.back();
4876 }
4879 E* AddAtPosition(V* var, int position) {
4880 elements_[position].Reset(var);
4881 return &elements_[position];
4882 }
4883 void Clear() {
4884 elements_.clear();
4885 if (!elements_map_.empty()) {
4886 elements_map_.clear();
4887 }
4888 }
4891 void Resize(size_t size) { elements_.resize(size); }
4892 bool Empty() const { return elements_.empty(); }
4896 for (int i = 0; i < container.elements_.size(); ++i) {
4897 const E& element = container.elements_[i];
4898 const V* const var = element.Var();
4899 int index = -1;
4900 if (i < elements_.size() && elements_[i].Var() == var) {
4901 index = i;
4902 } else if (!Find(var, &index)) {
4903 continue;
4904 }
4905 DCHECK_GE(index, 0);
4906 E* const local_element = &elements_[index];
4907 local_element->Copy(element);
4908 if (element.Activated()) {
4909 local_element->Activate();
4910 } else {
4911 local_element->Deactivate();
4912 }
4913 }
4914 }
4917 void Copy(const AssignmentContainer<V, E>& container) {
4918 Clear();
4919 for (int i = 0; i < container.elements_.size(); ++i) {
4920 const E& element = container.elements_[i];
4921 FastAdd(element.Var())->Copy(element);
4922 }
4923 }
4924 bool Contains(const V* const var) const {
4925 int index;
4926 return Find(var, &index);
4927 }
4928 E* MutableElement(const V* const var) {
4929 E* const element = MutableElementOrNull(var);
4930 DCHECK(element != nullptr)
4931 << "Unknown variable " << var->DebugString() << " in solution";
4932 return element;
4933 }
4934 E* MutableElementOrNull(const V* const var) {
4935 int index = -1;
4936 if (Find(var, &index)) {
4937 return MutableElement(index);
4938 }
4939 return nullptr;
4940 }
4941 const E& Element(const V* const var) const {
4942 const E* const element = ElementPtrOrNull(var);
4943 DCHECK(element != nullptr)
4944 << "Unknown variable " << var->DebugString() << " in solution";
4945 return *element;
4946 }
4947 const E* ElementPtrOrNull(const V* const var) const {
4948 int index = -1;
4949 if (Find(var, &index)) {
4950 return &Element(index);
4951 }
4952 return nullptr;
4953 }
4954 const std::vector<E>& elements() const { return elements_; }
4955 E* MutableElement(int index) { return &elements_[index]; }
4956 const E& Element(int index) const { return elements_[index]; }
4957 int Size() const { return elements_.size(); }
4958 void Store() {
4959 for (E& element : elements_) {
4960 element.Store();
4961 }
4962 }
4963 void Restore() {
4964 for (E& element : elements_) {
4965 if (element.Activated()) {
4966 element.Restore();
4967 }
4968 }
4969 }
4970 bool AreAllElementsBound() const {
4971 for (const E& element : elements_) {
4972 if (!element.Bound()) return false;
4973 }
4974 return true;
4975 }
4976
4980 bool operator==(const AssignmentContainer<V, E>& container) const {
4982 if (Size() != container.Size()) {
4983 return false;
4984 }
4986 EnsureMapIsUpToDate();
4990 for (const E& element : container.elements_) {
4991 const int position =
4992 gtl::FindWithDefault(elements_map_, element.Var(), -1);
4993 if (position < 0 || elements_[position] != element) {
4994 return false;
4995 }
4996 }
4997 return true;
4998 }
4999 bool operator!=(const AssignmentContainer<V, E>& container) const {
5000 return !(*this == container);
5001 }
5002
5003 private:
5004 void EnsureMapIsUpToDate() const {
5005 absl::flat_hash_map<const V*, int>* map =
5006 const_cast<absl::flat_hash_map<const V*, int>*>(&elements_map_);
5007 for (int i = map->size(); i < elements_.size(); ++i) {
5008 (*map)[elements_[i].Var()] = i;
5009 }
5010 }
5011 bool Find(const V* const var, int* index) const {
5013 const size_t kMaxSizeForLinearAccess = 11;
5014 if (Size() <= kMaxSizeForLinearAccess) {
5018 for (int i = 0; i < elements_.size(); ++i) {
5019 if (var == elements_[i].Var()) {
5020 *index = i;
5021 return true;
5022 }
5023 }
5024 return false;
5025 } else {
5026 EnsureMapIsUpToDate();
5027 DCHECK_EQ(elements_map_.size(), elements_.size());
5028 return gtl::FindCopy(elements_map_, var, index);
5029 }
5030 }
5031
5032 std::vector<E> elements_;
5033 absl::flat_hash_map<const V*, int> elements_map_;
5034};
5035
5039 public:
5045
5046 explicit Assignment(Solver* const s);
5047 explicit Assignment(const Assignment* const copy);
5048 ~Assignment() override;
5049
5050 void Clear();
5051 bool Empty() const {
5052 return int_var_container_.Empty() && interval_var_container_.Empty() &&
5053 sequence_var_container_.Empty();
5054 }
5055 int Size() const {
5057 }
5058 int NumIntVars() const { return int_var_container_.Size(); }
5059 int NumIntervalVars() const { return interval_var_container_.Size(); }
5060 int NumSequenceVars() const { return sequence_var_container_.Size(); }
5061 void Store();
5062 void Restore();
5063
5066 bool Load(const std::string& filename);
5067#if !defined(SWIG)
5068 bool Load(File* file);
5069#endif
5070 void Load(const AssignmentProto& assignment_proto);
5072 bool Save(const std::string& filename) const;
5073#if !defined(SWIG)
5074 bool Save(File* file) const;
5075#endif // #if !defined(SWIG)
5076 void Save(AssignmentProto* const assignment_proto) const;
5077
5078 void AddObjective(IntVar* const v);
5079 void ClearObjective() { objective_element_.Reset(nullptr); }
5080 IntVar* Objective() const;
5081 bool HasObjective() const { return (objective_element_.Var() != nullptr); }
5082 int64 ObjectiveMin() const;
5083 int64 ObjectiveMax() const;
5084 int64 ObjectiveValue() const;
5085 bool ObjectiveBound() const;
5086 void SetObjectiveMin(int64 m);
5087 void SetObjectiveMax(int64 m);
5089 void SetObjectiveRange(int64 l, int64 u);
5090
5091 IntVarElement* Add(IntVar* const var);
5092 void Add(const std::vector<IntVar*>& vars);
5095 int64 Min(const IntVar* const var) const;
5096 int64 Max(const IntVar* const var) const;
5097 int64 Value(const IntVar* const var) const;
5098 bool Bound(const IntVar* const var) const;
5099 void SetMin(const IntVar* const var, int64 m);
5100 void SetMax(const IntVar* const var, int64 m);
5101 void SetRange(const IntVar* const var, int64 l, int64 u);
5102 void SetValue(const IntVar* const var, int64 value);
5103
5105 void Add(const std::vector<IntervalVar*>& vars);
5108 int64 StartMin(const IntervalVar* const var) const;
5109 int64 StartMax(const IntervalVar* const var) const;
5110 int64 StartValue(const IntervalVar* const var) const;
5111 int64 DurationMin(const IntervalVar* const var) const;
5112 int64 DurationMax(const IntervalVar* const var) const;
5113 int64 DurationValue(const IntervalVar* const var) const;
5114 int64 EndMin(const IntervalVar* const var) const;
5115 int64 EndMax(const IntervalVar* const var) const;
5116 int64 EndValue(const IntervalVar* const var) const;
5117 int64 PerformedMin(const IntervalVar* const var) const;
5118 int64 PerformedMax(const IntervalVar* const var) const;
5119 int64 PerformedValue(const IntervalVar* const var) const;
5120 void SetStartMin(const IntervalVar* const var, int64 m);
5121 void SetStartMax(const IntervalVar* const var, int64 m);
5122 void SetStartRange(const IntervalVar* const var, int64 mi, int64 ma);
5123 void SetStartValue(const IntervalVar* const var, int64 value);
5124 void SetDurationMin(const IntervalVar* const var, int64 m);
5125 void SetDurationMax(const IntervalVar* const var, int64 m);
5126 void SetDurationRange(const IntervalVar* const var, int64 mi, int64 ma);
5127 void SetDurationValue(const IntervalVar* const var, int64 value);
5128 void SetEndMin(const IntervalVar* const var, int64 m);
5129 void SetEndMax(const IntervalVar* const var, int64 m);
5130 void SetEndRange(const IntervalVar* const var, int64 mi, int64 ma);
5131 void SetEndValue(const IntervalVar* const var, int64 value);
5132 void SetPerformedMin(const IntervalVar* const var, int64 m);
5133 void SetPerformedMax(const IntervalVar* const var, int64 m);
5134 void SetPerformedRange(const IntervalVar* const var, int64 mi, int64 ma);
5135 void SetPerformedValue(const IntervalVar* const var, int64 value);
5136
5138 void Add(const std::vector<SequenceVar*>& vars);
5141 const std::vector<int>& ForwardSequence(const SequenceVar* const var) const;
5142 const std::vector<int>& BackwardSequence(const SequenceVar* const var) const;
5143 const std::vector<int>& Unperformed(const SequenceVar* const var) const;
5144 void SetSequence(const SequenceVar* const var,
5145 const std::vector<int>& forward_sequence,
5146 const std::vector<int>& backward_sequence,
5147 const std::vector<int>& unperformed);
5148 void SetForwardSequence(const SequenceVar* const var,
5149 const std::vector<int>& forward_sequence);
5150 void SetBackwardSequence(const SequenceVar* const var,
5151 const std::vector<int>& backward_sequence);
5152 void SetUnperformed(const SequenceVar* const var,
5153 const std::vector<int>& unperformed);
5154
5155 void Activate(const IntVar* const var);
5156 void Deactivate(const IntVar* const var);
5157 bool Activated(const IntVar* const var) const;
5158
5159 void Activate(const IntervalVar* const var);
5160 void Deactivate(const IntervalVar* const var);
5161 bool Activated(const IntervalVar* const var) const;
5162
5163 void Activate(const SequenceVar* const var);
5164 void Deactivate(const SequenceVar* const var);
5165 bool Activated(const SequenceVar* const var) const;
5166
5167 void ActivateObjective();
5168 void DeactivateObjective();
5169 bool ActivatedObjective() const;
5170
5171 std::string DebugString() const override;
5172
5173 bool AreAllElementsBound() const {
5174 return int_var_container_.AreAllElementsBound() &&
5175 interval_var_container_.AreAllElementsBound() &&
5176 sequence_var_container_.AreAllElementsBound();
5177 }
5178
5179 bool Contains(const IntVar* const var) const;
5180 bool Contains(const IntervalVar* const var) const;
5181 bool Contains(const SequenceVar* const var) const;
5183 void CopyIntersection(const Assignment* assignment);
5186 void Copy(const Assignment* assignment);
5187
5188 // TODO(user): Add element iterators to avoid exposing container class.
5189 const IntContainer& IntVarContainer() const { return int_var_container_; }
5190 IntContainer* MutableIntVarContainer() { return &int_var_container_; }
5192 return interval_var_container_;
5193 }
5195 return &interval_var_container_;
5196 }
5198 return sequence_var_container_;
5199 }
5201 return &sequence_var_container_;
5202 }
5203 bool operator==(const Assignment& assignment) const {
5204 return int_var_container_ == assignment.int_var_container_ &&
5205 interval_var_container_ == assignment.interval_var_container_ &&
5206 sequence_var_container_ == assignment.sequence_var_container_ &&
5207 objective_element_ == assignment.objective_element_;
5208 }
5209 bool operator!=(const Assignment& assignment) const {
5210 return !(*this == assignment);
5211 }
5212
5213 private:
5214 IntContainer int_var_container_;
5215 IntervalContainer interval_var_container_;
5216 SequenceContainer sequence_var_container_;
5217 IntVarElement objective_element_;
5218 DISALLOW_COPY_AND_ASSIGN(Assignment);
5219};
5220
5221std::ostream& operator<<(std::ostream& out,
5222 const Assignment& assignment);
5223
5229void SetAssignmentFromAssignment(Assignment* target_assignment,
5230 const std::vector<IntVar*>& target_vars,
5231 const Assignment* source_assignment,
5232 const std::vector<IntVar*>& source_vars);
5233
5234class Pack : public Constraint {
5235 public:
5236 Pack(Solver* const s, const std::vector<IntVar*>& vars, int number_of_bins);
5237
5238 ~Pack() override;
5239
5244
5249 const std::vector<int64>& weights, const std::vector<int64>& bounds);
5250
5256 Solver::IndexEvaluator1 weights, const std::vector<int64>& bounds);
5257
5263 Solver::IndexEvaluator2 weights, const std::vector<int64>& bounds);
5264
5267 void AddWeightedSumEqualVarDimension(const std::vector<int64>& weights,
5268 const std::vector<IntVar*>& loads);
5269
5274 const std::vector<IntVar*>& loads);
5275
5286 const std::vector<IntVar*>& usage, const std::vector<int64>& capacity);
5287
5290 void AddWeightedSumOfAssignedDimension(const std::vector<int64>& weights,
5291 IntVar* const cost_var);
5292
5295 void AddCountUsedBinDimension(IntVar* const count_var);
5296
5299 void AddCountAssignedItemsDimension(IntVar* const count_var);
5300
5301 void Post() override;
5302 void ClearAll();
5303 void PropagateDelayed();
5304 void InitialPropagate() override;
5305 void Propagate();
5306 void OneDomain(int var_index);
5307 std::string DebugString() const override;
5308 bool IsUndecided(int var_index, int bin_index) const;
5309 void SetImpossible(int var_index, int bin_index);
5310 void Assign(int var_index, int bin_index);
5311 bool IsAssignedStatusKnown(int var_index) const;
5312 bool IsPossible(int var_index, int bin_index) const;
5313 IntVar* AssignVar(int var_index, int bin_index) const;
5314 void SetAssigned(int var_index);
5315 void SetUnassigned(int var_index);
5316 void RemoveAllPossibleFromBin(int bin_index);
5317 void AssignAllPossibleToBin(int bin_index);
5318 void AssignFirstPossibleToBin(int bin_index);
5321 void Accept(ModelVisitor* const visitor) const override;
5322
5323 private:
5324 bool IsInProcess() const;
5325 const std::vector<IntVar*> vars_;
5326 const int bins_;
5327 std::vector<Dimension*> dims_;
5328 std::unique_ptr<RevBitMatrix> unprocessed_;
5329 std::vector<std::vector<int>> forced_;
5330 std::vector<std::vector<int>> removed_;
5331 std::vector<IntVarIterator*> holes_;
5332 uint64 stamp_;
5333 Demon* demon_;
5334 std::vector<std::pair<int, int>> to_set_;
5335 std::vector<std::pair<int, int>> to_unset_;
5336 bool in_process_;
5337};
5338
5340 public:
5342 const std::vector<IntervalVar*>& intervals,
5343 const std::string& name);
5344 ~DisjunctiveConstraint() override;
5345
5348
5353 void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5354
5355 int64 TransitionTime(int before_index, int after_index) {
5357 return transition_time_(before_index, after_index);
5358 }
5359
5360#if !defined(SWIG)
5361 virtual const std::vector<IntVar*>& nexts() const = 0;
5362 virtual const std::vector<IntVar*>& actives() const = 0;
5363 virtual const std::vector<IntVar*>& time_cumuls() const = 0;
5364 virtual const std::vector<IntVar*>& time_slacks() const = 0;
5365#endif // !defined(SWIG)
5366
5367 protected:
5368 const std::vector<IntervalVar*> intervals_;
5370
5371 private:
5372 DISALLOW_COPY_AND_ASSIGN(DisjunctiveConstraint);
5373};
5374
5377class SolutionPool : public BaseObject {
5378 public:
5380 ~SolutionPool() override {}
5381
5384 virtual void Initialize(Assignment* const assignment) = 0;
5385
5388 virtual void RegisterNewSolution(Assignment* const assignment) = 0;
5389
5392 virtual void GetNextSolution(Assignment* const assignment) = 0;
5393
5396 virtual bool SyncNeeded(Assignment* const local_assignment) = 0;
5397};
5398} // namespace operations_research
5399
5400#endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
Definition: base/file.h:32
bool operator==(const AssignmentContainer< V, E > &container) const
Returns true if this and 'container' both represent the same V* -> E map.
const E * ElementPtrOrNull(const V *const var) const
bool Contains(const V *const var) const
const E & Element(const V *const var) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
void Copy(const AssignmentContainer< V, E > &container)
Copies all the elements of 'container' to this container, clearing its previous content.
bool operator!=(const AssignmentContainer< V, E > &container) const
void CopyIntersection(const AssignmentContainer< V, E > &container)
Copies the elements of 'container' which are already in the calling container.
E * FastAdd(V *var)
Adds element without checking its presence in the container.
const std::vector< E > & elements() const
void Resize(size_t size)
Advanced usage: Resizes the container, potentially adding elements with null variables.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const std::vector< int > & Unperformed(const SequenceVar *const var) const
int64 DurationMin(const IntervalVar *const var) const
void SetForwardSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence)
int64 Value(const IntVar *const var) const
void Deactivate(const IntVar *const var)
void SetStartMin(const IntervalVar *const var, int64 m)
SequenceContainer * MutableSequenceVarContainer()
void SetBackwardSequence(const SequenceVar *const var, const std::vector< int > &backward_sequence)
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
void SetDurationValue(const IntervalVar *const var, int64 value)
void SetEndMax(const IntervalVar *const var, int64 m)
int64 EndMax(const IntervalVar *const var) const
const IntervalContainer & IntervalVarContainer() const
int64 StartValue(const IntervalVar *const var) const
AssignmentContainer< SequenceVar, SequenceVarElement > SequenceContainer
void SetStartMax(const IntervalVar *const var, int64 m)
void SetPerformedValue(const IntervalVar *const var, int64 value)
int64 PerformedMin(const IntervalVar *const var) const
bool Load(const std::string &filename)
Loads an assignment from a file; does not add variables to the assignment (only the variables contain...
int64 Min(const IntVar *const var) const
bool Contains(const IntVar *const var) const
bool Activated(const IntVar *const var) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
int64 EndMin(const IntervalVar *const var) const
void SetMax(const IntVar *const var, int64 m)
void SetPerformedRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetEndMin(const IntervalVar *const var, int64 m)
IntervalContainer * MutableIntervalVarContainer()
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
const SequenceContainer & SequenceVarContainer() const
int64 StartMin(const IntervalVar *const var) const
void SetPerformedMin(const IntervalVar *const var, int64 m)
void SetMin(const IntVar *const var, int64 m)
void SetPerformedMax(const IntervalVar *const var, int64 m)
int64 Max(const IntVar *const var) const
void SetEndValue(const IntervalVar *const var, int64 value)
void SetUnperformed(const SequenceVar *const var, const std::vector< int > &unperformed)
int64 DurationMax(const IntervalVar *const var) const
bool operator==(const Assignment &assignment) const
void SetStartValue(const IntervalVar *const var, int64 value)
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
void SetDurationMax(const IntervalVar *const var, int64 m)
AssignmentContainer< IntervalVar, IntervalVarElement > IntervalContainer
void SetStartRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
int64 PerformedMax(const IntervalVar *const var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
void SetSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
int64 DurationValue(const IntervalVar *const var) const
void SetDurationMin(const IntervalVar *const var, int64 m)
int64 StartMax(const IntervalVar *const var) const
int64 EndValue(const IntervalVar *const var) const
int64 PerformedValue(const IntervalVar *const var) const
IntVarElement * Add(IntVar *const var)
void SetEndRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetDurationRange(const IntervalVar *const var, int64 mi, int64 ma)
bool Bound(const IntVar *const var) const
const IntContainer & IntVarContainer() const
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
void SetRange(const IntVar *const var, int64 l, int64 u)
bool operator!=(const Assignment &assignment) const
This is the base class for all expressions that are not variables.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
CastConstraint(Solver *const solver, IntVar *const target_var)
A constraint is the main modeling object.
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
std::string DebugString() const override
virtual void Post()=0
This method is called when the constraint is processed by the solver.
A DecisionBuilder is responsible for creating the search tree.
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
virtual void Accept(ModelVisitor *const visitor) const
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
std::string DebugString() const override
A Decision represents a choice point in the search tree.
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
std::string DebugString() const override
A DecisionVisitor is used to inspect a decision.
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
A Demon is the base element of a propagation queue.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
Demon()
This indicates the priority of a demon.
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
std::string DebugString() const override
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
const std::vector< IntervalVar * > intervals_
virtual const std::vector< IntVar * > & time_slacks() const =0
virtual SequenceVar * MakeSequenceVar()=0
Creates a sequence variable from the constraint.
virtual const std::vector< IntVar * > & actives() const =0
virtual const std::vector< IntVar * > & nexts() const =0
virtual const std::vector< IntVar * > & time_cumuls() const =0
int64 TransitionTime(int before_index, int after_index)
DisjunctiveConstraint(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::string &name)
Definition: resource.cc:2551
void SetTransitionTime(Solver::IndexEvaluator2 transition_time)
Add a transition time between intervals.
Definition: resource.cc:2563
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:4194
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4162
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:4170
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:4218
ImprovementSearchLimit(Solver *const s, IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Definition: search.cc:4144
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:4187
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual void SetMax(int64 m)=0
void WhenRange(Solver::Closure closure)
Attach a demon that will watch the min or the max of the expression.
virtual void SetRange(int64 l, int64 u)
This method sets both the min and the max of the expression.
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMin(int64 m)=0
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual void Range(int64 *l, int64 *u)
By default calls Min() and Max(), but can be redefined when Min and Max code can be factorized.
virtual int64 Max() const =0
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
IntVar * VarWithName(const std::string &name)
Creates a variable from the expression and set the name of the resulting var.
Definition: expressions.cc:49
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
void WhenRange(Solver::Action action)
Attach a demon that will watch the min or the max of the expression.
void Copy(const IntVarElement &element)
bool operator!=(const IntVarElement &element) const
bool operator==(const IntVarElement &element) const
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
The class IntVar is a subset of IntExpr.
virtual IntVar * IsEqual(int64 constant)=0
IsEqual.
virtual int64 OldMax() const =0
Returns the previous max.
void WhenBound(Solver::Closure closure)
This method attaches a closure that will be awakened when the variable is bound.
virtual IntVarIterator * MakeHoleIterator(bool reversible) const =0
Creates a hole iterator.
virtual void RemoveValue(int64 v)=0
This method removes the value 'v' from the domain of the variable.
virtual void SetValues(const std::vector< int64 > &values)
This method intersects the current domain with the values in the array.
IntVar(Solver *const s)
Definition: expressions.cc:57
virtual IntVar * IsLessOrEqual(int64 constant)=0
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
void WhenDomain(Solver::Closure closure)
This method attaches a closure that will watch any domain modification of the domain of the variable.
void WhenDomain(Solver::Action action)
This method attaches an action that will watch any domain modification of the domain of the variable.
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
virtual void RemoveValues(const std::vector< int64 > &values)
This method remove the values from the domain of the variable.
IntVar * Var() override
Creates a variable from the expression.
virtual void WhenDomain(Demon *d)=0
This method attaches a demon that will watch any domain modification of the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
virtual void RemoveInterval(int64 l, int64 u)=0
This method removes the interval 'l' .
int index() const
Returns the index of the variable.
virtual uint64 Size() const =0
This method returns the number of values in the domain of the variable.
void WhenBound(Solver::Action action)
This method attaches an action that will be awakened when the variable is bound.
virtual IntVar * IsGreaterOrEqual(int64 constant)=0
bool IsVar() const override
Returns true if the expression is indeed a variable.
virtual IntVar * IsDifferent(int64 constant)=0
virtual IntVarIterator * MakeDomainIterator(bool reversible) const =0
Creates a domain iterator.
virtual int VarType() const
virtual int64 OldMin() const =0
Returns the previous min.
The class Iterator has two direct subclasses.
virtual void Init()=0
This method must be called before each loop.
virtual void Next()=0
This method moves the iterator to the next value.
virtual int64 Value() const =0
This method returns the current value of the iterator.
std::string DebugString() const override
Pretty Print.
virtual bool Ok() const =0
This method indicates if we can call Value() or not.
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
bool operator!=(const IntervalVarElement &element) const
bool operator==(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
Interval variables are often used in scheduling.
virtual int64 OldStartMin() const =0
virtual int64 StartMax() const =0
virtual IntExpr * SafeStartExpr(int64 unperformed_value)=0
These methods create expressions encapsulating the start, end and duration of the interval var.
void WhenDurationRange(Solver::Closure closure)
virtual IntExpr * DurationExpr()=0
virtual IntExpr * PerformedExpr()=0
void WhenAnything(Solver::Closure closure)
Attaches a closure awakened when anything about this interval changes.
virtual int64 OldEndMin() const =0
static const int64 kMaxValidValue
The largest acceptable value to be returned by EndMax()
void WhenStartBound(Solver::Closure closure)
virtual void WhenStartBound(Demon *const d)=0
void WhenEndRange(Solver::Closure closure)
void WhenAnything(Demon *const d)
Attaches a demon awakened when anything about this interval changes.
Definition: interval.cc:2227
virtual int64 DurationMax() const =0
virtual void SetPerformed(bool val)=0
virtual int64 EndMax() const =0
void WhenEndBound(Solver::Action action)
virtual void SetEndMax(int64 m)=0
virtual void WhenEndRange(Demon *const d)=0
virtual void SetStartMin(int64 m)=0
virtual void SetDurationMin(int64 m)=0
virtual void WhenDurationBound(Demon *const d)=0
virtual int64 OldDurationMin() const =0
virtual void SetEndMin(int64 m)=0
virtual bool WasPerformedBound() const =0
void WhenStartRange(Solver::Action action)
virtual void SetEndRange(int64 mi, int64 ma)=0
virtual void WhenDurationRange(Demon *const d)=0
static const int64 kMinValidValue
The smallest acceptable value to be returned by StartMin()
virtual IntExpr * SafeDurationExpr(int64 unperformed_value)=0
virtual void WhenEndBound(Demon *const d)=0
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
void WhenDurationBound(Solver::Action action)
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
IntervalVar(Solver *const solver, const std::string &name)
virtual void WhenPerformedBound(Demon *const d)=0
virtual void SetStartMax(int64 m)=0
virtual IntExpr * SafeEndExpr(int64 unperformed_value)=0
virtual int64 OldEndMax() const =0
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
void WhenStartBound(Solver::Action action)
virtual void SetStartRange(int64 mi, int64 ma)=0
void WhenAnything(Solver::Action action)
Attaches an action awakened when anything about this interval changes.
virtual int64 OldDurationMax() const =0
void WhenEndRange(Solver::Action action)
void WhenStartRange(Solver::Closure closure)
virtual IntExpr * EndExpr()=0
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual void WhenStartRange(Demon *const d)=0
virtual IntExpr * StartExpr()=0
These methods create expressions encapsulating the start, end and duration of the interval var.
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
virtual void SetDurationRange(int64 mi, int64 ma)=0
virtual void SetDurationMax(int64 m)=0
void WhenPerformedBound(Solver::Action action)
void WhenPerformedBound(Solver::Closure closure)
virtual int64 OldStartMax() const =0
void WhenEndBound(Solver::Closure closure)
virtual bool MayBePerformed() const =0
void WhenDurationRange(Solver::Action action)
void WhenDurationBound(Solver::Closure closure)
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
The base class for all local search operators.
Implements a complete cache for model elements: expressions and constraints.
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
static const char kSolutionLimitArgument[]
static const char kCountUsedBinsExtension[]
static const char kMirrorOperation[]
Operations.
static const char kAbs[]
Constraint and Expression types.
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kVariableUsageLessConstantExtension[]
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kActiveArgument[]
argument names:
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
static const char kBranchesLimitArgument[]
static const char kIntervalUnaryRelation[]
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kSmartTimeCheckArgument[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
virtual void BeginVisitExtension(const std::string &type)
static const char kStartSyncOnStartOperation[]
static const char kUsageLessConstantExtension[]
virtual void EndVisitExtension(const std::string &type)
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
static const char kUsageEqualVariableExtension[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
virtual void EndVisitModel(const std::string &type_name)
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kVariableGroupExtension[]
static const char kFailuresLimitArgument[]
static const char kScalProdGreaterOrEqual[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
static const char kIntervalBinaryRelation[]
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min, int64 index_max)
Using SWIG on callbacks is troublesome, so we hide these methods during the wrapping.
static const char kInt64ToInt64Extension[]
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
static const char kStartSyncOnEndOperation[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kCountAssignedItemsExtension[]
Extension names:
Subclass of RevArray<T> which adds numerical operations.
void Decr(Solver *const s, int index)
void Add(Solver *const s, int index, const T &to_add)
void Incr(Solver *const s, int index)
Subclass of Rev<T> which adds numerical operations.
void Add(Solver *const s, const T &to_add)
This class encapsulates an objective.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2738
int64 best() const
Returns the best value found during search.
void BeginNextDecision(DecisionBuilder *const db) override
Before calling DecisionBuilder::Next.
Definition: search.cc:2747
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:2840
bool AcceptSolution() override
This method is called when a solution is found.
Definition: search.cc:2765
virtual std::string Print() const
Definition: search.cc:2824
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:2777
void RefuteDecision(Decision *const d) override
Before refuting the decision.
Definition: search.cc:2763
IntVar * Var() const
Returns the variable that is optimized.
OptimizeVar(Solver *const s, bool maximize, IntVar *const a, int64 step)
Definition: search.cc:2717
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Internal methods.
Definition: search.cc:2790
std::string DebugString() const override
Definition: search.cc:2828
void AddWeightedSumOfAssignedDimension(const std::vector< int64 > &weights, IntVar *const cost_var)
This dimension enforces that cost_var == sum of weights[i] for all objects 'i' assigned to a bin.
Definition: pack.cc:1578
bool IsAssignedStatusKnown(int var_index) const
Definition: pack.cc:423
void Post() override
This method is called when the constraint is processed by the solver.
Definition: pack.cc:126
void AddCountAssignedItemsDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of items assigned to a bin in the pack.
Definition: pack.cc:1604
void InitialPropagate() override
This method performs the initial propagation of the constraint.
Definition: pack.cc:189
Pack(Solver *const s, const std::vector< IntVar * > &vars, int number_of_bins)
Definition: pack.cc:107
void SetImpossible(int var_index, int bin_index)
Definition: pack.cc:407
void SetAssigned(int var_index)
Definition: pack.cc:435
void AddWeightedSumEqualVarDimension(const std::vector< int64 > &weights, const std::vector< IntVar * > &loads)
This dimension imposes that for all bins b, the weighted sum (weights[i]) of all objects i assigned t...
Definition: pack.cc:1558
bool IsUndecided(int var_index, int bin_index) const
Definition: pack.cc:403
bool IsPossible(int var_index, int bin_index) const
Definition: pack.cc:427
void AssignFirstPossibleToBin(int bin_index)
Definition: pack.cc:475
void AddCountUsedBinDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of bins used in the pack.
Definition: pack.cc:1597
void OneDomain(int var_index)
Definition: pack.cc:333
void SetUnassigned(int var_index)
Definition: pack.cc:443
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64 > &capacity)
This dimension imposes: forall b in bins, sum (i in items: usage[i] * is_assigned(i,...
Definition: pack.cc:1587
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
Definition: pack.cc:392
void AssignAllPossibleToBin(int bin_index)
Definition: pack.cc:465
void Assign(int var_index, int bin_index)
Definition: pack.cc:415
void UnassignAllRemainingItems()
Definition: pack.cc:492
std::string DebugString() const override
Definition: pack.cc:379
void AssignAllRemainingItems()
Definition: pack.cc:482
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64 > &weights, const std::vector< int64 > &bounds)
Dimensions are additional constraints than can restrict what is possible with the pack constraint.
Definition: pack.cc:1528
IntVar * AssignVar(int var_index, int bin_index) const
Definition: pack.cc:431
void RemoveAllPossibleFromBin(int bin_index)
Definition: pack.cc:455
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
virtual std::string name() const
Object naming.
void reset_action_on_fail()
This method clears the failure callback.
bool HasName() const
Returns whether the object has been named or not.
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
void FreezeQueue()
This method freezes the propagation queue.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
virtual std::string BaseName() const
Returns a base name for automatic naming.
void set_variable_to_clean_on_fail(IntVar *v)
Shortcut for variable cleaner.
void UnfreezeQueue()
This method unfreezes the propagation queue.
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:3988
absl::Duration duration_limit() const
bool IsUncheckedSolutionLimitReached() override
Returns true if the limit of solutions has been reached including unchecked solutions.
Definition: search.cc:4039
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
void ExitSearch() override
End of the search.
Definition: search.cc:4020
RegularLimit(Solver *const s, absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check, bool cumulative)
Definition: search.cc:3949
int ProgressPercent() override
Returns a percentage representing the propress of the search before reaching limits.
Definition: search.cc:3996
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:4053
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
Definition: search.cc:4031
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
std::string DebugString() const override
Definition: search.cc:4045
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:3980
Reversible array of POD types.
const T & operator[](int index) const
const T & Value(int index) const
RevArray(int size, const T &val)
void SetValue(Solver *const s, int index, const T &val)
This class adds reversibility to a POD type.
void SetValue(Solver *const s, const T &val)
Reversible Immutable MultiMap class.
Base class of all search limits.
void EnterSearch() override
Internal methods.
Definition: search.cc:3919
virtual SearchLimit * MakeClone() const =0
Allocates a clone of the limit.
void PeriodicCheck() override
Periodic call to check limits in long running methods.
Definition: search.cc:3934
virtual void Init()=0
This method is called when the search limit is initialized.
void BeginNextDecision(DecisionBuilder *const b) override
Before calling DecisionBuilder::Next.
Definition: search.cc:3924
virtual void Copy(const SearchLimit *const limit)=0
Copy a limit.
void RefuteDecision(Decision *const d) override
Before refuting the decision.
Definition: search.cc:3929
bool crossed() const
Returns true if the limit has been crossed.
std::string DebugString() const override
virtual bool Check()=0
This method is called to check the status of the limit.
A search monitor is a simple set of callbacks to monitor all search events.
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
virtual void RestartSearch()
Restart the search.
virtual void ExitSearch()
End of the search.
virtual bool IsUncheckedSolutionLimitReached()
Returns true if the limit of solutions has been reached including unchecked solutions.
virtual bool LocalOptimum()
When a local optimum is reached.
virtual int ProgressPercent()
Returns a percentage representing the propress of the search before reaching limits.
virtual void NoMoreSolutions()
When the search tree is finished.
virtual void BeginFail()
Just when the failure occurs.
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
virtual void BeginInitialPropagation()
Before the initial propagation.
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
virtual void EnterSearch()
Beginning of the search.
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
virtual void EndFail()
After completing the backtrack.
virtual void EndInitialPropagation()
After the initial propagation.
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual bool AtSolution()
This method is called when a valid solution is found.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
virtual bool AcceptSolution()
This method is called when a solution is found.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
bool operator==(const SequenceVarElement &element) const
const std::vector< int > & BackwardSequence() const
bool operator!=(const SequenceVarElement &element) const
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & Unperformed() const
void SetUnperformed(const std::vector< int > &unperformed)
const std::vector< int > & ForwardSequence() const
void Copy(const SequenceVarElement &element)
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
void SetForwardSequence(const std::vector< int > &forward_sequence)
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
void ComputePossibleFirstsAndLasts(std::vector< int > *const possible_firsts, std::vector< int > *const possible_lasts)
Computes the set of indices of interval variables that can be ranked first in the set of unranked act...
void FillSequence(std::vector< int > *const rank_first, std::vector< int > *const rank_last, std::vector< int > *const unperformed) const
Clears 'rank_first' and 'rank_last', and fills them with the intervals in the order of the ranks.
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
Applies the following sequence of ranks, ranks first, then rank last.
void ComputeStatistics(int *const ranked, int *const not_ranked, int *const unperformed) const
Compute statistics on the sequence.
void ActiveHorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all unranked interval vars in the sequence.
void HorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all interval vars in the sequence.
Definition: sched_search.cc:91
int64 size() const
Returns the number of interval vars in the sequence.
IntVar * Next(int index) const
Returns the next of the index_th interval of the sequence.
Definition: sched_search.cc:54
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
Definition: sched_search.cc:50
void RankLast(int index)
Ranks the index_th interval var first of all unranked interval vars.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: sched_search.cc:71
void DurationRange(int64 *const dmin, int64 *const dmax) const
Returns the minimum and maximum duration of combined interval vars in the sequence.
Definition: sched_search.cc:75
void RankFirst(int index)
Ranks the index_th interval var first of all unranked interval vars.
void RankNotLast(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
void RankNotFirst(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
SequenceVar(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)
Definition: sched_search.cc:37
std::string DebugString() const override
Definition: sched_search.cc:56
This class represent a reversible FIFO structure.
This class is the root class of all solution collectors.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2263
int64 Value(int n, IntVar *const var) const
This is a shortcut to get the Value of 'var' in the nth solution.
Definition: search.cc:2347
int64 failures(int n) const
Returns the number of failures encountered at the time of the nth solution.
Definition: search.cc:2337
void Push(const SolutionData &data)
void PushSolution()
Push the current state as a new solution.
Definition: search.cc:2272
void AddObjective(IntVar *const objective)
Definition: search.cc:2257
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
void Add(IntVar *const var)
Add API.
Definition: search.cc:2221
int solution_count() const
Returns how many solutions were stored during the search.
Definition: search.cc:2325
int64 DurationValue(int n, IntervalVar *const var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
Definition: search.cc:2355
int64 PerformedValue(int n, IntervalVar *const var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
Definition: search.cc:2363
const std::vector< int > & Unperformed(int n, SequenceVar *const var) const
This is a shortcut to get the list of unperformed of 'var' in the nth solution.
Definition: search.cc:2377
SolutionData BuildSolutionDataForCurrentState()
Definition: search.cc:2284
Assignment * solution(int n) const
Returns the nth solution.
Definition: search.cc:2320
int64 wall_time(int n) const
Returns the wall time in ms for the nth solution.
Definition: search.cc:2327
int64 EndValue(int n, IntervalVar *const var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
Definition: search.cc:2359
const std::vector< int > & ForwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the ForwardSequence of 'var' in the nth solution.
Definition: search.cc:2367
int64 objective_value(int n) const
Returns the objective value of the nth solution.
Definition: search.cc:2342
void FreeSolution(Assignment *solution)
Definition: search.cc:2309
std::unique_ptr< Assignment > prototype_
SolutionCollector(Solver *const solver, const Assignment *assignment)
Definition: search.cc:2205
int64 branches(int n) const
Returns the number of branches when the nth solution was found.
Definition: search.cc:2332
void PopSolution()
Remove and delete the last popped solution.
Definition: search.cc:2276
std::string DebugString() const override
const std::vector< int > & BackwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the BackwardSequence of 'var' in the nth solution.
Definition: search.cc:2372
int64 StartValue(int n, IntervalVar *const var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
Definition: search.cc:2351
This class is used to manage a pool of solutions.
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
SolverState state() const
State of the solver.
Decision * MakeDecision(Action apply, Action refute)
Definition: search.cc:610
std::function< bool(int64)> IndexFilter1
IntExpr * MakeElement(const std::vector< int64 > &values, IntVar *const index)
values[index]
Definition: element.cc:647
SearchMonitor * MakeLubyRestart(int scale_factor)
This search monitor will restart the search periodically.
Definition: search.cc:4643
Constraint * MakeMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr in set.
Definition: expr_cst.cc:1160
void SaveValue(T *o)
reversibility
SolutionCollector * MakeAllSolutionCollector()
Collect all solutions of the search.
Definition: search.cc:2711
DecisionModification
The Solver is responsible for creating the search tree.
@ NO_CHANGE
Keeps the default behavior, i.e.
@ SWITCH_BRANCHES
Applies right branch first.
@ KEEP_RIGHT
Left branches are ignored.
@ KEEP_LEFT
Right branches are ignored.
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
bool IsBooleanVar(IntExpr *const expr, IntVar **inner_var, bool *is_negated) const
Returns true if expr represents either boolean_var or 1 - boolean_var.
RegularLimit * MakeLimit(absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check=false, bool cumulative=false)
Limits the search with the 'time', 'branches', 'failures' and 'solutions' limits.
Definition: search.cc:4117
void MakeBoolVarArray(int var_count, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' boolean variables having name "name<i>" wher...
LocalSearchFilter * MakeVariableDomainFilter()
Decision * MakeSplitVariableDomain(IntVar *const var, int64 val, bool start_with_lower_half)
Definition: search.cc:1679
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
Constraint * MakeDeviation(const std::vector< IntVar * > &vars, IntVar *const deviation_var, int64 total_sum)
Deviation constraint: sum_i |n * vars[i] - total_sum| <= deviation_var and sum_i vars[i] == total_sum...
Definition: deviation.cc:411
std::vector< int64 > tmp_vector_
Unsafe temporary vector.
void ClearLocalSearchState()
Clears the local search state.
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a maximization weigthed objective.
Definition: search.cc:2910
SolutionCollector * MakeLastSolutionCollector()
Collect the last solution of the search.
Definition: search.cc:2481
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Definition: search.cc:4105
Decision * MakeAssignVariableValue(IntVar *const var, int64 val)
Decisions.
Definition: search.cc:1558
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
Definition: search.cc:418
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
Definition: trace.cc:844
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var >= value)
Definition: expr_cst.cc:677
SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Callback-based search limit.
Definition: search.cc:4370
Constraint * MakeNullIntersectExcept(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars, int64 escape_value)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:738
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
Constraint * MakeLess(IntExpr *const left, IntExpr *const right)
left < right
Definition: range_cst.cc:546
Constraint * MakeIntervalVarRelation(IntervalVar *const t, UnaryIntervalRelation r, int64 d)
This method creates a relation between an interval var and a date.
Definition: timetabling.cc:113
friend void InternalSaveBooleanVarValue(Solver *const, IntVar *const)
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
Constraint * MakeSubCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path for those that do not loop upon them...
IntExpr * MakeAbs(IntExpr *const expr)
|expr|
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Definition: range_cst.cc:512
Constraint * MakeIsDifferentCt(IntExpr *const v1, IntExpr *const v2, IntVar *const b)
b == (v1 != v2)
Definition: range_cst.cc:686
Constraint * MakeLessOrEqual(IntExpr *const left, IntExpr *const right)
left <= right
Definition: range_cst.cc:526
IntExpr * MakePiecewiseLinearExpr(IntExpr *expr, const PiecewiseLinearFunction &f)
General piecewise-linear function expression, built from f(x) where f is piecewise-linear.
int64 solutions() const
The number of solutions found since the start of the search.
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
Constraint * MakeNullIntersect(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:733
DisjunctiveConstraint * MakeStrictDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
Definition: resource.cc:2579
IntVar * MakeIsGreaterVar(IntExpr *const left, IntExpr *const right)
status var of (left > right)
Definition: range_cst.cc:796
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
IntExpr * MakeMin(const std::vector< IntVar * > &vars)
std::min(vars)
Definition: expr_array.cc:3278
Constraint * MakeIsLessCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v < c)
Definition: expr_cst.cc:813
static constexpr int kNumPriorities
Number of priorities for demons.
Decision * MakeAssignVariableValueOrFail(IntVar *const var, int64 value)
Definition: search.cc:1596
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
OptimizeVar * MakeMaximize(IntVar *const v, int64 step)
Creates a maximization objective.
Definition: search.cc:2853
ConstraintSolverParameters parameters() const
Stored Parameters.
int64 failures() const
The number of failures encountered since the creation of the solver.
Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the minimu...
Definition: constraints.cc:560
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
Definition: search.cc:4815
SolverState
This enum represents the state of the solver w.r.t. the search.
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
@ OUTSIDE_SEARCH
Before search, after search.
@ IN_ROOT_NODE
Executing the root node.
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
@ IN_SEARCH
Executing the search code.
int64 demon_runs(DemonPriority p) const
The number of demons executed during search for a given priority.
Constraint * MakeAbsEquality(IntVar *const var, IntVar *const abs_var)
Creates the constraint abs(var) == abs_var.
std::function< bool(int64, int64, int64)> VariableValueComparator
std::string SearchContext() const
DemonProfiler * demon_profiler() const
Access to demon profiler.
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
IntVar * RegisterIntVar(IntVar *const var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
Definition: trace.cc:856
SearchMonitor * MakeGenericTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &tabu_vars, int64 forbid_tenure)
Creates a Tabu Search based on the vars |vars|.
Definition: search.cc:3249
SearchMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *const v, int64 step, int64 initial_temperature)
Creates a Simulated Annealing monitor.
Definition: search.cc:3352
absl::Time Now() const
The 'absolute time' as seen by the solver.
IntVar * MakeIsDifferentVar(IntExpr *const v1, IntExpr *const v2)
status var of (v1 != v2)
Definition: range_cst.cc:641
IntVar * MakeIsEqualVar(IntExpr *const v1, IntExpr *v2)
status var of (v1 == v2)
Definition: range_cst.cc:577
Constraint * MakeNotBetweenCt(IntExpr *const expr, int64 l, int64 u)
(expr < l || expr > u) This constraint is lazy as it will not make holes in the domain of variables.
Definition: expr_cst.cc:953
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
Constraint * MakeCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path.
OptimizationDirection
Optimization directions.
IntervalStrategy
This enum describes the straregy used to select the next interval variable and its value to be fixed.
@ INTERVAL_SET_TIMES_FORWARD
Selects the variable with the lowest starting time of all variables, and fixes its starting time to t...
@ INTERVAL_SIMPLE
The simple is INTERVAL_SET_TIMES_FORWARD.
@ INTERVAL_SET_TIMES_BACKWARD
Selects the variable with the highest ending time of all variables, and fixes the ending time to this...
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
Constraint * MakeGreater(IntExpr *const left, IntExpr *const right)
left > right
Definition: range_cst.cc:560
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
This constraint packs all variables onto 'number_of_bins' variables.
Definition: pack.cc:1611
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64 initial_state, const std::vector< int64 > &final_states)
This constraint create a finite automaton that will check the sequence of variables vars.
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
Demon * MakeActionDemon(Action action)
Creates a demon from a callback.
Definition: constraints.cc:507
DecisionBuilder * Try(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which will create a search tree where each decision builder is called from...
Definition: search.cc:700
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than right.
Definition: constraints.cc:540
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
Constraint * MakeBetweenCt(IntExpr *const expr, int64 l, int64 u)
(l <= expr <= u)
Definition: expr_cst.cc:920
Constraint * MakeIsEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var == value)
Definition: expr_cst.cc:485
RegularLimit * MakeFailuresLimit(int64 failures)
Creates a search limit that constrains the number of failures that can happen when exploring the sear...
Definition: search.cc:4100
RegularLimit * MakeTimeLimit(int64 time_in_ms)
SearchMonitor * MakeSearchLog(int branch_period)
The SearchMonitors below will display a periodic search log on LOG(INFO) every branch_period branches...
Definition: search.cc:284
IntValueStrategy
This enum describes the strategy used to select the next variable value to set.
@ INT_VALUE_SIMPLE
The simple selection is ASSIGN_MIN_VALUE.
@ ASSIGN_CENTER_VALUE
Selects the first possible value which is the closest to the center of the domain of the selected var...
@ SPLIT_UPPER_HALF
Split the domain in two around the center, and choose the lower part first.
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
@ ASSIGN_RANDOM_VALUE
Selects randomly one of the possible values of the selected variable.
@ INT_VALUE_DEFAULT
The default behavior is ASSIGN_MIN_VALUE.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
@ SPLIT_LOWER_HALF
Split the domain in two around the center, and choose the lower part first.
IntExpr * MakePower(IntExpr *const expr, int64 n)
expr ^ n (n > 0)
UnaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between an inte...
@ ENDS_BEFORE
t ends before d, i.e. End(t) <= d.
@ AVOID_DATE
STARTS_AFTER or ENDS_BEFORE, i.e.
@ ENDS_AFTER
t ends after d, i.e. End(t) >= d.
@ STARTS_BEFORE
t starts before d, i.e. Start(t) <= d.
@ STARTS_AT
t starts at d, i.e. Start(t) == d.
@ ENDS_AT
t ends at d, i.e. End(t) == d.
@ STARTS_AFTER
t starts after d, i.e. Start(t) >= d.
@ CROSS_DATE
STARTS_BEFORE and ENDS_AFTER at the same time, i.e.
Constraint * MakeDelayedPathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Delayed version of the same constraint: propagation on the nexts variables is delayed until all const...
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
IntVar * MakeIsDifferentCstVar(IntExpr *const var, int64 value)
status var of (var != value)
Definition: expr_cst.cc:578
Constraint * MakeCover(const std::vector< IntervalVar * > &vars, IntervalVar *const target_var)
This constraint states that the target_var is the convex hull of the intervals.
void SetSearchContext(Search *search, const std::string &search_context)
Constraint * MakeIsGreaterCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v > c)
Definition: expr_cst.cc:714
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64 > &values)
Definition: search.cc:1752
Constraint * MakeCumulative(const std::vector< IntervalVar * > &intervals, const std::vector< int64 > &demands, int64 capacity, const std::string &name)
This constraint forces that, for any integer t, the sum of the demands corresponding to an interval c...
Definition: resource.cc:2586
Constraint * MakeNonOverlappingBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64 escape_value)
All variables are pairwise different, unless they are assigned to the escape value.
Definition: alldiff_cst.cc:720
int64 Rand64(int64 size)
Returns a random value between 0 and 'size' - 1;.
Constraint * MakePathTransitPrecedenceConstraint(std::vector< IntVar * > nexts, std::vector< IntVar * > transits, const std::vector< std::pair< int, int > > &precedences)
Same as MakePathPrecedenceConstraint but will force i to be before j if the sum of transits on the pa...
void SetUseFastLocalSearch(bool use_fast_local_search)
enabled for metaheuristics.
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64 value)
Definition: search.cc:1625
IntervalVar * MakeIntervalRelaxedMin(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the min start and ...
Definition: interval.cc:2218
IntervalVar * MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the end of another inter...
Definition: interval.cc:2417
Constraint * MakePathConnected(std::vector< IntVar * > nexts, std::vector< int64 > sources, std::vector< int64 > sinks, std::vector< IntVar * > status)
Constraint enforcing that status[i] is true iff there's a path defined on next variables from sources...
Demon * MakeClosureDemon(Closure closure)
!defined(SWIG)
Definition: constraints.cc:511
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
DecisionBuilder * MakeSolveOnce(DecisionBuilder *const db)
SolveOnce will collapse a search tree described by a decision builder 'db' and a set of monitors and ...
Definition: search.cc:4413
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
IntervalVar * MakeFixedInterval(int64 start, int64 duration, const std::string &name)
Creates a fixed and performed interval.
Definition: interval.cc:2234
LocalSearchFilter * MakeRejectFilter()
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Creates a large neighborhood search operator which creates fragments (set of relaxed variables) with ...
Constraint * MakeIsLessCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left < right)
Definition: range_cst.cc:773
Decision * MakeVariableLessOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1684
DisjunctiveConstraint * MakeDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
Definition: resource.cc:2574
void ShouldFail()
These methods are only useful for the SWIG wrappers, which need a way to externally cause the Solver ...
int SearchDepth() const
Gets the search depth of the current active search.
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
IntVar * MakeIsMemberVar(IntExpr *const expr, const std::vector< int64 > &values)
Definition: expr_cst.cc:1490
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Definition: expr_cst.cc:460
Constraint * MakeScalProdLessOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
Definition: expr_array.cc:3526
Constraint * MakeNotMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr not in set.
Definition: expr_cst.cc:1229
BinaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between the two...
@ ENDS_AFTER_END
t1 ends after t2 end, i.e. End(t1) >= End(t2) + delay.
@ ENDS_AFTER_START
t1 ends after t2 start, i.e. End(t1) >= Start(t2) + delay.
@ STAYS_IN_SYNC
STARTS_AT_START and ENDS_AT_END at the same time.
@ ENDS_AT_END
t1 ends at t2 end, i.e. End(t1) == End(t2) + delay.
@ STARTS_AT_END
t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
@ ENDS_AT_START
t1 ends at t2 start, i.e. End(t1) == Start(t2) + delay.
@ STARTS_AFTER_END
t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
@ STARTS_AFTER_START
t1 starts after t2 start, i.e. Start(t1) >= Start(t2) + delay.
@ STARTS_AT_START
t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
Constraint * MakeMaxEquality(const std::vector< IntVar * > &vars, IntVar *const max_var)
Definition: expr_array.cc:3386
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
@ EXCHANGE
Operator which exchanges the positions of two nodes.
@ MAKEINACTIVE
Operator which makes path nodes inactive.
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
@ SIMPLELNS
Operator which defines one neighbor per variable.
@ INCREMENT
Operator which defines one neighbor per variable.
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
@ TWOOPT
Operator which reverses a sub-chain of a path.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
@ DECREMENT
Operator which defines a neighborhood to decrement values.
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
Constraint * MakeIsEqualCt(IntExpr *const v1, IntExpr *v2, IntVar *const b)
b == (v1 == v2)
Definition: range_cst.cc:622
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
IntExpr * MakeOpposite(IntExpr *const expr)
-expr
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
OptimizeVar * MakeWeightedOptimize(bool maximize, const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a weighted objective with a given sense (true = maximization).
Definition: search.cc:2896
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Constraint * MakeIfThenElseCt(IntVar *const condition, IntExpr *const then_expr, IntExpr *const else_expr, IntVar *const target_var)
Special cases with arrays of size two.
Definition: element.cc:1597
Decision * MakeScheduleOrExpedite(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
Demon * MakeConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:33
std::string DebugString() const
!defined(SWIG)
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Definition: constraints.cc:515
IntervalVar * MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the start of another int...
Definition: interval.cc:2410
Demon * RegisterDemon(Demon *const demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
IntExpr * MakeModulo(IntExpr *const x, int64 mod)
Modulo expression x % mod (with the python convention for modulo).
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
IntExpr * MakeConditionalExpression(IntVar *const condition, IntExpr *const expr, int64 unperformed_value)
Conditional Expr condition ? expr : unperformed_value.
Constraint * MakeIsBetweenCt(IntExpr *const expr, int64 l, int64 u, IntVar *const b)
b == (l <= expr <= u)
Definition: expr_cst.cc:1048
IntervalVar * MakeIntervalRelaxedMax(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the max start and ...
Definition: interval.cc:2209
int64 wall_time() const
DEPRECATED: Use Now() instead.
Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, const std::vector< IntVar * > &cards)
Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].
Definition: count_cst.cc:964
RegularLimit * MakeBranchesLimit(int64 branches)
Creates a search limit that constrains the number of branches explored in the search tree.
Definition: search.cc:4095
ImprovementSearchLimit * MakeImprovementLimit(IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Limits the search based on the improvements of 'objective_var'.
Definition: search.cc:4259
Constraint * MakeAtMost(std::vector< IntVar * > vars, int64 value, int64 max_count)
|{i | vars[i] == value}| <= max_count
Definition: count_cst.cc:955
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *const map)
Compute the number of constraints a variable is attached to.
Definition: utilities.cc:815
int64 accepted_neighbors() const
The number of accepted neighbors.
SearchMonitor * MakeConstantRestart(int frequency)
This search monitor will restart the search periodically after 'frequency' failures.
Definition: search.cc:4676
std::function< int64(int64, int64, int64)> IndexEvaluator3
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
int constraints() const
Counts the number of constraints that have been added to the solver before the search.
Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64 cst)
Definition: expr_array.cc:3428
Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than or equal to right.
Definition: constraints.cc:545
void MakeFixedDurationIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval variables built with the corresponding parameters.
Definition: interval.cc:2253
EvaluatorStrategy
This enum is used by Solver::MakePhase to specify how to select variables and values during the searc...
@ CHOOSE_STATIC_GLOBAL_BEST
Pairs are compared at the first call of the selector, and results are cached.
@ CHOOSE_DYNAMIC_GLOBAL_BEST
Pairs are compared each time a variable is selected.
void set_optimization_direction(OptimizationDirection direction)
int SolveDepth() const
Gets the number of nested searches.
int64 neighbors() const
The number of neighbors created.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Decision * MakeRankFirstInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank first the ith interval var in the sequence variable.
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
Definition: expr_array.cc:3321
Constraint * MakeIsLessOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left <= right)
Definition: range_cst.cc:730
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
Constraint * MakeIntervalVarRelationWithDelay(IntervalVar *const t1, BinaryIntervalRelation r, IntervalVar *const t2, int64 delay)
This method creates a relation between two interval vars.
Definition: timetabling.cc:238
Constraint * MakeScalProdGreaterOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coeffs, int64 cst)
Definition: expr_array.cc:3512
IntExpr * MakeDifference(IntExpr *const left, IntExpr *const right)
left - right
std::string model_name() const
Returns the name of the model.
void MakeIntVarArray(int var_count, int64 vmin, int64 vmax, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' variables having bounds vmin and vmax and ha...
RegularLimitParameters MakeDefaultRegularLimitParameters() const
Creates a regular limit proto containing default values.
Definition: search.cc:4131
RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Definition: search.cc:4090
Decision * MakeVariableGreaterOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1688
IntVar * MakeBoolVar()
MakeBoolVar will create a variable with a {0, 1} domain.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Decision * MakeScheduleOrPostpone(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
Definition: search.cc:394
IntExpr * MakeDiv(IntExpr *const expr, int64 value)
expr / value (integer division)
SearchMonitor * MakeGuidedLocalSearch(bool maximize, IntVar *const objective, IndexEvaluator2 objective_function, int64 step, const std::vector< IntVar * > &vars, double penalty_factor)
Creates a Guided Local Search monitor.
Definition: search.cc:3894
int64 filtered_neighbors() const
The number of filtered neighbors (neighbors accepted by filters).
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
Constraint * MakeNonEquality(IntExpr *const left, IntExpr *const right)
left != right
Definition: range_cst.cc:564
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
IntVar * MakeIsLessVar(IntExpr *const left, IntExpr *const right)
status var of (left < right)
Definition: range_cst.cc:742
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
int SearchLeftDepth() const
Gets the search left depth of the current active search.
void AddBacktrackAction(Action a, bool fast)
When SaveValue() is not the best way to go, one can create a reversible action that will be called up...
Constraint * MakeTemporalDisjunction(IntervalVar *const t1, IntervalVar *const t2, IntVar *const alt)
This constraint implements a temporal disjunction between two interval vars t1 and t2.
Definition: timetabling.cc:403
void MakeIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval var built with the corresponding parameters.
Definition: interval.cc:2379
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
IntVar * MakeIsBetweenVar(IntExpr *const v, int64 l, int64 u)
Definition: expr_cst.cc:1084
void ReSeed(int32 seed)
Reseed the solver random generator.
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
Decision * balancing_decision() const
IntervalVar * MakeFixedDurationIntervalVar(int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name)
Creates an interval var with a fixed duration.
Definition: interval.cc:2239
Constraint * MakeIsMemberCt(IntExpr *const expr, const std::vector< int64 > &values, IntVar *const boolvar)
boolvar == (expr in set)
Definition: expr_cst.cc:1478
IntVarStrategy
This enum describes the strategy used to select the next branching variable at each node during the s...
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ CHOOSE_MIN_SIZE
Among unbound variables, select the variable with the smallest size.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_PATH
Selects the next unbound variable on a path, the path being defined by the variables: var[i] correspo...
@ CHOOSE_HIGHEST_MAX
Among unbound variables, select the variable with the highest maximal value.
@ CHOOSE_MIN_SIZE_LOWEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_REGRET_ON_MIN
Among unbound variables, select the variable with the largest gap between the first and the second va...
@ CHOOSE_MIN_SIZE_HIGHEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_SIZE
Among unbound variables, select the variable with the highest size.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_LOWEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_LOWEST_MIN
Among unbound variables, select the variable with the smallest minimal value.
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Phases on IntVar arrays.
Definition: search.cc:2008
SequenceStrategy
Used for scheduling. Not yet implemented.
Solver(const std::string &name)
Solver API.
std::function< int64(int64, int64)> IndexEvaluator2
Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that 'left' and 'right' both represent permutations of [0....
Definition: constraints.cc:550
IntervalVar * MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the end of another int...
Definition: interval.cc:2403
DecisionBuilder * MakeNestedOptimize(DecisionBuilder *const db, Assignment *const solution, bool maximize, int64 step)
NestedOptimize will collapse a search tree described by a decision builder 'db' and a set of monitors...
Definition: search.cc:4532
ModelCache * Cache() const
Returns the cache of the model.
Definition: model_cache.cc:849
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64 value, int64 max_count)
|{i | vars[i] == value}| == max_count
Definition: count_cst.cc:30
Decision * MakeRankLastInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank last the ith interval var in the sequence variable.
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
All variables are pairwise different.
Definition: alldiff_cst.cc:690
Constraint * MakeSortingConstraint(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &sorted)
Creates a constraint binding the arrays of variables "vars" and "sorted_vars": sorted_vars[0] must be...
Definition: alldiff_cst.cc:714
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
IntExpr * MakeSemiContinuousExpr(IntExpr *const expr, int64 fixed_charge, int64 step)
Semi continuous Expression (x <= 0 -> f(x) = 0; x > 0 -> f(x) = ax + b) a >= 0 and b >= 0.
Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:38
IntExpr * MakeScalProd(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefs)
scalar product
Definition: expr_array.cc:3541
Constraint * MakeNonOverlappingNonStrictBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
bool NameAllVariables() const
Returns whether all variables should be named.
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
Definition: search.cc:438
IntExpr * MakeIndexExpression(const std::vector< IntVar * > &vars, int64 value)
Returns the expression expr such that vars[expr] == value.
Definition: element.cc:1745
Constraint * MakeIsDifferentCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var != value)
Definition: expr_cst.cc:587
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
SearchMonitor * MakeTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &vars, int64 keep_tenure, int64 forbid_tenure, double tabu_factor)
MetaHeuristics which try to get the search out of local optima.
Definition: search.cc:3240
IntExpr * MakeSquare(IntExpr *const expr)
expr * expr
IntervalVar * MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the start of another i...
Definition: interval.cc:2396
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a minimization weighted objective.
Definition: search.cc:2903
int64 branches() const
The number of branches explored since the creation of the solver.
std::function< int64(Solver *solver, const std::vector< IntVar * > &vars, int64 first_unbound, int64 last_unbound)> VariableIndexSelector
IntervalVar * MakeMirrorInterval(IntervalVar *const interval_var)
Creates an interval var that is the mirror image of the given one, that is, the interval var obtained...
Definition: interval.cc:2204
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Creates a local search operator which concatenates a vector of operators.
Constraint * MakeSumLessOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Variation on arrays.
Definition: expr_array.cc:3408
Constraint * MakeIsGreaterCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left > right)
Definition: range_cst.cc:800
Assignment * MakeAssignment()
This method creates an empty assignment.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
Definition: utilities.cc:807
std::function< void()> Closure
Constraint * MakePathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Creates a constraint which accumulates values along a path such that: cumuls[next[i]] = cumuls[i] + t...
IntVar * MakeIntVar(int64 min, int64 max, const std::string &name)
MakeIntVar will create the best range based int var for the bounds given.
std::function< void(Solver *)> Action
SolutionCollector * MakeFirstSolutionCollector()
Collect the first solution of the search.
Definition: search.cc:2435
T * RevAllocArray(T *object)
Like RevAlloc() above, but for an array of objects: the array must have been allocated with the new[]...
int32 Rand32(int32 size)
Returns a random value between 0 and 'size' - 1;.
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *const index, int64 target)
This constraint is a special case of the element constraint with an array of integer variables,...
Definition: element.cc:1730
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
Definition: search.cc:552
std::function< IntVar *(int64)> Int64ToIntVar
Constraint * MakeElementEquality(const std::vector< int64 > &vals, IntVar *const index, IntVar *const target)
Definition: element.cc:1667
Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the maximu...
Definition: constraints.cc:555
IntExpr * MakeConvexPiecewiseExpr(IntExpr *expr, int64 early_cost, int64 early_date, int64 late_date, int64 late_cost)
Convex piecewise function.
IntVar * MakeIsLessCstVar(IntExpr *const var, int64 value)
status var of (var < value)
Definition: expr_cst.cc:793
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
SolutionCollector * MakeBestValueSolutionCollector(const Assignment *const assignment, bool maximize)
Collect the solution corresponding to the optimal value of the objective of 'assignment'; if 'assignm...
Definition: search.cc:2548
IntVar * MakeIsGreaterCstVar(IntExpr *const var, int64 value)
status var of (var > value)
Definition: expr_cst.cc:694
Constraint * MakeMinEquality(const std::vector< IntVar * > &vars, IntVar *const min_var)
Definition: expr_array.cc:3364
Constraint * MakePathPrecedenceConstraint(std::vector< IntVar * > nexts, const std::vector< std::pair< int, int > > &precedences)
Contraint enforcing, for each pair (i,j) in precedences, i to be before j in paths defined by next va...
void AddCastConstraint(CastConstraint *const constraint, IntVar *const target_var, IntExpr *const expr)
Adds 'constraint' to the solver and marks it as a cast constraint, that is, a constraint created call...
IntervalVar * MakeIntervalVar(int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name)
Creates an interval var by specifying the bounds on start, duration, and end.
Definition: interval.cc:2370
IntVar * MakeIsLessOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var <= value)
Definition: expr_cst.cc:776
OptimizeVar * MakeMinimize(IntVar *const v, int64 step)
Creates a minimization objective.
Definition: search.cc:2849
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
Constraint * MakeIsLessOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var <= value)
Definition: expr_cst.cc:797
std::function< DecisionModification()> BranchSelector
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
std::function< int64(const IntVar *v, int64 id)> VariableValueSelector
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
Definition: search.cc:458
static int64 MemoryUsage()
Current memory usage in bytes.
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
IntExpr * MakeProd(IntExpr *const left, IntExpr *const right)
left * right
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *const assignment, DecisionBuilder *const db, const std::vector< IntVar * > &vars)
Returns a decision builder for which the left-most leaf corresponds to assignment,...
Definition: search.cc:2195
void set_fail_intercept(std::function< void()> fail_intercept)
Internal.
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Constraint * MakeGreaterOrEqual(IntExpr *const left, IntExpr *const right)
left >= right
Definition: range_cst.cc:542
OptimizeVar * MakeOptimize(bool maximize, IntVar *const v, int64 step)
Creates a objective with a given sense (true = maximization).
Definition: search.cc:2857
Constraint * MakeIsGreaterOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var >= value)
Definition: expr_cst.cc:698
IntVar * MakeIsGreaterOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left >= right)
Definition: range_cst.cc:785
Constraint * MakeIsGreaterOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left >= right)
Definition: range_cst.cc:790
Constraint * MakeSumGreaterOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Definition: expr_array.cc:3418
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
This method creates a constraint where the graph of the relation between the variables is given in ex...
T * RevAlloc(T *object)
Registers the given object as being reversible.
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
bool IsProduct(IntExpr *const expr, IntExpr **inner_expr, int64 *coefficient)
Returns true if expr represents a product of a expr and a constant.
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
IntExpr * MakeMonotonicElement(IndexEvaluator1 values, bool increasing, IntVar *const index)
Function based element.
Definition: element.cc:859
Constraint * MakeNoCycle(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, IndexFilter1 sink_handler=nullptr)
Prevent cycles.
IntVar * MakeIntConst(int64 val, const std::string &name)
IntConst will create a constant expression.
SolutionCollector * MakeNBestValueSolutionCollector(const Assignment *const assignment, int solution_count, bool maximize)
Same as MakeBestValueSolutionCollector but collects the best solution_count solutions.
Definition: search.cc:2652
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition: utilities.cc:811
IntVar * MakeIsLessOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left <= right)
Definition: range_cst.cc:698
IntervalVar * RegisterIntervalVar(IntervalVar *const var)
Registers a new IntervalVar and wraps it inside a TraceIntervalVar if necessary.
Definition: trace.cc:865
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
@ GE
Move is accepted when the current objective value >= objective.Min.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
Constraint * MakeScalProdEquality(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
Definition: expr_array.cc:3483
OptimizationDirection optimization_direction() const
The direction of optimization, getter and setter.
void SaveAndAdd(T *adr, T val)
All-in-one SaveAndAdd_value.
This class represents a sorted list of disjoint, closed intervals.
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
ABSL_DECLARE_FLAG(int64, cp_random_seed)
Declaration of the core objects for the constraint solver.
CpModelProto proto
SharedBoundsManager * bounds
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
MPCallback * callback
int int32
static const int64 kint64max
int64_t int64
uint64_t uint64
const bool DEBUG_MODE
Definition: macros.h:24
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
Definition: file.cc:141
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
int64 One()
This method returns 1.
int index
Definition: pack.cc:508
int64 time
Definition: resource.cc:1683
int64 delta
Definition: resource.cc:1684
int64 capacity
int64 coefficient
std::vector< double > coefficients
Rev< int64 > end_min
Rev< int64 > end_max
Rev< int64 > start_max
Rev< int64 > start_min
const int64 stamp_
Definition: search.cc:3039
This struct holds all parameters for the default search.
int heuristic_num_failures_limit
The failure limit for each heuristic that we run.
int initialization_splits
Maximum number of intervals that the initialization of impacts will scan per variable.
DecisionBuilder * decision_builder
When defined, this overrides the default impact based decision builder.
DisplayLevel display_level
This represents the amount of information displayed by the default search.
ValueSelection value_selection_schema
This parameter describes which value to select for a given var.
VariableSelection var_selection_schema
This parameter describes how the next variable to instantiate will be chosen.
bool persistent_impact
Whether to keep the impact from the first search for other searches, or to recompute the impact for e...
bool use_last_conflict
Should we use last conflict method. The default is false.
int heuristic_period
The distance in nodes between each run of the heuristics.
int random_seed
Seed used to initialize the random part in some heuristics.
bool run_all_heuristics
The default phase will run heuristics periodically.
static Iterator Begin(IntVarIterator *it)
These are the only way to construct an Iterator.
bool operator!=(const Iterator &other) const
static Iterator End(IntVarIterator *it)
bool operator<(const SolutionData &other) const
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
IntegerCastInfo(IntVar *const v, IntExpr *const e, Constraint *const c)
Creates a search monitor from logging parameters.
int branch_period
SearchMonitors will display a periodic search log every branch_period branches explored.
OptimizeVar * objective
SearchMonitors will display values of objective or variable (both cannot be used together).
std::function< std::string()> display_callback
SearchMonitors will display the result of display_callback at each new solution found and when the se...
double scaling_factor
When displayed, objective or var values will be scaled and offset by the given values in the followin...
bool display_on_new_solutions_only
To be used to protect from cases where display_callback assumes variables are instantiated,...