OR-Tools  8.2
cp_model_utils.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_SAT_CP_MODEL_UTILS_H_
15#define OR_TOOLS_SAT_CP_MODEL_UTILS_H_
16
17#include <algorithm>
18#include <functional>
19#include <string>
20#include <vector>
21
22#include "absl/container/flat_hash_set.h"
25#include "ortools/sat/cp_model.pb.h"
27
28namespace operations_research {
29namespace sat {
30
31// Small utility functions to deal with negative variable/literal references.
32inline int NegatedRef(int ref) { return -ref - 1; }
33inline int PositiveRef(int ref) { return std::max(ref, NegatedRef(ref)); }
34inline bool RefIsPositive(int ref) { return ref >= 0; }
35
36// Small utility functions to deal with half-reified constraints.
37inline bool HasEnforcementLiteral(const ConstraintProto& ct) {
38 return !ct.enforcement_literal().empty();
39}
40inline int EnforcementLiteral(const ConstraintProto& ct) {
41 return ct.enforcement_literal(0);
42}
43
44// Fills the target as negated ref.
45void SetToNegatedLinearExpression(const LinearExpressionProto& input_expr,
46 LinearExpressionProto* output_negated_expr);
47
48// Collects all the references used by a constraint. This function is used in a
49// few places to have a "generic" code dealing with constraints. Note that the
50// enforcement_literal is NOT counted here and that the vectors can have
51// duplicates.
53 std::vector<int> variables;
54 std::vector<int> literals;
55};
57
58// Applies the given function to all variables/literals/intervals indices of the
59// constraint. This function is used in a few places to have a "generic" code
60// dealing with constraints.
61void ApplyToAllVariableIndices(const std::function<void(int*)>& function,
62 ConstraintProto* ct);
63void ApplyToAllLiteralIndices(const std::function<void(int*)>& function,
64 ConstraintProto* ct);
65void ApplyToAllIntervalIndices(const std::function<void(int*)>& function,
66 ConstraintProto* ct);
67
68// Returns the name of the ConstraintProto::ConstraintCase oneof enum.
69// Note(user): There is no such function in the proto API as of 16/01/2017.
70std::string ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case);
71
72// Returns the sorted list of variables used by a constraint.
73// Note that this include variable used as a literal.
74std::vector<int> UsedVariables(const ConstraintProto& ct);
75
76// Returns the sorted list of interval used by a constraint.
77std::vector<int> UsedIntervals(const ConstraintProto& ct);
78
79// Returns true if a proto.domain() contain the given value.
80// The domain is expected to be encoded as a sorted disjoint interval list.
81template <typename ProtoWithDomain>
82bool DomainInProtoContains(const ProtoWithDomain& proto, int64 value) {
83 for (int i = 0; i < proto.domain_size(); i += 2) {
84 if (value >= proto.domain(i) && value <= proto.domain(i + 1)) return true;
85 }
86 return false;
87}
88
89// Serializes a Domain into the domain field of a proto.
90template <typename ProtoWithDomain>
91void FillDomainInProto(const Domain& domain, ProtoWithDomain* proto) {
92 proto->clear_domain();
93 proto->mutable_domain()->Reserve(domain.NumIntervals());
94 for (const ClosedInterval& interval : domain) {
95 proto->add_domain(interval.start);
96 proto->add_domain(interval.end);
97 }
98}
99
100// Reads a Domain from the domain field of a proto.
101template <typename ProtoWithDomain>
102Domain ReadDomainFromProto(const ProtoWithDomain& proto) {
103#if defined(__PORTABLE_PLATFORM__)
105 {proto.domain().begin(), proto.domain().end()});
106#else
107 return Domain::FromFlatSpanOfIntervals(proto.domain());
108#endif
109}
110
111// Returns the list of values in a given domain.
112// This will fail if the domain contains more than one millions values.
113//
114// TODO(user): work directly on the Domain class instead.
115template <typename ProtoWithDomain>
116std::vector<int64> AllValuesInDomain(const ProtoWithDomain& proto) {
117 std::vector<int64> result;
118 for (int i = 0; i < proto.domain_size(); i += 2) {
119 for (int64 v = proto.domain(i); v <= proto.domain(i + 1); ++v) {
120 CHECK_LE(result.size(), 1e6);
121 result.push_back(v);
122 }
123 }
124 return result;
125}
126
127// Scales back a objective value to a double value from the original model.
128inline double ScaleObjectiveValue(const CpObjectiveProto& proto, int64 value) {
129 double result = static_cast<double>(value);
130 if (value == kint64min) result = -std::numeric_limits<double>::infinity();
131 if (value == kint64max) result = std::numeric_limits<double>::infinity();
132 result += proto.offset();
133 if (proto.scaling_factor() == 0) return result;
134 return proto.scaling_factor() * result;
135}
136
137// Removes the objective scaling and offset from the given value.
138inline double UnscaleObjectiveValue(const CpObjectiveProto& proto,
139 double value) {
140 double result = value;
141 if (proto.scaling_factor() != 0) {
142 result /= proto.scaling_factor();
143 }
144 return result - proto.offset();
145}
146
147// Computes the "inner" objective of a response that contains a solution.
148// This is the objective without offset and scaling. Call ScaleObjectiveValue()
149// to get the user facing objective.
150int64 ComputeInnerObjective(const CpObjectiveProto& objective,
151 const CpSolverResponse& response);
152
153} // namespace sat
154} // namespace operations_research
155
156#endif // OR_TOOLS_SAT_CP_MODEL_UTILS_H_
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
We call domain any subset of Int64 = [kint64min, kint64max].
static Domain FromFlatIntervals(const std::vector< int64 > &flat_intervals)
This method is available in Python, Java and .NET.
int NumIntervals() const
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals.
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
CpModelProto proto
SharedResponseManager * response
const Constraint * ct
int64 value
static const int64 kint64max
int64_t int64
static const int64 kint64min
bool HasEnforcementLiteral(const ConstraintProto &ct)
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)
std::vector< int64 > AllValuesInDomain(const ProtoWithDomain &proto)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
int64 ComputeInnerObjective(const CpObjectiveProto &objective, const CpSolverResponse &response)
double UnscaleObjectiveValue(const CpObjectiveProto &proto, double value)
void ApplyToAllLiteralIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void ApplyToAllIntervalIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
int EnforcementLiteral(const ConstraintProto &ct)
double ScaleObjectiveValue(const CpObjectiveProto &proto, int64 value)
void ApplyToAllVariableIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)
std::string ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)
bool RefIsPositive(int ref)
bool DomainInProtoContains(const ProtoWithDomain &proto, int64 value)
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
IntervalVar * interval
Definition: resource.cc:98
Represents a closed interval [start, end].