OR-Tools  8.2
flatzinc/model.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_FLATZINC_MODEL_H_
15#define OR_TOOLS_FLATZINC_MODEL_H_
16
17#include <map>
18#include <string>
19
20#include "absl/container/flat_hash_map.h"
25
26namespace operations_research {
27namespace fz {
28
29struct Constraint;
30class Model;
31
32// A domain represents the possible values of a variable, and its type
33// (which carries display information, i.e. a Boolean will be displayed
34// differently than an integer with domain {0, 1}).
35// It can be:
36// - an explicit list of all possible values, in which case is_interval is
37// false. If the list is empty, then the domain is empty.
38// - an interval, in which case is_interval is true and values.size() == 2,
39// and the interval is [values[0], values[1]].
40// - all integers, in which case values is empty, and is_interval is true.
41// Note that semi-infinite intervals aren't supported.
42// - a Boolean domain({ 0, 1 } with Boolean display tag).
43// TODO(user): Rework domains, all int64 should be kintmin..kint64max.
44// It is a bit tricky though as we must take care of overflows.
45// If is_a_set is true, then this domain has a set semantics. For a set
46// variable, any subset of the initial set of values is a valid assignment,
47// instead of exactly one value.
48struct Domain {
49 // The values will be sorted and duplicate values will be removed.
50 static Domain IntegerList(std::vector<int64> values);
51 static Domain AllInt64();
53 static Domain Interval(int64 included_min, int64 included_max);
54 static Domain Boolean();
55 static Domain SetOfIntegerList(std::vector<int64> values);
56 static Domain SetOfAllInt64();
58 static Domain SetOfInterval(int64 included_min, int64 included_max);
59 static Domain SetOfBoolean();
60 static Domain EmptyDomain();
61
62 bool HasOneValue() const;
63 bool empty() const;
64
65 // Returns the min of the domain.
66 int64 Min() const;
67
68 // Returns the max of the domain.
69 int64 Max() const;
70
71 // Returns the value of the domain. HasOneValue() must return true.
72 int64 Value() const;
73
74 // Returns true if the domain is [kint64min..kint64max]
75 bool IsAllInt64() const;
76
77 // Various inclusion tests on a domain.
78 bool Contains(int64 value) const;
79 bool OverlapsIntList(const std::vector<int64>& vec) const;
80 bool OverlapsIntInterval(int64 lb, int64 ub) const;
81 bool OverlapsDomain(const Domain& other) const;
82
83 // All the following modifiers change the internal representation
84 // list to interval or interval to list.
86 bool IntersectWithDomain(const Domain& domain);
87 bool IntersectWithInterval(int64 interval_min, int64 interval_max);
88 bool IntersectWithListOfIntegers(const std::vector<int64>& integers);
89
90 // Returns true iff the value did belong to the domain, and was removed.
91 // Try to remove the value. It returns true if it was actually removed.
92 // If the value is inside a large interval, then it will not be removed.
94 std::string DebugString() const;
95
96 // These should never be modified from outside the class.
97 std::vector<int64> values;
100 // Indicates if the domain was created as a set domain.
102};
103
104// An int var is a name with a domain of possible values, along with
105// some tags. Typically, an IntegerVariable is on the heap, and owned by the
106// global Model object.
108 // This method tries to unify two variables. This can happen during the
109 // parsing of the model or during presolve. This is possible if at least one
110 // of the two variable is not the target of a constraint. (otherwise it
111 // returns false).
112 // The semantic of the merge is the following:
113 // - the resulting domain is the intersection of the two domains.
114 // - if one variable is not temporary, the result is not temporary.
115 // - if one variable is temporary, the name is the name of the other
116 // variable. If both variables are temporary or both variables are not
117 // temporary, the name is chosen arbitrarily between the two names.
118 bool Merge(const std::string& other_name, const Domain& other_domain,
119 bool other_temporary);
120
121 std::string DebugString() const;
122
123 std::string name;
125 // Indicates if the variable is a temporary variable created when flattening
126 // the model. For instance, if you write x == y * z + y, then it will be
127 // expanded into y * z == t and x = t + y. And t will be a temporary variable.
128 bool temporary : 1;
129 // Indicates if the variable should be created at all. A temporary variable
130 // can be unreachable in the active model if nobody uses it. In that case,
131 // there is no need to create it.
132 bool active : 1;
133
134 private:
135 friend class Model;
136
137 IntegerVariable(const std::string& name_, const Domain& domain_,
138 bool temporary_);
139};
140
141// An argument is either an integer value, an integer domain, a
142// reference to a variable, or an array of variable references.
143struct Argument {
144 enum Type {
152 };
153
155 static Argument Interval(int64 imin, int64 imax);
156 static Argument IntegerList(std::vector<int64> values);
157 static Argument DomainList(std::vector<Domain> domains);
158 static Argument IntVarRef(IntegerVariable* const var);
159 static Argument IntVarRefArray(std::vector<IntegerVariable*> vars);
160 static Argument VoidArgument();
161 static Argument FromDomain(const Domain& domain);
162
163 std::string DebugString() const;
164
165 // Returns true if the argument is a variable.
166 bool IsVariable() const;
167 // Returns true if the argument has only one value (integer value, integer
168 // list of size 1, interval of size 1, or variable with a singleton domain).
169 bool HasOneValue() const;
170 // Returns the value of the argument. Does DCHECK(HasOneValue()).
171 int64 Value() const;
172 // Returns true if it an integer list, or an array of integer
173 // variables (or domain) each having only one value.
174 bool IsArrayOfValues() const;
175 // Returns true if the argument is an integer value, an integer
176 // list, or an interval, and it contains the given value.
177 // It will check that the type is actually one of the above.
178 bool Contains(int64 value) const;
179 // Returns the value of the pos-th element.
180 int64 ValueAt(int pos) const;
181 // Returns the variable inside the argument if the type is INT_VAR_REF,
182 // or nullptr otherwise.
183 IntegerVariable* Var() const;
184 // Returns the variable at position pos inside the argument if the type is
185 // INT_VAR_REF_ARRAY or nullptr otherwise.
186 IntegerVariable* VarAt(int pos) const;
187
189 std::vector<int64> values;
190 std::vector<IntegerVariable*> variables;
191 std::vector<Domain> domains;
192};
193
194// A constraint has a type, some arguments, and a few tags. Typically, a
195// Constraint is on the heap, and owned by the global Model object.
197 Constraint(const std::string& t, std::vector<Argument> args,
198 bool strong_propag)
199 : type(t),
200 arguments(std::move(args)),
201 strong_propagation(strong_propag),
202 active(true),
204
205 std::string DebugString() const;
206
207 // Helpers to be used during presolve.
208 void MarkAsInactive();
209 // Helper method to remove one argument.
210 void RemoveArg(int arg_pos);
211 // Set as a False constraint.
212 void SetAsFalse();
213
214 // The flatzinc type of the constraint (i.e. "int_eq" for integer equality)
215 // stored as a string.
216 std::string type;
217 std::vector<Argument> arguments;
218 // Is true if the constraint should use the strongest level of propagation.
219 // This is a hint in the model. For instance, in the AllDifferent constraint,
220 // there are different algorithms to propagate with different pruning/speed
221 // ratios. When strong_propagation is true, one should use, if possible, the
222 // algorithm with the strongest pruning.
224 // Indicates if the constraint is active. Presolve can make it inactive by
225 // propagating it, or by regrouping it. Once a constraint is inactive, it is
226 // logically removed from the model, it is not extracted, and it is ignored by
227 // presolve.
228 bool active : 1;
229
230 // Indicates if presolve has finished propagating this constraint.
232};
233
234// An annotation is a set of information. It has two use cases. One during
235// parsing to store intermediate information on model objects (i.e. the defines
236// part of a constraint). The other use case is to store all search
237// declarations. This persists after model parsing.
239 enum Type {
248 };
249
250 static Annotation Empty();
251 static Annotation AnnotationList(std::vector<Annotation> list);
252 static Annotation Identifier(const std::string& id);
253 static Annotation FunctionCallWithArguments(const std::string& id,
254 std::vector<Annotation> args);
255 static Annotation FunctionCall(const std::string& id);
258 static Annotation Variable(IntegerVariable* const var);
259 static Annotation VariableList(std::vector<IntegerVariable*> variables);
260 static Annotation String(const std::string& str);
261
262 std::string DebugString() const;
263 bool IsFunctionCallWithIdentifier(const std::string& identifier) const {
264 return type == FUNCTION_CALL && id == identifier;
265 }
266 // Copy all the variable references contained in this annotation (and its
267 // children). Depending on the type of this annotation, there can be zero,
268 // one, or several.
269 void AppendAllIntegerVariables(std::vector<IntegerVariable*>* vars) const;
270
274 std::string id;
275 std::vector<Annotation> annotations;
276 std::vector<IntegerVariable*> variables;
277 std::string string_value;
278};
279
280// Information on what should be displayed when a solution is found.
281// It follows the flatzinc specification (www.minizinc.org).
283 struct Bounds {
284 Bounds(int64 min_value_, int64 max_value_)
285 : min_value(min_value_), max_value(max_value_) {}
286 std::string DebugString() const;
289 };
290
291 // Will output: name = <variable value>.
292 static SolutionOutputSpecs SingleVariable(const std::string& name,
294 bool display_as_boolean);
295 // Will output (for example):
296 // name = array2d(min1..max1, min2..max2, [list of variable values])
297 // for a 2d array (bounds.size() == 2).
299 const std::string& name, std::vector<Bounds> bounds,
300 std::vector<IntegerVariable*> flat_variables, bool display_as_boolean);
301 // Empty output.
303
304 std::string DebugString() const;
305
306 std::string name;
308 std::vector<IntegerVariable*> flat_variables;
309 // These are the starts and ends of intervals for displaying (potentially
310 // multi-dimensional) arrays.
311 std::vector<Bounds> bounds;
313};
314
315class Model {
316 public:
317 explicit Model(const std::string& name)
318 : name_(name), objective_(nullptr), maximize_(true) {}
319 ~Model();
320
321 // ----- Builder methods -----
322
323 // The objects returned by AddVariable(), AddConstant(), and AddConstraint()
324 // are owned by the model and will remain live for its lifetime.
325 IntegerVariable* AddVariable(const std::string& name, const Domain& domain,
326 bool defined);
328 // Creates and add a constraint to the model.
329 void AddConstraint(const std::string& id, std::vector<Argument> arguments,
330 bool is_domain);
331 void AddConstraint(const std::string& id, std::vector<Argument> arguments);
333
334 // Set the search annotations and the objective: either simply satisfy the
335 // problem, or minimize or maximize the given variable (which must have been
336 // added with AddVariable() already).
337 void Satisfy(std::vector<Annotation> search_annotations);
338 void Minimize(IntegerVariable* obj,
339 std::vector<Annotation> search_annotations);
340 void Maximize(IntegerVariable* obj,
341 std::vector<Annotation> search_annotations);
342
343 bool IsInconsistent() const;
344
345 // ----- Accessors and mutators -----
346
347 const std::vector<IntegerVariable*>& variables() const { return variables_; }
348 const std::vector<Constraint*>& constraints() const { return constraints_; }
349 const std::vector<Annotation>& search_annotations() const {
350 return search_annotations_;
351 }
352#if !defined(SWIG)
354 return util::MutableVectorIteration<Annotation>(&search_annotations_);
355 }
356#endif
357 const std::vector<SolutionOutputSpecs>& output() const { return output_; }
358#if !defined(SWIG)
361 }
362#endif
363 bool maximize() const { return maximize_; }
364 IntegerVariable* objective() const { return objective_; }
365 void SetObjective(IntegerVariable* obj) { objective_ = obj; }
366
367 // Services.
368 std::string DebugString() const;
369
370 const std::string& name() const { return name_; }
371
372 private:
373 const std::string name_;
374 // owned.
375 // TODO(user): use unique_ptr
376 std::vector<IntegerVariable*> variables_;
377 // owned.
378 // TODO(user): use unique_ptr
379 std::vector<Constraint*> constraints_;
380 // The objective variable (it belongs to variables_).
381 IntegerVariable* objective_;
382 bool maximize_;
383 // All search annotations are stored as a vector of Annotation.
384 std::vector<Annotation> search_annotations_;
385 std::vector<SolutionOutputSpecs> output_;
386};
387
388// Stand-alone statistics class on the model.
389// TODO(user): Clean up API to pass a Model* in argument.
391 public:
392 explicit ModelStatistics(const Model& model) : model_(model) {}
394 return constraints_per_variables_[var].size();
395 }
396 void BuildStatistics();
397 void PrintStatistics() const;
398
399 private:
400 const Model& model_;
401 std::map<std::string, std::vector<Constraint*>> constraints_per_type_;
402 absl::flat_hash_map<const IntegerVariable*, std::vector<Constraint*>>
403 constraints_per_variables_;
404};
405
406// Helper method to flatten Search annotations.
407void FlattenAnnotations(const Annotation& ann, std::vector<Annotation>* out);
408
409} // namespace fz
410} // namespace operations_research
411
412#endif // OR_TOOLS_FLATZINC_MODEL_H_
util::MutableVectorIteration< SolutionOutputSpecs > mutable_output()
IntegerVariable * AddVariable(const std::string &name, const Domain &domain, bool defined)
Definition: model.cc:826
const std::string & name() const
const std::vector< Annotation > & search_annotations() const
const std::vector< SolutionOutputSpecs > & output() const
Model(const std::string &name)
void Satisfy(std::vector< Annotation > search_annotations)
Definition: model.cc:857
void Maximize(IntegerVariable *obj, std::vector< Annotation > search_annotations)
Definition: model.cc:869
std::string DebugString() const
Definition: model.cc:876
const std::vector< IntegerVariable * > & variables() const
IntegerVariable * objective() const
void AddOutput(SolutionOutputSpecs output)
Definition: model.cc:853
void SetObjective(IntegerVariable *obj)
util::MutableVectorIteration< Annotation > mutable_search_annotations()
IntegerVariable * AddConstant(int64 value)
Definition: model.cc:834
void AddConstraint(const std::string &id, std::vector< Argument > arguments, bool is_domain)
Definition: model.cc:841
void Minimize(IntegerVariable *obj, std::vector< Annotation > search_annotations)
Definition: model.cc:862
bool IsInconsistent() const
Definition: model.cc:903
const std::vector< Constraint * > & constraints() const
int NumVariableOccurrences(IntegerVariable *var)
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int64_t int64
void FlattenAnnotations(const Annotation &ann, std::vector< Annotation > *out)
Definition: model.cc:953
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
STL namespace.
static Annotation IntegerValue(int64 value)
Definition: model.cc:694
std::vector< IntegerVariable * > variables
static Annotation Variable(IntegerVariable *const var)
Definition: model.cc:701
std::string DebugString() const
Definition: model.cc:738
static Annotation FunctionCall(const std::string &id)
Definition: model.cc:677
static Annotation AnnotationList(std::vector< Annotation > list)
Definition: model.cc:648
static Annotation String(const std::string &str)
Definition: model.cc:719
static Annotation Identifier(const std::string &id)
Definition: model.cc:657
bool IsFunctionCallWithIdentifier(const std::string &identifier) const
std::vector< Annotation > annotations
static Annotation Empty()
Definition: model.cc:640
static Annotation Interval(int64 interval_min, int64 interval_max)
Definition: model.cc:686
void AppendAllIntegerVariables(std::vector< IntegerVariable * > *vars) const
Definition: model.cc:728
static Annotation FunctionCallWithArguments(const std::string &id, std::vector< Annotation > args)
Definition: model.cc:666
static Annotation VariableList(std::vector< IntegerVariable * > variables)
Definition: model.cc:710
int64 ValueAt(int pos) const
Definition: model.cc:549
IntegerVariable * Var() const
Definition: model.cc:574
static Argument DomainList(std::vector< Domain > domains)
Definition: model.cc:408
std::vector< IntegerVariable * > variables
IntegerVariable * VarAt(int pos) const
Definition: model.cc:578
static Argument VoidArgument()
Definition: model.cc:429
static Argument Interval(int64 imin, int64 imax)
Definition: model.cc:393
static Argument IntVarRefArray(std::vector< IntegerVariable * > vars)
Definition: model.cc:422
std::string DebugString() const
Definition: model.cc:447
static Argument IntegerList(std::vector< int64 > values)
Definition: model.cc:401
bool Contains(int64 value) const
Definition: model.cc:531
static Argument IntVarRef(IntegerVariable *const var)
Definition: model.cc:415
static Argument FromDomain(const Domain &domain)
Definition: model.cc:435
static Argument IntegerValue(int64 value)
Definition: model.cc:386
Constraint(const std::string &t, std::vector< Argument > args, bool strong_propag)
void RemoveArg(int arg_pos)
Definition: model.cc:624
std::string DebugString() const
Definition: model.cc:614
std::vector< Argument > arguments
bool OverlapsIntList(const std::vector< int64 > &vec) const
Definition: model.cc:289
static Domain IntegerList(std::vector< int64 > values)
Definition: model.cc:31
static Domain EmptyDomain()
Definition: model.cc:108
bool IntersectWithSingleton(int64 value)
Definition: model.cc:139
static Domain SetOfIntegerValue(int64 value)
Definition: model.cc:90
bool OverlapsDomain(const Domain &other) const
Definition: model.cc:327
static Domain SetOfAllInt64()
Definition: model.cc:84
static Domain Boolean()
Definition: model.cc:68
static Domain SetOfIntegerList(std::vector< int64 > values)
Definition: model.cc:78
bool IntersectWithInterval(int64 interval_min, int64 interval_max)
Definition: model.cc:143
bool RemoveValue(int64 value)
Definition: model.cc:339
std::string DebugString() const
Definition: model.cc:370
static Domain Interval(int64 included_min, int64 included_max)
Definition: model.cc:58
bool IntersectWithListOfIntegers(const std::vector< int64 > &integers)
Definition: model.cc:191
static Domain AllInt64()
Definition: model.cc:41
bool IntersectWithDomain(const Domain &domain)
Definition: model.cc:116
bool Contains(int64 value) const
Definition: model.cc:265
bool OverlapsIntInterval(int64 lb, int64 ub) const
Definition: model.cc:313
static Domain SetOfBoolean()
Definition: model.cc:102
static Domain SetOfInterval(int64 included_min, int64 included_max)
Definition: model.cc:96
static Domain IntegerValue(int64 value)
Definition: model.cc:49
std::vector< int64 > values
bool Merge(const std::string &other_name, const Domain &other_domain, bool other_temporary)
Definition: model.cc:592
Bounds(int64 min_value_, int64 max_value_)
static SolutionOutputSpecs MultiDimensionalArray(const std::string &name, std::vector< Bounds > bounds, std::vector< IntegerVariable * > flat_variables, bool display_as_boolean)
Definition: model.cc:790
std::vector< IntegerVariable * > flat_variables
static SolutionOutputSpecs VoidOutput()
Definition: model.cc:802
static SolutionOutputSpecs SingleVariable(const std::string &name, IntegerVariable *variable, bool display_as_boolean)
Definition: model.cc:780