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"
24 #include "ortools/base/logging.h"
25 #include "ortools/sat/cp_model.pb.h"
27 
28 namespace operations_research {
29 namespace sat {
30 
31 // Small utility functions to deal with negative variable/literal references.
32 inline int NegatedRef(int ref) { return -ref - 1; }
33 inline int PositiveRef(int ref) { return std::max(ref, NegatedRef(ref)); }
34 inline bool RefIsPositive(int ref) { return ref >= 0; }
35 
36 // Small utility functions to deal with half-reified constraints.
37 inline bool HasEnforcementLiteral(const ConstraintProto& ct) {
38  return !ct.enforcement_literal().empty();
39 }
40 inline int EnforcementLiteral(const ConstraintProto& ct) {
41  return ct.enforcement_literal(0);
42 }
43 
44 // Fills the target as negated ref.
45 void 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 };
56 IndexReferences GetReferencesUsedByConstraint(const ConstraintProto& ct);
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.
61 void ApplyToAllVariableIndices(const std::function<void(int*)>& function,
62  ConstraintProto* ct);
63 void ApplyToAllLiteralIndices(const std::function<void(int*)>& function,
64  ConstraintProto* ct);
65 void 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.
70 std::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.
74 std::vector<int> UsedVariables(const ConstraintProto& ct);
75 
76 // Returns the sorted list of interval used by a constraint.
77 std::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.
81 template <typename ProtoWithDomain>
82 bool 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.
90 template <typename ProtoWithDomain>
91 void 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.
101 template <typename ProtoWithDomain>
102 Domain 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.
115 template <typename ProtoWithDomain>
116 std::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.
128 inline 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.
138 inline 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.
150 int64 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
std::vector< int > UsedVariables(const ConstraintProto &ct)
double UnscaleObjectiveValue(const CpObjectiveProto &proto, double value)
bool RefIsPositive(int ref)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)
bool HasEnforcementLiteral(const ConstraintProto &ct)
int64 ComputeInnerObjective(const CpObjectiveProto &objective, const CpSolverResponse &response)
std::vector< int64 > AllValuesInDomain(const ProtoWithDomain &proto)
void ApplyToAllLiteralIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
double ScaleObjectiveValue(const CpObjectiveProto &proto, int64 value)
void ApplyToAllIntervalIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
void ApplyToAllVariableIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)
bool DomainInProtoContains(const ProtoWithDomain &proto, int64 value)
std::string ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)
int EnforcementLiteral(const ConstraintProto &ct)
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].