-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
integer.h
2084 lines (1796 loc) · 85.1 KB
/
integer.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef OR_TOOLS_SAT_INTEGER_H_
#define OR_TOOLS_SAT_INTEGER_H_
#include <stdlib.h>
#include <algorithm>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <memory>
#include <ostream>
#include <string>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/container/btree_map.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/inlined_vector.h"
#include "absl/log/check.h"
#include "absl/strings/str_cat.h"
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/base/strong_vector.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_base.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/sat/sat_solver.h"
#include "ortools/util/bitset.h"
#include "ortools/util/rev.h"
#include "ortools/util/saturated_arithmetic.h"
#include "ortools/util/sorted_interval_list.h"
#include "ortools/util/strong_integers.h"
#include "ortools/util/time_limit.h"
namespace operations_research {
namespace sat {
// Value type of an integer variable. An integer variable is always bounded
// on both sides, and this type is also used to store the bounds [lb, ub] of the
// range of each integer variable.
//
// Note that both bounds are inclusive, which allows to write many propagation
// algorithms for just one of the bound and apply it to the negated variables to
// get the symmetric algorithm for the other bound.
DEFINE_STRONG_INT64_TYPE(IntegerValue);
// The max range of an integer variable is [kMinIntegerValue, kMaxIntegerValue].
//
// It is symmetric so the set of possible ranges stays the same when we take the
// negation of a variable. Moreover, we need some IntegerValue that fall outside
// this range on both side so that we can usually take care of integer overflow
// by simply doing "saturated arithmetic" and if one of the bound overflow, the
// two bounds will "cross" each others and we will get an empty range.
constexpr IntegerValue kMaxIntegerValue(
std::numeric_limits<IntegerValue::ValueType>::max() - 1);
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value());
inline double ToDouble(IntegerValue value) {
const double kInfinity = std::numeric_limits<double>::infinity();
if (value >= kMaxIntegerValue) return kInfinity;
if (value <= kMinIntegerValue) return -kInfinity;
return static_cast<double>(value.value());
}
template <class IntType>
inline IntType IntTypeAbs(IntType t) {
return IntType(std::abs(t.value()));
}
inline IntegerValue CeilRatio(IntegerValue dividend,
IntegerValue positive_divisor) {
DCHECK_GT(positive_divisor, 0);
const IntegerValue result = dividend / positive_divisor;
const IntegerValue adjust =
static_cast<IntegerValue>(result * positive_divisor < dividend);
return result + adjust;
}
inline IntegerValue FloorRatio(IntegerValue dividend,
IntegerValue positive_divisor) {
DCHECK_GT(positive_divisor, 0);
const IntegerValue result = dividend / positive_divisor;
const IntegerValue adjust =
static_cast<IntegerValue>(result * positive_divisor > dividend);
return result - adjust;
}
// Overflows and saturated arithmetic.
inline IntegerValue CapProdI(IntegerValue a, IntegerValue b) {
return IntegerValue(CapProd(a.value(), b.value()));
}
inline IntegerValue CapSubI(IntegerValue a, IntegerValue b) {
return IntegerValue(CapSub(a.value(), b.value()));
}
inline IntegerValue CapAddI(IntegerValue a, IntegerValue b) {
return IntegerValue(CapAdd(a.value(), b.value()));
}
inline bool ProdOverflow(IntegerValue t, IntegerValue value) {
return AtMinOrMaxInt64(CapProd(t.value(), value.value()));
}
inline bool AtMinOrMaxInt64I(IntegerValue t) {
return AtMinOrMaxInt64(t.value());
}
// Helper for dividing several small integers by the same value. Note that there
// is no point using this class is the divisor is a compile-time constant, since
// the compiler should be smart enough to do this automatically.
// Building a `QuickSmallDivision` object costs an integer division, but each
// call to `DivideByDivisor` will only do an integer multiplication and a shift.
//
// This class always return the exact value of the division for all possible
// values of `dividend` and `divisor`.
class QuickSmallDivision {
public:
explicit QuickSmallDivision(uint16_t divisor)
: inverse_((1ull << 48) / divisor + 1) {}
uint16_t DivideByDivisor(uint16_t dividend) const {
return static_cast<uint16_t>((inverse_ * static_cast<uint64_t>(dividend)) >>
48);
}
private:
uint64_t inverse_;
};
// Returns dividend - FloorRatio(dividend, divisor) * divisor;
//
// This function is around the same speed than the computation above, but it
// never causes integer overflow. Note also that when calling FloorRatio() then
// PositiveRemainder(), the compiler should optimize the modulo away and just
// reuse the one from the first integer division.
inline IntegerValue PositiveRemainder(IntegerValue dividend,
IntegerValue positive_divisor) {
DCHECK_GT(positive_divisor, 0);
const IntegerValue m = dividend % positive_divisor;
return m < 0 ? m + positive_divisor : m;
}
inline bool AddTo(IntegerValue a, IntegerValue* result) {
if (AtMinOrMaxInt64I(a)) return false;
const IntegerValue add = CapAddI(a, *result);
if (AtMinOrMaxInt64I(add)) return false;
*result = add;
return true;
}
// Computes result += a * b, and return false iff there is an overflow.
inline bool AddProductTo(IntegerValue a, IntegerValue b, IntegerValue* result) {
const IntegerValue prod = CapProdI(a, b);
if (AtMinOrMaxInt64I(prod)) return false;
const IntegerValue add = CapAddI(prod, *result);
if (AtMinOrMaxInt64I(add)) return false;
*result = add;
return true;
}
// Index of an IntegerVariable.
//
// Each time we create an IntegerVariable we also create its negation. This is
// done like that so internally we only stores and deal with lower bound. The
// upper bound being the lower bound of the negated variable.
DEFINE_STRONG_INDEX_TYPE(IntegerVariable);
const IntegerVariable kNoIntegerVariable(-1);
inline IntegerVariable NegationOf(IntegerVariable i) {
return IntegerVariable(i.value() ^ 1);
}
inline bool VariableIsPositive(IntegerVariable i) {
return (i.value() & 1) == 0;
}
inline IntegerVariable PositiveVariable(IntegerVariable i) {
return IntegerVariable(i.value() & (~1));
}
// Special type for storing only one thing for var and NegationOf(var).
DEFINE_STRONG_INDEX_TYPE(PositiveOnlyIndex);
inline PositiveOnlyIndex GetPositiveOnlyIndex(IntegerVariable var) {
return PositiveOnlyIndex(var.value() / 2);
}
inline std::string IntegerTermDebugString(IntegerVariable var,
IntegerValue coeff) {
coeff = VariableIsPositive(var) ? coeff : -coeff;
return absl::StrCat(coeff.value(), "*X", var.value() / 2);
}
// Returns the vector of the negated variables.
std::vector<IntegerVariable> NegationOf(
const std::vector<IntegerVariable>& vars);
// The integer equivalent of a literal.
// It represents an IntegerVariable and an upper/lower bound on it.
//
// Overflow: all the bounds below kMinIntegerValue and kMaxIntegerValue are
// treated as kMinIntegerValue - 1 and kMaxIntegerValue + 1.
struct IntegerLiteral {
// Because IntegerLiteral should never be created at a bound less constrained
// than an existing IntegerVariable bound, we don't allow GreaterOrEqual() to
// have a bound lower than kMinIntegerValue, and LowerOrEqual() to have a
// bound greater than kMaxIntegerValue. The other side is not constrained
// to allow for a computed bound to overflow. Note that both the full initial
// domain and the empty domain can always be represented.
static IntegerLiteral GreaterOrEqual(IntegerVariable i, IntegerValue bound);
static IntegerLiteral LowerOrEqual(IntegerVariable i, IntegerValue bound);
// These two static integer literals represent an always true and an always
// false condition.
static IntegerLiteral TrueLiteral();
static IntegerLiteral FalseLiteral();
// Clients should prefer the static construction methods above.
IntegerLiteral() : var(kNoIntegerVariable), bound(0) {}
IntegerLiteral(IntegerVariable v, IntegerValue b) : var(v), bound(b) {
DCHECK_GE(bound, kMinIntegerValue);
DCHECK_LE(bound, kMaxIntegerValue + 1);
}
bool IsValid() const { return var != kNoIntegerVariable; }
bool IsAlwaysTrue() const { return var == kNoIntegerVariable && bound <= 0; }
bool IsAlwaysFalse() const { return var == kNoIntegerVariable && bound > 0; }
// The negation of x >= bound is x <= bound - 1.
IntegerLiteral Negated() const;
bool operator==(IntegerLiteral o) const {
return var == o.var && bound == o.bound;
}
bool operator!=(IntegerLiteral o) const {
return var != o.var || bound != o.bound;
}
std::string DebugString() const {
return VariableIsPositive(var)
? absl::StrCat("I", var.value() / 2, ">=", bound.value())
: absl::StrCat("I", var.value() / 2, "<=", -bound.value());
}
// Note that bound should be in [kMinIntegerValue, kMaxIntegerValue + 1].
IntegerVariable var = kNoIntegerVariable;
IntegerValue bound = IntegerValue(0);
};
inline std::ostream& operator<<(std::ostream& os, IntegerLiteral i_lit) {
os << i_lit.DebugString();
return os;
}
inline std::ostream& operator<<(std::ostream& os,
absl::Span<const IntegerLiteral> literals) {
os << "[";
bool first = true;
for (const IntegerLiteral literal : literals) {
if (first) {
first = false;
} else {
os << ",";
}
os << literal.DebugString();
}
os << "]";
return os;
}
using InlinedIntegerLiteralVector = absl::InlinedVector<IntegerLiteral, 2>;
using InlinedIntegerValueVector =
absl::InlinedVector<std::pair<IntegerVariable, IntegerValue>, 2>;
// Represents [coeff * variable + constant] or just a [constant].
//
// In some places it is useful to manipulate such expression instead of having
// to create an extra integer variable. This is mainly used for scheduling
// related constraints.
struct AffineExpression {
// Helper to construct an AffineExpression.
AffineExpression() = default;
AffineExpression(IntegerValue cst) // NOLINT(runtime/explicit)
: constant(cst) {}
AffineExpression(IntegerVariable v) // NOLINT(runtime/explicit)
: var(v), coeff(1) {}
AffineExpression(IntegerVariable v, IntegerValue c)
: var(c >= 0 ? v : NegationOf(v)), coeff(IntTypeAbs(c)) {}
AffineExpression(IntegerVariable v, IntegerValue c, IntegerValue cst)
: var(c >= 0 ? v : NegationOf(v)), coeff(IntTypeAbs(c)), constant(cst) {}
// Returns the integer literal corresponding to expression >= value or
// expression <= value.
//
// On constant expressions, they will return IntegerLiteral::TrueLiteral()
// or IntegerLiteral::FalseLiteral().
IntegerLiteral GreaterOrEqual(IntegerValue bound) const;
IntegerLiteral LowerOrEqual(IntegerValue bound) const;
AffineExpression Negated() const {
if (var == kNoIntegerVariable) return AffineExpression(-constant);
return AffineExpression(NegationOf(var), coeff, -constant);
}
AffineExpression MultipliedBy(IntegerValue multiplier) const {
// Note that this also works if multiplier is negative.
return AffineExpression(var, coeff * multiplier, constant * multiplier);
}
bool operator==(AffineExpression o) const {
return var == o.var && coeff == o.coeff && constant == o.constant;
}
// Returns the value of this affine expression given its variable value.
IntegerValue ValueAt(IntegerValue var_value) const {
return coeff * var_value + constant;
}
// Returns the affine expression value under a given LP solution.
double LpValue(const util_intops::StrongVector<IntegerVariable, double>&
lp_values) const {
if (var == kNoIntegerVariable) return ToDouble(constant);
return ToDouble(coeff) * lp_values[var] + ToDouble(constant);
}
bool IsConstant() const { return var == kNoIntegerVariable; }
std::string DebugString() const {
if (var == kNoIntegerVariable) return absl::StrCat(constant.value());
if (constant == 0) {
return absl::StrCat("(", coeff.value(), " * X", var.value(), ")");
} else {
return absl::StrCat("(", coeff.value(), " * X", var.value(), " + ",
constant.value(), ")");
}
}
// The coefficient MUST be positive. Use NegationOf(var) if needed.
//
// TODO(user): Make this private to enforce the invariant that coeff cannot be
// negative.
IntegerVariable var = kNoIntegerVariable; // kNoIntegerVariable for constant.
IntegerValue coeff = IntegerValue(0); // Zero for constant.
IntegerValue constant = IntegerValue(0);
};
template <typename H>
H AbslHashValue(H h, const AffineExpression& e) {
if (e.var != kNoIntegerVariable) {
h = H::combine(std::move(h), e.var);
h = H::combine(std::move(h), e.coeff);
}
h = H::combine(std::move(h), e.constant);
return h;
}
// A model singleton that holds the root level integer variable domains.
// we just store a single domain for both var and its negation.
struct IntegerDomains
: public util_intops::StrongVector<PositiveOnlyIndex, Domain> {};
// A model singleton used for debugging. If this is set in the model, then we
// can check that various derived constraint do not exclude this solution (if it
// is a known optimal solution for instance).
struct DebugSolution {
// This is the value of all proto variables.
// It should be of the same size of the PRESOLVED model and should correspond
// to a solution to the presolved model.
std::vector<int64_t> proto_values;
// This is filled from proto_values at load-time, and using the
// cp_model_mapping, we cache the solution of the integer variables that are
// mapped. Note that it is possible that not all integer variable are mapped.
//
// TODO(user): When this happen we should be able to infer the value of these
// derived variable in the solution. For now, we only do that for the
// objective variable.
util_intops::StrongVector<IntegerVariable, bool> ivar_has_value;
util_intops::StrongVector<IntegerVariable, IntegerValue> ivar_values;
};
// A value and a literal.
struct ValueLiteralPair {
struct CompareByLiteral {
bool operator()(const ValueLiteralPair& a,
const ValueLiteralPair& b) const {
return a.literal < b.literal;
}
};
struct CompareByValue {
bool operator()(const ValueLiteralPair& a,
const ValueLiteralPair& b) const {
return (a.value < b.value) ||
(a.value == b.value && a.literal < b.literal);
}
};
bool operator==(const ValueLiteralPair& o) const {
return value == o.value && literal == o.literal;
}
std::string DebugString() const;
IntegerValue value = IntegerValue(0);
Literal literal = Literal(kNoLiteralIndex);
};
std::ostream& operator<<(std::ostream& os, const ValueLiteralPair& p);
struct LiteralValueValue {
Literal literal;
IntegerValue left_value;
IntegerValue right_value;
// Used for testing.
bool operator==(const LiteralValueValue& rhs) const {
return literal.Index() == rhs.literal.Index() &&
left_value == rhs.left_value && right_value == rhs.right_value;
}
std::string DebugString() const {
return absl::StrCat("(lit(", literal.Index().value(), ") * ",
left_value.value(), " * ", right_value.value(), ")");
}
};
// Sometimes we propagate fact with no reason at a positive level, those
// will automatically be fixed on the next restart.
//
// TODO(user): If we change the logic to not restart right away, we probably
// need to remove duplicates bounds for the same variable.
struct DelayedRootLevelDeduction {
std::vector<Literal> literal_to_fix;
std::vector<IntegerLiteral> integer_literal_to_fix;
};
// Each integer variable x will be associated with a set of literals encoding
// (x >= v) for some values of v. This class maintains the relationship between
// the integer variables and such literals which can be created by a call to
// CreateAssociatedLiteral().
//
// The advantage of creating such Boolean variables is that the SatSolver which
// is driving the search can then take this variable as a decision and maintain
// these variables activity and so on. These variables can also be propagated
// directly by the learned clauses.
//
// This class also support a non-lazy full domain encoding which will create one
// literal per possible value in the domain. See FullyEncodeVariable(). This is
// meant to be called by constraints that directly work on the variable values
// like a table constraint or an all-diff constraint.
//
// TODO(user): We could also lazily create precedences Booleans between two
// arbitrary IntegerVariable. This is better done in the PrecedencesPropagator
// though.
class IntegerEncoder {
public:
explicit IntegerEncoder(Model* model)
: sat_solver_(model->GetOrCreate<SatSolver>()),
trail_(model->GetOrCreate<Trail>()),
delayed_to_fix_(model->GetOrCreate<DelayedRootLevelDeduction>()),
domains_(*model->GetOrCreate<IntegerDomains>()),
num_created_variables_(0) {}
// This type is neither copyable nor movable.
IntegerEncoder(const IntegerEncoder&) = delete;
IntegerEncoder& operator=(const IntegerEncoder&) = delete;
~IntegerEncoder() {
VLOG(1) << "#variables created = " << num_created_variables_;
}
// Memory optimization: you can call this before encoding variables.
void ReserveSpaceForNumVariables(int num_vars);
// Fully encode a variable using its current initial domain.
// If the variable is already fully encoded, this does nothing.
//
// This creates new Booleans variables as needed:
// 1) num_values for the literals X == value. Except when there is just
// two value in which case only one variable is created.
// 2) num_values - 3 for the literals X >= value or X <= value (using their
// negation). The -3 comes from the fact that we can reuse the equality
// literals for the two extreme points.
//
// The encoding for NegationOf(var) is automatically created too. It reuses
// the same Boolean variable as the encoding of var.
//
// TODO(user): It is currently only possible to call that at the decision
// level zero because we cannot add ternary clause in the middle of the
// search (for now). This is Checked.
void FullyEncodeVariable(IntegerVariable var);
// Returns true if we know that PartialDomainEncoding(var) span the full
// domain of var. This is always true if FullyEncodeVariable(var) has been
// called.
bool VariableIsFullyEncoded(IntegerVariable var) const;
// Returns the list of literal <=> var == value currently associated to the
// given variable. The result is sorted by value. We filter literal at false,
// and if a literal is true, then you will get a singleton. To be sure to get
// the full set of encoded value, then you should call this at level zero.
//
// The FullDomainEncoding() just check VariableIsFullyEncoded() and returns
// the same result.
//
// WARNING: The reference returned is only valid until the next call to one
// of these functions.
const std::vector<ValueLiteralPair>& FullDomainEncoding(
IntegerVariable var) const;
const std::vector<ValueLiteralPair>& PartialDomainEncoding(
IntegerVariable var) const;
// Returns the "canonical" (i_lit, negation of i_lit) pair. This mainly
// deal with domain with initial hole like [1,2][5,6] so that if one ask
// for x <= 3, this get canonicalized in the pair (x <= 2, x >= 5).
//
// Note that it is an error to call this with a literal that is trivially true
// or trivially false according to the initial variable domain. This is
// CHECKed to make sure we don't create wasteful literal.
//
// TODO(user): This is linear in the domain "complexity", we can do better if
// needed.
std::pair<IntegerLiteral, IntegerLiteral> Canonicalize(
IntegerLiteral i_lit) const;
// Returns, after creating it if needed, a Boolean literal such that:
// - if true, then the IntegerLiteral is true.
// - if false, then the negated IntegerLiteral is true.
//
// Note that this "canonicalize" the given literal first.
//
// This add the proper implications with the two "neighbor" literals of this
// one if they exist. This is the "list encoding" in: Thibaut Feydy, Peter J.
// Stuckey, "Lazy Clause Generation Reengineered", CP 2009.
Literal GetOrCreateAssociatedLiteral(IntegerLiteral i_lit);
Literal GetOrCreateLiteralAssociatedToEquality(IntegerVariable var,
IntegerValue value);
// Associates the Boolean literal to (X >= bound) or (X == value). If a
// literal was already associated to this fact, this will add an equality
// constraints between both literals. If the fact is trivially true or false,
// this will fix the given literal.
void AssociateToIntegerLiteral(Literal literal, IntegerLiteral i_lit);
void AssociateToIntegerEqualValue(Literal literal, IntegerVariable var,
IntegerValue value);
// Returns kNoLiteralIndex if there is no associated or the associated literal
// otherwise.
//
// Tricky: for domain with hole, like [0,1][5,6], we assume some equivalence
// classes, like >=2, >=3, >=4 are all the same as >= 5.
bool IsFixedOrHasAssociatedLiteral(IntegerLiteral i_lit) const;
LiteralIndex GetAssociatedLiteral(IntegerLiteral i_lit) const;
LiteralIndex GetAssociatedEqualityLiteral(IntegerVariable var,
IntegerValue value) const;
// Advanced usage. It is more efficient to create the associated literals in
// order, but it might be anoying to do so. Instead, you can first call
// DisableImplicationBetweenLiteral() and when you are done creating all the
// associated literals, you can call (only at level zero)
// AddAllImplicationsBetweenAssociatedLiterals() which will also turn back on
// the implications between literals for the one that will be added
// afterwards.
void DisableImplicationBetweenLiteral() { add_implications_ = false; }
void AddAllImplicationsBetweenAssociatedLiterals();
// Returns the IntegerLiterals that were associated with the given Literal.
const InlinedIntegerLiteralVector& GetIntegerLiterals(Literal lit) const {
if (lit.Index() >= reverse_encoding_.size()) {
return empty_integer_literal_vector_;
}
return reverse_encoding_[lit];
}
// Returns the variable == value pairs that were associated with the given
// Literal. Note that only positive IntegerVariable appears here.
const InlinedIntegerValueVector& GetEqualityLiterals(Literal lit) const {
if (lit.Index() >= reverse_equality_encoding_.size()) {
return empty_integer_value_vector_;
}
return reverse_equality_encoding_[lit];
}
// Returns all the variables for which this literal is associated to either
// var >= value or var == value.
const std::vector<IntegerVariable>& GetAllAssociatedVariables(
Literal lit) const {
temp_associated_vars_.clear();
for (const IntegerLiteral l : GetIntegerLiterals(lit)) {
temp_associated_vars_.push_back(l.var);
}
for (const auto& [var, value] : GetEqualityLiterals(lit)) {
temp_associated_vars_.push_back(var);
}
return temp_associated_vars_;
}
// If it exists, returns a [0,1] integer variable which is equal to 1 iff the
// given literal is true. Returns kNoIntegerVariable if such variable does not
// exist. Note that one can create one by creating a new IntegerVariable and
// calling AssociateToIntegerEqualValue().
IntegerVariable GetLiteralView(Literal lit) const {
if (lit.Index() >= literal_view_.size()) return kNoIntegerVariable;
return literal_view_[lit];
}
// If this is true, then a literal can be linearized with an affine expression
// involving an integer variable.
ABSL_MUST_USE_RESULT bool LiteralOrNegationHasView(
Literal lit, IntegerVariable* view = nullptr,
bool* view_is_direct = nullptr) const;
// Returns a Boolean literal associated with a bound lower than or equal to
// the one of the given IntegerLiteral. If the given IntegerLiteral is true,
// then the returned literal should be true too. Returns kNoLiteralIndex if no
// such literal was created.
//
// Ex: if 'i' is (x >= 4) and we already created a literal associated to
// (x >= 2) but not to (x >= 3), we will return the literal associated with
// (x >= 2).
LiteralIndex SearchForLiteralAtOrBefore(IntegerLiteral i_lit,
IntegerValue* bound) const;
// Gets the literal always set to true, make it if it does not exist.
Literal GetTrueLiteral() {
if (literal_index_true_ == kNoLiteralIndex) {
DCHECK_EQ(0, sat_solver_->CurrentDecisionLevel());
const Literal literal_true =
Literal(sat_solver_->NewBooleanVariable(), true);
literal_index_true_ = literal_true.Index();
// This might return false if we are already UNSAT.
// TODO(user): Make sure we abort right away on unsat!
(void)sat_solver_->AddUnitClause(literal_true);
}
return Literal(literal_index_true_);
}
Literal GetFalseLiteral() { return GetTrueLiteral().Negated(); }
// Returns the set of Literal associated to IntegerLiteral of the form var >=
// value. We make a copy, because this can be easily invalidated when calling
// any function of this class. So it is less efficient but safer.
std::vector<ValueLiteralPair> PartialGreaterThanEncoding(
IntegerVariable var) const;
// Makes sure all element in the >= encoding are non-trivial and canonical.
// The input variable must be positive.
bool UpdateEncodingOnInitialDomainChange(IntegerVariable var, Domain domain);
private:
// Adds the implications:
// Literal(before) <= associated_lit <= Literal(after).
// Arguments:
// - map is just encoding_by_var_[associated_lit.var] and is passed as a
// slight optimization.
// - 'it' is the current position of associated_lit in map, i.e. we must have
// it->second == associated_lit.
void AddImplications(
const absl::btree_map<IntegerValue, Literal>& map,
absl::btree_map<IntegerValue, Literal>::const_iterator it,
Literal associated_lit);
SatSolver* sat_solver_;
Trail* trail_;
DelayedRootLevelDeduction* delayed_to_fix_;
const IntegerDomains& domains_;
bool add_implications_ = true;
int64_t num_created_variables_ = 0;
// We keep all the literals associated to an Integer variable in a map ordered
// by bound (so we can properly add implications between the literals
// corresponding to the same variable).
//
// Note that we only keep this for positive variable.
// The one for the negation can be infered by it.
//
// Like x >= 1 x >= 4 x >= 5
// Correspond to x <= 0 x <= 3 x <= 4
// That is -x >= 0 -x >= -2 -x >= -4
//
// With potentially stronger <= bound if we fall into domain holes.
//
// TODO(user): Remove the entry no longer needed because of level zero
// propagations.
util_intops::StrongVector<PositiveOnlyIndex,
absl::btree_map<IntegerValue, Literal>>
encoding_by_var_;
// Store for a given LiteralIndex the list of its associated IntegerLiterals.
const InlinedIntegerLiteralVector empty_integer_literal_vector_;
util_intops::StrongVector<LiteralIndex, InlinedIntegerLiteralVector>
reverse_encoding_;
const InlinedIntegerValueVector empty_integer_value_vector_;
util_intops::StrongVector<LiteralIndex, InlinedIntegerValueVector>
reverse_equality_encoding_;
// Used by GetAllAssociatedVariables().
mutable std::vector<IntegerVariable> temp_associated_vars_;
// Store for a given LiteralIndex its IntegerVariable view or kNoLiteralIndex
// if there is none.
util_intops::StrongVector<LiteralIndex, IntegerVariable> literal_view_;
// Mapping (variable == value) -> associated literal. Note that even if
// there is more than one literal associated to the same fact, we just keep
// the first one that was added.
//
// Note that we only keep positive IntegerVariable here to reduce memory
// usage.
absl::flat_hash_map<std::pair<PositiveOnlyIndex, IntegerValue>, Literal>
equality_to_associated_literal_;
// Mutable because this is lazily cleaned-up by PartialDomainEncoding().
mutable util_intops::StrongVector<PositiveOnlyIndex,
absl::InlinedVector<ValueLiteralPair, 2>>
equality_by_var_;
// Variables that are fully encoded.
mutable util_intops::StrongVector<PositiveOnlyIndex, bool> is_fully_encoded_;
// A literal that is always true, convenient to encode trivial domains.
// This will be lazily created when needed.
LiteralIndex literal_index_true_ = kNoLiteralIndex;
// Temporary memory used by FullyEncodeVariable().
std::vector<IntegerValue> tmp_values_;
std::vector<ValueLiteralPair> tmp_encoding_;
// Temporary memory for the result of PartialDomainEncoding().
mutable std::vector<ValueLiteralPair> partial_encoding_;
};
class LazyReasonInterface {
public:
LazyReasonInterface() = default;
virtual ~LazyReasonInterface() = default;
// When called, this must fill the two vectors so that literals contains any
// Literal part of the reason and dependencies contains the trail index of any
// IntegerLiteral that is also part of the reason.
//
// Remark: integer_literal[trail_index] might not exist or has nothing to
// do with what was propagated.
//
// TODO(user): {id, propagation_slack, var_to_explain, trail_index} is just a
// generic "payload" and we should probably rename it as such so that each
// implementation can store different things.
virtual void Explain(int id, IntegerValue propagation_slack,
IntegerVariable var_to_explain, int trail_index,
std::vector<Literal>* literals_reason,
std::vector<int>* trail_indices_reason) = 0;
};
// This class maintains a set of integer variables with their current bounds.
// Bounds can be propagated from an external "source" and this class helps
// to maintain the reason for each propagation.
class IntegerTrail final : public SatPropagator {
public:
explicit IntegerTrail(Model* model)
: SatPropagator("IntegerTrail"),
delayed_to_fix_(model->GetOrCreate<DelayedRootLevelDeduction>()),
domains_(model->GetOrCreate<IntegerDomains>()),
encoder_(model->GetOrCreate<IntegerEncoder>()),
trail_(model->GetOrCreate<Trail>()),
sat_solver_(model->GetOrCreate<SatSolver>()),
time_limit_(model->GetOrCreate<TimeLimit>()),
parameters_(*model->GetOrCreate<SatParameters>()) {
model->GetOrCreate<SatSolver>()->AddPropagator(this);
}
// This type is neither copyable nor movable.
IntegerTrail(const IntegerTrail&) = delete;
IntegerTrail& operator=(const IntegerTrail&) = delete;
~IntegerTrail() final;
// SatPropagator interface. These functions make sure the current bounds
// information is in sync with the current solver literal trail. Any
// class/propagator using this class must make sure it is synced to the
// correct state before calling any of its functions.
bool Propagate(Trail* trail) final;
void Untrail(const Trail& trail, int literal_trail_index) final;
absl::Span<const Literal> Reason(const Trail& trail, int trail_index,
int64_t conflict_id) const final;
// Returns the number of created integer variables.
//
// Note that this is twice the number of call to AddIntegerVariable() since
// we automatically create the NegationOf() variable too.
IntegerVariable NumIntegerVariables() const {
return IntegerVariable(var_lbs_.size());
}
// Optimization: you can call this before calling AddIntegerVariable()
// num_vars time.
void ReserveSpaceForNumVariables(int num_vars);
// Adds a new integer variable. Adding integer variable can only be done when
// the decision level is zero (checked). The given bounds are INCLUSIVE and
// must not cross.
//
// Note on integer overflow: 'upper_bound - lower_bound' must fit on an
// int64_t, this is DCHECKed. More generally, depending on the constraints
// that are added, the bounds magnitude must be small enough to satisfy each
// constraint overflow precondition.
IntegerVariable AddIntegerVariable(IntegerValue lower_bound,
IntegerValue upper_bound);
// Same as above but for a more complex domain specified as a sorted list of
// disjoint intervals. See the Domain class.
IntegerVariable AddIntegerVariable(const Domain& domain);
// Returns the initial domain of the given variable. Note that the min/max
// are updated with level zero propagation, but not holes.
const Domain& InitialVariableDomain(IntegerVariable var) const;
// Takes the intersection with the current initial variable domain.
//
// TODO(user): There is some memory inefficiency if this is called many time
// because of the underlying data structure we use. In practice, when used
// with a presolve, this is not often used, so that is fine though.
bool UpdateInitialDomain(IntegerVariable var, Domain domain);
// Same as AddIntegerVariable(value, value), but this is a bit more efficient
// because it reuses another constant with the same value if its exist.
//
// Note(user): Creating constant integer variable is a bit wasteful, but not
// that much, and it allows to simplify a lot of constraints that do not need
// to handle this case any differently than the general one. Maybe there is a
// better solution, but this is not really high priority as of December 2016.
IntegerVariable GetOrCreateConstantIntegerVariable(IntegerValue value);
int NumConstantVariables() const;
// Same as AddIntegerVariable() but uses the maximum possible range. Note
// that since we take negation of bounds in various places, we make sure that
// we don't have overflow when we take the negation of the lower bound or of
// the upper bound.
IntegerVariable AddIntegerVariable() {
return AddIntegerVariable(kMinIntegerValue, kMaxIntegerValue);
}
// Returns the current lower/upper bound of the given integer variable.
IntegerValue LowerBound(IntegerVariable i) const;
IntegerValue UpperBound(IntegerVariable i) const;
// If one needs to do a lot of LowerBound()/UpperBound() it will be faster
// to cache the current pointer to the underlying vector.
const IntegerValue* LowerBoundsData() const { return var_lbs_.data(); }
// Checks if the variable is fixed.
bool IsFixed(IntegerVariable i) const;
// Checks that the variable is fixed and returns its value.
IntegerValue FixedValue(IntegerVariable i) const;
// Same as above for an affine expression.
IntegerValue LowerBound(AffineExpression expr) const;
IntegerValue UpperBound(AffineExpression expr) const;
bool IsFixed(AffineExpression expr) const;
IntegerValue FixedValue(AffineExpression expr) const;
// Returns the integer literal that represent the current lower/upper bound of
// the given integer variable.
IntegerLiteral LowerBoundAsLiteral(IntegerVariable i) const;
IntegerLiteral UpperBoundAsLiteral(IntegerVariable i) const;
// Returns the integer literal that represent the current lower/upper bound of
// the given affine expression. In case the expression is constant, it returns
// IntegerLiteral::TrueLiteral().
IntegerLiteral LowerBoundAsLiteral(AffineExpression expr) const;
IntegerLiteral UpperBoundAsLiteral(AffineExpression expr) const;
// Returns the current value (if known) of an IntegerLiteral.
bool IntegerLiteralIsTrue(IntegerLiteral l) const;
bool IntegerLiteralIsFalse(IntegerLiteral l) const;
// Returns globally valid lower/upper bound on the given integer variable.
IntegerValue LevelZeroLowerBound(IntegerVariable var) const;
IntegerValue LevelZeroUpperBound(IntegerVariable var) const;
// Returns globally valid lower/upper bound on the given affine expression.
IntegerValue LevelZeroLowerBound(AffineExpression exp) const;
IntegerValue LevelZeroUpperBound(AffineExpression exp) const;
// Returns true if the variable is fixed at level 0.
bool IsFixedAtLevelZero(IntegerVariable var) const;
// Returns true if the affine expression is fixed at level 0.
bool IsFixedAtLevelZero(AffineExpression expr) const;
// Advanced usage.
// Returns the current lower bound assuming the literal is true.
IntegerValue ConditionalLowerBound(Literal l, IntegerVariable i) const;
IntegerValue ConditionalLowerBound(Literal l, AffineExpression expr) const;
// Returns the current upper bound assuming the literal is true.
IntegerValue ConditionalUpperBound(Literal l, IntegerVariable i) const;
IntegerValue ConditionalUpperBound(Literal l, AffineExpression expr) const;
// Advanced usage. Given the reason for
// (Sum_i coeffs[i] * reason[i].var >= current_lb) initially in reason,
// this function relaxes the reason given that we only need the explanation of
// (Sum_i coeffs[i] * reason[i].var >= current_lb - slack).
//
// Preconditions:
// - coeffs must be of same size as reason, and all entry must be positive.
// - *reason must initially contains the trivial initial reason, that is
// the current lower-bound of each variables.
//
// TODO(user): Requiring all initial literal to be at their current bound is
// not really clean. Maybe we can change the API to only take IntegerVariable
// and produce the reason directly.
//
// TODO(user): change API so that this work is performed during the conflict
// analysis where we can be smarter in how we relax the reason. Note however
// that this function is mainly used when we have a conflict, so this is not
// really high priority.
//
// TODO(user): Test that the code work in the presence of integer overflow.
void RelaxLinearReason(IntegerValue slack,
absl::Span<const IntegerValue> coeffs,
std::vector<IntegerLiteral>* reason) const;
// Same as above but take in IntegerVariables instead of IntegerLiterals.
void AppendRelaxedLinearReason(IntegerValue slack,
absl::Span<const IntegerValue> coeffs,
absl::Span<const IntegerVariable> vars,
std::vector<IntegerLiteral>* reason) const;
// Same as above but relax the given trail indices.
void RelaxLinearReason(IntegerValue slack,
absl::Span<const IntegerValue> coeffs,
std::vector<int>* trail_indices) const;
// Removes from the reasons the literal that are always true.
// This is mainly useful for experiments/testing.
void RemoveLevelZeroBounds(std::vector<IntegerLiteral>* reason) const;
// Enqueue new information about a variable bound. Calling this with a less
// restrictive bound than the current one will have no effect.
//
// The reason for this "assignment" must be provided as:
// - A set of Literal currently being all false.
// - A set of IntegerLiteral currently being all true.
//
// IMPORTANT: Notice the inversed sign in the literal reason. This is a bit
// confusing but internally SAT use this direction for efficiency.
//
// Note(user): Duplicates Literal/IntegerLiteral are supported because we call
// STLSortAndRemoveDuplicates() in MergeReasonInto(), but maybe they shouldn't
// for efficiency reason.
//
// TODO(user): If the given bound is equal to the current bound, maybe the new
// reason is better? how to decide and what to do in this case? to think about
// it. Currently we simply don't do anything.
ABSL_MUST_USE_RESULT bool Enqueue(IntegerLiteral i_lit) {
return EnqueueInternal(i_lit, false, {}, {}, integer_trail_.size());
}
ABSL_MUST_USE_RESULT bool Enqueue(
IntegerLiteral i_lit, absl::Span<const Literal> literal_reason,
absl::Span<const IntegerLiteral> integer_reason) {
return EnqueueInternal(i_lit, false, literal_reason, integer_reason,
integer_trail_.size());
}
// Enqueue new information about a variable bound. It has the same behavior
// as the Enqueue() method, except that it accepts true and false integer
// literals, both for i_lit, and for the integer reason.
//
// This method will do nothing if i_lit is a true literal. It will report a
// conflict if i_lit is a false literal, and enqueue i_lit normally otherwise.
// Furthemore, it will check that the integer reason does not contain any
// false literals, and will remove true literals before calling
// ReportConflict() or Enqueue().
ABSL_MUST_USE_RESULT bool SafeEnqueue(
IntegerLiteral i_lit, absl::Span<const IntegerLiteral> integer_reason);
// Pushes the given integer literal assuming that the Boolean literal is true.
// This can do a few things:
// - If lit it true, add it to the reason and push the integer bound.
// - If the bound is infeasible, push lit to false.
// - If the underlying variable is optional and also controlled by lit, push
// the bound even if lit is not assigned.
ABSL_MUST_USE_RESULT bool ConditionalEnqueue(