14#ifndef OR_TOOLS_SAT_CP_MODEL_UTILS_H_
15#define OR_TOOLS_SAT_CP_MODEL_UTILS_H_
24#if !defined(__PORTABLE_PLATFORM__)
27#include "absl/flags/declare.h"
28#include "absl/log/check.h"
29#include "absl/status/status.h"
30#include "absl/strings/match.h"
31#include "absl/strings/string_view.h"
32#include "absl/types/span.h"
33#include "google/protobuf/message.h"
34#include "google/protobuf/text_format.h"
72 LinearExpressionProto* output_negated_expr);
84 std::vector<int>* variables,
85 std::vector<int>* literals);
129template <
typename ProtoWithDomain>
131 for (
int i = 0;
i < proto.domain_size();
i += 2) {
132 if (value >= proto.domain(
i) && value <= proto.domain(
i + 1))
return true;
138template <
typename ProtoWithDomain>
140 proto->clear_domain();
141 proto->mutable_domain()->Reserve(domain.
NumIntervals());
143 proto->add_domain(interval.start);
144 proto->add_domain(interval.end);
149template <
typename ProtoWithDomain>
151#if defined(__PORTABLE_PLATFORM__)
153 {proto.domain().begin(), proto.domain().end()});
163template <
typename ProtoWithDomain>
165 std::vector<int64_t> result;
166 for (
int i = 0;
i < proto.domain_size();
i += 2) {
167 for (int64_t v = proto.domain(
i); v <= proto.domain(
i + 1); ++v) {
168 CHECK_LE(result.size(), 1e6);
178 double result =
static_cast<double>(value);
179 if (value == std::numeric_limits<int64_t>::min())
180 result = -std::numeric_limits<double>::infinity();
181 if (value == std::numeric_limits<int64_t>::max())
182 result = std::numeric_limits<double>::infinity();
202 double result = value;
206 return result - proto.
offset();
213 absl::Span<const int64_t>
solution);
237 const int64_t var_value = (value - expr.
offset()) / expr.
coeffs(0);
238 DCHECK_EQ(value, var_value * expr.
coeffs(0) + expr.
offset());
255 LinearConstraintProto* linear);
261 LinearConstraintProto* linear,
266 const LinearExpressionProto& expr, int64_t coefficient,
267 LinearConstraintProto* linear);
271 const LinearExpressionProto&
b,
272 int64_t b_scaling = 1);
275template <
class ExpressionList>
279 for (
const int var : expr.vars()) {
281 if (unique_var == -1) {
283 }
else if (var != unique_var) {
288 return unique_var != -1;
296 const google::protobuf::RepeatedField<T>& sequence, uint64_t seed) {
297 if (sequence.empty())
return seed;
298 return fasthash64(
reinterpret_cast<const char*
>(sequence.data()),
299 sequence.size() *
sizeof(T), seed);
304 return fasthash64(
reinterpret_cast<const char*
>(&field),
sizeof(T), seed);
314#if !defined(__PORTABLE_PLATFORM__)
338#if defined(__PORTABLE_PLATFORM__)
341 if (absl::EndsWith(filename,
"txt") ||
342 absl::EndsWith(filename,
"textproto")) {
343 std::string proto_string;
344 google::protobuf::TextFormat::Printer printer;
346 printer.PrintToString(proto, &proto_string);
359 if (absl::MakeConstSpan(lhs.
literals()) !=
360 absl::MakeConstSpan(rhs.
literals())) {
372 for (
const int lit : m.
literals()) {
373 h = H::combine(std::move(h), lit);
380 if (absl::MakeConstSpan(lhs.
vars()) != absl::MakeConstSpan(rhs.
vars())) {
383 if (absl::MakeConstSpan(lhs.
coeffs()) != absl::MakeConstSpan(rhs.
coeffs())) {
386 if (absl::MakeConstSpan(lhs.
domain()) != absl::MakeConstSpan(rhs.
domain())) {
394 for (
const int var : m.
vars()) {
395 h = H::combine(std::move(h), var);
397 for (
const int64_t coeff : m.
coeffs()) {
398 h = H::combine(std::move(h), coeff);
400 for (
const int64_t bound : m.
domain()) {
401 h = H::combine(std::move(h), bound);
void Clear(IndexType i)
Sets the bit at position i to 0.
void Set(IndexType i)
Sets the bit at position i to 1.
static Domain FromFlatIntervals(const std::vector< int64_t > &flat_intervals)
static Domain FromFlatSpanOfIntervals(absl::Span< const int64_t > flat_intervals)
::int32_t literals(int index) const
int literals_size() const
repeated int32 literals = 1;
::int32_t enforcement_literal(int index) const
const ::operations_research::sat::IntervalConstraintProto & interval() const
const ::operations_research::sat::ConstraintProto & constraints(int index) const
double scaling_factor() const
::int64_t integer_scaling_factor() const
::int64_t integer_after_offset() const
::int64_t integer_before_offset() const
const ::operations_research::sat::LinearExpressionProto & size() const
const ::operations_research::sat::LinearExpressionProto & end() const
const ::operations_research::sat::LinearExpressionProto & start() const
::int32_t vars(int index) const
::int64_t coeffs(int index) const
::int64_t domain(int index) const
::int64_t coeffs(int index) const
::int32_t vars(int index) const
int vars_size() const
repeated int32 vars = 1;
ABSL_DECLARE_FLAG(bool, cp_model_dump_models)
absl::Status SetBinaryProto(absl::string_view file_name, const google::protobuf::Message &proto, Options options)
absl::Status SetContents(absl::string_view file_name, absl::string_view contents, Options options)
void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)
Fills the target as negated ref.
constexpr uint64_t kDefaultFingerprintSeed
Default seed for fingerprints.
uint64_t FingerprintRepeatedField(const google::protobuf::RepeatedField< T > &sequence, uint64_t seed)
void RemoveVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)
double UnscaleObjectiveValue(const CpObjectiveProto &proto, double value)
Removes the objective scaling and offset from the given value.
bool RefIsPositive(int ref)
int64_t ComputeInnerObjective(const CpObjectiveProto &objective, absl::Span< const int64_t > solution)
bool operator==(const BoolArgumentProto &lhs, const BoolArgumentProto &rhs)
bool HasEnforcementLiteral(const ConstraintProto &ct)
Small utility functions to deal with half-reified constraints.
int CombineSeed(int base_seed, int64_t delta)
We assume delta >= 0 and we only use the low bit of delta.
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
bool DomainInProtoContains(const ProtoWithDomain &proto, int64_t value)
void ApplyToAllIntervalIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
bool SafeAddLinearExpressionToLinearConstraint(const LinearExpressionProto &expr, int64_t coefficient, LinearConstraintProto *linear)
Same method, but returns if the addition was possible without overflowing.
int64_t GetInnerVarValue(const LinearExpressionProto &expr, int64_t value)
uint64_t FingerprintSingleField(const T &field, uint64_t seed)
double ScaleObjectiveValue(const CpObjectiveProto &proto, int64_t value)
Scales back a objective value to a double value from the original model.
bool ConvertCpModelProtoToCnf(const CpModelProto &cp_model, std::string *out)
uint64_t FingerprintExpression(const LinearExpressionProto &lin, uint64_t seed)
Returns a stable fingerprint of a linear expression.
uint64_t FingerprintModel(const CpModelProto &model, uint64_t seed)
Returns a stable fingerprint of a model.
bool ExpressionIsAffine(const LinearExpressionProto &expr)
Checks if the expression is affine or constant.
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Returns the sorted list of interval used by a constraint.
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Serializes a Domain into the domain field of a proto.
int64_t AffineExpressionValueAt(const LinearExpressionProto &expr, int64_t value)
Evaluates an affine expression at the given value.
H AbslHashValue(H h, const IntVar &i)
– ABSL HASHING SUPPORT --------------------------------------------------—
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Reads a Domain from the domain field of a proto.
bool ExpressionsContainsOnlyOneVar(const ExpressionList &exprs)
Returns true if there exactly one variable appearing in all the expressions.
void SetupTextFormatPrinter(google::protobuf::TextFormat::Printer *printer)
absl::string_view ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)
bool ExpressionContainsSingleRef(const LinearExpressionProto &expr)
Returns true if a linear expression can be reduced to a single ref.
int64_t LinearExpressionGcd(const LinearExpressionProto &expr, int64_t gcd)
void ApplyToAllLiteralIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void DivideLinearExpression(int64_t divisor, LinearExpressionProto *expr)
void AddLinearExpressionToLinearConstraint(const LinearExpressionProto &expr, int64_t coefficient, LinearConstraintProto *linear)
int GetSingleRefFromExpression(const LinearExpressionProto &expr)
int64_t ScaleInnerObjectiveValue(const CpObjectiveProto &proto, int64_t value)
Similar to ScaleObjectiveValue() but uses the integer version.
int EnforcementLiteral(const ConstraintProto &ct)
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
void InsertVariablesFromInterval(const CpModelProto &model_proto, int index, Bitset64< int > &output)
Insert/Remove variables from an interval constraint into a bitset.
bool LinearExpressionProtosAreEqual(const LinearExpressionProto &a, const LinearExpressionProto &b, int64_t b_scaling)
Returns true iff a == b * b_scaling.
IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)
void ApplyToAllVariableIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void AddWeightedLiteralToLinearConstraint(int lit, int64_t coeff, LinearConstraintProto *linear, int64_t *offset)
bool AffineExpressionContainsVar(const LinearExpressionProto &expr, int var)
Returns true if the expression is a * var + b.
std::vector< int64_t > AllValuesInDomain(const ProtoWithDomain &proto)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
std::vector< int > variables
std::vector< int > literals