1 // Copyright 2010-2021 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
14 /// Declaration of the core objects for the constraint solver.
15 ///
16 /// The literature around constraint programming is extremely dense but one
17 /// can find some basic introductions in the following links:
18 /// - http://en.wikipedia.org/wiki/Constraint_programming
19 /// - http://kti.mff.cuni.cz/~bartak/constraints/index.html
20 ///
21 /// Here is a very simple Constraint Programming problem:
22 ///
23 /// If we see 56 legs and 20 heads, how many two-legged pheasants
24 /// and four-legged rabbits are we looking at?
25 ///
26 /// Here is some simple Constraint Programming code to find out:
27 ///
28 /// void pheasant() {
29 /// Solver s("pheasant");
30 /// // Create integer variables to represent the number of pheasants and
31 /// // rabbits, with a minimum of 0 and a maximum of 20.
32 /// IntVar* const p = s.MakeIntVar(0, 20, "pheasant"));
33 /// IntVar* const r = s.MakeIntVar(0, 20, "rabbit"));
34 /// // The number of heads is the sum of pheasants and rabbits.
35 /// IntExpr* const heads = s.MakeSum(p, r);
36 /// // The number of legs is the sum of pheasants * 2 and rabbits * 4.
37 /// IntExpr* const legs = s.MakeSum(s.MakeProd(p, 2), s.MakeProd(r, 4));
38 /// // Constraints: the number of legs is 56 and heads is 20.
39 /// Constraint* const ct_legs = s.MakeEquality(legs, 56);
40 /// Constraint* const ct_heads = s.MakeEquality(heads, 20);
41 /// s.AddConstraint(ct_legs);
42 /// s.AddConstraint(ct_heads);
43 /// DecisionBuilder* const db = s.MakePhase(p, r,
44 /// Solver::CHOOSE_FIRST_UNBOUND,
45 /// Solver::ASSIGN_MIN_VALUE);
46 /// s.NewSearch(db);
47 /// CHECK(s.NextSolution());
48 /// LOG(INFO) << "rabbits -> " << r->Value() << ", pheasants -> "
49 /// << p->Value();
50 /// LOG(INFO) << s.DebugString();
51 /// s.EndSearch();
52 /// }
53 ///
54 /// which outputs:
55 ///
56 /// rabbits -> 8, pheasants -> 12
57 /// Solver(name = "pheasant",
58 /// state = OUTSIDE_SEARCH,
59 /// branches = 0,
60 /// fails = 0,
61 /// decisions = 0
62 /// propagation loops = 11,
63 /// demons Run = 25,
64 /// Run time = 0 ms)
65 ///
66 ///
67
68 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
70
71 #include <stddef.h>
72 #include <stdint.h>
73
74 #include <deque>
75 #include <functional>
76 #include <memory>
77 #include <random>
78 #include <string>
79 #include <tuple>
80 #include <utility>
81 #include <vector>
82
83 #include "absl/base/attributes.h"
84 #include "absl/base/log_severity.h"
85 #include "absl/container/flat_hash_map.h"
86 #include "absl/container/flat_hash_set.h"
87 #include "absl/flags/declare.h"
88 #include "absl/flags/flag.h"
89 #include "absl/random/random.h"
90 #include "absl/strings/str_format.h"
91 #include "absl/time/time.h"
92 #include "ortools/base/integral_types.h"
93 #include "ortools/base/logging.h"
94 #include "ortools/base/macros.h"
95 #include "ortools/base/map_util.h"
96 #include "ortools/base/timer.h"
97 #include "ortools/constraint_solver/search_stats.pb.h"
98 #include "ortools/constraint_solver/solver_parameters.pb.h"
99 #include "ortools/util/piecewise_linear_function.h"
100 #include "ortools/util/sorted_interval_list.h"
101 #include "ortools/util/tuple_set.h"
102
103 #if !defined(SWIG)
104 ABSL_DECLARE_FLAG(int64_t, cp_random_seed);
105 #endif // !defined(SWIG)
106
107 class File;
108
109 namespace operations_research {
110
111 class Assignment;
112 class AssignmentProto;
113 class BaseObject;
114 class CastConstraint;
115 class Constraint;
116 class Decision;
117 class DecisionBuilder;
118 class DecisionVisitor;
119 class Demon;
120 class DemonProfiler;
121 class Dimension;
122 class DisjunctiveConstraint;
123 class ImprovementSearchLimit;
124 class IntExpr;
125 class IntVar;
126 class IntVarAssignment;
127 class IntVarLocalSearchFilter;
128 class IntervalVar;
129 class IntervalVarAssignment;
130 class LocalSearchFilter;
131 class LocalSearchFilterManager;
132 class LocalSearchMonitor;
133 class LocalSearchOperator;
134 class LocalSearchPhaseParameters;
135 class LocalSearchProfiler;
136 class ModelCache;
137 class ModelVisitor;
138 class OptimizeVar;
139 class Pack;
140 class ProfiledDecisionBuilder;
141 class PropagationBaseObject;
142 class PropagationMonitor;
143 class Queue;
144 class RegularLimit;
145 class RegularLimitParameters;
146 class RevBitMatrix;
147 class Search;
148 class SearchLimit;
149 class SearchMonitor;
150 class SequenceVar;
151 class SequenceVarAssignment;
152 class SolutionCollector;
153 class SolutionPool;
154 class SymmetryBreaker;
155 struct StateInfo;
156 struct Trail;
157 template <class T>
158 class SimpleRevFIFO;
159
CpRandomSeed()160 inline int64_t CpRandomSeed() {
161 return absl::GetFlag(FLAGS_cp_random_seed) == -1
162 ? absl::Uniform<int64_t>(absl::BitGen(), 0, kint64max)
163 : absl::GetFlag(FLAGS_cp_random_seed);
164 }
165
166 /// This struct holds all parameters for the default search.
167 /// DefaultPhaseParameters is only used by Solver::MakeDefaultPhase methods.
168 /// Note this is for advanced users only.
169 struct DefaultPhaseParameters {
170 public:
171 enum VariableSelection {
172 CHOOSE_MAX_SUM_IMPACT = 0,
173 CHOOSE_MAX_AVERAGE_IMPACT = 1,
174 CHOOSE_MAX_VALUE_IMPACT = 2,
175 };
176
177 enum ValueSelection {
178 SELECT_MIN_IMPACT = 0,
179 SELECT_MAX_IMPACT = 1,
180 };
181
182 enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };
183
184 /// This parameter describes how the next variable to instantiate
185 /// will be chosen.
186 VariableSelection var_selection_schema;
187
188 /// This parameter describes which value to select for a given var.
189 ValueSelection value_selection_schema;
190
191 /// Maximum number of intervals that the initialization of impacts will scan
192 /// per variable.
193 int initialization_splits;
194
195 /// The default phase will run heuristics periodically. This parameter
196 /// indicates if we should run all heuristics, or a randomly selected
197 /// one.
198 bool run_all_heuristics;
199
200 /// The distance in nodes between each run of the heuristics. A
201 /// negative or null value will mean that we will not run heuristics
202 /// at all.
203 int heuristic_period;
204
205 /// The failure limit for each heuristic that we run.
206 int heuristic_num_failures_limit;
207
208 /// Whether to keep the impact from the first search for other searches,
209 /// or to recompute the impact for each new search.
210 bool persistent_impact;
211
212 /// Seed used to initialize the random part in some heuristics.
213 int random_seed;
214
215 /// This represents the amount of information displayed by the default search.
216 /// NONE means no display, VERBOSE means extra information.
217 DisplayLevel display_level;
218
219 /// Should we use last conflict method. The default is false.
220 bool use_last_conflict;
221
222 /// When defined, this overrides the default impact based decision builder.
223 DecisionBuilder* decision_builder;
224
225 DefaultPhaseParameters();
226 };
227
228 /// Solver Class
229 ///
230 /// A solver represents the main computation engine. It implements the entire
231 /// range of Constraint Programming protocols:
232 /// - Reversibility
233 /// - Propagation
234 /// - Search
235 ///
236 /// Usually, Constraint Programming code consists of
237 /// - the creation of the Solver,
238 /// - the creation of the decision variables of the model,
239 /// - the creation of the constraints of the model and their addition to the
240 /// solver() through the AddConstraint() method,
241 /// - the creation of the main DecisionBuilder class,
242 /// - the launch of the solve() method with the decision builder.
243 ///
244 /// For the time being, Solver is neither MT_SAFE nor MT_HOT.
245 class Solver {
246 public:
247 /// Holds semantic information stating that the 'expression' has been
248 /// cast into 'variable' using the Var() method, and that
249 /// 'maintainer' is responsible for maintaining the equality between
250 /// 'variable' and 'expression'.
251 struct IntegerCastInfo {
IntegerCastInfoIntegerCastInfo252 IntegerCastInfo()
253 : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
IntegerCastInfoIntegerCastInfo254 IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
255 : variable(v), expression(e), maintainer(c) {}
256 IntVar* variable;
257 IntExpr* expression;
258 Constraint* maintainer;
259 };
260
261 /// Number of priorities for demons.
262 static constexpr int kNumPriorities = 3;
263
264 /// This enum describes the strategy used to select the next branching
265 /// variable at each node during the search.
266 enum IntVarStrategy {
267 /// The default behavior is CHOOSE_FIRST_UNBOUND.
268 INT_VAR_DEFAULT,
269
270 /// The simple selection is CHOOSE_FIRST_UNBOUND.
271 INT_VAR_SIMPLE,
272
273 /// Select the first unbound variable.
274 /// Variables are considered in the order of the vector of IntVars used
275 /// to create the selector.
276 CHOOSE_FIRST_UNBOUND,
277
278 /// Randomly select one of the remaining unbound variables.
279 CHOOSE_RANDOM,
280
281 /// Among unbound variables, select the variable with the smallest size,
282 /// i.e., the smallest number of possible values.
283 /// In case of a tie, the selected variables is the one with the lowest min
284 /// value.
285 /// In case of a tie, the first one is selected, first being defined by the
286 /// order in the vector of IntVars used to create the selector.
287 CHOOSE_MIN_SIZE_LOWEST_MIN,
288
289 /// Among unbound variables, select the variable with the smallest size,
290 /// i.e., the smallest number of possible values.
291 /// In case of a tie, the selected variable is the one with the highest min
292 /// value.
293 /// In case of a tie, the first one is selected, first being defined by the
294 /// order in the vector of IntVars used to create the selector.
295 CHOOSE_MIN_SIZE_HIGHEST_MIN,
296
297 /// Among unbound variables, select the variable with the smallest size,
298 /// i.e., the smallest number of possible values.
299 /// In case of a tie, the selected variables is the one with the lowest max
300 /// value.
301 /// In case of a tie, the first one is selected, first being defined by the
302 /// order in the vector of IntVars used to create the selector.
303 CHOOSE_MIN_SIZE_LOWEST_MAX,
304
305 /// Among unbound variables, select the variable with the smallest size,
306 /// i.e., the smallest number of possible values.
307 /// In case of a tie, the selected variable is the one with the highest max
308 /// value.
309 /// In case of a tie, the first one is selected, first being defined by the
310 /// order in the vector of IntVars used to create the selector.
311 CHOOSE_MIN_SIZE_HIGHEST_MAX,
312
313 /// Among unbound variables, select the variable with the smallest minimal
314 /// value.
315 /// In case of a tie, the first one is selected, "first" defined by the
316 /// order in the vector of IntVars used to create the selector.
317 CHOOSE_LOWEST_MIN,
318
319 /// Among unbound variables, select the variable with the highest maximal
320 /// value.
321 /// In case of a tie, the first one is selected, first being defined by the
322 /// order in the vector of IntVars used to create the selector.
323 CHOOSE_HIGHEST_MAX,
324
325 /// Among unbound variables, select the variable with the smallest size.
326 /// In case of a tie, the first one is selected, first being defined by the
327 /// order in the vector of IntVars used to create the selector.
328 CHOOSE_MIN_SIZE,
329
330 /// Among unbound variables, select the variable with the highest size.
331 /// In case of a tie, the first one is selected, first being defined by the
332 /// order in the vector of IntVars used to create the selector.
333 CHOOSE_MAX_SIZE,
334
335 /// Among unbound variables, select the variable with the largest
336 /// gap between the first and the second values of the domain.
337 CHOOSE_MAX_REGRET_ON_MIN,
338
339 /// Selects the next unbound variable on a path, the path being defined by
340 /// the variables: var[i] corresponds to the index of the next of i.
341 CHOOSE_PATH,
342 };
343 // TODO(user): add HIGHEST_MIN and LOWEST_MAX.
344
345 /// This enum describes the strategy used to select the next variable value to
346 /// set.
347 enum IntValueStrategy {
348 /// The default behavior is ASSIGN_MIN_VALUE.
349 INT_VALUE_DEFAULT,
350
351 /// The simple selection is ASSIGN_MIN_VALUE.
352 INT_VALUE_SIMPLE,
353
354 /// Selects the min value of the selected variable.
355 ASSIGN_MIN_VALUE,
356
357 /// Selects the max value of the selected variable.
358 ASSIGN_MAX_VALUE,
359
360 /// Selects randomly one of the possible values of the selected variable.
361 ASSIGN_RANDOM_VALUE,
362
363 /// Selects the first possible value which is the closest to the center
364 /// of the domain of the selected variable.
365 /// The center is defined as (min + max) / 2.
366 ASSIGN_CENTER_VALUE,
367
368 /// Split the domain in two around the center, and choose the lower
369 /// part first.
370 SPLIT_LOWER_HALF,
371
372 /// Split the domain in two around the center, and choose the lower
373 /// part first.
374 SPLIT_UPPER_HALF,
375 };
376
377 /// This enum is used by Solver::MakePhase to specify how to select variables
378 /// and values during the search.
379 /// In Solver::MakePhase(const std::vector<IntVar*>&, IntVarStrategy,
380 /// IntValueStrategy), variables are selected first, and then the associated
381 /// value.
382 /// In Solver::MakePhase(const std::vector<IntVar*>& vars, IndexEvaluator2,
383 /// EvaluatorStrategy), the selection is done scanning every pair
384 /// <variable, possible value>. The next selected pair is then the best among
385 /// all possibilities, i.e. the pair with the smallest evaluation.
386 /// As this is costly, two options are offered: static or dynamic evaluation.
387 enum EvaluatorStrategy {
388 /// Pairs are compared at the first call of the selector, and results are
389 /// cached. Next calls to the selector use the previous computation, and so
390 /// are not up-to-date, e.g. some <variable, value> pairs may not be
391 /// possible anymore due to propagation since the first to call.
392 CHOOSE_STATIC_GLOBAL_BEST,
393
394 /// Pairs are compared each time a variable is selected. That way all pairs
395 /// are relevant and evaluation is accurate.
396 /// This strategy runs in O(number-of-pairs) at each variable selection,
397 /// versus O(1) in the static version.
398 CHOOSE_DYNAMIC_GLOBAL_BEST,
399 };
400
401 /// Used for scheduling. Not yet implemented.
402 enum SequenceStrategy {
403 SEQUENCE_DEFAULT,
404 SEQUENCE_SIMPLE,
405 CHOOSE_MIN_SLACK_RANK_FORWARD,
406 CHOOSE_RANDOM_RANK_FORWARD,
407 };
408
409 /// This enum describes the straregy used to select the next interval variable
410 /// and its value to be fixed.
411 enum IntervalStrategy {
412 /// The default is INTERVAL_SET_TIMES_FORWARD.
413 INTERVAL_DEFAULT,
414 /// The simple is INTERVAL_SET_TIMES_FORWARD.
415 INTERVAL_SIMPLE,
416 /// Selects the variable with the lowest starting time of all variables,
417 /// and fixes its starting time to this lowest value.
418 INTERVAL_SET_TIMES_FORWARD,
419 /// Selects the variable with the highest ending time of all variables,
420 /// and fixes the ending time to this highest values.
421 INTERVAL_SET_TIMES_BACKWARD
422 };
423
424 /// This enum is used in Solver::MakeOperator to specify the neighborhood to
425 /// create.
426 enum LocalSearchOperators {
427 /// Operator which reverses a sub-chain of a path. It is called TwoOpt
428 /// because it breaks two arcs on the path; resulting paths are called
429 /// two-optimal.
430 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
431 /// (where (1, 5) are first and last nodes of the path and can therefore not
432 /// be moved):
433 /// 1 -> [3 -> 2] -> 4 -> 5
434 /// 1 -> [4 -> 3 -> 2] -> 5
435 /// 1 -> 2 -> [4 -> 3] -> 5
436 TWOOPT,
437
438 /// Relocate: OROPT and RELOCATE.
439 /// Operator which moves a sub-chain of a path to another position; the
440 /// specified chain length is the fixed length of the chains being moved.
441 /// When this length is 1, the operator simply moves a node to another
442 /// position.
443 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a chain
444 /// length of 2 (where (1, 5) are first and last nodes of the path and can
445 /// therefore not be moved):
446 /// 1 -> 4 -> [2 -> 3] -> 5
447 /// 1 -> [3 -> 4] -> 2 -> 5
448 ///
449 /// Using Relocate with chain lengths of 1, 2 and 3 together is equivalent
450 /// to the OrOpt operator on a path. The OrOpt operator is a limited
451 /// version of 3Opt (breaks 3 arcs on a path).
452 OROPT,
453
454 /// Relocate neighborhood with length of 1 (see OROPT comment).
455 RELOCATE,
456
457 /// Operator which exchanges the positions of two nodes.
458 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
459 /// (where (1, 5) are first and last nodes of the path and can therefore not
460 /// be moved):
461 /// 1 -> [3] -> [2] -> 4 -> 5
462 /// 1 -> [4] -> 3 -> [2] -> 5
463 /// 1 -> 2 -> [4] -> [3] -> 5
464 EXCHANGE,
465
466 /// Operator which cross exchanges the starting chains of 2 paths, including
467 /// exchanging the whole paths.
468 /// First and last nodes are not moved.
469 /// Possible neighbors for the paths 1 -> 2 -> 3 -> 4 -> 5 and 6 -> 7 -> 8
470 /// (where (1, 5) and (6, 8) are first and last nodes of the paths and can
471 /// therefore not be moved):
472 /// 1 -> [7] -> 3 -> 4 -> 5 6 -> [2] -> 8
473 /// 1 -> [7] -> 4 -> 5 6 -> [2 -> 3] -> 8
474 /// 1 -> [7] -> 5 6 -> [2 -> 3 -> 4] -> 8
475 CROSS,
476
477 /// Operator which inserts an inactive node into a path.
478 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
479 /// (where 1 and 4 are first and last nodes of the path) are:
480 /// 1 -> [5] -> 2 -> 3 -> 4
481 /// 1 -> 2 -> [5] -> 3 -> 4
482 /// 1 -> 2 -> 3 -> [5] -> 4
483 MAKEACTIVE,
484
485 /// Operator which makes path nodes inactive.
486 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are
487 /// first and last nodes of the path) are:
488 /// 1 -> 3 -> 4 with 2 inactive
489 /// 1 -> 2 -> 4 with 3 inactive
490 MAKEINACTIVE,
491
492 /// Operator which makes a "chain" of path nodes inactive.
493 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are
494 /// first and last nodes of the path) are:
495 /// 1 -> 3 -> 4 with 2 inactive
496 /// 1 -> 2 -> 4 with 3 inactive
497 /// 1 -> 4 with 2 and 3 inactive
498 MAKECHAININACTIVE,
499
500 /// Operator which replaces an active node by an inactive one.
501 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
502 /// (where 1 and 4 are first and last nodes of the path) are:
503 /// 1 -> [5] -> 3 -> 4 with 2 inactive
504 /// 1 -> 2 -> [5] -> 4 with 3 inactive
505 SWAPACTIVE,
506
507 /// Operator which makes an inactive node active and an active one inactive.
508 /// It is similar to SwapActiveOperator except that it tries to insert the
509 /// inactive node in all possible positions instead of just the position of
510 /// the node made inactive.
511 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
512 /// (where 1 and 4 are first and last nodes of the path) are:
513 /// 1 -> [5] -> 3 -> 4 with 2 inactive
514 /// 1 -> 3 -> [5] -> 4 with 2 inactive
515 /// 1 -> [5] -> 2 -> 4 with 3 inactive
516 /// 1 -> 2 -> [5] -> 4 with 3 inactive
517 EXTENDEDSWAPACTIVE,
518
519 /// Operator which relaxes two sub-chains of three consecutive arcs each.
520 /// Each sub-chain is defined by a start node and the next three arcs. Those
521 /// six arcs are relaxed to build a new neighbor.
522 /// PATHLNS explores all possible pairs of starting nodes and so defines
523 /// n^2 neighbors, n being the number of nodes.
524 /// Note that the two sub-chains can be part of the same path; they even may
525 /// overlap.
526 PATHLNS,
527
528 /// Operator which relaxes one entire path and all inactive nodes, thus
529 /// defining num_paths neighbors.
530 FULLPATHLNS,
531
532 /// Operator which relaxes all inactive nodes and one sub-chain of six
533 /// consecutive arcs. That way the path can be improved by inserting
534 /// inactive nodes or swapping arcs.
535 UNACTIVELNS,
536
537 /// Operator which defines one neighbor per variable. Each neighbor tries to
538 /// increment by one the value of the corresponding variable. When a new
539 /// solution is found the neighborhood is rebuilt from scratch, i.e., tries
540 /// to increment values in the variable order.
541 /// Consider for instance variables x and y. x is incremented one by one to
542 /// its max, and when it is not possible to increment x anymore, y is
543 /// incremented once. If this is a solution, then next neighbor tries to
544 /// increment x.
545 INCREMENT,
546
547 /// Operator which defines a neighborhood to decrement values.
548 /// The behavior is the same as INCREMENT, except values are decremented
549 /// instead of incremented.
550 DECREMENT,
551
552 /// Operator which defines one neighbor per variable. Each neighbor relaxes
553 /// one variable.
554 /// When a new solution is found the neighborhood is rebuilt from scratch.
555 /// Consider for instance variables x and y. First x is relaxed and the
556 /// solver is looking for the best possible solution (with only x relaxed).
557 /// Then y is relaxed, and the solver is looking for a new solution.
558 /// If a new solution is found, then the next variable to be relaxed is x.
559 SIMPLELNS
560 };
561
562 /// This enum is used in Solver::MakeOperator associated with an evaluator
563 /// to specify the neighborhood to create.
564 enum EvaluatorLocalSearchOperators {
565 /// Lin-Kernighan local search.
566 /// While the accumulated local gain is positive, perform a 2opt or a 3opt
567 /// move followed by a series of 2opt moves. Return a neighbor for which the
568 /// global gain is positive.
569 LK,
570
571 /// Sliding TSP operator.
572 /// Uses an exact dynamic programming algorithm to solve the TSP
573 /// corresponding to path sub-chains.
574 /// For a subchain 1 -> 2 -> 3 -> 4 -> 5 -> 6, solves the TSP on
575 /// nodes A, 2, 3, 4, 5, where A is a merger of nodes 1 and 6 such that
576 /// cost(A,i) = cost(1,i) and cost(i,A) = cost(i,6).
577 TSPOPT,
578
579 /// TSP-base LNS.
580 /// Randomly merge consecutive nodes until n "meta"-nodes remain and solve
581 /// the corresponding TSP.
582 /// This is an "unlimited" neighborhood which must be stopped by search
583 /// limits. To force diversification, the operator iteratively forces each
584 /// node to serve as base of a meta-node.
585 TSPLNS
586 };
587
588 /// This enum is used in Solver::MakeLocalSearchObjectiveFilter. It specifies
589 /// the behavior of the objective filter to create. The goal is to define
590 /// under which condition a move is accepted based on the current objective
591 /// value.
592 enum LocalSearchFilterBound {
593 /// Move is accepted when the current objective value >= objective.Min.
594 GE,
595 /// Move is accepted when the current objective value <= objective.Max.
596 LE,
597 /// Move is accepted when the current objective value is in the interval
598 /// objective.Min .. objective.Max.
599 EQ
600 };
601
602 /// This enum represents the three possible priorities for a demon in the
603 /// Solver queue.
604 /// Note: this is for advanced users only.
605 enum DemonPriority {
606 /// DELAYED_PRIORITY is the lowest priority: Demons will be processed after
607 /// VAR_PRIORITY and NORMAL_PRIORITY demons.
608 DELAYED_PRIORITY = 0,
609
610 /// VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
611 VAR_PRIORITY = 1,
612
613 /// NORMAL_PRIORITY is the highest priority: Demons will be processed first.
614 NORMAL_PRIORITY = 2,
615 };
616
617 /// This enum is used in Solver::MakeIntervalVarRelation to specify the
618 /// temporal relation between the two intervals t1 and t2.
619 enum BinaryIntervalRelation {
620 /// t1 ends after t2 end, i.e. End(t1) >= End(t2) + delay.
621 ENDS_AFTER_END,
622
623 /// t1 ends after t2 start, i.e. End(t1) >= Start(t2) + delay.
624 ENDS_AFTER_START,
625
626 /// t1 ends at t2 end, i.e. End(t1) == End(t2) + delay.
627 ENDS_AT_END,
628
629 /// t1 ends at t2 start, i.e. End(t1) == Start(t2) + delay.
630 ENDS_AT_START,
631
632 /// t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
633 STARTS_AFTER_END,
634
635 /// t1 starts after t2 start, i.e. Start(t1) >= Start(t2) + delay.
636 STARTS_AFTER_START,
637
638 /// t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
639 STARTS_AT_END,
640
641 /// t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
642 STARTS_AT_START,
643
644 /// STARTS_AT_START and ENDS_AT_END at the same time.
645 /// t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
646 /// t1 ends at t2 end, i.e. End(t1) == End(t2).
647 STAYS_IN_SYNC
648 };
649
650 /// This enum is used in Solver::MakeIntervalVarRelation to specify the
651 /// temporal relation between an interval t and an integer d.
652 enum UnaryIntervalRelation {
653 /// t ends after d, i.e. End(t) >= d.
654 ENDS_AFTER,
655
656 /// t ends at d, i.e. End(t) == d.
657 ENDS_AT,
658
659 /// t ends before d, i.e. End(t) <= d.
660 ENDS_BEFORE,
661
662 /// t starts after d, i.e. Start(t) >= d.
663 STARTS_AFTER,
664
665 /// t starts at d, i.e. Start(t) == d.
666 STARTS_AT,
667
668 /// t starts before d, i.e. Start(t) <= d.
669 STARTS_BEFORE,
670
671 /// STARTS_BEFORE and ENDS_AFTER at the same time, i.e. d is in t.
672 /// t starts before d, i.e. Start(t) <= d.
673 /// t ends after d, i.e. End(t) >= d.
674 CROSS_DATE,
675
676 /// STARTS_AFTER or ENDS_BEFORE, i.e. d is not in t.
677 /// t starts after d, i.e. Start(t) >= d.
678 /// t ends before d, i.e. End(t) <= d.
679 AVOID_DATE
680 };
681
682 /// The Solver is responsible for creating the search tree. Thanks to the
683 /// DecisionBuilder, it creates a new decision with two branches at each node:
684 /// left and right.
685 /// The DecisionModification enum is used to specify how the branch selector
686 /// should behave.
687 enum DecisionModification {
688 /// Keeps the default behavior, i.e. apply left branch first, and then right
689 /// branch in case of backtracking.
690 NO_CHANGE,
691
692 /// Right branches are ignored. This is used to make the code faster when
693 /// backtrack makes no sense or is not useful.
694 /// This is faster as there is no need to create one new node per decision.
695 KEEP_LEFT,
696
697 /// Left branches are ignored. This is used to make the code faster when
698 /// backtrack makes no sense or is not useful.
699 /// This is faster as there is no need to create one new node per decision.
700 KEEP_RIGHT,
701
702 /// Backtracks to the previous decisions, i.e. left and right branches are
703 /// not applied.
704 KILL_BOTH,
705
706 /// Applies right branch first. Left branch will be applied in case of
707 /// backtracking.
708 SWITCH_BRANCHES
709 };
710
711 /// This enum is used internally in private methods Solver::PushState and
712 /// Solver::PopState to tag states in the search tree.
713 enum MarkerType { SENTINEL, SIMPLE_MARKER, CHOICE_POINT, REVERSIBLE_ACTION };
714
715 /// This enum represents the state of the solver w.r.t. the search.
716 enum SolverState {
717 /// Before search, after search.
718 OUTSIDE_SEARCH,
719 /// Executing the root node.
720 IN_ROOT_NODE,
721 /// Executing the search code.
722 IN_SEARCH,
723 /// After successful NextSolution and before EndSearch.
724 AT_SOLUTION,
725 /// After failed NextSolution and before EndSearch.
726 NO_MORE_SOLUTIONS,
727 /// After search, the model is infeasible.
728 PROBLEM_INFEASIBLE
729 };
730
731 /// Optimization directions.
732 enum OptimizationDirection { NOT_SET, MAXIMIZATION, MINIMIZATION };
733
734 /// Callback typedefs
735 typedef std::function<int64_t(int64_t)> IndexEvaluator1;
736 typedef std::function<int64_t(int64_t, int64_t)> IndexEvaluator2;
737 typedef std::function<int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3;
738
739 typedef std::function<bool(int64_t)> IndexFilter1;
740
741 typedef std::function<IntVar*(int64_t)> Int64ToIntVar;
742
743 typedef std::function<int64_t(Solver* solver,
744 const std::vector<IntVar*>& vars,
745 int64_t first_unbound, int64_t last_unbound)>
746 VariableIndexSelector;
747
748 typedef std::function<int64_t(const IntVar* v, int64_t id)>
749 VariableValueSelector;
750 typedef std::function<bool(int64_t, int64_t, int64_t)>
751 VariableValueComparator;
752 typedef std::function<DecisionModification()> BranchSelector;
753 // TODO(user): wrap in swig.
754 typedef std::function<void(Solver*)> Action;
755 typedef std::function<void()> Closure;
756
757 /// Solver API
758 explicit Solver(const std::string& name);
759 Solver(const std::string& name, const ConstraintSolverParameters& parameters);
760 ~Solver();
761
762 /// Stored Parameters.
parameters()763 ConstraintSolverParameters parameters() const { return parameters_; }
764 /// Create a ConstraintSolverParameters proto with all the default values.
765 // TODO(user): Move to constraint_solver_parameters.h.
766 static ConstraintSolverParameters DefaultSolverParameters();
767
768 /// reversibility
769
770 /// SaveValue() saves the value of the corresponding object. It must be
771 /// called before modifying the object. The value will be restored upon
772 /// backtrack.
773 template <class T>
SaveValue(T * o)774 void SaveValue(T* o) {
775 InternalSaveValue(o);
776 }
777
778 /// Registers the given object as being reversible. By calling this method,
779 /// the caller gives ownership of the object to the solver, which will
780 /// delete it when there is a backtrack out of the current state.
781 ///
782 /// Returns the argument for convenience: this way, the caller may directly
783 /// invoke a constructor in the argument, without having to store the pointer
784 /// first.
785 ///
786 /// This function is only for users that define their own subclasses of
787 /// BaseObject: for all subclasses predefined in the library, the
788 /// corresponding factory methods (e.g., MakeIntVar(...),
789 /// MakeAllDifferent(...) already take care of the registration.
790 template <typename T>
RevAlloc(T * object)791 T* RevAlloc(T* object) {
792 return reinterpret_cast<T*>(SafeRevAlloc(object));
793 }
794
795 /// Like RevAlloc() above, but for an array of objects: the array
796 /// must have been allocated with the new[] operator. The entire array
797 /// will be deleted when backtracking out of the current state.
798 ///
799 /// This method is valid for arrays of int, int64_t, uint64_t, bool,
800 /// BaseObject*, IntVar*, IntExpr*, and Constraint*.
801 template <typename T>
RevAllocArray(T * object)802 T* RevAllocArray(T* object) {
803 return reinterpret_cast<T*>(SafeRevAllocArray(object));
804 }
805
806 /// Adds the constraint 'c' to the model.
807 ///
808 /// After calling this method, and until there is a backtrack that undoes the
809 /// addition, any assignment of variables to values must satisfy the given
810 /// constraint in order to be considered feasible. There are two fairly
811 /// different use cases:
812 ///
813 /// - the most common use case is modeling: the given constraint is really
814 /// part of the problem that the user is trying to solve. In this use case,
815 /// AddConstraint is called outside of search (i.e., with <tt>state() ==
816 /// OUTSIDE_SEARCH</tt>). Most users should only use AddConstraint in this
817 /// way. In this case, the constraint will belong to the model forever: it
818 /// cannot not be removed by backtracking.
819 ///
820 /// - a rarer use case is that 'c' is not a real constraint of the model. It
821 /// may be a constraint generated by a branching decision (a constraint whose
822 /// goal is to restrict the search space), a symmetry breaking constraint (a
823 /// constraint that does restrict the search space, but in a way that cannot
824 /// have an impact on the quality of the solutions in the subtree), or an
825 /// inferred constraint that, while having no semantic value to the model (it
826 /// does not restrict the set of solutions), is worth having because we
827 /// believe it may strengthen the propagation. In these cases, it happens
828 /// that the constraint is added during the search (i.e., with state() ==
829 /// IN_SEARCH or state() == IN_ROOT_NODE). When a constraint is
830 /// added during a search, it applies only to the subtree of the search tree
831 /// rooted at the current node, and will be automatically removed by
832 /// backtracking.
833 ///
834 /// This method does not take ownership of the constraint. If the constraint
835 /// has been created by any factory method (Solver::MakeXXX), it will
836 /// automatically be deleted. However, power users who implement their own
837 /// constraints should do: solver.AddConstraint(solver.RevAlloc(new
838 /// MyConstraint(...));
839 void AddConstraint(Constraint* const c);
840 /// Adds 'constraint' to the solver and marks it as a cast constraint, that
841 /// is, a constraint created calling Var() on an expression. This is used
842 /// internally.
843 void AddCastConstraint(CastConstraint* const constraint,
844 IntVar* const target_var, IntExpr* const expr);
845
846 /// @{
847 /// Solves the problem using the given DecisionBuilder and returns true if a
848 /// solution was found and accepted.
849 ///
850 /// These methods are the ones most users should use to search for a solution.
851 /// Note that the definition of 'solution' is subtle. A solution here is
852 /// defined as a leaf of the search tree with respect to the given decision
853 /// builder for which there is no failure. What this means is that, contrary
854 /// to intuition, a solution may not have all variables of the model bound.
855 /// It is the responsibility of the decision builder to keep returning
856 /// decisions until all variables are indeed bound. The most extreme
857 /// counterexample is calling Solve with a trivial decision builder whose
858 /// Next() method always returns nullptr. In this case, Solve immediately
859 /// returns 'true', since not assigning any variable to any value is a
860 /// solution, unless the root node propagation discovers that the model is
861 /// infeasible.
862 ///
863 /// This function must be called either from outside of search,
864 /// or from within the Next() method of a decision builder.
865 ///
866 /// Solve will terminate whenever any of the following event arise:
867 /// * A search monitor asks the solver to terminate the search by calling
868 /// solver()->FinishCurrentSearch().
869 /// * A solution is found that is accepted by all search monitors, and none of
870 /// the search monitors decides to search for another one.
871 ///
872 /// Upon search termination, there will be a series of backtracks all the way
873 /// to the top level. This means that a user cannot expect to inspect the
874 /// solution by querying variables after a call to Solve(): all the
875 /// information will be lost. In order to do something with the solution, the
876 /// user must either:
877 ///
878 /// * Use a search monitor that can process such a leaf. See, in particular,
879 /// the SolutionCollector class.
880 /// * Do not use Solve. Instead, use the more fine-grained approach using
881 /// methods NewSearch(...), NextSolution(), and EndSearch().
882 ///
883 /// @param db The decision builder that will generate the search tree.
884 /// @param monitors A vector of search monitors that will be notified of
885 /// various events during the search. In their reaction to these events, such
886 /// monitors may influence the search.
887 bool Solve(DecisionBuilder* const db,
888 const std::vector<SearchMonitor*>& monitors);
889 bool Solve(DecisionBuilder* const db);
890 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1);
891 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
892 SearchMonitor* const m2);
893 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
894 SearchMonitor* const m2, SearchMonitor* const m3);
895 bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
896 SearchMonitor* const m2, SearchMonitor* const m3,
897 SearchMonitor* const m4);
898 /// @}
899
900 /// @{
901 /// Decomposed search.
902 /// The code for a top level search should look like
903 /// solver->NewSearch(db);
904 /// while (solver->NextSolution()) {
905 /// //.. use the current solution
906 /// }
907 /// solver()->EndSearch();
908
909 void NewSearch(DecisionBuilder* const db,
910 const std::vector<SearchMonitor*>& monitors);
911 void NewSearch(DecisionBuilder* const db);
912 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1);
913 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
914 SearchMonitor* const m2);
915 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
916 SearchMonitor* const m2, SearchMonitor* const m3);
917 void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
918 SearchMonitor* const m2, SearchMonitor* const m3,
919 SearchMonitor* const m4);
920
921 bool NextSolution();
922 void RestartSearch();
923 void EndSearch();
924 /// @}
925
926 /// SolveAndCommit using a decision builder and up to three
927 /// search monitors, usually one for the objective, one for the limits
928 /// and one to collect solutions.
929 ///
930 /// The difference between a SolveAndCommit() and a Solve() method
931 /// call is the fact that SolveAndCommit will not backtrack all
932 /// modifications at the end of the search. This method is only
933 /// usable during the Next() method of a decision builder.
934 bool SolveAndCommit(DecisionBuilder* const db,
935 const std::vector<SearchMonitor*>& monitors);
936 bool SolveAndCommit(DecisionBuilder* const db);
937 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1);
938 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
939 SearchMonitor* const m2);
940 bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
941 SearchMonitor* const m2, SearchMonitor* const m3);
942
943 /// Checks whether the given assignment satisfies all relevant constraints.
944 bool CheckAssignment(Assignment* const solution);
945
946 /// Checks whether adding this constraint will lead to an immediate
947 /// failure. It will return false if the model is already inconsistent, or if
948 /// adding the constraint makes it inconsistent.
949 bool CheckConstraint(Constraint* const ct);
950
951 /// State of the solver.
state()952 SolverState state() const { return state_; }
953
954 /// Abandon the current branch in the search tree. A backtrack will follow.
955 void Fail();
956
957 #if !defined(SWIG)
958 /// When SaveValue() is not the best way to go, one can create a reversible
959 /// action that will be called upon backtrack. The "fast" parameter
960 /// indicates whether we need restore all values saved through SaveValue()
961 /// before calling this method.
962 void AddBacktrackAction(Action a, bool fast);
963 #endif /// !defined(SWIG)
964
965 /// misc debug string.
966 std::string DebugString() const;
967
968 /// Current memory usage in bytes
969 static int64_t MemoryUsage();
970
971 /// The 'absolute time' as seen by the solver. Unless a user-provided clock
972 /// was injected via SetClock() (eg. for unit tests), this is a real walltime,
973 /// shifted so that it was 0 at construction. All so-called "walltime" limits
974 /// are relative to this time.
975 absl::Time Now() const;
976
977 /// DEPRECATED: Use Now() instead.
978 /// Time elapsed, in ms since the creation of the solver.
979 int64_t wall_time() const;
980
981 /// The number of branches explored since the creation of the solver.
branches()982 int64_t branches() const { return branches_; }
983
984 /// The number of solutions found since the start of the search.
985 int64_t solutions() const;
986
987 /// The number of unchecked solutions found by local search.
988 int64_t unchecked_solutions() const;
989
990 /// The number of demons executed during search for a given priority.
demon_runs(DemonPriority p)991 int64_t demon_runs(DemonPriority p) const { return demon_runs_[p]; }
992
993 /// The number of failures encountered since the creation of the solver.
failures()994 int64_t failures() const { return fails_; }
995
996 /// The number of neighbors created.
neighbors()997 int64_t neighbors() const { return neighbors_; }
998
999 /// The number of filtered neighbors (neighbors accepted by filters).
filtered_neighbors()1000 int64_t filtered_neighbors() const { return filtered_neighbors_; }
1001
1002 /// The number of accepted neighbors.
accepted_neighbors()1003 int64_t accepted_neighbors() const { return accepted_neighbors_; }
1004
1005 /// The stamp indicates how many moves in the search tree we have performed.
1006 /// It is useful to detect if we need to update same lazy structures.
1007 uint64_t stamp() const;
1008
1009 /// The fail_stamp() is incremented after each backtrack.
1010 uint64_t fail_stamp() const;
1011
1012 /// The direction of optimization, getter and setter.
optimization_direction()1013 OptimizationDirection optimization_direction() const {
1014 return optimization_direction_;
1015 }
set_optimization_direction(OptimizationDirection direction)1016 void set_optimization_direction(OptimizationDirection direction) {
1017 optimization_direction_ = direction;
1018 }
1019
1020 // All factories (MakeXXX methods) encapsulate creation of objects
1021 // through RevAlloc(). Hence, the Solver used for allocating the
1022 // returned object will retain ownership of the allocated memory.
1023 // Destructors are called upon backtrack, or when the Solver is
1024 // itself destructed.
1025
1026 // ----- Int Variables and Constants -----
1027
1028 /// MakeIntVar will create the best range based int var for the bounds given.
1029 IntVar* MakeIntVar(int64_t min, int64_t max, const std::string& name);
1030
1031 /// MakeIntVar will create a variable with the given sparse domain.
1032 IntVar* MakeIntVar(const std::vector<int64_t>& values,
1033 const std::string& name);
1034
1035 /// MakeIntVar will create a variable with the given sparse domain.
1036 IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);
1037
1038 /// MakeIntVar will create the best range based int var for the bounds given.
1039 IntVar* MakeIntVar(int64_t min, int64_t max);
1040
1041 /// MakeIntVar will create a variable with the given sparse domain.
1042 IntVar* MakeIntVar(const std::vector<int64_t>& values);
1043
1044 /// MakeIntVar will create a variable with the given sparse domain.
1045 IntVar* MakeIntVar(const std::vector<int>& values);
1046
1047 /// MakeBoolVar will create a variable with a {0, 1} domain.
1048 IntVar* MakeBoolVar(const std::string& name);
1049
1050 /// MakeBoolVar will create a variable with a {0, 1} domain.
1051 IntVar* MakeBoolVar();
1052
1053 /// IntConst will create a constant expression.
1054 IntVar* MakeIntConst(int64_t val, const std::string& name);
1055
1056 /// IntConst will create a constant expression.
1057 IntVar* MakeIntConst(int64_t val);
1058
1059 /// This method will append the vector vars with 'var_count' variables
1060 /// having bounds vmin and vmax and having name "name<i>" where <i> is
1061 /// the index of the variable.
1062 void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1063 const std::string& name, std::vector<IntVar*>* vars);
1064 /// This method will append the vector vars with 'var_count' variables
1065 /// having bounds vmin and vmax and having no names.
1066 void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1067 std::vector<IntVar*>* vars);
1068 /// Same but allocates an array and returns it.
1069 IntVar** MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1070 const std::string& name);
1071
1072 /// This method will append the vector vars with 'var_count' boolean
1073 /// variables having name "name<i>" where <i> is the index of the
1074 /// variable.
1075 void MakeBoolVarArray(int var_count, const std::string& name,
1076 std::vector<IntVar*>* vars);
1077 /// This method will append the vector vars with 'var_count' boolean
1078 /// variables having no names.
1079 void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
1080 /// Same but allocates an array and returns it.
1081 IntVar** MakeBoolVarArray(int var_count, const std::string& name);
1082
1083 // ----- Integer Expressions -----
1084
1085 /// left + right.
1086 IntExpr* MakeSum(IntExpr* const left, IntExpr* const right);
1087 /// expr + value.
1088 IntExpr* MakeSum(IntExpr* const expr, int64_t value);
1089 /// sum of all vars.
1090 IntExpr* MakeSum(const std::vector<IntVar*>& vars);
1091
1092 /// scalar product
1093 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1094 const std::vector<int64_t>& coefs);
1095 /// scalar product
1096 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1097 const std::vector<int>& coefs);
1098
1099 /// left - right
1100 IntExpr* MakeDifference(IntExpr* const left, IntExpr* const right);
1101 /// value - expr
1102 IntExpr* MakeDifference(int64_t value, IntExpr* const expr);
1103 /// -expr
1104 IntExpr* MakeOpposite(IntExpr* const expr);
1105
1106 /// left * right
1107 IntExpr* MakeProd(IntExpr* const left, IntExpr* const right);
1108 /// expr * value
1109 IntExpr* MakeProd(IntExpr* const expr, int64_t value);
1110
1111 /// expr / value (integer division)
1112 IntExpr* MakeDiv(IntExpr* const expr, int64_t value);
1113 /// numerator / denominator (integer division). Terms need to be positive.
1114 IntExpr* MakeDiv(IntExpr* const numerator, IntExpr* const denominator);
1115
1116 /// |expr|
1117 IntExpr* MakeAbs(IntExpr* const expr);
1118 /// expr * expr
1119 IntExpr* MakeSquare(IntExpr* const expr);
1120 /// expr ^ n (n > 0)
1121 IntExpr* MakePower(IntExpr* const expr, int64_t n);
1122
1123 /// values[index]
1124 IntExpr* MakeElement(const std::vector<int64_t>& values, IntVar* const index);
1125 /// values[index]
1126 IntExpr* MakeElement(const std::vector<int>& values, IntVar* const index);
1127
1128 /// Function-based element. The constraint takes ownership of the
1129 /// callback. The callback must be able to cope with any possible
1130 /// value in the domain of 'index' (potentially negative ones too).
1131 IntExpr* MakeElement(IndexEvaluator1 values, IntVar* const index);
1132 /// Function based element. The constraint takes ownership of the
1133 /// callback. The callback must be monotonic. It must be able to
1134 /// cope with any possible value in the domain of 'index'
1135 /// (potentially negative ones too). Furtermore, monotonicity is not
1136 /// checked. Thus giving a non-monotonic function, or specifying an
1137 /// incorrect increasing parameter will result in undefined behavior.
1138 IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
1139 IntVar* const index);
1140 /// 2D version of function-based element expression, values(expr1, expr2).
1141 IntExpr* MakeElement(IndexEvaluator2 values, IntVar* const index1,
1142 IntVar* const index2);
1143
1144 /// vars[expr]
1145 IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* const index);
1146
1147 #if !defined(SWIG)
1148 /// vars(argument)
1149 IntExpr* MakeElement(Int64ToIntVar vars, int64_t range_start,
1150 int64_t range_end, IntVar* argument);
1151 #endif // SWIG
1152
1153 /// Returns the expression expr such that vars[expr] == value.
1154 /// It assumes that vars are all different.
1155 IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64_t value);
1156
1157 /// Special cases with arrays of size two.
1158 Constraint* MakeIfThenElseCt(IntVar* const condition,
1159 IntExpr* const then_expr,
1160 IntExpr* const else_expr,
1161 IntVar* const target_var);
1162
1163 /// std::min(vars)
1164 IntExpr* MakeMin(const std::vector<IntVar*>& vars);
1165 /// std::min (left, right)
1166 IntExpr* MakeMin(IntExpr* const left, IntExpr* const right);
1167 /// std::min(expr, value)
1168 IntExpr* MakeMin(IntExpr* const expr, int64_t value);
1169 /// std::min(expr, value)
1170 IntExpr* MakeMin(IntExpr* const expr, int value);
1171
1172 /// std::max(vars)
1173 IntExpr* MakeMax(const std::vector<IntVar*>& vars);
1174 /// std::max(left, right)
1175 IntExpr* MakeMax(IntExpr* const left, IntExpr* const right);
1176 /// std::max(expr, value)
1177 IntExpr* MakeMax(IntExpr* const expr, int64_t value);
1178 /// std::max(expr, value)
1179 IntExpr* MakeMax(IntExpr* const expr, int value);
1180
1181 /// Convex piecewise function.
1182 IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64_t early_cost,
1183 int64_t early_date, int64_t late_date,
1184 int64_t late_cost);
1185
1186 /// Semi continuous Expression (x <= 0 -> f(x) = 0; x > 0 -> f(x) = ax + b)
1187 /// a >= 0 and b >= 0
1188 IntExpr* MakeSemiContinuousExpr(IntExpr* const expr, int64_t fixed_charge,
1189 int64_t step);
1190
1191 /// General piecewise-linear function expression, built from f(x) where f is
1192 /// piecewise-linear. The resulting expression is f(expr).
1193 // TODO(user): Investigate if we can merge all three piecewise linear
1194 /// expressions.
1195 #ifndef SWIG
1196 IntExpr* MakePiecewiseLinearExpr(IntExpr* expr,
1197 const PiecewiseLinearFunction& f);
1198 #endif
1199
1200 /// Modulo expression x % mod (with the python convention for modulo).
1201 IntExpr* MakeModulo(IntExpr* const x, int64_t mod);
1202
1203 /// Modulo expression x % mod (with the python convention for modulo).
1204 IntExpr* MakeModulo(IntExpr* const x, IntExpr* const mod);
1205
1206 /// Conditional Expr condition ? expr : unperformed_value
1207 IntExpr* MakeConditionalExpression(IntVar* const condition,
1208 IntExpr* const expr,
1209 int64_t unperformed_value);
1210
1211 /// This constraint always succeeds.
1212 Constraint* MakeTrueConstraint();
1213 /// This constraint always fails.
1214 Constraint* MakeFalseConstraint();
1215 Constraint* MakeFalseConstraint(const std::string& explanation);
1216
1217 /// boolvar == (var == value)
1218 Constraint* MakeIsEqualCstCt(IntExpr* const var, int64_t value,
1219 IntVar* const boolvar);
1220 /// status var of (var == value)
1221 IntVar* MakeIsEqualCstVar(IntExpr* const var, int64_t value);
1222 /// b == (v1 == v2)
1223 Constraint* MakeIsEqualCt(IntExpr* const v1, IntExpr* v2, IntVar* const b);
1224 /// status var of (v1 == v2)
1225 IntVar* MakeIsEqualVar(IntExpr* const v1, IntExpr* v2);
1226 /// left == right
1227 Constraint* MakeEquality(IntExpr* const left, IntExpr* const right);
1228 /// expr == value
1229 Constraint* MakeEquality(IntExpr* const expr, int64_t value);
1230 /// expr == value
1231 Constraint* MakeEquality(IntExpr* const expr, int value);
1232
1233 /// boolvar == (var != value)
1234 Constraint* MakeIsDifferentCstCt(IntExpr* const var, int64_t value,
1235 IntVar* const boolvar);
1236 /// status var of (var != value)
1237 IntVar* MakeIsDifferentCstVar(IntExpr* const var, int64_t value);
1238 /// status var of (v1 != v2)
1239 IntVar* MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2);
1240 /// b == (v1 != v2)
1241 Constraint* MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
1242 IntVar* const b);
1243 /// left != right
1244 Constraint* MakeNonEquality(IntExpr* const left, IntExpr* const right);
1245 /// expr != value
1246 Constraint* MakeNonEquality(IntExpr* const expr, int64_t value);
1247 /// expr != value
1248 Constraint* MakeNonEquality(IntExpr* const expr, int value);
1249
1250 /// boolvar == (var <= value)
1251 Constraint* MakeIsLessOrEqualCstCt(IntExpr* const var, int64_t value,
1252 IntVar* const boolvar);
1253 /// status var of (var <= value)
1254 IntVar* MakeIsLessOrEqualCstVar(IntExpr* const var, int64_t value);
1255 /// status var of (left <= right)
1256 IntVar* MakeIsLessOrEqualVar(IntExpr* const left, IntExpr* const right);
1257 /// b == (left <= right)
1258 Constraint* MakeIsLessOrEqualCt(IntExpr* const left, IntExpr* const right,
1259 IntVar* const b);
1260 /// left <= right
1261 Constraint* MakeLessOrEqual(IntExpr* const left, IntExpr* const right);
1262 /// expr <= value
1263 Constraint* MakeLessOrEqual(IntExpr* const expr, int64_t value);
1264 /// expr <= value
1265 Constraint* MakeLessOrEqual(IntExpr* const expr, int value);
1266
1267 /// boolvar == (var >= value)
1268 Constraint* MakeIsGreaterOrEqualCstCt(IntExpr* const var, int64_t value,
1269 IntVar* const boolvar);
1270 /// status var of (var >= value)
1271 IntVar* MakeIsGreaterOrEqualCstVar(IntExpr* const var, int64_t value);
1272 /// status var of (left >= right)
1273 IntVar* MakeIsGreaterOrEqualVar(IntExpr* const left, IntExpr* const right);
1274 /// b == (left >= right)
1275 Constraint* MakeIsGreaterOrEqualCt(IntExpr* const left, IntExpr* const right,
1276 IntVar* const b);
1277 /// left >= right
1278 Constraint* MakeGreaterOrEqual(IntExpr* const left, IntExpr* const right);
1279 /// expr >= value
1280 Constraint* MakeGreaterOrEqual(IntExpr* const expr, int64_t value);
1281 /// expr >= value
1282 Constraint* MakeGreaterOrEqual(IntExpr* const expr, int value);
1283
1284 /// b == (v > c)
1285 Constraint* MakeIsGreaterCstCt(IntExpr* const v, int64_t c, IntVar* const b);
1286 /// status var of (var > value)
1287 IntVar* MakeIsGreaterCstVar(IntExpr* const var, int64_t value);
1288 /// status var of (left > right)
1289 IntVar* MakeIsGreaterVar(IntExpr* const left, IntExpr* const right);
1290 /// b == (left > right)
1291 Constraint* MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
1292 IntVar* const b);
1293 /// left > right
1294 Constraint* MakeGreater(IntExpr* const left, IntExpr* const right);
1295 /// expr > value
1296 Constraint* MakeGreater(IntExpr* const expr, int64_t value);
1297 /// expr > value
1298 Constraint* MakeGreater(IntExpr* const expr, int value);
1299
1300 /// b == (v < c)
1301 Constraint* MakeIsLessCstCt(IntExpr* const v, int64_t c, IntVar* const b);
1302 /// status var of (var < value)
1303 IntVar* MakeIsLessCstVar(IntExpr* const var, int64_t value);
1304 /// status var of (left < right)
1305 IntVar* MakeIsLessVar(IntExpr* const left, IntExpr* const right);
1306 /// b == (left < right)
1307 Constraint* MakeIsLessCt(IntExpr* const left, IntExpr* const right,
1308 IntVar* const b);
1309 /// left < right
1310 Constraint* MakeLess(IntExpr* const left, IntExpr* const right);
1311 /// expr < value
1312 Constraint* MakeLess(IntExpr* const expr, int64_t value);
1313 /// expr < value
1314 Constraint* MakeLess(IntExpr* const expr, int value);
1315
1316 /// Variation on arrays.
1317 Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64_t cst);
1318 Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
1319 int64_t cst);
1320 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64_t cst);
1321 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars,
1322 IntVar* const var);
1323 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1324 const std::vector<int64_t>& coefficients,
1325 int64_t cst);
1326 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1327 const std::vector<int>& coefficients,
1328 int64_t cst);
1329 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1330 const std::vector<int64_t>& coefficients,
1331 IntVar* const target);
1332 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1333 const std::vector<int>& coefficients,
1334 IntVar* const target);
1335 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1336 const std::vector<int64_t>& coeffs,
1337 int64_t cst);
1338 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1339 const std::vector<int>& coeffs,
1340 int64_t cst);
1341 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1342 const std::vector<int64_t>& coefficients,
1343 int64_t cst);
1344 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1345 const std::vector<int>& coefficients,
1346 int64_t cst);
1347
1348 Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
1349 IntVar* const min_var);
1350 Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
1351 IntVar* const max_var);
1352
1353 Constraint* MakeElementEquality(const std::vector<int64_t>& vals,
1354 IntVar* const index, IntVar* const target);
1355 Constraint* MakeElementEquality(const std::vector<int>& vals,
1356 IntVar* const index, IntVar* const target);
1357 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1358 IntVar* const index, IntVar* const target);
1359 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1360 IntVar* const index, int64_t target);
1361 /// Creates the constraint abs(var) == abs_var.
1362 Constraint* MakeAbsEquality(IntVar* const var, IntVar* const abs_var);
1363 /// This constraint is a special case of the element constraint with
1364 /// an array of integer variables, where the variables are all
1365 /// different and the index variable is constrained such that
1366 /// vars[index] == target.
1367 Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
1368 IntVar* const index, int64_t target);
1369
1370 /// This method is a specialized case of the MakeConstraintDemon
1371 /// method to call the InitiatePropagate of the constraint 'ct'.
1372 Demon* MakeConstraintInitialPropagateCallback(Constraint* const ct);
1373 /// This method is a specialized case of the MakeConstraintDemon
1374 /// method to call the InitiatePropagate of the constraint 'ct' with
1375 /// low priority.
1376 Demon* MakeDelayedConstraintInitialPropagateCallback(Constraint* const ct);
1377 #if !defined(SWIG)
1378 /// Creates a demon from a callback.
1379 Demon* MakeActionDemon(Action action);
1380 #endif /// !defined(SWIG)
1381 /// Creates a demon from a closure.
1382 Demon* MakeClosureDemon(Closure closure);
1383
1384 // ----- Between and related constraints -----
1385
1386 /// (l <= expr <= u)
1387 Constraint* MakeBetweenCt(IntExpr* const expr, int64_t l, int64_t u);
1388
1389 /// (expr < l || expr > u)
1390 /// This constraint is lazy as it will not make holes in the domain of
1391 /// variables. It will propagate only when expr->Min() >= l
1392 /// or expr->Max() <= u.
1393 Constraint* MakeNotBetweenCt(IntExpr* const expr, int64_t l, int64_t u);
1394
1395 /// b == (l <= expr <= u)
1396 Constraint* MakeIsBetweenCt(IntExpr* const expr, int64_t l, int64_t u,
1397 IntVar* const b);
1398 IntVar* MakeIsBetweenVar(IntExpr* const v, int64_t l, int64_t u);
1399
1400 // ----- Member and related constraints -----
1401
1402 /// expr in set. Propagation is lazy, i.e. this constraint does not
1403 /// creates holes in the domain of the variable.
1404 Constraint* MakeMemberCt(IntExpr* const expr,
1405 const std::vector<int64_t>& values);
1406 Constraint* MakeMemberCt(IntExpr* const expr, const std::vector<int>& values);
1407
1408 /// expr not in set.
1409 Constraint* MakeNotMemberCt(IntExpr* const expr,
1410 const std::vector<int64_t>& values);
1411 Constraint* MakeNotMemberCt(IntExpr* const expr,
1412 const std::vector<int>& values);
1413
1414 /// expr should not be in the list of forbidden intervals [start[i]..end[i]].
1415 Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int64_t> starts,
1416 std::vector<int64_t> ends);
1417 /// expr should not be in the list of forbidden intervals [start[i]..end[i]].
1418 Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int> starts,
1419 std::vector<int> ends);
1420 #if !defined(SWIG)
1421 /// expr should not be in the list of forbidden intervals.
1422 Constraint* MakeNotMemberCt(IntExpr* expr,
1423 SortedDisjointIntervalList intervals);
1424 #endif // !defined(SWIG)
1425
1426 /// boolvar == (expr in set)
1427 Constraint* MakeIsMemberCt(IntExpr* const expr,
1428 const std::vector<int64_t>& values,
1429 IntVar* const boolvar);
1430 Constraint* MakeIsMemberCt(IntExpr* const expr,
1431 const std::vector<int>& values,
1432 IntVar* const boolvar);
1433 IntVar* MakeIsMemberVar(IntExpr* const expr,
1434 const std::vector<int64_t>& values);
1435 IntVar* MakeIsMemberVar(IntExpr* const expr, const std::vector<int>& values);
1436
1437 /// |{i | vars[i] == value}| <= max_count
1438 Constraint* MakeAtMost(std::vector<IntVar*> vars, int64_t value,
1439 int64_t max_count);
1440 /// |{i | vars[i] == value}| == max_count
1441 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
1442 int64_t max_count);
1443 /// |{i | vars[i] == value}| == max_count
1444 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
1445 IntVar* const max_count);
1446
1447 /// Aggregated version of count: |{i | v[i] == values[j]}| == cards[j]
1448 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1449 const std::vector<int64_t>& values,
1450 const std::vector<IntVar*>& cards);
1451 /// Aggregated version of count: |{i | v[i] == values[j]}| == cards[j]
1452 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1453 const std::vector<int>& values,
1454 const std::vector<IntVar*>& cards);
1455 /// Aggregated version of count: |{i | v[i] == j}| == cards[j]
1456 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1457 const std::vector<IntVar*>& cards);
1458 /// Aggregated version of count with bounded cardinalities:
1459 /// forall j in 0 .. card_size - 1: card_min <= |{i | v[i] == j}| <= card_max
1460 Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64_t card_min,
1461 int64_t card_max, int64_t card_size);
1462 /// Aggregated version of count with bounded cardinalities:
1463 /// forall j in 0 .. card_size - 1:
1464 /// card_min[j] <= |{i | v[i] == j}| <= card_max[j]
1465 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1466 const std::vector<int64_t>& card_min,
1467 const std::vector<int64_t>& card_max);
1468 /// Aggregated version of count with bounded cardinalities:
1469 /// forall j in 0 .. card_size - 1:
1470 /// card_min[j] <= |{i | v[i] == j}| <= card_max[j]
1471 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1472 const std::vector<int>& card_min,
1473 const std::vector<int>& card_max);
1474 /// Aggregated version of count with bounded cardinalities:
1475 /// forall j in 0 .. card_size - 1:
1476 /// card_min[j] <= |{i | v[i] == values[j]}| <= card_max[j]
1477 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1478 const std::vector<int64_t>& values,
1479 const std::vector<int64_t>& card_min,
1480 const std::vector<int64_t>& card_max);
1481 /// Aggregated version of count with bounded cardinalities:
1482 /// forall j in 0 .. card_size - 1:
1483 /// card_min[j] <= |{i | v[i] == values[j]}| <= card_max[j]
1484 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1485 const std::vector<int>& values,
1486 const std::vector<int>& card_min,
1487 const std::vector<int>& card_max);
1488
1489 /// Deviation constraint:
1490 /// sum_i |n * vars[i] - total_sum| <= deviation_var and
1491 /// sum_i vars[i] == total_sum
1492 /// n = #vars
1493 Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
1494 IntVar* const deviation_var, int64_t total_sum);
1495
1496 /// All variables are pairwise different. This corresponds to the
1497 /// stronger version of the propagation algorithm.
1498 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);
1499
1500 /// All variables are pairwise different. If 'stronger_propagation'
1501 /// is true, stronger, and potentially slower propagation will
1502 /// occur. This API will be deprecated in the future.
1503 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
1504 bool stronger_propagation);
1505
1506 /// All variables are pairwise different, unless they are assigned to
1507 /// the escape value.
1508 Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
1509 int64_t escape_value);
1510 // TODO(user): Do we need a version with an array of escape values.
1511
1512 /// Creates a constraint binding the arrays of variables "vars" and
1513 /// "sorted_vars": sorted_vars[0] must be equal to the minimum of all
1514 /// variables in vars, and so on: the value of sorted_vars[i] must be
1515 /// equal to the i-th value of variables invars.
1516 ///
1517 /// This constraint propagates in both directions: from "vars" to
1518 /// "sorted_vars" and vice-versa.
1519 ///
1520 /// Behind the scenes, this constraint maintains that:
1521 /// - sorted is always increasing.
1522 /// - whatever the values of vars, there exists a permutation that
1523 /// injects its values into the sorted variables.
1524 ///
1525 /// For more info, please have a look at:
1526 /// https://mpi-inf.mpg.de/~mehlhorn/ftp/Mehlhorn-Thiel.pdf
1527 Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
1528 const std::vector<IntVar*>& sorted);
1529 // TODO(user): Add void MakeSortedArray(
1530 // const std::vector<IntVar*>& vars,
1531 // std::vector<IntVar*>* const sorted);
1532
1533 /// Creates a constraint that enforces that left is lexicographically less
1534 /// than right.
1535 Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
1536 const std::vector<IntVar*>& right);
1537
1538 /// Creates a constraint that enforces that left is lexicographically less
1539 /// than or equal to right.
1540 Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
1541 const std::vector<IntVar*>& right);
1542
1543 /// Creates a constraint that enforces that 'left' and 'right' both
1544 /// represent permutations of [0..left.size()-1], and that 'right' is
1545 /// the inverse permutation of 'left', i.e. for all i in
1546 /// [0..left.size()-1], right[left[i]] = i.
1547 Constraint* MakeInversePermutationConstraint(
1548 const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);
1549
1550 /// Creates a constraint that binds the index variable to the index of the
1551 /// first variable with the maximum value.
1552 Constraint* MakeIndexOfFirstMaxValueConstraint(
1553 IntVar* index, const std::vector<IntVar*>& vars);
1554
1555 /// Creates a constraint that binds the index variable to the index of the
1556 /// first variable with the minimum value.
1557 Constraint* MakeIndexOfFirstMinValueConstraint(
1558 IntVar* index, const std::vector<IntVar*>& vars);
1559
1560 /// Creates a constraint that states that all variables in the first
1561 /// vector are different from all variables in the second
1562 /// group. Thus the set of values in the first vector does not
1563 /// intersect with the set of values in the second vector.
1564 Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
1565 const std::vector<IntVar*>& second_vars);
1566
1567 /// Creates a constraint that states that all variables in the first
1568 /// vector are different from all variables from the second group,
1569 /// unless they are assigned to the escape value. Thus the set of
1570 /// values in the first vector minus the escape value does not
1571 /// intersect with the set of values in the second vector.
1572 Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
1573 const std::vector<IntVar*>& second_vars,
1574 int64_t escape_value);
1575
1576 // TODO(user): Implement MakeAllNullIntersect taking an array of
1577 // variable vectors.
1578
1579 /// Prevent cycles. The "nexts" variables represent the next in the chain.
1580 /// "active" variables indicate if the corresponding next variable is active;
1581 /// this could be useful to model unperformed nodes in a routing problem.
1582 /// A callback can be added to specify sink values (by default sink values
1583 /// are values >= vars.size()). Ownership of the callback is passed to the
1584 /// constraint.
1585 /// If assume_paths is either not specified or true, the constraint assumes
1586 /// the "nexts" variables represent paths (and performs a faster propagation);
1587 /// otherwise the constraint assumes they represent a forest.
1588 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1589 const std::vector<IntVar*>& active,
1590 IndexFilter1 sink_handler = nullptr);
1591 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1592 const std::vector<IntVar*>& active,
1593 IndexFilter1 sink_handler, bool assume_paths);
1594
1595 /// Force the "nexts" variable to create a complete Hamiltonian path.
1596 Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);
1597
1598 /// Force the "nexts" variable to create a complete Hamiltonian path
1599 /// for those that do not loop upon themselves.
1600 Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);
1601
1602 /// Creates a constraint which accumulates values along a path such that:
1603 /// cumuls[next[i]] = cumuls[i] + transits[i].
1604 /// Active variables indicate if the corresponding next variable is active;
1605 /// this could be useful to model unperformed nodes in a routing problem.
1606 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1607 const std::vector<IntVar*>& active,
1608 const std::vector<IntVar*>& cumuls,
1609 const std::vector<IntVar*>& transits);
1610 /// Delayed version of the same constraint: propagation on the nexts variables
1611 /// is delayed until all constraints have propagated.
1612 // TODO(user): Merge with other path-cumuls constraints.
1613 Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1614 const std::vector<IntVar*>& active,
1615 const std::vector<IntVar*>& cumuls,
1616 const std::vector<IntVar*>& transits);
1617 /// Creates a constraint which accumulates values along a path such that:
1618 /// cumuls[next[i]] = cumuls[i] + transit_evaluator(i, next[i]).
1619 /// Active variables indicate if the corresponding next variable is active;
1620 /// this could be useful to model unperformed nodes in a routing problem.
1621 /// Ownership of transit_evaluator is taken and it must be a repeatable
1622 /// callback.
1623 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1624 const std::vector<IntVar*>& active,
1625 const std::vector<IntVar*>& cumuls,
1626 IndexEvaluator2 transit_evaluator);
1627
1628 /// Creates a constraint which accumulates values along a path such that:
1629 /// cumuls[next[i]] = cumuls[i] + transit_evaluator(i, next[i]) + slacks[i].
1630 /// Active variables indicate if the corresponding next variable is active;
1631 /// this could be useful to model unperformed nodes in a routing problem.
1632 /// Ownership of transit_evaluator is taken and it must be a repeatable
1633 /// callback.
1634 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1635 const std::vector<IntVar*>& active,
1636 const std::vector<IntVar*>& cumuls,
1637 const std::vector<IntVar*>& slacks,
1638 IndexEvaluator2 transit_evaluator);
1639 /// Constraint enforcing that status[i] is true iff there's a path defined on
1640 /// next variables from sources[i] to sinks[i].
1641 // TODO(user): Only does checking on WhenBound events on next variables.
1642 /// Check whether more propagation is needed.
1643 Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1644 std::vector<int64_t> sources,
1645 std::vector<int64_t> sinks,
1646 std::vector<IntVar*> status);
1647 #ifndef SWIG
1648 /// Constraint enforcing, for each pair (i,j) in precedences, i to be before j
1649 /// in paths defined by next variables.
1650 // TODO(user): This constraint does not make holes in variable domains;
1651 /// the implementation can easily be modified to do that; evaluate the impact
1652 /// on models solved with local search.
1653 Constraint* MakePathPrecedenceConstraint(
1654 std::vector<IntVar*> nexts,
1655 const std::vector<std::pair<int, int>>& precedences);
1656 /// Same as MakePathPrecedenceConstraint but ensures precedence pairs on some
1657 /// paths follow a LIFO or FIFO order.
1658 /// LIFO order: given 2 pairs (a,b) and (c,d), if a is before c on the path
1659 /// then d must be before b or b must be before c.
1660 /// FIFO order: given 2 pairs (a,b) and (c,d), if a is before c on the path
1661 /// then b must be before d.
1662 /// LIFO (resp. FIFO) orders are enforced only on paths starting by indices in
1663 /// lifo_path_starts (resp. fifo_path_start).
1664 Constraint* MakePathPrecedenceConstraint(
1665 std::vector<IntVar*> nexts,
1666 const std::vector<std::pair<int, int>>& precedences,
1667 const std::vector<int>& lifo_path_starts,
1668 const std::vector<int>& fifo_path_starts);
1669 /// Same as MakePathPrecedenceConstraint but will force i to be before j if
1670 /// the sum of transits on the path from i to j is strictly positive.
1671 Constraint* MakePathTransitPrecedenceConstraint(
1672 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1673 const std::vector<std::pair<int, int>>& precedences);
1674 #endif // !SWIG
1675 /// This constraint maps the domain of 'var' onto the array of
1676 /// variables 'actives'. That is
1677 /// for all i in [0 .. size - 1]: actives[i] == 1 <=> var->Contains(i);
1678 Constraint* MakeMapDomain(IntVar* const var,
1679 const std::vector<IntVar*>& actives);
1680
1681 /// This method creates a constraint where the graph of the relation
1682 /// between the variables is given in extension. There are 'arity'
1683 /// variables involved in the relation and the graph is given by a
1684 /// integer tuple set.
1685 Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1686 const IntTupleSet& tuples);
1687
1688 /// This constraint create a finite automaton that will check the
1689 /// sequence of variables vars. It uses a transition table called
1690 /// 'transition_table'. Each transition is a triple
1691 /// (current_state, variable_value, new_state).
1692 /// The initial state is given, and the set of accepted states is decribed
1693 /// by 'final_states'. These states are hidden inside the constraint.
1694 /// Only the transitions (i.e. the variables) are visible.
1695 Constraint* MakeTransitionConstraint(
1696 const std::vector<IntVar*>& vars, const IntTupleSet& transition_table,
1697 int64_t initial_state, const std::vector<int64_t>& final_states);
1698
1699 /// This constraint create a finite automaton that will check the
1700 /// sequence of variables vars. It uses a transition table called
1701 /// 'transition_table'. Each transition is a triple
1702 /// (current_state, variable_value, new_state).
1703 /// The initial state is given, and the set of accepted states is decribed
1704 /// by 'final_states'. These states are hidden inside the constraint.
1705 /// Only the transitions (i.e. the variables) are visible.
1706 Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1707 const IntTupleSet& transition_table,
1708 int64_t initial_state,
1709 const std::vector<int>& final_states);
1710
1711 #if defined(SWIGPYTHON)
1712 /// Compatibility layer for Python API.
MakeAllowedAssignments(const std::vector<IntVar * > & vars,const std::vector<std::vector<int64_t>> & raw_tuples)1713 Constraint* MakeAllowedAssignments(
1714 const std::vector<IntVar*>& vars,
1715 const std::vector<std::vector<int64_t> /*keep for swig*/>& raw_tuples) {
1716 IntTupleSet tuples(vars.size());
1717 tuples.InsertAll(raw_tuples);
1718 return MakeAllowedAssignments(vars, tuples);
1719 }
1720
MakeTransitionConstraint(const std::vector<IntVar * > & vars,const std::vector<std::vector<int64_t>> & raw_transitions,int64_t initial_state,const std::vector<int> & final_states)1721 Constraint* MakeTransitionConstraint(
1722 const std::vector<IntVar*>& vars,
1723 const std::vector<std::vector<int64_t> /*keep for swig*/>&
1724 raw_transitions,
1725 int64_t initial_state, const std::vector<int>& final_states) {
1726 IntTupleSet transitions(3);
1727 transitions.InsertAll(raw_transitions);
1728 return MakeTransitionConstraint(vars, transitions, initial_state,
1729 final_states);
1730 }
1731 #endif
1732
1733 /// This constraint states that all the boxes must not overlap.
1734 /// The coordinates of box i are:
1735 /// (x_vars[i], y_vars[i]),
1736 /// (x_vars[i], y_vars[i] + y_size[i]),
1737 /// (x_vars[i] + x_size[i], y_vars[i]),
1738 /// (x_vars[i] + x_size[i], y_vars[i] + y_size[i]).
1739 /// The sizes must be non-negative. Boxes with a zero dimension can be
1740 /// pushed like any box.
1741 Constraint* MakeNonOverlappingBoxesConstraint(
1742 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1743 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1744 Constraint* MakeNonOverlappingBoxesConstraint(
1745 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1746 const std::vector<int64_t>& x_size, const std::vector<int64_t>& y_size);
1747 Constraint* MakeNonOverlappingBoxesConstraint(
1748 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1749 const std::vector<int>& x_size, const std::vector<int>& y_size);
1750
1751 /// This constraint states that all the boxes must not overlap.
1752 /// The coordinates of box i are:
1753 /// (x_vars[i], y_vars[i]),
1754 /// (x_vars[i], y_vars[i] + y_size[i]),
1755 /// (x_vars[i] + x_size[i], y_vars[i]),
1756 /// (x_vars[i] + x_size[i], y_vars[i] + y_size[i]).
1757 /// The sizes must be positive.
1758 /// Boxes with a zero dimension can be placed anywhere.
1759 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1760 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1761 const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1762 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1763 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1764 const std::vector<int64_t>& x_size, const std::vector<int64_t>& y_size);
1765 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1766 const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1767 const std::vector<int>& x_size, const std::vector<int>& y_size);
1768
1769 /// This constraint packs all variables onto 'number_of_bins'
1770 /// variables. For any given variable, a value of 'number_of_bins'
1771 /// indicates that the variable is not assigned to any bin.
1772 /// Dimensions, i.e., cumulative constraints on this packing, can be
1773 /// added directly from the pack class.
1774 Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);
1775
1776 /// Creates an interval var with a fixed duration. The duration must
1777 /// be greater than 0. If optional is true, then the interval can be
1778 /// performed or unperformed. If optional is false, then the interval
1779 /// is always performed.
1780 IntervalVar* MakeFixedDurationIntervalVar(int64_t start_min,
1781 int64_t start_max, int64_t duration,
1782 bool optional,
1783 const std::string& name);
1784
1785 /// This method fills the vector with 'count' interval variables built with
1786 /// the corresponding parameters.
1787 void MakeFixedDurationIntervalVarArray(
1788 int count, int64_t start_min, int64_t start_max, int64_t duration,
1789 bool optional, const std::string& name,
1790 std::vector<IntervalVar*>* const array);
1791
1792 /// Creates a performed interval var with a fixed duration. The duration must
1793 /// be greater than 0.
1794 IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1795 int64_t duration,
1796 const std::string& name);
1797
1798 /// Creates an interval var with a fixed duration, and performed_variable.
1799 /// The duration must be greater than 0.
1800 IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1801 int64_t duration,
1802 IntVar* const performed_variable,
1803 const std::string& name);
1804
1805 /// This method fills the vector with 'count' interval var built with
1806 /// the corresponding start variables.
1807 void MakeFixedDurationIntervalVarArray(
1808 const std::vector<IntVar*>& start_variables, int64_t duration,
1809 const std::string& name, std::vector<IntervalVar*>* const array);
1810
1811 /// This method fills the vector with interval variables built with
1812 /// the corresponding start variables.
1813 void MakeFixedDurationIntervalVarArray(
1814 const std::vector<IntVar*>& start_variables,
1815 const std::vector<int64_t>& durations, const std::string& name,
1816 std::vector<IntervalVar*>* const array);
1817 /// This method fills the vector with interval variables built with
1818 /// the corresponding start variables.
1819 void MakeFixedDurationIntervalVarArray(
1820 const std::vector<IntVar*>& start_variables,
1821 const std::vector<int>& durations, const std::string& name,
1822 std::vector<IntervalVar*>* const array);
1823
1824 /// This method fills the vector with interval variables built with
1825 /// the corresponding start and performed variables.
1826 void MakeFixedDurationIntervalVarArray(
1827 const std::vector<IntVar*>& start_variables,
1828 const std::vector<int64_t>& durations,
1829 const std::vector<IntVar*>& performed_variables, const std::string& name,
1830 std::vector<IntervalVar*>* const array);
1831
1832 /// This method fills the vector with interval variables built with
1833 /// the corresponding start and performed variables.
1834 void MakeFixedDurationIntervalVarArray(
1835 const std::vector<IntVar*>& start_variables,
1836 const std::vector<int>& durations,
1837 const std::vector<IntVar*>& performed_variables, const std::string& name,
1838 std::vector<IntervalVar*>* const array);
1839
1840 /// Creates a fixed and performed interval.
1841 IntervalVar* MakeFixedInterval(int64_t start, int64_t duration,
1842 const std::string& name);
1843
1844 /// Creates an interval var by specifying the bounds on start,
1845 /// duration, and end.
1846 IntervalVar* MakeIntervalVar(int64_t start_min, int64_t start_max,
1847 int64_t duration_min, int64_t duration_max,
1848 int64_t end_min, int64_t end_max, bool optional,
1849 const std::string& name);
1850
1851 /// This method fills the vector with 'count' interval var built with
1852 /// the corresponding parameters.
1853 void MakeIntervalVarArray(int count, int64_t start_min, int64_t start_max,
1854 int64_t duration_min, int64_t duration_max,
1855 int64_t end_min, int64_t end_max, bool optional,
1856 const std::string& name,
1857 std::vector<IntervalVar*>* const array);
1858
1859 /// Creates an interval var that is the mirror image of the given one, that
1860 /// is, the interval var obtained by reversing the axis.
1861 IntervalVar* MakeMirrorInterval(IntervalVar* const interval_var);
1862
1863 /// Creates an interval var with a fixed duration whose start is
1864 /// synchronized with the start of another interval, with a given
1865 /// offset. The performed status is also in sync with the performed
1866 /// status of the given interval variable.
1867 IntervalVar* MakeFixedDurationStartSyncedOnStartIntervalVar(
1868 IntervalVar* const interval_var, int64_t duration, int64_t offset);
1869
1870 /// Creates an interval var with a fixed duration whose start is
1871 /// synchronized with the end of another interval, with a given
1872 /// offset. The performed status is also in sync with the performed
1873 /// status of the given interval variable.
1874 IntervalVar* MakeFixedDurationStartSyncedOnEndIntervalVar(
1875 IntervalVar* const interval_var, int64_t duration, int64_t offset);
1876
1877 /// Creates an interval var with a fixed duration whose end is
1878 /// synchronized with the start of another interval, with a given
1879 /// offset. The performed status is also in sync with the performed
1880 /// status of the given interval variable.
1881 IntervalVar* MakeFixedDurationEndSyncedOnStartIntervalVar(
1882 IntervalVar* const interval_var, int64_t duration, int64_t offset);
1883
1884 /// Creates an interval var with a fixed duration whose end is
1885 /// synchronized with the end of another interval, with a given
1886 /// offset. The performed status is also in sync with the performed
1887 /// status of the given interval variable.
1888 IntervalVar* MakeFixedDurationEndSyncedOnEndIntervalVar(
1889 IntervalVar* const interval_var, int64_t duration, int64_t offset);
1890
1891 /// Creates and returns an interval variable that wraps around the given one,
1892 /// relaxing the min start and end. Relaxing means making unbounded when
1893 /// optional. If the variable is non-optional, this method returns
1894 /// interval_var.
1895 ///
1896 /// More precisely, such an interval variable behaves as follows:
1897 /// * When the underlying must be performed, the returned interval variable
1898 /// behaves exactly as the underlying;
1899 /// * When the underlying may or may not be performed, the returned interval
1900 /// variable behaves like the underlying, except that it is unbounded on
1901 /// the min side;
1902 /// * When the underlying cannot be performed, the returned interval variable
1903 /// is of duration 0 and must be performed in an interval unbounded on
1904 /// both sides.
1905 ///
1906 /// This is very useful to implement propagators that may only modify
1907 /// the start max or end max.
1908 IntervalVar* MakeIntervalRelaxedMin(IntervalVar* const interval_var);
1909
1910 /// Creates and returns an interval variable that wraps around the given one,
1911 /// relaxing the max start and end. Relaxing means making unbounded when
1912 /// optional. If the variable is non optional, this method returns
1913 /// interval_var.
1914 ///
1915 /// More precisely, such an interval variable behaves as follows:
1916 /// * When the underlying must be performed, the returned interval variable
1917 /// behaves exactly as the underlying;
1918 /// * When the underlying may or may not be performed, the returned interval
1919 /// variable behaves like the underlying, except that it is unbounded on
1920 /// the max side;
1921 /// * When the underlying cannot be performed, the returned interval variable
1922 /// is of duration 0 and must be performed in an interval unbounded on
1923 /// both sides.
1924 ///
1925 /// This is very useful for implementing propagators that may only modify
1926 /// the start min or end min.
1927 IntervalVar* MakeIntervalRelaxedMax(IntervalVar* const interval_var);
1928
1929 /// This method creates a relation between an interval var and a
1930 /// date.
1931 Constraint* MakeIntervalVarRelation(IntervalVar* const t,
1932 UnaryIntervalRelation r, int64_t d);
1933
1934 /// This method creates a relation between two interval vars.
1935 Constraint* MakeIntervalVarRelation(IntervalVar* const t1,
1936 BinaryIntervalRelation r,
1937 IntervalVar* const t2);
1938
1939 /// This method creates a relation between two interval vars.
1940 /// The given delay is added to the second interval.
1941 /// i.e.: t1 STARTS_AFTER_END of t2 with a delay of 2
1942 /// means t1 will start at least two units of time after the end of t2.
1943 Constraint* MakeIntervalVarRelationWithDelay(IntervalVar* const t1,
1944 BinaryIntervalRelation r,
1945 IntervalVar* const t2,
1946 int64_t delay);
1947
1948 /// This constraint implements a temporal disjunction between two
1949 /// interval vars t1 and t2. 'alt' indicates which alternative was
1950 /// chosen (alt == 0 is equivalent to t1 before t2).
1951 Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1952 IntervalVar* const t2, IntVar* const alt);
1953
1954 /// This constraint implements a temporal disjunction between two
1955 /// interval vars.
1956 Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1957 IntervalVar* const t2);
1958
1959 /// This constraint forces all interval vars into an non-overlapping
1960 /// sequence. Intervals with zero duration can be scheduled anywhere.
1961 DisjunctiveConstraint* MakeDisjunctiveConstraint(
1962 const std::vector<IntervalVar*>& intervals, const std::string& name);
1963
1964 /// This constraint forces all interval vars into an non-overlapping
1965 /// sequence. Intervals with zero durations cannot overlap with over
1966 /// intervals.
1967 DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
1968 const std::vector<IntervalVar*>& intervals, const std::string& name);
1969
1970 /// This constraint forces that, for any integer t, the sum of the demands
1971 /// corresponding to an interval containing t does not exceed the given
1972 /// capacity.
1973 ///
1974 /// Intervals and demands should be vectors of equal size.
1975 ///
1976 /// Demands should only contain non-negative values. Zero values are
1977 /// supported, and the corresponding intervals are filtered out, as they
1978 /// neither impact nor are impacted by this constraint.
1979 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1980 const std::vector<int64_t>& demands,
1981 int64_t capacity, const std::string& name);
1982
1983 /// This constraint forces that, for any integer t, the sum of the demands
1984 /// corresponding to an interval containing t does not exceed the given
1985 /// capacity.
1986 ///
1987 /// Intervals and demands should be vectors of equal size.
1988 ///
1989 /// Demands should only contain non-negative values. Zero values are
1990 /// supported, and the corresponding intervals are filtered out, as they
1991 /// neither impact nor are impacted by this constraint.
1992 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1993 const std::vector<int>& demands, int64_t capacity,
1994 const std::string& name);
1995
1996 /// This constraint forces that, for any integer t, the sum of the demands
1997 /// corresponding to an interval containing t does not exceed the given
1998 /// capacity.
1999 ///
2000 /// Intervals and demands should be vectors of equal size.
2001 ///
2002 /// Demands should only contain non-negative values. Zero values are
2003 /// supported, and the corresponding intervals are filtered out, as they
2004 /// neither impact nor are impacted by this constraint.
2005 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2006 const std::vector<int64_t>& demands,
2007 IntVar* const capacity, const std::string& name);
2008
2009 /// This constraint enforces that, for any integer t, the sum of the demands
2010 /// corresponding to an interval containing t does not exceed the given
2011 /// capacity.
2012 ///
2013 /// Intervals and demands should be vectors of equal size.
2014 ///
2015 /// Demands should only contain non-negative values. Zero values are
2016 /// supported, and the corresponding intervals are filtered out, as they
2017 /// neither impact nor are impacted by this constraint.
2018 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2019 const std::vector<int>& demands,
2020 IntVar* const capacity, const std::string& name);
2021
2022 /// This constraint enforces that, for any integer t, the sum of demands
2023 /// corresponding to an interval containing t does not exceed the given
2024 /// capacity.
2025 ///
2026 /// Intervals and demands should be vectors of equal size.
2027 ///
2028 /// Demands should be positive.
2029 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2030 const std::vector<IntVar*>& demands,
2031 int64_t capacity, const std::string& name);
2032
2033 /// This constraint enforces that, for any integer t, the sum of demands
2034 /// corresponding to an interval containing t does not exceed the given
2035 /// capacity.
2036 ///
2037 /// Intervals and demands should be vectors of equal size.
2038 ///
2039 /// Demands should be positive.
2040 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2041 const std::vector<IntVar*>& demands,
2042 IntVar* const capacity, const std::string& name);
2043
2044 /// This constraint states that the target_var is the convex hull of
2045 /// the intervals. If none of the interval variables is performed,
2046 /// then the target var is unperformed too. Also, if the target
2047 /// variable is unperformed, then all the intervals variables are
2048 /// unperformed too.
2049 Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
2050 IntervalVar* const target_var);
2051
2052 /// This constraints states that the two interval variables are equal.
2053 Constraint* MakeEquality(IntervalVar* const var1, IntervalVar* const var2);
2054
2055 /// This method creates an empty assignment.
2056 Assignment* MakeAssignment();
2057
2058 /// This method creates an assignment which is a copy of 'a'.
2059 Assignment* MakeAssignment(const Assignment* const a);
2060
2061 /// Collect the first solution of the search.
2062 SolutionCollector* MakeFirstSolutionCollector(
2063 const Assignment* const assignment);
2064 /// Collect the first solution of the search. The variables will need to
2065 /// be added later.
2066 SolutionCollector* MakeFirstSolutionCollector();
2067
2068 /// Collect the last solution of the search.
2069 SolutionCollector* MakeLastSolutionCollector(
2070 const Assignment* const assignment);
2071 /// Collect the last solution of the search. The variables will need to
2072 /// be added later.
2073 SolutionCollector* MakeLastSolutionCollector();
2074
2075 /// Collect the solution corresponding to the optimal value of the objective
2076 /// of 'assignment'; if 'assignment' does not have an objective no solution is
2077 /// collected. This collector only collects one solution corresponding to the
2078 /// best objective value (the first one found).
2079 SolutionCollector* MakeBestValueSolutionCollector(
2080 const Assignment* const assignment, bool maximize);
2081 /// Collect the solution corresponding to the optimal value of the
2082 /// objective of 'assignment'; if 'assignment' does not have an objective no
2083 /// solution is collected. This collector only collects one solution
2084 /// corresponding to the best objective value (the first one
2085 /// found). The variables will need to be added later.
2086 SolutionCollector* MakeBestValueSolutionCollector(bool maximize);
2087
2088 /// Same as MakeBestValueSolutionCollector but collects the best
2089 /// solution_count solutions. Collected solutions are sorted in increasing
2090 /// optimality order (the best solution is the last one).
2091 SolutionCollector* MakeNBestValueSolutionCollector(
2092 const Assignment* const assignment, int solution_count, bool maximize);
2093 SolutionCollector* MakeNBestValueSolutionCollector(int solution_count,
2094 bool maximize);
2095
2096 /// Collect all solutions of the search.
2097 SolutionCollector* MakeAllSolutionCollector(
2098 const Assignment* const assignment);
2099 /// Collect all solutions of the search. The variables will need to
2100 /// be added later.
2101 SolutionCollector* MakeAllSolutionCollector();
2102
2103 /// Creates a minimization objective.
2104 OptimizeVar* MakeMinimize(IntVar* const v, int64_t step);
2105
2106 /// Creates a maximization objective.
2107 OptimizeVar* MakeMaximize(IntVar* const v, int64_t step);
2108
2109 /// Creates a objective with a given sense (true = maximization).
2110 OptimizeVar* MakeOptimize(bool maximize, IntVar* const v, int64_t step);
2111
2112 /// Creates a minimization weighted objective. The actual objective is
2113 /// scalar_prod(sub_objectives, weights).
2114 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2115 const std::vector<int64_t>& weights,
2116 int64_t step);
2117
2118 /// Creates a minimization weighted objective. The actual objective is
2119 /// scalar_prod(sub_objectives, weights).
2120 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2121 const std::vector<int>& weights,
2122 int64_t step);
2123
2124 /// Creates a maximization weigthed objective.
2125 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2126 const std::vector<int64_t>& weights,
2127 int64_t step);
2128
2129 /// Creates a maximization weigthed objective.
2130 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2131 const std::vector<int>& weights,
2132 int64_t step);
2133
2134 /// Creates a weighted objective with a given sense (true = maximization).
2135 OptimizeVar* MakeWeightedOptimize(bool maximize,
2136 const std::vector<IntVar*>& sub_objectives,
2137 const std::vector<int64_t>& weights,
2138 int64_t step);
2139
2140 /// Creates a weighted objective with a given sense (true = maximization).
2141 OptimizeVar* MakeWeightedOptimize(bool maximize,
2142 const std::vector<IntVar*>& sub_objectives,
2143 const std::vector<int>& weights,
2144 int64_t step);
2145
2146 /// MetaHeuristics which try to get the search out of local optima.
2147
2148 /// Creates a Tabu Search monitor.
2149 /// In the context of local search the behavior is similar to MakeOptimize(),
2150 /// creating an objective in a given sense. The behavior differs once a local
2151 /// optimum is reached: thereafter solutions which degrade the value of the
2152 /// objective are allowed if they are not "tabu". A solution is "tabu" if it
2153 /// doesn't respect the following rules:
2154 /// - improving the best solution found so far
2155 /// - variables in the "keep" list must keep their value, variables in the
2156 /// "forbid" list must not take the value they have in the list.
2157 /// Variables with new values enter the tabu lists after each new solution
2158 /// found and leave the lists after a given number of iterations (called
2159 /// tenure). Only the variables passed to the method can enter the lists.
2160 /// The tabu criterion is softened by the tabu factor which gives the number
2161 /// of "tabu" violations which is tolerated; a factor of 1 means no violations
2162 /// allowed; a factor of 0 means all violations are allowed.
2163
2164 SearchMonitor* MakeTabuSearch(bool maximize, IntVar* const v, int64_t step,
2165 const std::vector<IntVar*>& vars,
2166 int64_t keep_tenure, int64_t forbid_tenure,
2167 double tabu_factor);
2168
2169 /// Creates a Tabu Search based on the vars |vars|.
2170 /// A solution is "tabu" if all the vars in |vars| keep their value.
2171 SearchMonitor* MakeGenericTabuSearch(bool maximize, IntVar* const v,
2172 int64_t step,
2173 const std::vector<IntVar*>& tabu_vars,
2174 int64_t forbid_tenure);
2175
2176 /// Creates a Simulated Annealing monitor.
2177 // TODO(user): document behavior
2178 SearchMonitor* MakeSimulatedAnnealing(bool maximize, IntVar* const v,
2179 int64_t step,
2180 int64_t initial_temperature);
2181
2182 /// Creates a Guided Local Search monitor.
2183 /// Description here: http://en.wikipedia.org/wiki/Guided_Local_Search
2184 SearchMonitor* MakeGuidedLocalSearch(bool maximize, IntVar* const objective,
2185 IndexEvaluator2 objective_function,
2186 int64_t step,
2187 const std::vector<IntVar*>& vars,
2188 double penalty_factor);
2189 SearchMonitor* MakeGuidedLocalSearch(
2190 bool maximize, IntVar* const objective,
2191 IndexEvaluator3 objective_function, int64_t step,
2192 const std::vector<IntVar*>& vars,
2193 const std::vector<IntVar*>& secondary_vars, double penalty_factor);
2194
2195 /// This search monitor will restart the search periodically.
2196 /// At the iteration n, it will restart after scale_factor * Luby(n) failures
2197 /// where Luby is the Luby Strategy (i.e. 1 1 2 1 1 2 4 1 1 2 1 1 2 4 8...).
2198 SearchMonitor* MakeLubyRestart(int scale_factor);
2199
2200 /// This search monitor will restart the search periodically after 'frequency'
2201 /// failures.
2202 SearchMonitor* MakeConstantRestart(int frequency);
2203
2204 /// Creates a search limit that constrains the running time.
2205 ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(absl::Duration time);
2206 #if !defined(SWIG)
2207 ABSL_DEPRECATED("Use the version taking absl::Duration() as argument")
2208 #endif // !defined(SWIG)
MakeTimeLimit(int64_t time_in_ms)2209 ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(int64_t time_in_ms) {
2210 return MakeTimeLimit(time_in_ms == kint64max
2211 ? absl::InfiniteDuration()
2212 : absl::Milliseconds(time_in_ms));
2213 }
2214
2215 /// Creates a search limit that constrains the number of branches
2216 /// explored in the search tree.
2217 ABSL_MUST_USE_RESULT RegularLimit* MakeBranchesLimit(int64_t branches);
2218
2219 /// Creates a search limit that constrains the number of failures
2220 /// that can happen when exploring the search tree.
2221 ABSL_MUST_USE_RESULT RegularLimit* MakeFailuresLimit(int64_t failures);
2222
2223 /// Creates a search limit that constrains the number of solutions found
2224 /// during the search.
2225 ABSL_MUST_USE_RESULT RegularLimit* MakeSolutionsLimit(int64_t solutions);
2226
2227 /// Limits the search with the 'time', 'branches', 'failures' and
2228 /// 'solutions' limits. 'smart_time_check' reduces the calls to the wall
2229 // timer by estimating the number of remaining calls, and 'cumulative' means
2230 // that the limit applies cumulatively, instead of search-by-search.
2231 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(absl::Duration time,
2232 int64_t branches,
2233 int64_t failures,
2234 int64_t solutions,
2235 bool smart_time_check = false,
2236 bool cumulative = false);
2237 /// Creates a search limit from its protobuf description
2238 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(
2239 const RegularLimitParameters& proto);
2240
2241 #if !defined(SWIG)
2242 ABSL_DEPRECATED("Use other MakeLimit() versions")
2243 #endif // !defined(SWIG)
2244 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(int64_t time, int64_t branches,
2245 int64_t failures,
2246 int64_t solutions,
2247 bool smart_time_check = false,
2248 bool cumulative = false);
2249
2250 /// Creates a regular limit proto containing default values.
2251 RegularLimitParameters MakeDefaultRegularLimitParameters() const;
2252
2253 /// Creates a search limit that is reached when either of the underlying limit
2254 /// is reached. That is, the returned limit is more stringent than both
2255 /// argument limits.
2256 ABSL_MUST_USE_RESULT SearchLimit* MakeLimit(SearchLimit* const limit_1,
2257 SearchLimit* const limit_2);
2258
2259 /// Limits the search based on the improvements of 'objective_var'. Stops the
2260 /// search when the improvement rate gets lower than a threshold value. This
2261 /// threshold value is computed based on the improvement rate during the first
2262 /// phase of the search.
2263 ABSL_MUST_USE_RESULT ImprovementSearchLimit* MakeImprovementLimit(
2264 IntVar* objective_var, bool maximize, double objective_scaling_factor,
2265 double objective_offset, double improvement_rate_coefficient,
2266 int improvement_rate_solutions_distance);
2267
2268 /// Callback-based search limit. Search stops when limiter returns true; if
2269 /// this happens at a leaf the corresponding solution will be rejected.
2270 ABSL_MUST_USE_RESULT SearchLimit* MakeCustomLimit(
2271 std::function<bool()> limiter);
2272
2273 // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).
2274
2275 /// The SearchMonitors below will display a periodic search log
2276 /// on LOG(INFO) every branch_period branches explored.
2277 SearchMonitor* MakeSearchLog(int branch_period);
2278
2279 /// At each solution, this monitor also display the var value.
2280 SearchMonitor* MakeSearchLog(int branch_period, IntVar* const var);
2281
2282 /// At each solution, this monitor will also display result of @p
2283 /// display_callback.
2284 SearchMonitor* MakeSearchLog(int branch_period,
2285 std::function<std::string()> display_callback);
2286
2287 /// At each solution, this monitor will display the 'var' value and the
2288 /// result of @p display_callback.
2289 SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
2290 std::function<std::string()> display_callback);
2291
2292 /// OptimizeVar Search Logs
2293 /// At each solution, this monitor will also display the 'opt_var' value.
2294 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var);
2295
2296 /// Creates a search monitor that will also print the result of the
2297 /// display callback.
2298 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var,
2299 std::function<std::string()> display_callback);
2300
2301 /// Creates a search monitor from logging parameters.
2302 struct SearchLogParameters {
2303 /// SearchMonitors will display a periodic search log every branch_period
2304 /// branches explored.
2305 int branch_period = 1;
2306 /// SearchMonitors will display values of objective or variable (both cannot
2307 /// be used together).
2308 OptimizeVar* objective = nullptr;
2309 IntVar* variable = nullptr;
2310 /// When displayed, objective or var values will be scaled and offset by
2311 /// the given values in the following way:
2312 /// scaling_factor * (value + offset).
2313 double scaling_factor = 1.0;
2314 double offset = 0;
2315 /// SearchMonitors will display the result of display_callback at each new
2316 /// solution found and when the search finishes if
2317 /// display_on_new_solutions_only is false.
2318 std::function<std::string()> display_callback;
2319 /// To be used to protect from cases where display_callback assumes
2320 /// variables are instantiated, which only happens in AtSolution().
2321 bool display_on_new_solutions_only = true;
2322 };
2323 SearchMonitor* MakeSearchLog(SearchLogParameters parameters);
2324
2325 /// Creates a search monitor that will trace precisely the behavior of the
2326 /// search. Use this only for low level debugging.
2327 SearchMonitor* MakeSearchTrace(const std::string& prefix);
2328
2329 /// ----- Callback-based search monitors -----
2330 SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
2331 SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
2332 SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);
2333
2334 /// Prints the model.
2335 ModelVisitor* MakePrintModelVisitor();
2336 /// Displays some nice statistics on the model.
2337 ModelVisitor* MakeStatisticsModelVisitor();
2338 #if !defined(SWIG)
2339 /// Compute the number of constraints a variable is attached to.
2340 ModelVisitor* MakeVariableDegreeVisitor(
2341 absl::flat_hash_map<const IntVar*, int>* const map);
2342 #endif // !defined(SWIG)
2343
2344 /// Symmetry Breaking.
2345 SearchMonitor* MakeSymmetryManager(
2346 const std::vector<SymmetryBreaker*>& visitors);
2347 SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1);
2348 SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2349 SymmetryBreaker* const v2);
2350 SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2351 SymmetryBreaker* const v2,
2352 SymmetryBreaker* const v3);
2353 SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2354 SymmetryBreaker* const v2,
2355 SymmetryBreaker* const v3,
2356 SymmetryBreaker* const v4);
2357
2358 /// Decisions.
2359 Decision* MakeAssignVariableValue(IntVar* const var, int64_t val);
2360 Decision* MakeVariableLessOrEqualValue(IntVar* const var, int64_t value);
2361 Decision* MakeVariableGreaterOrEqualValue(IntVar* const var, int64_t value);
2362 Decision* MakeSplitVariableDomain(IntVar* const var, int64_t val,
2363 bool start_with_lower_half);
2364 Decision* MakeAssignVariableValueOrFail(IntVar* const var, int64_t value);
2365 Decision* MakeAssignVariableValueOrDoNothing(IntVar* const var,
2366 int64_t value);
2367 Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
2368 const std::vector<int64_t>& values);
2369 Decision* MakeAssignVariablesValuesOrDoNothing(
2370 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values);
2371 Decision* MakeAssignVariablesValuesOrFail(const std::vector<IntVar*>& vars,
2372 const std::vector<int64_t>& values);
2373 Decision* MakeFailDecision();
2374 Decision* MakeDecision(Action apply, Action refute);
2375
2376 /// Creates a decision builder which sequentially composes decision builders.
2377 /// At each leaf of a decision builder, the next decision builder is therefore
2378 /// called. For instance, Compose(db1, db2) will result in the following tree:
2379 /// d1 tree |
2380 /// / | \ |
2381 /// db1 leaves |
2382 /// / | \ |
2383 /// db2 tree db2 tree db2 tree |
2384 DecisionBuilder* Compose(DecisionBuilder* const db1,
2385 DecisionBuilder* const db2);
2386 DecisionBuilder* Compose(DecisionBuilder* const db1,
2387 DecisionBuilder* const db2,
2388 DecisionBuilder* const db3);
2389 DecisionBuilder* Compose(DecisionBuilder* const db1,
2390 DecisionBuilder* const db2,
2391 DecisionBuilder* const db3,
2392 DecisionBuilder* const db4);
2393 DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);
2394
2395 /// Creates a decision builder which will create a search tree where each
2396 /// decision builder is called from the top of the search tree. For instance
2397 /// the decision builder Try(db1, db2) will entirely explore the search tree
2398 /// of db1 then the one of db2, resulting in the following search tree:
2399 /// Tree root |
2400 /// / \ |
2401 /// db1 tree db2 tree |
2402 ///
2403 /// This is very handy to try a decision builder which partially explores the
2404 /// search space and if it fails to try another decision builder.
2405 ///
2406 // TODO(user): The search tree can be balanced by using binary
2407 /// "Try"-builders "recursively". For instance, Try(a,b,c,d) will give a tree
2408 /// unbalanced to the right, whereas Try(Try(a,b), Try(b,c)) will give a
2409 /// balanced tree. Investigate if we should only provide the binary version
2410 /// and/or if we should balance automatically.
2411 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2);
2412 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2413 DecisionBuilder* const db3);
2414 DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2415 DecisionBuilder* const db3, DecisionBuilder* const db4);
2416 DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);
2417
2418 /// Phases on IntVar arrays.
2419 // TODO(user): name each of them differently, and document them (and do that
2420 /// for all other functions that have several homonyms in this .h).
2421 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2422 IntVarStrategy var_str, IntValueStrategy val_str);
2423 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2424 IndexEvaluator1 var_evaluator,
2425 IntValueStrategy val_str);
2426
2427 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2428 IntVarStrategy var_str,
2429 IndexEvaluator2 value_evaluator);
2430
2431 /// var_val1_val2_comparator(var, val1, val2) is true iff assigning value
2432 /// "val1" to variable "var" is better than assigning value "val2".
2433 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2434 IntVarStrategy var_str,
2435 VariableValueComparator var_val1_val2_comparator);
2436
2437 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2438 IndexEvaluator1 var_evaluator,
2439 IndexEvaluator2 value_evaluator);
2440
2441 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2442 IntVarStrategy var_str,
2443 IndexEvaluator2 value_evaluator,
2444 IndexEvaluator1 tie_breaker);
2445
2446 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2447 IndexEvaluator1 var_evaluator,
2448 IndexEvaluator2 value_evaluator,
2449 IndexEvaluator1 tie_breaker);
2450
2451 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
2452 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
2453 const DefaultPhaseParameters& parameters);
2454
2455 /// Shortcuts for small arrays.
2456 DecisionBuilder* MakePhase(IntVar* const v0, IntVarStrategy var_str,
2457 IntValueStrategy val_str);
2458 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2459 IntVarStrategy var_str, IntValueStrategy val_str);
2460 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2461 IntVar* const v2, IntVarStrategy var_str,
2462 IntValueStrategy val_str);
2463 DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2464 IntVar* const v2, IntVar* const v3,
2465 IntVarStrategy var_str, IntValueStrategy val_str);
2466
2467 /// Returns a decision that tries to schedule a task at a given time.
2468 /// On the Apply branch, it will set that interval var as performed and set
2469 /// its start to 'est'. On the Refute branch, it will just update the
2470 /// 'marker' to 'est' + 1. This decision is used in the
2471 /// INTERVAL_SET_TIMES_FORWARD strategy.
2472 Decision* MakeScheduleOrPostpone(IntervalVar* const var, int64_t est,
2473 int64_t* const marker);
2474
2475 /// Returns a decision that tries to schedule a task at a given time.
2476 /// On the Apply branch, it will set that interval var as performed and set
2477 /// its end to 'est'. On the Refute branch, it will just update the
2478 /// 'marker' to 'est' - 1. This decision is used in the
2479 /// INTERVAL_SET_TIMES_BACKWARD strategy.
2480 Decision* MakeScheduleOrExpedite(IntervalVar* const var, int64_t est,
2481 int64_t* const marker);
2482
2483 /// Returns a decision that tries to rank first the ith interval var
2484 /// in the sequence variable.
2485 Decision* MakeRankFirstInterval(SequenceVar* const sequence, int index);
2486
2487 /// Returns a decision that tries to rank last the ith interval var
2488 /// in the sequence variable.
2489 Decision* MakeRankLastInterval(SequenceVar* const sequence, int index);
2490
2491 /// Returns a decision builder which assigns values to variables which
2492 /// minimize the values returned by the evaluator. The arguments passed to the
2493 /// evaluator callback are the indices of the variables in vars and the values
2494 /// of these variables. Ownership of the callback is passed to the decision
2495 /// builder.
2496 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2497 IndexEvaluator2 eval, EvaluatorStrategy str);
2498
2499 /// Returns a decision builder which assigns values to variables
2500 /// which minimize the values returned by the evaluator. In case of
2501 /// tie breaks, the second callback is used to choose the best index
2502 /// in the array of equivalent pairs with equivalent evaluations. The
2503 /// arguments passed to the evaluator callback are the indices of the
2504 /// variables in vars and the values of these variables. Ownership of
2505 /// the callback is passed to the decision builder.
2506 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2507 IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2508 EvaluatorStrategy str);
2509
2510 /// Scheduling phases.
2511 DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
2512 IntervalStrategy str);
2513
2514 DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
2515 SequenceStrategy str);
2516
2517 /// Returns a decision builder for which the left-most leaf corresponds
2518 /// to assignment, the rest of the tree being explored using 'db'.
2519 DecisionBuilder* MakeDecisionBuilderFromAssignment(
2520 Assignment* const assignment, DecisionBuilder* const db,
2521 const std::vector<IntVar*>& vars);
2522
2523 /// Returns a decision builder that will add the given constraint to
2524 /// the model.
2525 DecisionBuilder* MakeConstraintAdder(Constraint* const ct);
2526
2527 /// SolveOnce will collapse a search tree described by a decision
2528 /// builder 'db' and a set of monitors and wrap it into a single point.
2529 /// If there are no solutions to this nested tree, then SolveOnce will
2530 /// fail. If there is a solution, it will find it and returns nullptr.
2531 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db);
2532 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2533 SearchMonitor* const monitor1);
2534 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2535 SearchMonitor* const monitor1,
2536 SearchMonitor* const monitor2);
2537 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2538 SearchMonitor* const monitor1,
2539 SearchMonitor* const monitor2,
2540 SearchMonitor* const monitor3);
2541 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2542 SearchMonitor* const monitor1,
2543 SearchMonitor* const monitor2,
2544 SearchMonitor* const monitor3,
2545 SearchMonitor* const monitor4);
2546 DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2547 const std::vector<SearchMonitor*>& monitors);
2548
2549 /// NestedOptimize will collapse a search tree described by a
2550 /// decision builder 'db' and a set of monitors and wrap it into a
2551 /// single point. If there are no solutions to this nested tree, then
2552 /// NestedOptimize will fail. If there are solutions, it will find
2553 /// the best as described by the mandatory objective in the solution
2554 /// as well as the optimization direction, instantiate all variables
2555 /// to this solution, and return nullptr.
2556 DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2557 Assignment* const solution, bool maximize,
2558 int64_t step);
2559 DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2560 Assignment* const solution, bool maximize,
2561 int64_t step,
2562 SearchMonitor* const monitor1);
2563 DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2564 Assignment* const solution, bool maximize,
2565 int64_t step,
2566 SearchMonitor* const monitor1,
2567 SearchMonitor* const monitor2);
2568 DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2569 Assignment* const solution, bool maximize,
2570 int64_t step,
2571 SearchMonitor* const monitor1,
2572 SearchMonitor* const monitor2,
2573 SearchMonitor* const monitor3);
2574 DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2575 Assignment* const solution, bool maximize,
2576 int64_t step,
2577 SearchMonitor* const monitor1,
2578 SearchMonitor* const monitor2,
2579 SearchMonitor* const monitor3,
2580 SearchMonitor* const monitor4);
2581 DecisionBuilder* MakeNestedOptimize(
2582 DecisionBuilder* const db, Assignment* const solution, bool maximize,
2583 int64_t step, const std::vector<SearchMonitor*>& monitors);
2584
2585 /// Returns a DecisionBuilder which restores an Assignment
2586 /// (calls void Assignment::Restore())
2587 DecisionBuilder* MakeRestoreAssignment(Assignment* assignment);
2588
2589 /// Returns a DecisionBuilder which stores an Assignment
2590 /// (calls void Assignment::Store())
2591 DecisionBuilder* MakeStoreAssignment(Assignment* assignment);
2592
2593 /// Local Search Operators.
2594 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2595 LocalSearchOperators op);
2596 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2597 const std::vector<IntVar*>& secondary_vars,
2598 LocalSearchOperators op);
2599 // TODO(user): Make the callback an IndexEvaluator2 when there are no
2600 // secondary variables.
2601 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2602 IndexEvaluator3 evaluator,
2603 EvaluatorLocalSearchOperators op);
2604 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2605 const std::vector<IntVar*>& secondary_vars,
2606 IndexEvaluator3 evaluator,
2607 EvaluatorLocalSearchOperators op);
2608
2609 /// Creates a large neighborhood search operator which creates fragments (set
2610 /// of relaxed variables) with up to number_of_variables random variables
2611 /// (sampling with replacement is performed meaning that at most
2612 /// number_of_variables variables are selected). Warning: this operator will
2613 /// always return neighbors; using it without a search limit will result in a
2614 /// non-ending search.
2615 /// Optionally a random seed can be specified.
2616 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2617 int number_of_variables);
2618 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2619 int number_of_variables,
2620 int32_t seed);
2621
2622 /// Creates a local search operator that tries to move the assignment of some
2623 /// variables toward a target. The target is given as an Assignment. This
2624 /// operator generates neighbors in which the only difference compared to the
2625 /// current state is that one variable that belongs to the target assignment
2626 /// is set to its target value.
2627 LocalSearchOperator* MakeMoveTowardTargetOperator(const Assignment& target);
2628
2629 /// Creates a local search operator that tries to move the assignment of some
2630 /// variables toward a target. The target is given either as two vectors: a
2631 /// vector of variables and a vector of associated target values. The two
2632 /// vectors should be of the same length. This operator generates neighbors in
2633 /// which the only difference compared to the current state is that one
2634 /// variable that belongs to the given vector is set to its target value.
2635 LocalSearchOperator* MakeMoveTowardTargetOperator(
2636 const std::vector<IntVar*>& variables,
2637 const std::vector<int64_t>& target_values);
2638
2639 /// Creates a local search operator which concatenates a vector of operators.
2640 /// Each operator from the vector is called sequentially. By default, when a
2641 /// neighbor is found the neighborhood exploration restarts from the last
2642 /// active operator (the one which produced the neighbor).
2643 /// This can be overridden by setting restart to true to force the exploration
2644 /// to start from the first operator in the vector.
2645 ///
2646 /// The default behavior can also be overridden using an evaluation callback
2647 /// to set the order in which the operators are explored (the callback is
2648 /// called in LocalSearchOperator::Start()). The first argument of the
2649 /// callback is the index of the operator which produced the last move, the
2650 /// second argument is the index of the operator to be evaluated. Ownership of
2651 /// the callback is taken by ConcatenateOperators.
2652 ///
2653 /// Example:
2654 ///
2655 /// const int kPriorities = {10, 100, 10, 0};
2656 /// int64_t Evaluate(int active_operator, int current_operator) {
2657 /// return kPriorities[current_operator];
2658 /// }
2659 ///
2660 /// LocalSearchOperator* concat =
2661 /// solver.ConcatenateOperators(operators,
2662 /// NewPermanentCallback(&Evaluate));
2663 ///
2664 /// The elements of the vector operators will be sorted by increasing priority
2665 /// and explored in that order (tie-breaks are handled by keeping the relative
2666 /// operator order in the vector). This would result in the following order:
2667 /// operators[3], operators[0], operators[2], operators[1].
2668 ///
2669 LocalSearchOperator* ConcatenateOperators(
2670 const std::vector<LocalSearchOperator*>& ops);
2671 LocalSearchOperator* ConcatenateOperators(
2672 const std::vector<LocalSearchOperator*>& ops, bool restart);
2673 LocalSearchOperator* ConcatenateOperators(
2674 const std::vector<LocalSearchOperator*>& ops,
2675 std::function<int64_t(int, int)> evaluator);
2676 /// Randomized version of local search concatenator; calls a random operator
2677 /// at each call to MakeNextNeighbor().
2678 LocalSearchOperator* RandomConcatenateOperators(
2679 const std::vector<LocalSearchOperator*>& ops);
2680
2681 /// Randomized version of local search concatenator; calls a random operator
2682 /// at each call to MakeNextNeighbor(). The provided seed is used to
2683 /// initialize the random number generator.
2684 LocalSearchOperator* RandomConcatenateOperators(
2685 const std::vector<LocalSearchOperator*>& ops, int32_t seed);
2686
2687 /// Creates a local search operator which concatenates a vector of operators.
2688 /// Uses Multi-Armed Bandit approach for choosing the next operator to use.
2689 /// Sorts operators based on Upper Confidence Bound Algorithm which evaluates
2690 /// each operator as sum of average improvement and exploration function.
2691 ///
2692 /// Updates the order of operators when accepts a neighbor with objective
2693 /// improvement.
2694 LocalSearchOperator* MultiArmedBanditConcatenateOperators(
2695 const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,
2696 double exploration_coefficient, bool maximize);
2697
2698 /// Creates a local search operator that wraps another local search
2699 /// operator and limits the number of neighbors explored (i.e., calls
2700 /// to MakeNextNeighbor from the current solution (between two calls
2701 /// to Start()). When this limit is reached, MakeNextNeighbor()
2702 /// returns false. The counter is cleared when Start() is called.
2703 LocalSearchOperator* MakeNeighborhoodLimit(LocalSearchOperator* const op,
2704 int64_t limit);
2705
2706 /// Local Search decision builders factories.
2707 /// Local search is used to improve a given solution. This initial solution
2708 /// can be specified either by an Assignment or by a DecisionBulder, and the
2709 /// corresponding variables, the initial solution being the first solution
2710 /// found by the DecisionBuilder.
2711 /// The LocalSearchPhaseParameters parameter holds the actual definition of
2712 /// the local search phase:
2713 /// - a local search operator used to explore the neighborhood of the current
2714 /// solution,
2715 /// - a decision builder to instantiate unbound variables once a neighbor has
2716 /// been defined; in the case of LNS-based operators instantiates fragment
2717 /// variables; search monitors can be added to this sub-search by wrapping
2718 /// the decision builder with MakeSolveOnce.
2719 /// - a search limit specifying how long local search looks for neighbors
2720 /// before accepting one; the last neighbor is always taken and in the case
2721 /// of a greedy search, this corresponds to the best local neighbor;
2722 /// first-accept (which is the default behavior) can be modeled using a
2723 /// solution found limit of 1,
2724 /// - a vector of local search filters used to speed up the search by pruning
2725 /// unfeasible neighbors.
2726 /// Metaheuristics can be added by defining specialized search monitors;
2727 /// currently down/up-hill climbing is available through OptimizeVar, as well
2728 /// as Guided Local Search, Tabu Search and Simulated Annealing.
2729 ///
2730 // TODO(user): Make a variant which runs a local search after each
2731 // solution found in a DFS.
2732
2733 DecisionBuilder* MakeLocalSearchPhase(
2734 Assignment* const assignment,
2735 LocalSearchPhaseParameters* const parameters);
2736 DecisionBuilder* MakeLocalSearchPhase(
2737 const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2738 LocalSearchPhaseParameters* const parameters);
2739 /// Variant with a sub_decison_builder specific to the first solution.
2740 DecisionBuilder* MakeLocalSearchPhase(
2741 const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2742 DecisionBuilder* const first_solution_sub_decision_builder,
2743 LocalSearchPhaseParameters* const parameters);
2744 DecisionBuilder* MakeLocalSearchPhase(
2745 const std::vector<SequenceVar*>& vars,
2746 DecisionBuilder* const first_solution,
2747 LocalSearchPhaseParameters* const parameters);
2748
2749 /// Solution Pool.
2750 SolutionPool* MakeDefaultSolutionPool();
2751
2752 /// Local Search Phase Parameters
2753 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2754 IntVar* objective, LocalSearchOperator* const ls_operator,
2755 DecisionBuilder* const sub_decision_builder);
2756 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2757 IntVar* objective, LocalSearchOperator* const ls_operator,
2758 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2759 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2760 IntVar* objective, LocalSearchOperator* const ls_operator,
2761 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2762 LocalSearchFilterManager* filter_manager);
2763
2764 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2765 IntVar* objective, SolutionPool* const pool,
2766 LocalSearchOperator* const ls_operator,
2767 DecisionBuilder* const sub_decision_builder);
2768 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2769 IntVar* objective, SolutionPool* const pool,
2770 LocalSearchOperator* const ls_operator,
2771 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2772 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2773 IntVar* objective, SolutionPool* const pool,
2774 LocalSearchOperator* const ls_operator,
2775 DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2776 LocalSearchFilterManager* filter_manager);
2777
2778 /// Local Search Filters
2779 LocalSearchFilter* MakeAcceptFilter();
2780 LocalSearchFilter* MakeRejectFilter();
2781 LocalSearchFilter* MakeVariableDomainFilter();
2782 IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2783 const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2784 Solver::LocalSearchFilterBound filter_enum);
2785 IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2786 const std::vector<IntVar*>& vars,
2787 const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2788 Solver::LocalSearchFilterBound filter_enum);
2789
2790 /// Performs PeriodicCheck on the top-level search; for instance, can be
2791 /// called from a nested solve to check top-level limits.
2792 void TopPeriodicCheck();
2793 /// Returns a percentage representing the propress of the search before
2794 /// reaching the limits of the top-level search (can be called from a nested
2795 /// solve).
2796 int TopProgressPercent();
2797
2798 /// The PushState and PopState methods manipulates the states
2799 /// of the reversible objects. They are visible only because they
2800 /// are useful to write unitary tests.
2801 void PushState();
2802 void PopState();
2803
2804 /// Gets the search depth of the current active search. Returns -1 if
2805 /// there is no active search opened.
2806 int SearchDepth() const;
2807
2808 /// Gets the search left depth of the current active search. Returns -1 if
2809 /// there is no active search opened.
2810 int SearchLeftDepth() const;
2811
2812 /// Gets the number of nested searches. It returns 0 outside search,
2813 /// 1 during the top level search, 2 or more in case of nested searches.
2814 int SolveDepth() const;
2815
2816 /// Sets the given branch selector on the current active search.
2817 void SetBranchSelector(BranchSelector bs);
2818
2819 /// Creates a decision builder that will set the branch selector.
2820 DecisionBuilder* MakeApplyBranchSelector(BranchSelector bs);
2821
2822 /// All-in-one SaveAndSetValue.
2823 template <class T>
SaveAndSetValue(T * adr,T val)2824 void SaveAndSetValue(T* adr, T val) {
2825 if (*adr != val) {
2826 InternalSaveValue(adr);
2827 *adr = val;
2828 }
2829 }
2830
2831 /// All-in-one SaveAndAdd_value.
2832 template <class T>
SaveAndAdd(T * adr,T val)2833 void SaveAndAdd(T* adr, T val) {
2834 if (val != 0) {
2835 InternalSaveValue(adr);
2836 (*adr) += val;
2837 }
2838 }
2839
2840 /// Returns a random value between 0 and 'size' - 1;
Rand64(int64_t size)2841 int64_t Rand64(int64_t size) {
2842 DCHECK_GT(size, 0);
2843 return absl::Uniform<int64_t>(random_, 0, size);
2844 }
2845
2846 /// Returns a random value between 0 and 'size' - 1;
Rand32(int32_t size)2847 int32_t Rand32(int32_t size) {
2848 DCHECK_GT(size, 0);
2849 return absl::Uniform<int32_t>(random_, 0, size);
2850 }
2851
2852 /// Reseed the solver random generator.
ReSeed(int32_t seed)2853 void ReSeed(int32_t seed) { random_.seed(seed); }
2854
2855 /// Exports the profiling information in a human readable overview.
2856 /// The parameter profile_level used to create the solver must be
2857 /// set to true.
2858 void ExportProfilingOverview(const std::string& filename);
2859
2860 /// Returns local search profiling information in a human readable format.
2861 // TODO(user): Merge demon and local search profiles.
2862 std::string LocalSearchProfile() const;
2863
2864 #if !defined(SWIG)
2865 /// Returns detailed cp search statistics.
2866 ConstraintSolverStatistics GetConstraintSolverStatistics() const;
2867 /// Returns detailed local search statistics.
2868 LocalSearchStatistics GetLocalSearchStatistics() const;
2869 #endif // !defined(SWIG)
2870
2871 /// Returns true whether the current search has been
2872 /// created using a Solve() call instead of a NewSearch one. It
2873 /// returns false if the solver is not in search at all.
2874 bool CurrentlyInSolve() const;
2875
2876 /// Counts the number of constraints that have been added
2877 /// to the solver before the search.
constraints()2878 int constraints() const { return constraints_list_.size(); }
2879
2880 /// Accepts the given model visitor.
2881 void Accept(ModelVisitor* const visitor) const;
2882
balancing_decision()2883 Decision* balancing_decision() const { return balancing_decision_.get(); }
2884
2885 /// Internal
2886 #if !defined(SWIG)
set_fail_intercept(std::function<void ()> fail_intercept)2887 void set_fail_intercept(std::function<void()> fail_intercept) {
2888 fail_intercept_ = std::move(fail_intercept);
2889 }
2890 #endif // !defined(SWIG)
clear_fail_intercept()2891 void clear_fail_intercept() { fail_intercept_ = nullptr; }
2892 /// Access to demon profiler.
demon_profiler()2893 DemonProfiler* demon_profiler() const { return demon_profiler_; }
2894 // TODO(user): Get rid of the following methods once fast local search is
2895 /// enabled for metaheuristics.
2896 /// Disables/enables fast local search.
SetUseFastLocalSearch(bool use_fast_local_search)2897 void SetUseFastLocalSearch(bool use_fast_local_search) {
2898 use_fast_local_search_ = use_fast_local_search;
2899 }
2900 /// Returns true if fast local search is enabled.
UseFastLocalSearch()2901 bool UseFastLocalSearch() const { return use_fast_local_search_; }
2902 /// Returns whether the object has been named or not.
2903 bool HasName(const PropagationBaseObject* object) const;
2904 /// Adds a new demon and wraps it inside a DemonProfiler if necessary.
2905 Demon* RegisterDemon(Demon* const demon);
2906 /// Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
2907 IntExpr* RegisterIntExpr(IntExpr* const expr);
2908 /// Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
2909 IntVar* RegisterIntVar(IntVar* const var);
2910 /// Registers a new IntervalVar and wraps it inside a TraceIntervalVar
2911 /// if necessary.
2912 IntervalVar* RegisterIntervalVar(IntervalVar* const var);
2913
2914 /// Returns the active search, nullptr outside search.
2915 Search* ActiveSearch() const;
2916 /// Returns the cache of the model.
2917 ModelCache* Cache() const;
2918 /// Returns whether we are instrumenting demons.
2919 bool InstrumentsDemons() const;
2920 /// Returns whether we are profiling the solver.
2921 bool IsProfilingEnabled() const;
2922 /// Returns whether we are profiling local search.
2923 bool IsLocalSearchProfilingEnabled() const;
2924 /// Returns whether we are tracing variables.
2925 bool InstrumentsVariables() const;
2926 /// Returns whether all variables should be named.
2927 bool NameAllVariables() const;
2928 /// Returns the name of the model.
2929 std::string model_name() const;
2930 /// Returns the propagation monitor.
2931 PropagationMonitor* GetPropagationMonitor() const;
2932 /// Adds the propagation monitor to the solver. This is called internally when
2933 /// a propagation monitor is passed to the Solve() or NewSearch() method.
2934 void AddPropagationMonitor(PropagationMonitor* const monitor);
2935 /// Returns the local search monitor.
2936 LocalSearchMonitor* GetLocalSearchMonitor() const;
2937 /// Adds the local search monitor to the solver. This is called internally
2938 /// when a propagation monitor is passed to the Solve() or NewSearch() method.
2939 void AddLocalSearchMonitor(LocalSearchMonitor* monitor);
2940 void SetSearchContext(Search* search, const std::string& search_context);
2941 std::string SearchContext() const;
2942 std::string SearchContext(const Search* search) const;
2943 /// Returns (or creates) an assignment representing the state of local search.
2944 // TODO(user): Investigate if this should be moved to Search.
2945 Assignment* GetOrCreateLocalSearchState();
2946 /// Clears the local search state.
ClearLocalSearchState()2947 void ClearLocalSearchState() { local_search_state_.reset(nullptr); }
2948
2949 /// Unsafe temporary vector. It is used to avoid leaks in operations
2950 /// that need storage and that may fail. See IntVar::SetValues() for
2951 /// instance. It is not locked; do not use in a multi-threaded or reentrant
2952 /// setup.
2953 std::vector<int64_t> tmp_vector_;
2954
2955 friend class BaseIntExpr;
2956 friend class Constraint;
2957 friend class DemonProfiler;
2958 friend class FindOneNeighbor;
2959 friend class IntVar;
2960 friend class PropagationBaseObject;
2961 friend class Queue;
2962 friend class SearchMonitor;
2963 friend class SearchLimit;
2964 friend class RoutingModel;
2965 friend class LocalSearchProfiler;
2966
2967 #if !defined(SWIG)
2968 friend void InternalSaveBooleanVarValue(Solver* const, IntVar* const);
2969 template <class>
2970 friend class SimpleRevFIFO;
2971 template <class K, class V>
2972 friend class RevImmutableMultiMap;
2973
2974 /// Returns true if expr represents either boolean_var or 1 -
2975 /// boolean_var. In that case, it fills inner_var and is_negated to be
2976 /// true if the expression is 1 - boolean_var -- equivalent to
2977 /// not(boolean_var).
2978 bool IsBooleanVar(IntExpr* const expr, IntVar** inner_var,
2979 bool* is_negated) const;
2980
2981 /// Returns true if expr represents a product of a expr and a
2982 /// constant. In that case, it fills inner_expr and coefficient with
2983 /// these, and returns true. In the other case, it fills inner_expr
2984 /// with expr, coefficient with 1, and returns false.
2985 bool IsProduct(IntExpr* const expr, IntExpr** inner_expr,
2986 int64_t* coefficient);
2987 #endif /// !defined(SWIG)
2988
2989 /// Internal. If the variables is the result of expr->Var(), this
2990 /// method returns expr, nullptr otherwise.
2991 IntExpr* CastExpression(const IntVar* const var) const;
2992
2993 /// Tells the solver to kill or restart the current search.
2994 void FinishCurrentSearch();
2995 void RestartCurrentSearch();
2996
2997 /// These methods are only useful for the SWIG wrappers, which need a way
2998 /// to externally cause the Solver to fail.
ShouldFail()2999 void ShouldFail() { should_fail_ = true; }
CheckFail()3000 void CheckFail() {
3001 if (!should_fail_) return;
3002 should_fail_ = false;
3003 Fail();
3004 }
3005
3006 /// Activates profiling on a decision builder.
3007 DecisionBuilder* MakeProfiledDecisionBuilderWrapper(DecisionBuilder* db);
3008
3009 private:
3010 void Init(); /// Initialization. To be called by the constructors only.
3011 void PushState(MarkerType t, const StateInfo& info);
3012 MarkerType PopState(StateInfo* info);
3013 void PushSentinel(int magic_code);
3014 void BacktrackToSentinel(int magic_code);
3015 void ProcessConstraints();
3016 bool BacktrackOneLevel(Decision** fail_decision);
3017 void JumpToSentinelWhenNested();
3018 void JumpToSentinel();
3019 void check_alloc_state();
3020 void FreezeQueue();
3021 void EnqueueVar(Demon* const d);
3022 void EnqueueDelayedDemon(Demon* const d);
3023 void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3024 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3025 void UnfreezeQueue();
3026 void reset_action_on_fail();
3027 void set_action_on_fail(Action a);
3028 void set_variable_to_clean_on_fail(IntVar* v);
3029 void IncrementUncheckedSolutionCounter();
3030 bool IsUncheckedSolutionLimitReached();
3031
3032 void InternalSaveValue(int* valptr);
3033 void InternalSaveValue(int64_t* valptr);
3034 void InternalSaveValue(uint64_t* valptr);
3035 void InternalSaveValue(double* valptr);
3036 void InternalSaveValue(bool* valptr);
3037 void InternalSaveValue(void** valptr);
InternalSaveValue(int64_t ** valptr)3038 void InternalSaveValue(int64_t** valptr) {
3039 InternalSaveValue(reinterpret_cast<void**>(valptr));
3040 }
3041
3042 BaseObject* SafeRevAlloc(BaseObject* ptr);
3043
3044 int* SafeRevAllocArray(int* ptr);
3045 int64_t* SafeRevAllocArray(int64_t* ptr);
3046 uint64_t* SafeRevAllocArray(uint64_t* ptr);
3047 double* SafeRevAllocArray(double* ptr);
3048 BaseObject** SafeRevAllocArray(BaseObject** ptr);
3049 IntVar** SafeRevAllocArray(IntVar** ptr);
3050 IntExpr** SafeRevAllocArray(IntExpr** ptr);
3051 Constraint** SafeRevAllocArray(Constraint** ptr);
3052 /// UnsafeRevAlloc is used internally for cells in SimpleRevFIFO
3053 /// and other structures like this.
3054 void* UnsafeRevAllocAux(void* ptr);
3055 template <class T>
UnsafeRevAlloc(T * ptr)3056 T* UnsafeRevAlloc(T* ptr) {
3057 return reinterpret_cast<T*>(
3058 UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
3059 }
3060 void** UnsafeRevAllocArrayAux(void** ptr);
3061 template <class T>
UnsafeRevAllocArray(T ** ptr)3062 T** UnsafeRevAllocArray(T** ptr) {
3063 return reinterpret_cast<T**>(
3064 UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
3065 }
3066
3067 void InitCachedIntConstants();
3068 void InitCachedConstraint();
3069
3070 /// Returns the Search object that is at the bottom of the search stack.
3071 /// Contrast with ActiveSearch(), which returns the search at the
3072 /// top of the stack.
TopLevelSearch()3073 Search* TopLevelSearch() const { return searches_.at(1); }
3074 /// Returns the Search object which is the parent of the active search, i.e.,
3075 /// the search below the top of the stack. If the active search is at the
3076 /// bottom of the stack, returns the active search.
ParentSearch()3077 Search* ParentSearch() const {
3078 const size_t search_size = searches_.size();
3079 DCHECK_GT(search_size, 1);
3080 return searches_[search_size - 2];
3081 }
3082
3083 /// Naming
3084 std::string GetName(const PropagationBaseObject* object);
3085 void SetName(const PropagationBaseObject* object, const std::string& name);
3086
3087 /// Variable indexing (note that indexing is not reversible).
3088 /// Returns a new index for an IntVar.
GetNewIntVarIndex()3089 int GetNewIntVarIndex() { return num_int_vars_++; }
3090
3091 /// Internal.
3092 bool IsADifference(IntExpr* expr, IntExpr** const left,
3093 IntExpr** const right);
3094
3095 const std::string name_;
3096 const ConstraintSolverParameters parameters_;
3097 absl::flat_hash_map<const PropagationBaseObject*, std::string>
3098 propagation_object_names_;
3099 absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3100 cast_information_;
3101 absl::flat_hash_set<const Constraint*> cast_constraints_;
3102 const std::string empty_name_;
3103 std::unique_ptr<Queue> queue_;
3104 std::unique_ptr<Trail> trail_;
3105 std::vector<Constraint*> constraints_list_;
3106 std::vector<Constraint*> additional_constraints_list_;
3107 std::vector<int> additional_constraints_parent_list_;
3108 SolverState state_;
3109 int64_t branches_;
3110 int64_t fails_;
3111 int64_t decisions_;
3112 int64_t demon_runs_[kNumPriorities];
3113 int64_t neighbors_;
3114 int64_t filtered_neighbors_;
3115 int64_t accepted_neighbors_;
3116 OptimizationDirection optimization_direction_;
3117 std::unique_ptr<ClockTimer> timer_;
3118 std::vector<Search*> searches_;
3119 std::mt19937 random_;
3120 uint64_t fail_stamp_;
3121 std::unique_ptr<Decision> balancing_decision_;
3122 /// intercept failures
3123 std::function<void()> fail_intercept_;
3124 /// Demon monitor
3125 DemonProfiler* const demon_profiler_;
3126 /// Local search mode
3127 bool use_fast_local_search_;
3128 /// Local search profiler monitor
3129 LocalSearchProfiler* const local_search_profiler_;
3130 /// Local search state.
3131 std::unique_ptr<Assignment> local_search_state_;
3132
3133 /// interval of constants cached, inclusive:
3134 enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3135 IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3136
3137 /// Cached constraints.
3138 Constraint* true_constraint_;
3139 Constraint* false_constraint_;
3140
3141 std::unique_ptr<Decision> fail_decision_;
3142 int constraint_index_;
3143 int additional_constraint_index_;
3144 int num_int_vars_;
3145
3146 std::unique_ptr<ModelCache> model_cache_;
3147 std::unique_ptr<PropagationMonitor> propagation_monitor_;
3148 PropagationMonitor* print_trace_;
3149 std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3150 int anonymous_variable_index_;
3151 bool should_fail_;
3152
3153 DISALLOW_COPY_AND_ASSIGN(Solver);
3154 };
3155
3156 std::ostream& operator<<(std::ostream& out, const Solver* const s); /// NOLINT
3157
3158 /// This method returns 0. It is useful when 0 can be cast either as
3159 /// a pointer or as an integer value and thus lead to an ambiguous
3160 /// function call.
Zero()3161 inline int64_t Zero() { return 0; }
3162
3163 /// This method returns 1
One()3164 inline int64_t One() { return 1; }
3165
3166 /// A BaseObject is the root of all reversibly allocated objects.
3167 /// A DebugString method and the associated << operator are implemented
3168 /// as a convenience.
3169 class BaseObject {
3170 public:
BaseObject()3171 BaseObject() {}
~BaseObject()3172 virtual ~BaseObject() {}
DebugString()3173 virtual std::string DebugString() const { return "BaseObject"; }
3174
3175 private:
3176 DISALLOW_COPY_AND_ASSIGN(BaseObject);
3177 };
3178
3179 std::ostream& operator<<(std::ostream& out, const BaseObject* o); /// NOLINT
3180
3181 /// The PropagationBaseObject is a subclass of BaseObject that is also
3182 /// friend to the Solver class. It allows accessing methods useful when
3183 /// writing new constraints or new expressions.
3184 class PropagationBaseObject : public BaseObject {
3185 public:
PropagationBaseObject(Solver * const s)3186 explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
~PropagationBaseObject()3187 ~PropagationBaseObject() override {}
3188
DebugString()3189 std::string DebugString() const override {
3190 if (name().empty()) {
3191 return "PropagationBaseObject";
3192 } else {
3193 return absl::StrFormat("PropagationBaseObject: %s", name());
3194 }
3195 }
solver()3196 Solver* solver() const { return solver_; }
3197
3198 /// This method freezes the propagation queue. It is useful when you
3199 /// need to apply multiple modifications at once.
FreezeQueue()3200 void FreezeQueue() { solver_->FreezeQueue(); }
3201
3202 /// This method unfreezes the propagation queue. All modifications
3203 /// that happened when the queue was frozen will be processed.
UnfreezeQueue()3204 void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3205
3206 /// This method pushes the demon onto the propagation queue. It will
3207 /// be processed directly if the queue is empty. It will be enqueued
3208 /// according to its priority otherwise.
EnqueueDelayedDemon(Demon * const d)3209 void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
EnqueueVar(Demon * const d)3210 void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
3211 void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3212 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3213
3214 #if !defined(SWIG)
3215 // This method sets a callback that will be called if a failure
3216 // happens during the propagation of the queue.
set_action_on_fail(Solver::Action a)3217 void set_action_on_fail(Solver::Action a) {
3218 solver_->set_action_on_fail(std::move(a));
3219 }
3220 #endif // !defined(SWIG)
3221
3222 /// This method clears the failure callback.
reset_action_on_fail()3223 void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3224
3225 /// Shortcut for variable cleaner.
set_variable_to_clean_on_fail(IntVar * v)3226 void set_variable_to_clean_on_fail(IntVar* v) {
3227 solver_->set_variable_to_clean_on_fail(v);
3228 }
3229
3230 /// Object naming.
3231 virtual std::string name() const;
3232 void set_name(const std::string& name);
3233 /// Returns whether the object has been named or not.
3234 bool HasName() const;
3235 /// Returns a base name for automatic naming.
3236 virtual std::string BaseName() const;
3237
3238 private:
3239 Solver* const solver_;
3240 DISALLOW_COPY_AND_ASSIGN(PropagationBaseObject);
3241 };
3242
3243 /// A Decision represents a choice point in the search tree. The two main
3244 /// methods are Apply() to go left, or Refute() to go right.
3245 class Decision : public BaseObject {
3246 public:
Decision()3247 Decision() {}
~Decision()3248 ~Decision() override {}
3249
3250 /// Apply will be called first when the decision is executed.
3251 virtual void Apply(Solver* const s) = 0;
3252
3253 /// Refute will be called after a backtrack.
3254 virtual void Refute(Solver* const s) = 0;
3255
DebugString()3256 std::string DebugString() const override { return "Decision"; }
3257 /// Accepts the given visitor.
3258 virtual void Accept(DecisionVisitor* const visitor) const;
3259
3260 private:
3261 DISALLOW_COPY_AND_ASSIGN(Decision);
3262 };
3263
3264 /// A DecisionVisitor is used to inspect a decision.
3265 /// It contains virtual methods for all type of 'declared' decisions.
3266 class DecisionVisitor : public BaseObject {
3267 public:
DecisionVisitor()3268 DecisionVisitor() {}
~DecisionVisitor()3269 ~DecisionVisitor() override {}
3270 virtual void VisitSetVariableValue(IntVar* const var, int64_t value);
3271 virtual void VisitSplitVariableDomain(IntVar* const var, int64_t value,
3272 bool start_with_lower_half);
3273 virtual void VisitScheduleOrPostpone(IntervalVar* const var, int64_t est);
3274 virtual void VisitScheduleOrExpedite(IntervalVar* const var, int64_t est);
3275 virtual void VisitRankFirstInterval(SequenceVar* const sequence, int index);
3276 virtual void VisitRankLastInterval(SequenceVar* const sequence, int index);
3277 virtual void VisitUnknownDecision();
3278
3279 private:
3280 DISALLOW_COPY_AND_ASSIGN(DecisionVisitor);
3281 };
3282
3283 /// A DecisionBuilder is responsible for creating the search tree. The
3284 /// important method is Next(), which returns the next decision to execute.
3285 class DecisionBuilder : public BaseObject {
3286 public:
DecisionBuilder()3287 DecisionBuilder() {}
~DecisionBuilder()3288 ~DecisionBuilder() override {}
3289 /// This is the main method of the decision builder class. It must
3290 /// return a decision (an instance of the class Decision). If it
3291 /// returns nullptr, this means that the decision builder has finished
3292 /// its work.
3293 virtual Decision* Next(Solver* const s) = 0;
3294 std::string DebugString() const override;
3295 #if !defined(SWIG)
3296 /// This method will be called at the start of the search. It asks
3297 /// the decision builder if it wants to append search monitors to the
3298 /// list of active monitors for this search. Please note there are no
3299 /// checks at this point for duplication.
3300 virtual void AppendMonitors(Solver* const solver,
3301 std::vector<SearchMonitor*>* const extras);
3302 virtual void Accept(ModelVisitor* const visitor) const;
3303 #endif
set_name(const std::string & name)3304 void set_name(const std::string& name) { name_ = name; }
3305 std::string GetName() const;
3306
3307 private:
3308 std::string name_;
3309 DISALLOW_COPY_AND_ASSIGN(DecisionBuilder);
3310 };
3311
3312 #if !defined(SWIG)
3313 class ProfiledDecisionBuilder : public DecisionBuilder {
3314 public:
3315 explicit ProfiledDecisionBuilder(DecisionBuilder* db);
~ProfiledDecisionBuilder()3316 ~ProfiledDecisionBuilder() override {}
name()3317 const std::string& name() const { return name_; }
seconds()3318 double seconds() const { return seconds_; }
3319 Decision* Next(Solver* const solver) override;
3320 std::string DebugString() const override;
3321 void AppendMonitors(Solver* const solver,
3322 std::vector<SearchMonitor*>* const extras) override;
3323 void Accept(ModelVisitor* const visitor) const override;
3324
3325 private:
3326 DecisionBuilder* const db_;
3327 const std::string name_;
3328 SimpleCycleTimer timer_;
3329 double seconds_;
3330 };
3331 #endif
3332
3333 /// A Demon is the base element of a propagation queue. It is the main
3334 /// object responsible for implementing the actual propagation
3335 /// of the constraint and pruning the inconsistent values in the domains
3336 /// of the variables. The main concept is that demons are listeners that are
3337 /// attached to the variables and listen to their modifications.
3338 /// There are two methods:
3339 /// - Run() is the actual method called when the demon is processed.
3340 /// - priority() returns its priority. Standard priorities are slow, normal
3341 /// or fast. "immediate" is reserved for variables and is treated separately.
3342 class Demon : public BaseObject {
3343 public:
3344 /// This indicates the priority of a demon. Immediate demons are treated
3345 /// separately and corresponds to variables.
Demon()3346 Demon() : stamp_(uint64_t{0}) {}
~Demon()3347 ~Demon() override {}
3348
3349 /// This is the main callback of the demon.
3350 virtual void Run(Solver* const s) = 0;
3351
3352 /// This method returns the priority of the demon. Usually a demon is
3353 /// fast, slow or normal. Immediate demons are reserved for internal
3354 /// use to maintain variables.
3355 virtual Solver::DemonPriority priority() const;
3356
3357 std::string DebugString() const override;
3358
3359 /// This method inhibits the demon in the search tree below the
3360 /// current position.
3361 void inhibit(Solver* const s);
3362
3363 /// This method un-inhibits the demon that was previously inhibited.
3364 void desinhibit(Solver* const s);
3365
3366 private:
3367 friend class Queue;
set_stamp(int64_t stamp)3368 void set_stamp(int64_t stamp) { stamp_ = stamp; }
stamp()3369 uint64_t stamp() const { return stamp_; }
3370 uint64_t stamp_;
3371 DISALLOW_COPY_AND_ASSIGN(Demon);
3372 };
3373
3374 /// Model visitor.
3375 class ModelVisitor : public BaseObject {
3376 public:
3377 /// Constraint and Expression types.
3378 static const char kAbs[];
3379 static const char kAbsEqual[];
3380 static const char kAllDifferent[];
3381 static const char kAllowedAssignments[];
3382 static const char kAtMost[];
3383 static const char kIndexOf[];
3384 static const char kBetween[];
3385 static const char kConditionalExpr[];
3386 static const char kCircuit[];
3387 static const char kConvexPiecewise[];
3388 static const char kCountEqual[];
3389 static const char kCover[];
3390 static const char kCumulative[];
3391 static const char kDeviation[];
3392 static const char kDifference[];
3393 static const char kDisjunctive[];
3394 static const char kDistribute[];
3395 static const char kDivide[];
3396 static const char kDurationExpr[];
3397 static const char kElement[];
3398 static const char kElementEqual[];
3399 static const char kEndExpr[];
3400 static const char kEquality[];
3401 static const char kFalseConstraint[];
3402 static const char kGlobalCardinality[];
3403 static const char kGreater[];
3404 static const char kGreaterOrEqual[];
3405 static const char kIntegerVariable[];
3406 static const char kIntervalBinaryRelation[];
3407 static const char kIntervalDisjunction[];
3408 static const char kIntervalUnaryRelation[];
3409 static const char kIntervalVariable[];
3410 static const char kInversePermutation[];
3411 static const char kIsBetween[];
3412 static const char kIsDifferent[];
3413 static const char kIsEqual[];
3414 static const char kIsGreater[];
3415 static const char kIsGreaterOrEqual[];
3416 static const char kIsLess[];
3417 static const char kIsLessOrEqual[];
3418 static const char kIsMember[];
3419 static const char kLess[];
3420 static const char kLessOrEqual[];
3421 static const char kLexLess[];
3422 static const char kLinkExprVar[];
3423 static const char kMapDomain[];
3424 static const char kMax[];
3425 static const char kMaxEqual[];
3426 static const char kMember[];
3427 static const char kMin[];
3428 static const char kMinEqual[];
3429 static const char kModulo[];
3430 static const char kNoCycle[];
3431 static const char kNonEqual[];
3432 static const char kNotBetween[];
3433 static const char kNotMember[];
3434 static const char kNullIntersect[];
3435 static const char kOpposite[];
3436 static const char kPack[];
3437 static const char kPathCumul[];
3438 static const char kDelayedPathCumul[];
3439 static const char kPerformedExpr[];
3440 static const char kPower[];
3441 static const char kProduct[];
3442 static const char kScalProd[];
3443 static const char kScalProdEqual[];
3444 static const char kScalProdGreaterOrEqual[];
3445 static const char kScalProdLessOrEqual[];
3446 static const char kSemiContinuous[];
3447 static const char kSequenceVariable[];
3448 static const char kSortingConstraint[];
3449 static const char kSquare[];
3450 static const char kStartExpr[];
3451 static const char kSum[];
3452 static const char kSumEqual[];
3453 static const char kSumGreaterOrEqual[];
3454 static const char kSumLessOrEqual[];
3455 static const char kTrace[];
3456 static const char kTransition[];
3457 static const char kTrueConstraint[];
3458 static const char kVarBoundWatcher[];
3459 static const char kVarValueWatcher[];
3460
3461 /// Extension names:
3462 static const char kCountAssignedItemsExtension[];
3463 static const char kCountUsedBinsExtension[];
3464 static const char kInt64ToBoolExtension[];
3465 static const char kInt64ToInt64Extension[];
3466 static const char kObjectiveExtension[];
3467 static const char kSearchLimitExtension[];
3468 static const char kUsageEqualVariableExtension[];
3469
3470 static const char kUsageLessConstantExtension[];
3471 static const char kVariableGroupExtension[];
3472 static const char kVariableUsageLessConstantExtension[];
3473 static const char kWeightedSumOfAssignedEqualVariableExtension[];
3474
3475 /// argument names:
3476 static const char kActiveArgument[];
3477 static const char kAssumePathsArgument[];
3478 static const char kBranchesLimitArgument[];
3479 static const char kCapacityArgument[];
3480 static const char kCardsArgument[];
3481 static const char kCoefficientsArgument[];
3482 static const char kCountArgument[];
3483 static const char kCumulativeArgument[];
3484 static const char kCumulsArgument[];
3485 static const char kDemandsArgument[];
3486 static const char kDurationMaxArgument[];
3487 static const char kDurationMinArgument[];
3488 static const char kEarlyCostArgument[];
3489 static const char kEarlyDateArgument[];
3490 static const char kEndMaxArgument[];
3491 static const char kEndMinArgument[];
3492 static const char kEndsArgument[];
3493 static const char kExpressionArgument[];
3494 static const char kFailuresLimitArgument[];
3495 static const char kFinalStatesArgument[];
3496 static const char kFixedChargeArgument[];
3497 static const char kIndex2Argument[];
3498 static const char kIndexArgument[];
3499 static const char kInitialState[];
3500 static const char kIntervalArgument[];
3501 static const char kIntervalsArgument[];
3502 static const char kLateCostArgument[];
3503 static const char kLateDateArgument[];
3504 static const char kLeftArgument[];
3505 static const char kMaxArgument[];
3506 static const char kMaximizeArgument[];
3507 static const char kMinArgument[];
3508 static const char kModuloArgument[];
3509 static const char kNextsArgument[];
3510 static const char kOptionalArgument[];
3511 static const char kPartialArgument[];
3512 static const char kPositionXArgument[];
3513 static const char kPositionYArgument[];
3514 static const char kRangeArgument[];
3515 static const char kRelationArgument[];
3516 static const char kRightArgument[];
3517 static const char kSequenceArgument[];
3518 static const char kSequencesArgument[];
3519 static const char kSizeArgument[];
3520 static const char kSizeXArgument[];
3521 static const char kSizeYArgument[];
3522 static const char kSmartTimeCheckArgument[];
3523 static const char kSolutionLimitArgument[];
3524 static const char kStartMaxArgument[];
3525 static const char kStartMinArgument[];
3526 static const char kStartsArgument[];
3527 static const char kStepArgument[];
3528 static const char kTargetArgument[];
3529 static const char kTimeLimitArgument[];
3530 static const char kTransitsArgument[];
3531 static const char kTuplesArgument[];
3532 static const char kValueArgument[];
3533 static const char kValuesArgument[];
3534 static const char kVariableArgument[];
3535 static const char kVarsArgument[];
3536 static const char kEvaluatorArgument[];
3537
3538 /// Operations.
3539 static const char kMirrorOperation[];
3540 static const char kRelaxedMaxOperation[];
3541 static const char kRelaxedMinOperation[];
3542 static const char kSumOperation[];
3543 static const char kDifferenceOperation[];
3544 static const char kProductOperation[];
3545 static const char kStartSyncOnStartOperation[];
3546 static const char kStartSyncOnEndOperation[];
3547 static const char kTraceOperation[];
3548
3549 ~ModelVisitor() override;
3550
3551 /// ----- Virtual methods for visitors -----
3552
3553 /// Begin/End visit element.
3554 virtual void BeginVisitModel(const std::string& type_name);
3555 virtual void EndVisitModel(const std::string& type_name);
3556 virtual void BeginVisitConstraint(const std::string& type_name,
3557 const Constraint* const constraint);
3558 virtual void EndVisitConstraint(const std::string& type_name,
3559 const Constraint* const constraint);
3560 virtual void BeginVisitExtension(const std::string& type);
3561 virtual void EndVisitExtension(const std::string& type);
3562 virtual void BeginVisitIntegerExpression(const std::string& type_name,
3563 const IntExpr* const expr);
3564 virtual void EndVisitIntegerExpression(const std::string& type_name,
3565 const IntExpr* const expr);
3566 virtual void VisitIntegerVariable(const IntVar* const variable,
3567 IntExpr* const delegate);
3568 virtual void VisitIntegerVariable(const IntVar* const variable,
3569 const std::string& operation, int64_t value,
3570 IntVar* const delegate);
3571 virtual void VisitIntervalVariable(const IntervalVar* const variable,
3572 const std::string& operation,
3573 int64_t value,
3574 IntervalVar* const delegate);
3575 virtual void VisitSequenceVariable(const SequenceVar* const variable);
3576
3577 /// Visit integer arguments.
3578 virtual void VisitIntegerArgument(const std::string& arg_name, int64_t value);
3579 virtual void VisitIntegerArrayArgument(const std::string& arg_name,
3580 const std::vector<int64_t>& values);
3581 virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
3582 const IntTupleSet& tuples);
3583
3584 /// Visit integer expression argument.
3585 virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
3586 IntExpr* const argument);
3587
3588 virtual void VisitIntegerVariableArrayArgument(
3589 const std::string& arg_name, const std::vector<IntVar*>& arguments);
3590
3591 /// Visit interval argument.
3592 virtual void VisitIntervalArgument(const std::string& arg_name,
3593 IntervalVar* const argument);
3594
3595 virtual void VisitIntervalArrayArgument(
3596 const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
3597 /// Visit sequence argument.
3598 virtual void VisitSequenceArgument(const std::string& arg_name,
3599 SequenceVar* const argument);
3600
3601 virtual void VisitSequenceArrayArgument(
3602 const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
3603 #if !defined(SWIG)
3604 /// Helpers.
3605 virtual void VisitIntegerVariableEvaluatorArgument(
3606 const std::string& arg_name, const Solver::Int64ToIntVar& arguments);
3607
3608 /// Using SWIG on callbacks is troublesome, so we hide these methods during
3609 /// the wrapping.
3610 void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min,
3611 int64_t index_max);
3612 void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1& eval,
3613 int64_t index_min, int64_t index_max);
3614 /// Expands function as array when index min is 0.
3615 void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1& eval,
3616 const std::string& arg_name, int64_t index_max);
3617 #endif // #if !defined(SWIG)
3618 };
3619
3620 /// A constraint is the main modeling object. It provides two methods:
3621 /// - Post() is responsible for creating the demons and attaching them to
3622 /// immediate demons().
3623 /// - InitialPropagate() is called once just after Post and performs
3624 /// the initial propagation. The subsequent propagations will be performed
3625 /// by the demons Posted during the post() method.
3626 class Constraint : public PropagationBaseObject {
3627 public:
Constraint(Solver * const solver)3628 explicit Constraint(Solver* const solver) : PropagationBaseObject(solver) {}
~Constraint()3629 ~Constraint() override {}
3630
3631 /// This method is called when the constraint is processed by the
3632 /// solver. Its main usage is to attach demons to variables.
3633 virtual void Post() = 0;
3634
3635 /// This method performs the initial propagation of the
3636 /// constraint. It is called just after the post.
3637 virtual void InitialPropagate() = 0;
3638 std::string DebugString() const override;
3639
3640 /// Calls Post and then Propagate to initialize the constraints. This
3641 /// is usually done in the root node.
3642 void PostAndPropagate();
3643
3644 /// Accepts the given visitor.
3645 virtual void Accept(ModelVisitor* const visitor) const;
3646
3647 /// Is the constraint created by a cast from expression to integer variable?
3648 bool IsCastConstraint() const;
3649
3650 /// Creates a Boolean variable representing the status of the constraint
3651 /// (false = constraint is violated, true = constraint is satisfied). It
3652 /// returns nullptr if the constraint does not support this API.
3653 virtual IntVar* Var();
3654
3655 private:
3656 DISALLOW_COPY_AND_ASSIGN(Constraint);
3657 };
3658
3659 /// Cast constraints are special channeling constraints designed
3660 /// to keep a variable in sync with an expression. They are
3661 /// created internally when Var() is called on a subclass of IntExpr.
3662 class CastConstraint : public Constraint {
3663 public:
CastConstraint(Solver * const solver,IntVar * const target_var)3664 CastConstraint(Solver* const solver, IntVar* const target_var)
3665 : Constraint(solver), target_var_(target_var) {
3666 CHECK(target_var != nullptr);
3667 }
~CastConstraint()3668 ~CastConstraint() override {}
3669
target_var()3670 IntVar* target_var() const { return target_var_; }
3671
3672 protected:
3673 IntVar* const target_var_;
3674 };
3675
3676 /// A search monitor is a simple set of callbacks to monitor all search events
3677 class SearchMonitor : public BaseObject {
3678 public:
3679 static constexpr int kNoProgress = -1;
3680
SearchMonitor(Solver * const s)3681 explicit SearchMonitor(Solver* const s) : solver_(s) {}
~SearchMonitor()3682 ~SearchMonitor() override {}
3683 /// Beginning of the search.
3684 virtual void EnterSearch();
3685
3686 /// Restart the search.
3687 virtual void RestartSearch();
3688
3689 /// End of the search.
3690 virtual void ExitSearch();
3691
3692 /// Before calling DecisionBuilder::Next.
3693 virtual void BeginNextDecision(DecisionBuilder* const b);
3694
3695 /// After calling DecisionBuilder::Next, along with the returned decision.
3696 virtual void EndNextDecision(DecisionBuilder* const b, Decision* const d);
3697
3698 /// Before applying the decision.
3699 virtual void ApplyDecision(Decision* const d);
3700
3701 /// Before refuting the decision.
3702 virtual void RefuteDecision(Decision* const d);
3703
3704 /// Just after refuting or applying the decision, apply is true after Apply.
3705 /// This is called only if the Apply() or Refute() methods have not failed.
3706 virtual void AfterDecision(Decision* const d, bool apply);
3707
3708 /// Just when the failure occurs.
3709 virtual void BeginFail();
3710
3711 /// After completing the backtrack.
3712 virtual void EndFail();
3713
3714 /// Before the initial propagation.
3715 virtual void BeginInitialPropagation();
3716
3717 /// After the initial propagation.
3718 virtual void EndInitialPropagation();
3719
3720 /// This method is called when a solution is found. It asserts whether the
3721 /// solution is valid. A value of false indicates that the solution
3722 /// should be discarded.
3723 virtual bool AcceptSolution();
3724
3725 /// This method is called when a valid solution is found. If the
3726 /// return value is true, then search will resume after. If the result
3727 /// is false, then search will stop there.
3728 virtual bool AtSolution();
3729
3730 /// When the search tree is finished.
3731 virtual void NoMoreSolutions();
3732
3733 /// When a local optimum is reached. If 'true' is returned, the last solution
3734 /// is discarded and the search proceeds with the next one.
3735 virtual bool LocalOptimum();
3736
3737 ///
3738 virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3739
3740 /// After accepting a neighbor during local search.
3741 virtual void AcceptNeighbor();
3742
3743 /// After accepting an unchecked neighbor during local search.
3744 virtual void AcceptUncheckedNeighbor();
3745
3746 /// Returns true if the limit of solutions has been reached including
3747 /// unchecked solutions.
IsUncheckedSolutionLimitReached()3748 virtual bool IsUncheckedSolutionLimitReached() { return false; }
3749
solver()3750 Solver* solver() const { return solver_; }
3751
3752 /// Periodic call to check limits in long running methods.
3753 virtual void PeriodicCheck();
3754
3755 /// Returns a percentage representing the propress of the search before
3756 /// reaching limits.
ProgressPercent()3757 virtual int ProgressPercent() { return kNoProgress; }
3758
3759 /// Accepts the given model visitor.
3760 virtual void Accept(ModelVisitor* const visitor) const;
3761
3762 /// Registers itself on the solver such that it gets notified of the search
3763 /// and propagation events.
3764 virtual void Install();
3765
3766 private:
3767 Solver* const solver_;
3768 DISALLOW_COPY_AND_ASSIGN(SearchMonitor);
3769 };
3770
3771 /// This class adds reversibility to a POD type.
3772 /// It contains the stamp optimization. i.e. the SaveValue call is done
3773 /// only once per node of the search tree. Please note that actual
3774 /// stamps always starts at 1, thus an initial value of 0 will always
3775 /// trigger the first SaveValue.
3776 template <class T>
3777 class Rev {
3778 public:
Rev(const T & val)3779 explicit Rev(const T& val) : stamp_(0), value_(val) {}
3780
Value()3781 const T& Value() const { return value_; }
3782
SetValue(Solver * const s,const T & val)3783 void SetValue(Solver* const s, const T& val) {
3784 if (val != value_) {
3785 if (stamp_ < s->stamp()) {
3786 s->SaveValue(&value_);
3787 stamp_ = s->stamp();
3788 }
3789 value_ = val;
3790 }
3791 }
3792
3793 private:
3794 uint64_t stamp_;
3795 T value_;
3796 };
3797
3798 /// Subclass of Rev<T> which adds numerical operations.
3799 template <class T>
3800 class NumericalRev : public Rev<T> {
3801 public:
NumericalRev(const T & val)3802 explicit NumericalRev(const T& val) : Rev<T>(val) {}
3803
Add(Solver * const s,const T & to_add)3804 void Add(Solver* const s, const T& to_add) {
3805 this->SetValue(s, this->Value() + to_add);
3806 }
3807
Incr(Solver * const s)3808 void Incr(Solver* const s) { Add(s, 1); }
3809
Decr(Solver * const s)3810 void Decr(Solver* const s) { Add(s, -1); }
3811 };
3812
3813 /// Reversible array of POD types.
3814 /// It contains the stamp optimization. I.e., the SaveValue call is done only
3815 /// once per node of the search tree.
3816 /// Please note that actual stamp always starts at 1, thus an initial value of
3817 /// 0 always triggers the first SaveValue.
3818 template <class T>
3819 class RevArray {
3820 public:
RevArray(int size,const T & val)3821 RevArray(int size, const T& val)
3822 : stamps_(new uint64_t[size]), values_(new T[size]), size_(size) {
3823 for (int i = 0; i < size; ++i) {
3824 stamps_[i] = 0;
3825 values_[i] = val;
3826 }
3827 }
3828
~RevArray()3829 ~RevArray() {}
3830
size()3831 int64_t size() const { return size_; }
3832
Value(int index)3833 const T& Value(int index) const { return values_[index]; }
3834
3835 #if !defined(SWIG)
3836 const T& operator[](int index) const { return values_[index]; }
3837 #endif
3838
SetValue(Solver * const s,int index,const T & val)3839 void SetValue(Solver* const s, int index, const T& val) {
3840 DCHECK_LT(index, size_);
3841 if (val != values_[index]) {
3842 if (stamps_[index] < s->stamp()) {
3843 s->SaveValue(&values_[index]);
3844 stamps_[index] = s->stamp();
3845 }
3846 values_[index] = val;
3847 }
3848 }
3849
3850 private:
3851 std::unique_ptr<uint64_t[]> stamps_;
3852 std::unique_ptr<T[]> values_;
3853 const int size_;
3854 };
3855
3856 /// Subclass of RevArray<T> which adds numerical operations.
3857 template <class T>
3858 class NumericalRevArray : public RevArray<T> {
3859 public:
NumericalRevArray(int size,const T & val)3860 NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
3861
Add(Solver * const s,int index,const T & to_add)3862 void Add(Solver* const s, int index, const T& to_add) {
3863 this->SetValue(s, index, this->Value(index) + to_add);
3864 }
3865
Incr(Solver * const s,int index)3866 void Incr(Solver* const s, int index) { Add(s, index, 1); }
3867
Decr(Solver * const s,int index)3868 void Decr(Solver* const s, int index) { Add(s, index, -1); }
3869 };
3870
3871 /// The class IntExpr is the base of all integer expressions in
3872 /// constraint programming.
3873 /// It contains the basic protocol for an expression:
3874 /// - setting and modifying its bound
3875 /// - querying if it is bound
3876 /// - listening to events modifying its bounds
3877 /// - casting it into a variable (instance of IntVar)
3878 class IntExpr : public PropagationBaseObject {
3879 public:
IntExpr(Solver * const s)3880 explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
~IntExpr()3881 ~IntExpr() override {}
3882
3883 virtual int64_t Min() const = 0;
3884 virtual void SetMin(int64_t m) = 0;
3885 virtual int64_t Max() const = 0;
3886 virtual void SetMax(int64_t m) = 0;
3887
3888 /// By default calls Min() and Max(), but can be redefined when Min and Max
3889 /// code can be factorized.
Range(int64_t * l,int64_t * u)3890 virtual void Range(int64_t* l, int64_t* u) {
3891 *l = Min();
3892 *u = Max();
3893 }
3894 /// This method sets both the min and the max of the expression.
SetRange(int64_t l,int64_t u)3895 virtual void SetRange(int64_t l, int64_t u) {
3896 SetMin(l);
3897 SetMax(u);
3898 }
3899
3900 /// This method sets the value of the expression.
SetValue(int64_t v)3901 virtual void SetValue(int64_t v) { SetRange(v, v); }
3902
3903 /// Returns true if the min and the max of the expression are equal.
Bound()3904 virtual bool Bound() const { return (Min() == Max()); }
3905
3906 /// Returns true if the expression is indeed a variable.
IsVar()3907 virtual bool IsVar() const { return false; }
3908
3909 /// Creates a variable from the expression.
3910 virtual IntVar* Var() = 0;
3911
3912 /// Creates a variable from the expression and set the name of the
3913 /// resulting var. If the expression is already a variable, then it
3914 /// will set the name of the expression, possibly overwriting it.
3915 /// This is just a shortcut to Var() followed by set_name().
3916 IntVar* VarWithName(const std::string& name);
3917
3918 /// Attach a demon that will watch the min or the max of the expression.
3919 virtual void WhenRange(Demon* d) = 0;
3920 /// Attach a demon that will watch the min or the max of the expression.
WhenRange(Solver::Closure closure)3921 void WhenRange(Solver::Closure closure) {
3922 WhenRange(solver()->MakeClosureDemon(std::move(closure)));
3923 }
3924
3925 #if !defined(SWIG)
3926 /// Attach a demon that will watch the min or the max of the expression.
WhenRange(Solver::Action action)3927 void WhenRange(Solver::Action action) {
3928 WhenRange(solver()->MakeActionDemon(std::move(action)));
3929 }
3930 #endif // SWIG
3931
3932 /// Accepts the given visitor.
3933 virtual void Accept(ModelVisitor* const visitor) const;
3934
3935 private:
3936 DISALLOW_COPY_AND_ASSIGN(IntExpr);
3937 };
3938
3939 /// The class Iterator has two direct subclasses. HoleIterators
3940 /// iterates over all holes, that is value removed between the
3941 /// current min and max of the variable since the last time the
3942 /// variable was processed in the queue. DomainIterators iterates
3943 /// over all elements of the variable domain. Both iterators are not
3944 /// robust to domain changes. Hole iterators can also report values outside
3945 /// the current min and max of the variable.
3946
3947 /// HoleIterators should only be called from a demon attached to the
3948 /// variable that has created this iterator.
3949
3950 /// IntVar* current_var;
3951 /// std::unique_ptr<IntVarIterator> it(current_var->MakeHoleIterator(false));
3952 /// for (const int64_t hole : InitAndGetValues(it)) {
3953 /// /// use the hole
3954 /// }
3955
3956 class IntVarIterator : public BaseObject {
3957 public:
~IntVarIterator()3958 ~IntVarIterator() override {}
3959
3960 /// This method must be called before each loop.
3961 virtual void Init() = 0;
3962
3963 /// This method indicates if we can call Value() or not.
3964 virtual bool Ok() const = 0;
3965
3966 /// This method returns the current value of the iterator.
3967 virtual int64_t Value() const = 0;
3968
3969 /// This method moves the iterator to the next value.
3970 virtual void Next() = 0;
3971
3972 /// Pretty Print.
DebugString()3973 std::string DebugString() const override { return "IntVar::Iterator"; }
3974 };
3975
3976 #ifndef SWIG
3977 /// Utility class to encapsulate an IntVarIterator and use it in a range-based
3978 /// loop. See the code snippet above IntVarIterator.
3979 ///
3980 /// It contains DEBUG_MODE-enabled code that DCHECKs that the
3981 /// same iterator instance isn't being iterated on in multiple places
3982 /// simultaneously.
3983 class InitAndGetValues {
3984 public:
InitAndGetValues(IntVarIterator * it)3985 explicit InitAndGetValues(IntVarIterator* it)
3986 : it_(it), begin_was_called_(false) {
3987 it_->Init();
3988 }
3989 struct Iterator;
3990
begin()3991 Iterator begin() {
3992 if (DEBUG_MODE) {
3993 DCHECK(!begin_was_called_);
3994 begin_was_called_ = true;
3995 }
3996 return Iterator::Begin(it_);
3997 }
end()3998 Iterator end() { return Iterator::End(it_); }
3999
4000 struct Iterator {
4001 /// These are the only way to construct an Iterator.
BeginIterator4002 static Iterator Begin(IntVarIterator* it) {
4003 return Iterator(it, /*is_end=*/false);
4004 }
EndIterator4005 static Iterator End(IntVarIterator* it) {
4006 return Iterator(it, /*is_end=*/true);
4007 }
4008
4009 int64_t operator*() const {
4010 DCHECK(it_->Ok());
4011 return it_->Value();
4012 }
4013 Iterator& operator++() {
4014 DCHECK(it_->Ok());
4015 it_->Next();
4016 return *this;
4017 }
4018 bool operator!=(const Iterator& other) const {
4019 DCHECK(other.it_ == it_);
4020 DCHECK(other.is_end_);
4021 return it_->Ok();
4022 }
4023
4024 private:
IteratorIterator4025 Iterator(IntVarIterator* it, bool is_end) : it_(it), is_end_(is_end) {}
4026
4027 IntVarIterator* const it_;
4028 const bool is_end_;
4029 };
4030
4031 private:
4032 IntVarIterator* const it_;
4033 bool begin_was_called_;
4034 };
4035 #endif // SWIG
4036
4037 /// The class IntVar is a subset of IntExpr. In addition to the
4038 /// IntExpr protocol, it offers persistence, removing values from the domains,
4039 /// and a finer model for events.
4040 class IntVar : public IntExpr {
4041 public:
4042 explicit IntVar(Solver* const s);
4043 IntVar(Solver* const s, const std::string& name);
~IntVar()4044 ~IntVar() override {}
4045
IsVar()4046 bool IsVar() const override { return true; }
Var()4047 IntVar* Var() override { return this; }
4048
4049 /// This method returns the value of the variable. This method checks
4050 /// before that the variable is bound.
4051 virtual int64_t Value() const = 0;
4052
4053 /// This method removes the value 'v' from the domain of the variable.
4054 virtual void RemoveValue(int64_t v) = 0;
4055
4056 /// This method removes the interval 'l' .. 'u' from the domain of
4057 /// the variable. It assumes that 'l' <= 'u'.
4058 virtual void RemoveInterval(int64_t l, int64_t u) = 0;
4059
4060 /// This method remove the values from the domain of the variable.
4061 virtual void RemoveValues(const std::vector<int64_t>& values);
4062
4063 /// This method intersects the current domain with the values in the array.
4064 virtual void SetValues(const std::vector<int64_t>& values);
4065
4066 /// This method attaches a demon that will be awakened when the
4067 /// variable is bound.
4068 virtual void WhenBound(Demon* d) = 0;
4069 /// This method attaches a closure that will be awakened when the
4070 /// variable is bound.
WhenBound(Solver::Closure closure)4071 void WhenBound(Solver::Closure closure) {
4072 WhenBound(solver()->MakeClosureDemon(std::move(closure)));
4073 }
4074
4075 #if !defined(SWIG)
4076 /// This method attaches an action that will be awakened when the
4077 /// variable is bound.
WhenBound(Solver::Action action)4078 void WhenBound(Solver::Action action) {
4079 WhenBound(solver()->MakeActionDemon(std::move(action)));
4080 }
4081 #endif // SWIG
4082
4083 /// This method attaches a demon that will watch any domain
4084 /// modification of the domain of the variable.
4085 virtual void WhenDomain(Demon* d) = 0;
4086 /// This method attaches a closure that will watch any domain
4087 /// modification of the domain of the variable.
WhenDomain(Solver::Closure closure)4088 void WhenDomain(Solver::Closure closure) {
4089 WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
4090 }
4091 #if !defined(SWIG)
4092 /// This method attaches an action that will watch any domain
4093 /// modification of the domain of the variable.
WhenDomain(Solver::Action action)4094 void WhenDomain(Solver::Action action) {
4095 WhenDomain(solver()->MakeActionDemon(std::move(action)));
4096 }
4097 #endif // SWIG
4098
4099 /// This method returns the number of values in the domain of the variable.
4100 virtual uint64_t Size() const = 0;
4101
4102 /// This method returns whether the value 'v' is in the domain of the
4103 /// variable.
4104 virtual bool Contains(int64_t v) const = 0;
4105
4106 /// Creates a hole iterator. When 'reversible' is false, the returned
4107 /// object is created on the normal C++ heap and the solver does NOT
4108 /// take ownership of the object.
4109 virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;
4110
4111 /// Creates a domain iterator. When 'reversible' is false, the
4112 /// returned object is created on the normal C++ heap and the solver
4113 /// does NOT take ownership of the object.
4114 virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;
4115
4116 /// Returns the previous min.
4117 virtual int64_t OldMin() const = 0;
4118
4119 /// Returns the previous max.
4120 virtual int64_t OldMax() const = 0;
4121
4122 virtual int VarType() const;
4123
4124 /// Accepts the given visitor.
4125 void Accept(ModelVisitor* const visitor) const override;
4126
4127 /// IsEqual
4128 virtual IntVar* IsEqual(int64_t constant) = 0;
4129 virtual IntVar* IsDifferent(int64_t constant) = 0;
4130 virtual IntVar* IsGreaterOrEqual(int64_t constant) = 0;
4131 virtual IntVar* IsLessOrEqual(int64_t constant) = 0;
4132
4133 /// Returns the index of the variable.
index()4134 int index() const { return index_; }
4135
4136 private:
4137 const int index_;
4138 DISALLOW_COPY_AND_ASSIGN(IntVar);
4139 };
4140
4141 /// This class is the root class of all solution collectors.
4142 /// It implements a basic query API to be used independently
4143 /// of the collector used.
4144 class SolutionCollector : public SearchMonitor {
4145 public:
4146 SolutionCollector(Solver* const solver, const Assignment* assignment);
4147 explicit SolutionCollector(Solver* const solver);
4148 ~SolutionCollector() override;
DebugString()4149 std::string DebugString() const override { return "SolutionCollector"; }
4150
4151 /// Add API.
4152 void Add(IntVar* const var);
4153 void Add(const std::vector<IntVar*>& vars);
4154 void Add(IntervalVar* const var);
4155 void Add(const std::vector<IntervalVar*>& vars);
4156 void Add(SequenceVar* const var);
4157 void Add(const std::vector<SequenceVar*>& vars);
4158 void AddObjective(IntVar* const objective);
4159
4160 /// Beginning of the search.
4161 void EnterSearch() override;
4162
4163 /// Returns how many solutions were stored during the search.
4164 int solution_count() const;
4165
4166 /// Returns the nth solution.
4167 Assignment* solution(int n) const;
4168
4169 /// Returns the wall time in ms for the nth solution.
4170 int64_t wall_time(int n) const;
4171
4172 /// Returns the number of branches when the nth solution was found.
4173 int64_t branches(int n) const;
4174
4175 /// Returns the number of failures encountered at the time of the nth
4176 /// solution.
4177 int64_t failures(int n) const;
4178
4179 /// Returns the objective value of the nth solution.
4180 int64_t objective_value(int n) const;
4181
4182 /// This is a shortcut to get the Value of 'var' in the nth solution.
4183 int64_t Value(int n, IntVar* const var) const;
4184
4185 /// This is a shortcut to get the StartValue of 'var' in the nth solution.
4186 int64_t StartValue(int n, IntervalVar* const var) const;
4187
4188 /// This is a shortcut to get the EndValue of 'var' in the nth solution.
4189 int64_t EndValue(int n, IntervalVar* const var) const;
4190
4191 /// This is a shortcut to get the DurationValue of 'var' in the nth solution.
4192 int64_t DurationValue(int n, IntervalVar* const var) const;
4193
4194 /// This is a shortcut to get the PerformedValue of 'var' in the nth solution.
4195 int64_t PerformedValue(int n, IntervalVar* const var) const;
4196
4197 /// This is a shortcut to get the ForwardSequence of 'var' in the
4198 /// nth solution. The forward sequence is the list of ranked interval
4199 /// variables starting from the start of the sequence.
4200 const std::vector<int>& ForwardSequence(int n, SequenceVar* const var) const;
4201 /// This is a shortcut to get the BackwardSequence of 'var' in the
4202 /// nth solution. The backward sequence is the list of ranked interval
4203 /// variables starting from the end of the sequence.
4204 const std::vector<int>& BackwardSequence(int n, SequenceVar* const var) const;
4205 /// This is a shortcut to get the list of unperformed of 'var' in the
4206 /// nth solution.
4207 const std::vector<int>& Unperformed(int n, SequenceVar* const var) const;
4208
4209 protected:
4210 struct SolutionData {
4211 Assignment* solution;
4212 int64_t time;
4213 int64_t branches;
4214 int64_t failures;
4215 int64_t objective_value;
4216 bool operator<(const SolutionData& other) const {
4217 return std::tie(solution, time, branches, failures, objective_value) <
4218 std::tie(other.solution, other.time, other.branches,
4219 other.failures, other.objective_value);
4220 }
4221 };
4222
4223 /// Push the current state as a new solution.
4224 void PushSolution();
Push(const SolutionData & data)4225 void Push(const SolutionData& data) { solution_data_.push_back(data); }
4226 /// Remove and delete the last popped solution.
4227 void PopSolution();
4228 SolutionData BuildSolutionDataForCurrentState();
4229 void FreeSolution(Assignment* solution);
4230 void check_index(int n) const;
4231
4232 std::unique_ptr<Assignment> prototype_;
4233 std::vector<SolutionData> solution_data_;
4234 std::vector<Assignment*> recycle_solutions_;
4235
4236 private:
4237 DISALLOW_COPY_AND_ASSIGN(SolutionCollector);
4238 };
4239
4240 // TODO(user): Refactor this into an Objective class:
4241 // - print methods for AtNode and AtSolution.
4242 // - support for weighted objective and lexicographical objective.
4243
4244 /// This class encapsulates an objective. It requires the direction
4245 /// (minimize or maximize), the variable to optimize, and the
4246 /// improvement step.
4247 class OptimizeVar : public SearchMonitor {
4248 public:
4249 OptimizeVar(Solver* const s, bool maximize, IntVar* const a, int64_t step);
4250 ~OptimizeVar() override;
4251
4252 /// Returns the best value found during search.
best()4253 int64_t best() const { return best_; }
4254
4255 /// Returns the variable that is optimized.
Var()4256 IntVar* Var() const { return var_; }
4257 /// Internal methods.
4258 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
4259 void EnterSearch() override;
4260 void BeginNextDecision(DecisionBuilder* const db) override;
4261 void RefuteDecision(Decision* const d) override;
4262 bool AtSolution() override;
4263 bool AcceptSolution() override;
4264 virtual std::string Print() const;
4265 std::string DebugString() const override;
4266 void Accept(ModelVisitor* const visitor) const override;
4267
4268 void ApplyBound();
4269
4270 protected:
4271 IntVar* const var_;
4272 int64_t step_;
4273 int64_t best_;
4274 bool maximize_;
4275 bool found_initial_solution_;
4276
4277 private:
4278 DISALLOW_COPY_AND_ASSIGN(OptimizeVar);
4279 };
4280
4281 /// Base class of all search limits.
4282 class SearchLimit : public SearchMonitor {
4283 public:
SearchLimit(Solver * const s)4284 explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
4285 ~SearchLimit() override;
4286
4287 /// Returns true if the limit has been crossed.
crossed()4288 bool crossed() const { return crossed_; }
4289
4290 /// This method is called to check the status of the limit. A return
4291 /// value of true indicates that we have indeed crossed the limit. In
4292 /// that case, this method will not be called again and the remaining
4293 /// search will be discarded.
4294 virtual bool Check() = 0;
4295
4296 /// This method is called when the search limit is initialized.
4297 virtual void Init() = 0;
4298
4299 /// Copy a limit. Warning: leads to a direct (no check) downcasting of 'limit'
4300 /// so one needs to be sure both SearchLimits are of the same type.
4301 virtual void Copy(const SearchLimit* const limit) = 0;
4302
4303 /// Allocates a clone of the limit.
4304 virtual SearchLimit* MakeClone() const = 0;
4305
4306 /// Internal methods.
4307 void EnterSearch() override;
4308 void BeginNextDecision(DecisionBuilder* const b) override;
4309 void PeriodicCheck() override;
4310 void RefuteDecision(Decision* const d) override;
DebugString()4311 std::string DebugString() const override {
4312 return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
4313 }
4314
4315 private:
4316 void TopPeriodicCheck();
4317
4318 bool crossed_;
4319 DISALLOW_COPY_AND_ASSIGN(SearchLimit);
4320 };
4321
4322 /// Usual limit based on wall_time, number of explored branches and
4323 /// number of failures in the search tree
4324 class RegularLimit : public SearchLimit {
4325 public:
4326 RegularLimit(Solver* const s, absl::Duration time, int64_t branches,
4327 int64_t failures, int64_t solutions, bool smart_time_check,
4328 bool cumulative);
4329 ~RegularLimit() override;
4330 void Copy(const SearchLimit* const limit) override;
4331 SearchLimit* MakeClone() const override;
4332 RegularLimit* MakeIdenticalClone() const;
4333 bool Check() override;
4334 void Init() override;
4335 void ExitSearch() override;
4336 void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures,
4337 int64_t solutions);
duration_limit()4338 absl::Duration duration_limit() const { return duration_limit_; }
wall_time()4339 int64_t wall_time() const {
4340 return duration_limit_ == absl::InfiniteDuration()
4341 ? kint64max
4342 : absl::ToInt64Milliseconds(duration_limit());
4343 }
branches()4344 int64_t branches() const { return branches_; }
failures()4345 int64_t failures() const { return failures_; }
solutions()4346 int64_t solutions() const { return solutions_; }
4347 bool IsUncheckedSolutionLimitReached() override;
4348 int ProgressPercent() override;
4349 std::string DebugString() const override;
4350
AbsoluteSolverDeadline()4351 absl::Time AbsoluteSolverDeadline() const {
4352 return solver_time_at_limit_start_ + duration_limit_;
4353 }
4354
4355 void Accept(ModelVisitor* const visitor) const override;
4356
4357 private:
4358 bool CheckTime();
4359 absl::Duration TimeElapsed();
GetPercent(int64_t value,int64_t offset,int64_t total)4360 static int64_t GetPercent(int64_t value, int64_t offset, int64_t total) {
4361 return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
4362 : -1;
4363 }
4364
4365 absl::Duration duration_limit_;
4366 absl::Time solver_time_at_limit_start_;
4367 absl::Duration last_time_elapsed_;
4368 int64_t check_count_;
4369 int64_t next_check_;
4370 bool smart_time_check_;
4371 int64_t branches_;
4372 int64_t branches_offset_;
4373 int64_t failures_;
4374 int64_t failures_offset_;
4375 int64_t solutions_;
4376 int64_t solutions_offset_;
4377 /// If cumulative if false, then the limit applies to each search
4378 /// independently. If it's true, the limit applies globally to all search for
4379 /// which this monitor is used.
4380 /// When cumulative is true, the offset fields have two different meanings
4381 /// depending on context:
4382 /// - within a search, it's an offset to be subtracted from the current value
4383 /// - outside of search, it's the amount consumed in previous searches
4384 bool cumulative_;
4385 };
4386
4387 // Limit based on the improvement rate of 'objective_var'.
4388 // This limit proceeds in two stages:
4389 // 1) During the phase of the search in which the objective_var is strictly
4390 // improving, a threshold value is computed as the minimum improvement rate of
4391 // the objective, based on the 'improvement_rate_coefficient' and
4392 // 'improvement_rate_solutions_distance' parameters.
4393 // 2) Then, if the search continues beyond this phase of strict improvement, the
4394 // limit stops the search when the improvement rate of the objective gets below
4395 // this threshold value.
4396 class ImprovementSearchLimit : public SearchLimit {
4397 public:
4398 ImprovementSearchLimit(Solver* const s, IntVar* objective_var, bool maximize,
4399 double objective_scaling_factor,
4400 double objective_offset,
4401 double improvement_rate_coefficient,
4402 int improvement_rate_solutions_distance);
4403 ~ImprovementSearchLimit() override;
4404 void Copy(const SearchLimit* const limit) override;
4405 SearchLimit* MakeClone() const override;
4406 bool Check() override;
4407 bool AtSolution() override;
4408 void Init() override;
4409
4410 private:
4411 IntVar* objective_var_;
4412 bool maximize_;
4413 double objective_scaling_factor_;
4414 double objective_offset_;
4415 double improvement_rate_coefficient_;
4416 int improvement_rate_solutions_distance_;
4417
4418 double best_objective_;
4419 // clang-format off
4420 std::deque<std::pair<double, int64_t> > improvements_;
4421 // clang-format on
4422 double threshold_;
4423 bool objective_updated_;
4424 bool gradient_stage_;
4425 };
4426
4427 /// Interval variables are often used in scheduling. The main characteristics
4428 /// of an IntervalVar are the start position, duration, and end
4429 /// date. All these characteristics can be queried and set, and demons can
4430 /// be posted on their modifications.
4431 ///
4432 /// An important aspect is optionality: an IntervalVar can be performed or not.
4433 /// If unperformed, then it simply does not exist, and its characteristics
4434 /// cannot be accessed any more. An interval var is automatically marked
4435 /// as unperformed when it is not consistent anymore (start greater
4436 /// than end, duration < 0...)
4437 class IntervalVar : public PropagationBaseObject {
4438 public:
4439 /// The smallest acceptable value to be returned by StartMin()
4440 static const int64_t kMinValidValue;
4441 /// The largest acceptable value to be returned by EndMax()
4442 static const int64_t kMaxValidValue;
IntervalVar(Solver * const solver,const std::string & name)4443 IntervalVar(Solver* const solver, const std::string& name)
4444 : PropagationBaseObject(solver) {
4445 set_name(name);
4446 }
~IntervalVar()4447 ~IntervalVar() override {}
4448
4449 /// These methods query, set, and watch the start position of the
4450 /// interval var.
4451 virtual int64_t StartMin() const = 0;
4452 virtual int64_t StartMax() const = 0;
4453 virtual void SetStartMin(int64_t m) = 0;
4454 virtual void SetStartMax(int64_t m) = 0;
4455 virtual void SetStartRange(int64_t mi, int64_t ma) = 0;
4456 virtual int64_t OldStartMin() const = 0;
4457 virtual int64_t OldStartMax() const = 0;
4458 virtual void WhenStartRange(Demon* const d) = 0;
WhenStartRange(Solver::Closure closure)4459 void WhenStartRange(Solver::Closure closure) {
4460 WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4461 }
4462 #if !defined(SWIG)
WhenStartRange(Solver::Action action)4463 void WhenStartRange(Solver::Action action) {
4464 WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4465 }
4466 #endif // SWIG
4467 virtual void WhenStartBound(Demon* const d) = 0;
WhenStartBound(Solver::Closure closure)4468 void WhenStartBound(Solver::Closure closure) {
4469 WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4470 }
4471 #if !defined(SWIG)
WhenStartBound(Solver::Action action)4472 void WhenStartBound(Solver::Action action) {
4473 WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4474 }
4475 #endif // SWIG
4476
4477 /// These methods query, set, and watch the duration of the interval var.
4478 virtual int64_t DurationMin() const = 0;
4479 virtual int64_t DurationMax() const = 0;
4480 virtual void SetDurationMin(int64_t m) = 0;
4481 virtual void SetDurationMax(int64_t m) = 0;
4482 virtual void SetDurationRange(int64_t mi, int64_t ma) = 0;
4483 virtual int64_t OldDurationMin() const = 0;
4484 virtual int64_t OldDurationMax() const = 0;
4485 virtual void WhenDurationRange(Demon* const d) = 0;
WhenDurationRange(Solver::Closure closure)4486 void WhenDurationRange(Solver::Closure closure) {
4487 WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4488 }
4489 #if !defined(SWIG)
WhenDurationRange(Solver::Action action)4490 void WhenDurationRange(Solver::Action action) {
4491 WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4492 }
4493 #endif // SWIG
4494 virtual void WhenDurationBound(Demon* const d) = 0;
WhenDurationBound(Solver::Closure closure)4495 void WhenDurationBound(Solver::Closure closure) {
4496 WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4497 }
4498 #if !defined(SWIG)
WhenDurationBound(Solver::Action action)4499 void WhenDurationBound(Solver::Action action) {
4500 WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4501 }
4502 #endif // SWIG
4503
4504 /// These methods query, set, and watch the end position of the interval var.
4505 virtual int64_t EndMin() const = 0;
4506 virtual int64_t EndMax() const = 0;
4507 virtual void SetEndMin(int64_t m) = 0;
4508 virtual void SetEndMax(int64_t m) = 0;
4509 virtual void SetEndRange(int64_t mi, int64_t ma) = 0;
4510 virtual int64_t OldEndMin() const = 0;
4511 virtual int64_t OldEndMax() const = 0;
4512 virtual void WhenEndRange(Demon* const d) = 0;
WhenEndRange(Solver::Closure closure)4513 void WhenEndRange(Solver::Closure closure) {
4514 WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4515 }
4516 #if !defined(SWIG)
WhenEndRange(Solver::Action action)4517 void WhenEndRange(Solver::Action action) {
4518 WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4519 }
4520 #endif // SWIG
4521 virtual void WhenEndBound(Demon* const d) = 0;
WhenEndBound(Solver::Closure closure)4522 void WhenEndBound(Solver::Closure closure) {
4523 WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4524 }
4525 #if !defined(SWIG)
WhenEndBound(Solver::Action action)4526 void WhenEndBound(Solver::Action action) {
4527 WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4528 }
4529 #endif // SWIG
4530
4531 /// These methods query, set, and watch the performed status of the
4532 /// interval var.
4533 virtual bool MustBePerformed() const = 0;
4534 virtual bool MayBePerformed() const = 0;
CannotBePerformed()4535 bool CannotBePerformed() const { return !MayBePerformed(); }
IsPerformedBound()4536 bool IsPerformedBound() const {
4537 return MustBePerformed() || !MayBePerformed();
4538 }
4539 virtual void SetPerformed(bool val) = 0;
4540 virtual bool WasPerformedBound() const = 0;
4541 virtual void WhenPerformedBound(Demon* const d) = 0;
WhenPerformedBound(Solver::Closure closure)4542 void WhenPerformedBound(Solver::Closure closure) {
4543 WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4544 }
4545 #if !defined(SWIG)
WhenPerformedBound(Solver::Action action)4546 void WhenPerformedBound(Solver::Action action) {
4547 WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4548 }
4549 #endif // SWIG
4550
4551 /// Attaches a demon awakened when anything about this interval changes.
4552 void WhenAnything(Demon* const d);
4553 /// Attaches a closure awakened when anything about this interval changes.
WhenAnything(Solver::Closure closure)4554 void WhenAnything(Solver::Closure closure) {
4555 WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4556 }
4557 #if !defined(SWIG)
4558 /// Attaches an action awakened when anything about this interval changes.
WhenAnything(Solver::Action action)4559 void WhenAnything(Solver::Action action) {
4560 WhenAnything(solver()->MakeActionDemon(std::move(action)));
4561 }
4562 #endif // SWIG
4563
4564 /// These methods create expressions encapsulating the start, end
4565 /// and duration of the interval var. Please note that these must not
4566 /// be used if the interval var is unperformed.
4567 virtual IntExpr* StartExpr() = 0;
4568 virtual IntExpr* DurationExpr() = 0;
4569 virtual IntExpr* EndExpr() = 0;
4570 virtual IntExpr* PerformedExpr() = 0;
4571 /// These methods create expressions encapsulating the start, end
4572 /// and duration of the interval var. If the interval var is
4573 /// unperformed, they will return the unperformed_value.
4574 virtual IntExpr* SafeStartExpr(int64_t unperformed_value) = 0;
4575 virtual IntExpr* SafeDurationExpr(int64_t unperformed_value) = 0;
4576 virtual IntExpr* SafeEndExpr(int64_t unperformed_value) = 0;
4577
4578 /// Accepts the given visitor.
4579 virtual void Accept(ModelVisitor* const visitor) const = 0;
4580
4581 private:
4582 DISALLOW_COPY_AND_ASSIGN(IntervalVar);
4583 };
4584
4585 /// A sequence variable is a variable whose domain is a set of possible
4586 /// orderings of the interval variables. It allows ordering of tasks. It
4587 /// has two sets of methods: ComputePossibleFirstsAndLasts(), which
4588 /// returns the list of interval variables that can be ranked first or
4589 /// last; and RankFirst/RankNotFirst/RankLast/RankNotLast, which can be
4590 /// used to create the search decision.
4591 class SequenceVar : public PropagationBaseObject {
4592 public:
4593 SequenceVar(Solver* const s, const std::vector<IntervalVar*>& intervals,
4594 const std::vector<IntVar*>& nexts, const std::string& name);
4595
4596 ~SequenceVar() override;
4597
4598 std::string DebugString() const override;
4599
4600 #if !defined(SWIG)
4601 /// Returns the minimum and maximum duration of combined interval
4602 /// vars in the sequence.
4603 void DurationRange(int64_t* const dmin, int64_t* const dmax) const;
4604
4605 /// Returns the minimum start min and the maximum end max of all
4606 /// interval vars in the sequence.
4607 void HorizonRange(int64_t* const hmin, int64_t* const hmax) const;
4608
4609 /// Returns the minimum start min and the maximum end max of all
4610 /// unranked interval vars in the sequence.
4611 void ActiveHorizonRange(int64_t* const hmin, int64_t* const hmax) const;
4612
4613 /// Compute statistics on the sequence.
4614 void ComputeStatistics(int* const ranked, int* const not_ranked,
4615 int* const unperformed) const;
4616 #endif // !defined(SWIG)
4617
4618 /// Ranks the index_th interval var first of all unranked interval
4619 /// vars. After that, it will no longer be considered ranked.
4620 void RankFirst(int index);
4621
4622 /// Indicates that the index_th interval var will not be ranked first
4623 /// of all currently unranked interval vars.
4624 void RankNotFirst(int index);
4625
4626 /// Ranks the index_th interval var first of all unranked interval
4627 /// vars. After that, it will no longer be considered ranked.
4628 void RankLast(int index);
4629
4630 /// Indicates that the index_th interval var will not be ranked first
4631 /// of all currently unranked interval vars.
4632 void RankNotLast(int index);
4633
4634 /// Computes the set of indices of interval variables that can be
4635 /// ranked first in the set of unranked activities.
4636 void ComputePossibleFirstsAndLasts(std::vector<int>* const possible_firsts,
4637 std::vector<int>* const possible_lasts);
4638
4639 /// Applies the following sequence of ranks, ranks first, then rank
4640 /// last. rank_first and rank_last represents different directions.
4641 /// rank_first[0] corresponds to the first interval of the sequence.
4642 /// rank_last[0] corresponds to the last interval of the sequence.
4643 /// All intervals in the unperformed vector will be marked as such.
4644 void RankSequence(const std::vector<int>& rank_first,
4645 const std::vector<int>& rank_last,
4646 const std::vector<int>& unperformed);
4647
4648 /// Clears 'rank_first' and 'rank_last', and fills them with the
4649 /// intervals in the order of the ranks. If all variables are ranked,
4650 /// 'rank_first' will contain all variables, and 'rank_last' will
4651 /// contain none.
4652 /// 'unperformed' will contains all such interval variables.
4653 /// rank_first and rank_last represents different directions.
4654 /// rank_first[0] corresponds to the first interval of the sequence.
4655 /// rank_last[0] corresponds to the last interval of the sequence.
4656 void FillSequence(std::vector<int>* const rank_first,
4657 std::vector<int>* const rank_last,
4658 std::vector<int>* const unperformed) const;
4659
4660 /// Returns the index_th interval of the sequence.
4661 IntervalVar* Interval(int index) const;
4662
4663 /// Returns the next of the index_th interval of the sequence.
4664 IntVar* Next(int index) const;
4665
4666 /// Returns the number of interval vars in the sequence.
size()4667 int64_t size() const { return intervals_.size(); }
4668
4669 /// Accepts the given visitor.
4670 virtual void Accept(ModelVisitor* const visitor) const;
4671
4672 private:
4673 int ComputeForwardFrontier();
4674 int ComputeBackwardFrontier();
4675 void UpdatePrevious() const;
4676
4677 const std::vector<IntervalVar*> intervals_;
4678 const std::vector<IntVar*> nexts_;
4679 mutable std::vector<int> previous_;
4680 };
4681
4682 class AssignmentElement {
4683 public:
AssignmentElement()4684 AssignmentElement() : activated_(true) {}
4685
Activate()4686 void Activate() { activated_ = true; }
Deactivate()4687 void Deactivate() { activated_ = false; }
Activated()4688 bool Activated() const { return activated_; }
4689
4690 private:
4691 bool activated_;
4692 };
4693
4694 class IntVarElement : public AssignmentElement {
4695 public:
4696 IntVarElement();
4697 explicit IntVarElement(IntVar* const var);
4698 void Reset(IntVar* const var);
4699 IntVarElement* Clone();
4700 void Copy(const IntVarElement& element);
Var()4701 IntVar* Var() const { return var_; }
Store()4702 void Store() {
4703 min_ = var_->Min();
4704 max_ = var_->Max();
4705 }
Restore()4706 void Restore() {
4707 if (var_ != nullptr) {
4708 var_->SetRange(min_, max_);
4709 }
4710 }
4711 void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
4712 void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
4713
Min()4714 int64_t Min() const { return min_; }
SetMin(int64_t m)4715 void SetMin(int64_t m) { min_ = m; }
Max()4716 int64_t Max() const { return max_; }
SetMax(int64_t m)4717 void SetMax(int64_t m) { max_ = m; }
Value()4718 int64_t Value() const {
4719 DCHECK_EQ(min_, max_);
4720 // Get the value from an unbound int var assignment element.
4721 return min_;
4722 }
Bound()4723 bool Bound() const { return (max_ == min_); }
SetRange(int64_t l,int64_t u)4724 void SetRange(int64_t l, int64_t u) {
4725 min_ = l;
4726 max_ = u;
4727 }
SetValue(int64_t v)4728 void SetValue(int64_t v) {
4729 min_ = v;
4730 max_ = v;
4731 }
4732 std::string DebugString() const;
4733
4734 bool operator==(const IntVarElement& element) const;
4735 bool operator!=(const IntVarElement& element) const {
4736 return !(*this == element);
4737 }
4738
4739 private:
4740 IntVar* var_;
4741 int64_t min_;
4742 int64_t max_;
4743 };
4744
4745 class IntervalVarElement : public AssignmentElement {
4746 public:
4747 IntervalVarElement();
4748 explicit IntervalVarElement(IntervalVar* const var);
4749 void Reset(IntervalVar* const var);
4750 IntervalVarElement* Clone();
4751 void Copy(const IntervalVarElement& element);
Var()4752 IntervalVar* Var() const { return var_; }
4753 void Store();
4754 void Restore();
4755 void LoadFromProto(
4756 const IntervalVarAssignment& interval_var_assignment_proto);
4757 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
4758
StartMin()4759 int64_t StartMin() const { return start_min_; }
StartMax()4760 int64_t StartMax() const { return start_max_; }
StartValue()4761 int64_t StartValue() const {
4762 CHECK_EQ(start_max_, start_min_);
4763 return start_max_;
4764 }
DurationMin()4765 int64_t DurationMin() const { return duration_min_; }
DurationMax()4766 int64_t DurationMax() const { return duration_max_; }
DurationValue()4767 int64_t DurationValue() const {
4768 CHECK_EQ(duration_max_, duration_min_);
4769 return duration_max_;
4770 }
EndMin()4771 int64_t EndMin() const { return end_min_; }
EndMax()4772 int64_t EndMax() const { return end_max_; }
EndValue()4773 int64_t EndValue() const {
4774 CHECK_EQ(end_max_, end_min_);
4775 return end_max_;
4776 }
PerformedMin()4777 int64_t PerformedMin() const { return performed_min_; }
PerformedMax()4778 int64_t PerformedMax() const { return performed_max_; }
PerformedValue()4779 int64_t PerformedValue() const {
4780 CHECK_EQ(performed_max_, performed_min_);
4781 return performed_max_;
4782 }
SetStartMin(int64_t m)4783 void SetStartMin(int64_t m) { start_min_ = m; }
SetStartMax(int64_t m)4784 void SetStartMax(int64_t m) { start_max_ = m; }
SetStartRange(int64_t mi,int64_t ma)4785 void SetStartRange(int64_t mi, int64_t ma) {
4786 start_min_ = mi;
4787 start_max_ = ma;
4788 }
SetStartValue(int64_t v)4789 void SetStartValue(int64_t v) {
4790 start_min_ = v;
4791 start_max_ = v;
4792 }
SetDurationMin(int64_t m)4793 void SetDurationMin(int64_t m) { duration_min_ = m; }
SetDurationMax(int64_t m)4794 void SetDurationMax(int64_t m) { duration_max_ = m; }
SetDurationRange(int64_t mi,int64_t ma)4795 void SetDurationRange(int64_t mi, int64_t ma) {
4796 duration_min_ = mi;
4797 duration_max_ = ma;
4798 }
SetDurationValue(int64_t v)4799 void SetDurationValue(int64_t v) {
4800 duration_min_ = v;
4801 duration_max_ = v;
4802 }
SetEndMin(int64_t m)4803 void SetEndMin(int64_t m) { end_min_ = m; }
SetEndMax(int64_t m)4804 void SetEndMax(int64_t m) { end_max_ = m; }
SetEndRange(int64_t mi,int64_t ma)4805 void SetEndRange(int64_t mi, int64_t ma) {
4806 end_min_ = mi;
4807 end_max_ = ma;
4808 }
SetEndValue(int64_t v)4809 void SetEndValue(int64_t v) {
4810 end_min_ = v;
4811 end_max_ = v;
4812 }
SetPerformedMin(int64_t m)4813 void SetPerformedMin(int64_t m) { performed_min_ = m; }
SetPerformedMax(int64_t m)4814 void SetPerformedMax(int64_t m) { performed_max_ = m; }
SetPerformedRange(int64_t mi,int64_t ma)4815 void SetPerformedRange(int64_t mi, int64_t ma) {
4816 performed_min_ = mi;
4817 performed_max_ = ma;
4818 }
SetPerformedValue(int64_t v)4819 void SetPerformedValue(int64_t v) {
4820 performed_min_ = v;
4821 performed_max_ = v;
4822 }
Bound()4823 bool Bound() const {
4824 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4825 end_min_ == end_max_ && performed_min_ == performed_max_);
4826 }
4827 std::string DebugString() const;
4828 bool operator==(const IntervalVarElement& element) const;
4829 bool operator!=(const IntervalVarElement& element) const {
4830 return !(*this == element);
4831 }
4832
4833 private:
4834 int64_t start_min_;
4835 int64_t start_max_;
4836 int64_t duration_min_;
4837 int64_t duration_max_;
4838 int64_t end_min_;
4839 int64_t end_max_;
4840 int64_t performed_min_;
4841 int64_t performed_max_;
4842 IntervalVar* var_;
4843 };
4844
4845 /// The SequenceVarElement stores a partial representation of ranked
4846 /// interval variables in the underlying sequence variable.
4847 /// This representation consists of three vectors:
4848 /// - the forward sequence. That is the list of interval variables
4849 /// ranked first in the sequence. The first element of the backward
4850 /// sequence is the first interval in the sequence variable.
4851 /// - the backward sequence. That is the list of interval variables
4852 /// ranked last in the sequence. The first element of the backward
4853 /// sequence is the last interval in the sequence variable.
4854 /// - The list of unperformed interval variables.
4855 /// Furthermore, if all performed variables are ranked, then by
4856 /// convention, the forward_sequence will contain all such variables
4857 /// and the backward_sequence will be empty.
4858 class SequenceVarElement : public AssignmentElement {
4859 public:
4860 SequenceVarElement();
4861 explicit SequenceVarElement(SequenceVar* const var);
4862 void Reset(SequenceVar* const var);
4863 SequenceVarElement* Clone();
4864 void Copy(const SequenceVarElement& element);
Var()4865 SequenceVar* Var() const { return var_; }
4866 void Store();
4867 void Restore();
4868 void LoadFromProto(
4869 const SequenceVarAssignment& sequence_var_assignment_proto);
4870 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
4871
4872 const std::vector<int>& ForwardSequence() const;
4873 const std::vector<int>& BackwardSequence() const;
4874 const std::vector<int>& Unperformed() const;
4875 void SetSequence(const std::vector<int>& forward_sequence,
4876 const std::vector<int>& backward_sequence,
4877 const std::vector<int>& unperformed);
4878 void SetForwardSequence(const std::vector<int>& forward_sequence);
4879 void SetBackwardSequence(const std::vector<int>& backward_sequence);
4880 void SetUnperformed(const std::vector<int>& unperformed);
Bound()4881 bool Bound() const {
4882 return forward_sequence_.size() + unperformed_.size() == var_->size();
4883 }
4884
4885 std::string DebugString() const;
4886
4887 bool operator==(const SequenceVarElement& element) const;
4888 bool operator!=(const SequenceVarElement& element) const {
4889 return !(*this == element);
4890 }
4891
4892 private:
4893 bool CheckClassInvariants();
4894
4895 SequenceVar* var_;
4896 std::vector<int> forward_sequence_;
4897 std::vector<int> backward_sequence_;
4898 std::vector<int> unperformed_;
4899 };
4900
4901 template <class V, class E>
4902 class AssignmentContainer {
4903 public:
AssignmentContainer()4904 AssignmentContainer() {}
Add(V * var)4905 E* Add(V* var) {
4906 CHECK(var != nullptr);
4907 int index = -1;
4908 if (!Find(var, &index)) {
4909 return FastAdd(var);
4910 } else {
4911 return &elements_[index];
4912 }
4913 }
4914 /// Adds element without checking its presence in the container.
FastAdd(V * var)4915 E* FastAdd(V* var) {
4916 DCHECK(var != nullptr);
4917 elements_.emplace_back(var);
4918 return &elements_.back();
4919 }
4920 /// Advanced usage: Adds element at a given position; position has to have
4921 /// been allocated with AssignmentContainer::Resize() beforehand.
AddAtPosition(V * var,int position)4922 E* AddAtPosition(V* var, int position) {
4923 elements_[position].Reset(var);
4924 return &elements_[position];
4925 }
Clear()4926 void Clear() {
4927 elements_.clear();
4928 if (!elements_map_.empty()) { /// 2x speedup on OR-Tools.
4929 elements_map_.clear();
4930 }
4931 }
4932 /// Advanced usage: Resizes the container, potentially adding elements with
4933 /// null variables.
Resize(size_t size)4934 void Resize(size_t size) { elements_.resize(size); }
Empty()4935 bool Empty() const { return elements_.empty(); }
4936 /// Copies the elements of 'container' which are already in the calling
4937 /// container.
CopyIntersection(const AssignmentContainer<V,E> & container)4938 void CopyIntersection(const AssignmentContainer<V, E>& container) {
4939 for (int i = 0; i < container.elements_.size(); ++i) {
4940 const E& element = container.elements_[i];
4941 const V* const var = element.Var();
4942 int index = -1;
4943 if (i < elements_.size() && elements_[i].Var() == var) {
4944 index = i;
4945 } else if (!Find(var, &index)) {
4946 continue;
4947 }
4948 DCHECK_GE(index, 0);
4949 E* const local_element = &elements_[index];
4950 local_element->Copy(element);
4951 if (element.Activated()) {
4952 local_element->Activate();
4953 } else {
4954 local_element->Deactivate();
4955 }
4956 }
4957 }
4958 /// Copies all the elements of 'container' to this container, clearing its
4959 /// previous content.
Copy(const AssignmentContainer<V,E> & container)4960 void Copy(const AssignmentContainer<V, E>& container) {
4961 Clear();
4962 for (int i = 0; i < container.elements_.size(); ++i) {
4963 const E& element = container.elements_[i];
4964 FastAdd(element.Var())->Copy(element);
4965 }
4966 }
Contains(const V * const var)4967 bool Contains(const V* const var) const {
4968 int index;
4969 return Find(var, &index);
4970 }
MutableElement(const V * const var)4971 E* MutableElement(const V* const var) {
4972 E* const element = MutableElementOrNull(var);
4973 DCHECK(element != nullptr)
4974 << "Unknown variable " << var->DebugString() << " in solution";
4975 return element;
4976 }
MutableElementOrNull(const V * const var)4977 E* MutableElementOrNull(const V* const var) {
4978 int index = -1;
4979 if (Find(var, &index)) {
4980 return MutableElement(index);
4981 }
4982 return nullptr;
4983 }
Element(const V * const var)4984 const E& Element(const V* const var) const {
4985 const E* const element = ElementPtrOrNull(var);
4986 DCHECK(element != nullptr)
4987 << "Unknown variable " << var->DebugString() << " in solution";
4988 return *element;
4989 }
ElementPtrOrNull(const V * const var)4990 const E* ElementPtrOrNull(const V* const var) const {
4991 int index = -1;
4992 if (Find(var, &index)) {
4993 return &Element(index);
4994 }
4995 return nullptr;
4996 }
elements()4997 const std::vector<E>& elements() const { return elements_; }
MutableElement(int index)4998 E* MutableElement(int index) { return &elements_[index]; }
Element(int index)4999 const E& Element(int index) const { return elements_[index]; }
Size()5000 int Size() const { return elements_.size(); }
Store()5001 void Store() {
5002 for (E& element : elements_) {
5003 element.Store();
5004 }
5005 }
Restore()5006 void Restore() {
5007 for (E& element : elements_) {
5008 if (element.Activated()) {
5009 element.Restore();
5010 }
5011 }
5012 }
AreAllElementsBound()5013 bool AreAllElementsBound() const {
5014 for (const E& element : elements_) {
5015 if (!element.Bound()) return false;
5016 }
5017 return true;
5018 }
5019
5020 /// Returns true if this and 'container' both represent the same V* -> E map.
5021 /// Runs in linear time; requires that the == operator on the type E is well
5022 /// defined.
5023 bool operator==(const AssignmentContainer<V, E>& container) const {
5024 /// We may not have any work to do
5025 if (Size() != container.Size()) {
5026 return false;
5027 }
5028 /// The == should be order-independent
5029 EnsureMapIsUpToDate();
5030 /// Do not use the hash_map::== operator! It
5031 /// compares both content and how the map is hashed (e.g., number of
5032 /// buckets). This is not what we want.
5033 for (const E& element : container.elements_) {
5034 const int position =
5035 gtl::FindWithDefault(elements_map_, element.Var(), -1);
5036 if (position < 0 || elements_[position] != element) {
5037 return false;
5038 }
5039 }
5040 return true;
5041 }
5042 bool operator!=(const AssignmentContainer<V, E>& container) const {
5043 return !(*this == container);
5044 }
5045
5046 private:
EnsureMapIsUpToDate()5047 void EnsureMapIsUpToDate() const {
5048 absl::flat_hash_map<const V*, int>* map =
5049 const_cast<absl::flat_hash_map<const V*, int>*>(&elements_map_);
5050 for (int i = map->size(); i < elements_.size(); ++i) {
5051 (*map)[elements_[i].Var()] = i;
5052 }
5053 }
Find(const V * const var,int * index)5054 bool Find(const V* const var, int* index) const {
5055 /// This threshold was determined from microbenchmarks on Nehalem platform.
5056 const size_t kMaxSizeForLinearAccess = 11;
5057 if (Size() <= kMaxSizeForLinearAccess) {
5058 /// Look for 'var' in the container by performing a linear
5059 /// search, avoiding the access to (and creation of) the elements
5060 /// hash table.
5061 for (int i = 0; i < elements_.size(); ++i) {
5062 if (var == elements_[i].Var()) {
5063 *index = i;
5064 return true;
5065 }
5066 }
5067 return false;
5068 } else {
5069 EnsureMapIsUpToDate();
5070 DCHECK_EQ(elements_map_.size(), elements_.size());
5071 return gtl::FindCopy(elements_map_, var, index);
5072 }
5073 }
5074
5075 std::vector<E> elements_;
5076 absl::flat_hash_map<const V*, int> elements_map_;
5077 };
5078
5079 /// An Assignment is a variable -> domains mapping, used
5080 /// to report solutions to the user.
5081 class Assignment : public PropagationBaseObject {
5082 public:
5083 typedef AssignmentContainer<IntVar, IntVarElement> IntContainer;
5084 typedef AssignmentContainer<IntervalVar, IntervalVarElement>
5085 IntervalContainer;
5086 typedef AssignmentContainer<SequenceVar, SequenceVarElement>
5087 SequenceContainer;
5088
5089 explicit Assignment(Solver* const s);
5090 explicit Assignment(const Assignment* const copy);
5091 ~Assignment() override;
5092
5093 void Clear();
Empty()5094 bool Empty() const {
5095 return int_var_container_.Empty() && interval_var_container_.Empty() &&
5096 sequence_var_container_.Empty();
5097 }
Size()5098 int Size() const {
5099 return NumIntVars() + NumIntervalVars() + NumSequenceVars();
5100 }
NumIntVars()5101 int NumIntVars() const { return int_var_container_.Size(); }
NumIntervalVars()5102 int NumIntervalVars() const { return interval_var_container_.Size(); }
NumSequenceVars()5103 int NumSequenceVars() const { return sequence_var_container_.Size(); }
5104 void Store();
5105 void Restore();
5106
5107 /// Loads an assignment from a file; does not add variables to the
5108 /// assignment (only the variables contained in the assignment are modified).
5109 bool Load(const std::string& filename);
5110 #if !defined(SWIG)
5111 bool Load(File* file);
5112 #endif /// #if !defined(SWIG)
5113 void Load(const AssignmentProto& assignment_proto);
5114 /// Saves the assignment to a file.
5115 bool Save(const std::string& filename) const;
5116 #if !defined(SWIG)
5117 bool Save(File* file) const;
5118 #endif // #if !defined(SWIG)
5119 void Save(AssignmentProto* const assignment_proto) const;
5120
5121 void AddObjective(IntVar* const v);
ClearObjective()5122 void ClearObjective() { objective_element_.Reset(nullptr); }
5123 IntVar* Objective() const;
HasObjective()5124 bool HasObjective() const { return (objective_element_.Var() != nullptr); }
5125 int64_t ObjectiveMin() const;
5126 int64_t ObjectiveMax() const;
5127 int64_t ObjectiveValue() const;
5128 bool ObjectiveBound() const;
5129 void SetObjectiveMin(int64_t m);
5130 void SetObjectiveMax(int64_t m);
5131 void SetObjectiveValue(int64_t value);
5132 void SetObjectiveRange(int64_t l, int64_t u);
5133
5134 IntVarElement* Add(IntVar* const var);
5135 void Add(const std::vector<IntVar*>& vars);
5136 /// Adds without checking if variable has been previously added.
5137 IntVarElement* FastAdd(IntVar* const var);
5138 int64_t Min(const IntVar* const var) const;
5139 int64_t Max(const IntVar* const var) const;
5140 int64_t Value(const IntVar* const var) const;
5141 bool Bound(const IntVar* const var) const;
5142 void SetMin(const IntVar* const var, int64_t m);
5143 void SetMax(const IntVar* const var, int64_t m);
5144 void SetRange(const IntVar* const var, int64_t l, int64_t u);
5145 void SetValue(const IntVar* const var, int64_t value);
5146
5147 IntervalVarElement* Add(IntervalVar* const var);
5148 void Add(const std::vector<IntervalVar*>& vars);
5149 /// Adds without checking if variable has been previously added.
5150 IntervalVarElement* FastAdd(IntervalVar* const var);
5151 int64_t StartMin(const IntervalVar* const var) const;
5152 int64_t StartMax(const IntervalVar* const var) const;
5153 int64_t StartValue(const IntervalVar* const var) const;
5154 int64_t DurationMin(const IntervalVar* const var) const;
5155 int64_t DurationMax(const IntervalVar* const var) const;
5156 int64_t DurationValue(const IntervalVar* const var) const;
5157 int64_t EndMin(const IntervalVar* const var) const;
5158 int64_t EndMax(const IntervalVar* const var) const;
5159 int64_t EndValue(const IntervalVar* const var) const;
5160 int64_t PerformedMin(const IntervalVar* const var) const;
5161 int64_t PerformedMax(const IntervalVar* const var) const;
5162 int64_t PerformedValue(const IntervalVar* const var) const;
5163 void SetStartMin(const IntervalVar* const var, int64_t m);
5164 void SetStartMax(const IntervalVar* const var, int64_t m);
5165 void SetStartRange(const IntervalVar* const var, int64_t mi, int64_t ma);
5166 void SetStartValue(const IntervalVar* const var, int64_t value);
5167 void SetDurationMin(const IntervalVar* const var, int64_t m);
5168 void SetDurationMax(const IntervalVar* const var, int64_t m);
5169 void SetDurationRange(const IntervalVar* const var, int64_t mi, int64_t ma);
5170 void SetDurationValue(const IntervalVar* const var, int64_t value);
5171 void SetEndMin(const IntervalVar* const var, int64_t m);
5172 void SetEndMax(const IntervalVar* const var, int64_t m);
5173 void SetEndRange(const IntervalVar* const var, int64_t mi, int64_t ma);
5174 void SetEndValue(const IntervalVar* const var, int64_t value);
5175 void SetPerformedMin(const IntervalVar* const var, int64_t m);
5176 void SetPerformedMax(const IntervalVar* const var, int64_t m);
5177 void SetPerformedRange(const IntervalVar* const var, int64_t mi, int64_t ma);
5178 void SetPerformedValue(const IntervalVar* const var, int64_t value);
5179
5180 SequenceVarElement* Add(SequenceVar* const var);
5181 void Add(const std::vector<SequenceVar*>& vars);
5182 /// Adds without checking if the variable had been previously added.
5183 SequenceVarElement* FastAdd(SequenceVar* const var);
5184 const std::vector<int>& ForwardSequence(const SequenceVar* const var) const;
5185 const std::vector<int>& BackwardSequence(const SequenceVar* const var) const;
5186 const std::vector<int>& Unperformed(const SequenceVar* const var) const;
5187 void SetSequence(const SequenceVar* const var,
5188 const std::vector<int>& forward_sequence,
5189 const std::vector<int>& backward_sequence,
5190 const std::vector<int>& unperformed);
5191 void SetForwardSequence(const SequenceVar* const var,
5192 const std::vector<int>& forward_sequence);
5193 void SetBackwardSequence(const SequenceVar* const var,
5194 const std::vector<int>& backward_sequence);
5195 void SetUnperformed(const SequenceVar* const var,
5196 const std::vector<int>& unperformed);
5197
5198 void Activate(const IntVar* const var);
5199 void Deactivate(const IntVar* const var);
5200 bool Activated(const IntVar* const var) const;
5201
5202 void Activate(const IntervalVar* const var);
5203 void Deactivate(const IntervalVar* const var);
5204 bool Activated(const IntervalVar* const var) const;
5205
5206 void Activate(const SequenceVar* const var);
5207 void Deactivate(const SequenceVar* const var);
5208 bool Activated(const SequenceVar* const var) const;
5209
5210 void ActivateObjective();
5211 void DeactivateObjective();
5212 bool ActivatedObjective() const;
5213
5214 std::string DebugString() const override;
5215
AreAllElementsBound()5216 bool AreAllElementsBound() const {
5217 return int_var_container_.AreAllElementsBound() &&
5218 interval_var_container_.AreAllElementsBound() &&
5219 sequence_var_container_.AreAllElementsBound();
5220 }
5221
5222 bool Contains(const IntVar* const var) const;
5223 bool Contains(const IntervalVar* const var) const;
5224 bool Contains(const SequenceVar* const var) const;
5225 /// Copies the intersection of the two assignments to the current assignment.
5226 void CopyIntersection(const Assignment* assignment);
5227 /// Copies 'assignment' to the current assignment, clearing its previous
5228 /// content.
5229 void Copy(const Assignment* assignment);
5230
5231 // TODO(user): Add element iterators to avoid exposing container class.
IntVarContainer()5232 const IntContainer& IntVarContainer() const { return int_var_container_; }
MutableIntVarContainer()5233 IntContainer* MutableIntVarContainer() { return &int_var_container_; }
IntervalVarContainer()5234 const IntervalContainer& IntervalVarContainer() const {
5235 return interval_var_container_;
5236 }
MutableIntervalVarContainer()5237 IntervalContainer* MutableIntervalVarContainer() {
5238 return &interval_var_container_;
5239 }
SequenceVarContainer()5240 const SequenceContainer& SequenceVarContainer() const {
5241 return sequence_var_container_;
5242 }
MutableSequenceVarContainer()5243 SequenceContainer* MutableSequenceVarContainer() {
5244 return &sequence_var_container_;
5245 }
5246 bool operator==(const Assignment& assignment) const {
5247 return int_var_container_ == assignment.int_var_container_ &&
5248 interval_var_container_ == assignment.interval_var_container_ &&
5249 sequence_var_container_ == assignment.sequence_var_container_ &&
5250 objective_element_ == assignment.objective_element_;
5251 }
5252 bool operator!=(const Assignment& assignment) const {
5253 return !(*this == assignment);
5254 }
5255
5256 private:
5257 IntContainer int_var_container_;
5258 IntervalContainer interval_var_container_;
5259 SequenceContainer sequence_var_container_;
5260 IntVarElement objective_element_;
5261 DISALLOW_COPY_AND_ASSIGN(Assignment);
5262 };
5263
5264 std::ostream& operator<<(std::ostream& out,
5265 const Assignment& assignment); /// NOLINT
5266
5267 /// Given a "source_assignment", clears the "target_assignment" and adds
5268 /// all IntVars in "target_vars", with the values of the variables set according
5269 /// to the corresponding values of "source_vars" in "source_assignment".
5270 /// source_vars and target_vars must have the same number of elements.
5271 /// The source and target assignments can belong to different Solvers.
5272 void SetAssignmentFromAssignment(Assignment* target_assignment,
5273 const std::vector<IntVar*>& target_vars,
5274 const Assignment* source_assignment,
5275 const std::vector<IntVar*>& source_vars);
5276
5277 class Pack : public Constraint {
5278 public:
5279 Pack(Solver* const s, const std::vector<IntVar*>& vars, int number_of_bins);
5280
5281 ~Pack() override;
5282
5283 /// Dimensions are additional constraints than can restrict what is
5284 /// possible with the pack constraint. It can be used to set capacity
5285 /// limits, to count objects per bin, to compute unassigned
5286 /// penalties...
5287
5288 /// This dimension imposes that for all bins b, the weighted sum
5289 /// (weights[i]) of all objects i assigned to 'b' is less or equal
5290 /// 'bounds[b]'.
5291 void AddWeightedSumLessOrEqualConstantDimension(
5292 const std::vector<int64_t>& weights, const std::vector<int64_t>& bounds);
5293
5294 /// This dimension imposes that for all bins b, the weighted sum
5295 /// (weights->Run(i)) of all objects i assigned to 'b' is less or
5296 /// equal to 'bounds[b]'. Ownership of the callback is transferred to
5297 /// the pack constraint.
5298 void AddWeightedSumLessOrEqualConstantDimension(
5299 Solver::IndexEvaluator1 weights, const std::vector<int64_t>& bounds);
5300
5301 /// This dimension imposes that for all bins b, the weighted sum
5302 /// (weights->Run(i, b) of all objects i assigned to 'b' is less or
5303 /// equal to 'bounds[b]'. Ownership of the callback is transferred to
5304 /// the pack constraint.
5305 void AddWeightedSumLessOrEqualConstantDimension(
5306 Solver::IndexEvaluator2 weights, const std::vector<int64_t>& bounds);
5307
5308 /// This dimension imposes that for all bins b, the weighted sum
5309 /// (weights[i]) of all objects i assigned to 'b' is equal to loads[b].
5310 void AddWeightedSumEqualVarDimension(const std::vector<int64_t>& weights,
5311 const std::vector<IntVar*>& loads);
5312
5313 /// This dimension imposes that for all bins b, the weighted sum
5314 /// (weights->Run(i, b)) of all objects i assigned to 'b' is equal to
5315 /// loads[b].
5316 void AddWeightedSumEqualVarDimension(Solver::IndexEvaluator2 weights,
5317 const std::vector<IntVar*>& loads);
5318
5319 /// This dimension imposes:
5320 /// forall b in bins,
5321 /// sum (i in items: usage[i] * is_assigned(i, b)) <= capacity[b]
5322 /// where is_assigned(i, b) is true if and only if item i is assigned
5323 /// to the bin b.
5324 ///
5325 /// This can be used to model shapes of items by linking variables of
5326 /// the same item on parallel dimensions with an allowed assignment
5327 /// constraint.
5328 void AddSumVariableWeightsLessOrEqualConstantDimension(
5329 const std::vector<IntVar*>& usage, const std::vector<int64_t>& capacity);
5330
5331 /// This dimension enforces that cost_var == sum of weights[i] for
5332 /// all objects 'i' assigned to a bin.
5333 void AddWeightedSumOfAssignedDimension(const std::vector<int64_t>& weights,
5334 IntVar* const cost_var);
5335
5336 /// This dimension links 'count_var' to the actual number of bins used in the
5337 /// pack.
5338 void AddCountUsedBinDimension(IntVar* const count_var);
5339
5340 /// This dimension links 'count_var' to the actual number of items
5341 /// assigned to a bin in the pack.
5342 void AddCountAssignedItemsDimension(IntVar* const count_var);
5343
5344 void Post() override;
5345 void ClearAll();
5346 void PropagateDelayed();
5347 void InitialPropagate() override;
5348 void Propagate();
5349 void OneDomain(int var_index);
5350 std::string DebugString() const override;
5351 bool IsUndecided(int var_index, int bin_index) const;
5352 void SetImpossible(int var_index, int bin_index);
5353 void Assign(int var_index, int bin_index);
5354 bool IsAssignedStatusKnown(int var_index) const;
5355 bool IsPossible(int var_index, int bin_index) const;
5356 IntVar* AssignVar(int var_index, int bin_index) const;
5357 void SetAssigned(int var_index);
5358 void SetUnassigned(int var_index);
5359 void RemoveAllPossibleFromBin(int bin_index);
5360 void AssignAllPossibleToBin(int bin_index);
5361 void AssignFirstPossibleToBin(int bin_index);
5362 void AssignAllRemainingItems();
5363 void UnassignAllRemainingItems();
5364 void Accept(ModelVisitor* const visitor) const override;
5365
5366 private:
5367 bool IsInProcess() const;
5368 const std::vector<IntVar*> vars_;
5369 const int bins_;
5370 std::vector<Dimension*> dims_;
5371 std::unique_ptr<RevBitMatrix> unprocessed_;
5372 std::vector<std::vector<int>> forced_;
5373 std::vector<std::vector<int>> removed_;
5374 std::vector<IntVarIterator*> holes_;
5375 uint64_t stamp_;
5376 Demon* demon_;
5377 std::vector<std::pair<int, int>> to_set_;
5378 std::vector<std::pair<int, int>> to_unset_;
5379 bool in_process_;
5380 };
5381
5382 class DisjunctiveConstraint : public Constraint {
5383 public:
5384 DisjunctiveConstraint(Solver* const s,
5385 const std::vector<IntervalVar*>& intervals,
5386 const std::string& name);
5387 ~DisjunctiveConstraint() override;
5388
5389 /// Creates a sequence variable from the constraint.
5390 virtual SequenceVar* MakeSequenceVar() = 0;
5391
5392 /// Add a transition time between intervals. It forces the distance between
5393 /// the end of interval a and start of interval b that follows it to be at
5394 /// least transition_time(a, b). This function must always return
5395 /// a positive or null value.
5396 void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5397
TransitionTime(int before_index,int after_index)5398 int64_t TransitionTime(int before_index, int after_index) {
5399 DCHECK(transition_time_);
5400 return transition_time_(before_index, after_index);
5401 }
5402
5403 #if !defined(SWIG)
5404 virtual const std::vector<IntVar*>& nexts() const = 0;
5405 virtual const std::vector<IntVar*>& actives() const = 0;
5406 virtual const std::vector<IntVar*>& time_cumuls() const = 0;
5407 virtual const std::vector<IntVar*>& time_slacks() const = 0;
5408 #endif // !defined(SWIG)
5409
5410 protected:
5411 const std::vector<IntervalVar*> intervals_;
5412 Solver::IndexEvaluator2 transition_time_;
5413
5414 private:
5415 DISALLOW_COPY_AND_ASSIGN(DisjunctiveConstraint);
5416 };
5417
5418 /// This class is used to manage a pool of solutions. It can transform
5419 /// a single point local search into a multipoint local search.
5420 class SolutionPool : public BaseObject {
5421 public:
SolutionPool()5422 SolutionPool() {}
~SolutionPool()5423 ~SolutionPool() override {}
5424
5425 /// This method is called to initialize the solution pool with the assignment
5426 /// from the local search.
5427 virtual void Initialize(Assignment* const assignment) = 0;
5428
5429 /// This method is called when a new solution has been accepted by the local
5430 /// search.
5431 virtual void RegisterNewSolution(Assignment* const assignment) = 0;
5432
5433 /// This method is called when the local search starts a new neighborhood to
5434 /// initialize the default assignment.
5435 virtual void GetNextSolution(Assignment* const assignment) = 0;
5436
5437 /// This method checks if the local solution needs to be updated with
5438 /// an external one.
5439 virtual bool SyncNeeded(Assignment* const local_assignment) = 0;
5440 };
5441 } // namespace operations_research
5442
5443 #endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
5444