1// Copyright 2010-2021 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// Proto describing a general Constraint Programming (CP) problem.
15
16syntax = "proto3";
17
18package operations_research.sat;
19
20option csharp_namespace = "Google.OrTools.Sat";
21option java_package = "com.google.ortools.sat";
22option java_multiple_files = true;
23option java_outer_classname = "CpModelProtobuf";
24
25
26// An integer variable.
27//
28// It will be referred to by an int32 corresponding to its index in a
29// CpModelProto variables field.
30//
31// Depending on the context, a reference to a variable whose domain is in [0, 1]
32// can also be seen as a Boolean that will be true if the variable value is 1
33// and false if it is 0. When used in this context, the field name will always
34// contain the word "literal".
35//
36// Negative reference (advanced usage): to simplify the creation of a model and
37// for efficiency reasons, all the "literal" or "variable" fields can also
38// contain a negative index. A negative index i will refer to the negation of
39// the integer variable at index -i -1 or to NOT the literal at the same index.
40//
41// Ex: A variable index 4 will refer to the integer variable model.variables(4)
42// and an index of -5 will refer to the negation of the same variable. A literal
43// index 4 will refer to the logical fact that model.variable(4) == 1 and a
44// literal index of -5 will refer to the logical fact model.variable(4) == 0.
45message IntegerVariableProto {
46  // For debug/logging only. Can be empty.
47  string name = 1;
48
49  // The variable domain given as a sorted list of n disjoint intervals
50  // [min, max] and encoded as [min_0, max_0,  ..., min_{n-1}, max_{n-1}].
51  //
52  // The most common example being just [min, max].
53  // If min == max, then this is a constant variable.
54  //
55  // We have:
56  //  - domain_size() is always even.
57  //  - min == domain.front();
58  //  - max == domain.back();
59  //  - for all i < n   :      min_i <= max_i
60  //  - for all i < n-1 :  max_i + 1 < min_{i+1}.
61  //
62  // Note that we check at validation that a variable domain is small enough so
63  // that we don't run into integer overflow in our algorithms. Because of that,
64  // you cannot just have "unbounded" variable like [0, kint64max] and should
65  // try to specify tighter domains.
66  repeated int64 domain = 2;
67}
68
69// Argument of the constraints of the form OP(literals).
70message BoolArgumentProto {
71  repeated int32 literals = 1;
72}
73
74// Some constraints supports linear expression instead of just using a reference
75// to a variable. This is especially useful during presolve to reduce the model
76// size.
77message LinearExpressionProto {
78  repeated int32 vars = 1;
79  repeated int64 coeffs = 2;
80  int64 offset = 3;
81}
82
83message LinearArgumentProto {
84  LinearExpressionProto target = 1;
85  repeated LinearExpressionProto exprs = 2;
86}
87
88// All affine expressions must take different values.
89message AllDifferentConstraintProto {
90  repeated LinearExpressionProto exprs = 1;
91}
92
93// The linear sum vars[i] * coeffs[i] must fall in the given domain. The domain
94// has the same format as the one in IntegerVariableProto.
95//
96// Note that the validation code currently checks using the domain of the
97// involved variables that the sum can always be computed without integer
98// overflow and throws an error otherwise.
99message LinearConstraintProto {
100  repeated int32 vars = 1;
101  repeated int64 coeffs = 2;  // Same size as vars.
102  repeated int64 domain = 3;
103}
104
105// The constraint target = vars[index].
106// This enforces that index takes one of the value in [0, vars_size()).
107message ElementConstraintProto {
108  int32 index = 1;
109  int32 target = 2;
110  repeated int32 vars = 3;
111}
112
113// This "special" constraint not only enforces (start + size == end) and (size
114// >= 0) but can also be referred by other constraints using this "interval"
115// concept.
116message IntervalConstraintProto {
117  // IMPORTANT: For now, this constraint do not enforce any relations on the
118  // view, and a linear constraint must be added together with this to enforce
119  // enforcement => start + size == end. An enforcement => size >=0 might also
120  // be needed.
121  //
122  // IMPORTANT: For now, we just support affine relation. We could easily
123  // create an intermediate variable to support full linear expression, but this
124  // isn't done currently.
125  LinearExpressionProto start = 4;
126  LinearExpressionProto end = 5;
127  LinearExpressionProto size = 6;
128}
129
130// All the intervals (index of IntervalConstraintProto) must be disjoint. More
131// formally, there must exist a sequence so that for each consecutive intervals,
132// we have end_i <= start_{i+1}. In particular, intervals of size zero do matter
133// for this constraint. This is also known as a disjunctive constraint in
134// scheduling.
135message NoOverlapConstraintProto {
136  repeated int32 intervals = 1;
137}
138
139// The boxes defined by [start_x, end_x) * [start_y, end_y) cannot overlap.
140// Furthermore, one box is optional if at least one of the x or y interval is
141// optional.
142message NoOverlap2DConstraintProto {
143  repeated int32 x_intervals = 1;
144  repeated int32 y_intervals = 2;  // Same size as x_intervals.
145  bool boxes_with_null_area_can_overlap = 3;
146  // TODO(user): Add optional areas as repeated LinearExpressionProto.
147}
148
149// The sum of the demands of the intervals at each interval point cannot exceed
150// a capacity. Note that intervals are interpreted as [start, end) and as
151// such intervals like [2,3) and [3,4) do not overlap for the point of view of
152// this constraint. Moreover, intervals of size zero are ignored.
153message CumulativeConstraintProto {
154  LinearExpressionProto capacity = 1;
155  repeated int32 intervals = 2;
156  repeated LinearExpressionProto demands = 3;  // Same size as intervals.
157}
158
159// Maintain a reservoir level within bounds. The water level starts at 0, and at
160// any time, it must be within [min_level, max_level].
161//
162// If the variable actives[i] is true, and if the variable times[i] is assigned
163// a value t, then the current level changes by level_changes[i] (which is
164// constant) at the time t. Therefore, at any time t:
165//
166// sum(level_changes[i] * actives[i] if times[i] <= t) in [min_level, max_level]
167//
168// Note that min level must be <= 0, and the max level must be >= 0. Please use
169// fixed level_changes to simulate initial state.
170//
171// The array of boolean variables 'actives', if defined, indicates which actions
172// are actually performed. If this array is not defined, then it is assumed that
173// all actions will be performed.
174message ReservoirConstraintProto {
175  int64 min_level = 1;
176  int64 max_level = 2;
177  repeated LinearExpressionProto time_exprs = 3;  // affine expressions.
178  repeated int64 level_changes = 4;               // constants, can be negative.
179  repeated int32 active_literals = 5;
180}
181
182// The circuit constraint is defined on a graph where the arc presence are
183// controlled by literals. Each arc is given by an index in the
184// tails/heads/literals lists that must have the same size.
185//
186// For now, we ignore node indices with no incident arc. All the other nodes
187// must have exactly one incoming and one outgoing selected arc (i.e. literal at
188// true). All the selected arcs that are not self-loops must form a single
189// circuit. Note that multi-arcs are allowed, but only one of them will be true
190// at the same time. Multi-self loop are disallowed though.
191message CircuitConstraintProto {
192  repeated int32 tails = 3;
193  repeated int32 heads = 4;
194  repeated int32 literals = 5;
195}
196
197// The "VRP" (Vehicle Routing Problem) constraint.
198//
199// The direct graph where arc #i (from tails[i] to head[i]) is present iff
200// literals[i] is true must satisfy this set of properties:
201// - #incoming arcs == 1 except for node 0.
202// - #outgoing arcs == 1 except for node 0.
203// - for node zero, #incoming arcs == #outgoing arcs.
204// - There are no duplicate arcs.
205// - Self-arcs are allowed except for node 0.
206// - There is no cycle in this graph, except through node 0.
207//
208// Note: Currently this constraint expect all the nodes in [0, num_nodes) to
209// have at least one incident arc. The model will be considered invalid if it
210// is not the case. You can add self-arc fixed to one to ignore some nodes if
211// needed.
212//
213// TODO(user): It is probably possible to generalize this constraint to a
214// no-cycle in a general graph, or a no-cycle with sum incoming <= 1 and sum
215// outgoing <= 1 (more efficient implementation). On the other hand, having this
216// specific constraint allow us to add specific "cuts" to a VRP problem.
217message RoutesConstraintProto {
218  repeated int32 tails = 1;
219  repeated int32 heads = 2;
220  repeated int32 literals = 3;
221
222  // EXPERIMENTAL. The demands for each node, and the maximum capacity for each
223  // route. Note that this is currently only used for the LP relaxation and one
224  // need to add the corresponding constraint to enforce this outside of the LP.
225  //
226  // TODO(user): Ideally, we should be able to extract any dimension like these
227  // (i.e. capacity, route_length, etc..) automatically from the encoding. The
228  // classical way to encode that is to have "current_capacity" variables along
229  // the route and linear equations of the form:
230  //   arc_literal => (current_capacity_tail + demand <= current_capacity_head)
231  repeated int32 demands = 4;
232  int64 capacity = 5;
233}
234
235// The values of the n-tuple formed by the given variables can only be one of
236// the listed n-tuples in values. The n-tuples are encoded in a flattened way:
237//     [tuple0_v0, tuple0_v1, ..., tuple0_v{n-1}, tuple1_v0, ...].
238message TableConstraintProto {
239  repeated int32 vars = 1;
240  repeated int64 values = 2;
241
242  // If true, the meaning is "negated", that is we forbid any of the given
243  // tuple from a feasible assignment.
244  bool negated = 3;
245}
246
247// The two arrays of variable each represent a function, the second is the
248// inverse of the first: f_direct[i] == j <=> f_inverse[j] == i.
249message InverseConstraintProto {
250  repeated int32 f_direct = 1;
251  repeated int32 f_inverse = 2;
252}
253
254// This constraint forces a sequence of variables to be accepted by an
255// automaton.
256message AutomatonConstraintProto {
257  // A state is identified by a non-negative number. It is preferable to keep
258  // all the states dense in says [0, num_states). The automaton starts at
259  // starting_state and must finish in any of the final states.
260  int64 starting_state = 2;
261  repeated int64 final_states = 3;
262
263  // List of transitions (all 3 vectors have the same size). Both tail and head
264  // are states, label is any variable value. No two outgoing transitions from
265  // the same state can have the same label.
266  repeated int64 transition_tail = 4;
267  repeated int64 transition_head = 5;
268  repeated int64 transition_label = 6;
269
270  // The sequence of variables. The automaton is ran for vars_size() "steps" and
271  // the value of vars[i] corresponds to the transition label at step i.
272  repeated int32 vars = 7;
273}
274
275// A list of variables, without any semantics.
276message ListOfVariablesProto {
277  repeated int32 vars = 1;
278}
279
280// Next id: 31
281message ConstraintProto {
282  // For debug/logging only. Can be empty.
283  string name = 1;
284
285  // The constraint will be enforced iff all literals listed here are true. If
286  // this is empty, then the constraint will always be enforced. An enforced
287  // constraint must be satisfied, and an un-enforced one will simply be
288  // ignored.
289  //
290  // This is also called half-reification. To have an equivalence between a
291  // literal and a constraint (full reification), one must add both a constraint
292  // (controlled by a literal l) and its negation (controlled by the negation of
293  // l).
294  //
295  // Important: as of September 2018, only a few constraint support enforcement:
296  // - bool_or, bool_and, linear: fully supported.
297  // - interval: only support a single enforcement literal.
298  // - other: no support (but can be added on a per-demand basis).
299  repeated int32 enforcement_literal = 2;
300
301  // The actual constraint with its arguments.
302  oneof constraint {
303    // The bool_or constraint forces at least one literal to be true.
304    BoolArgumentProto bool_or = 3;
305
306    // The bool_and constraint forces all of the literals to be true.
307    //
308    // This is a "redundant" constraint in the sense that this can easily be
309    // encoded with many bool_or or at_most_one. It is just more space efficient
310    // and handled slightly differently internally.
311    BoolArgumentProto bool_and = 4;
312
313    // The at_most_one constraint enforces that no more than one literal is
314    // true at the same time.
315    //
316    // Note that an at most one constraint of length n could be encoded with n
317    // bool_and constraint with n-1 term on the right hand side. So in a sense,
318    // this constraint contribute directly to the "implication-graph" or the
319    // 2-SAT part of the model.
320    //
321    // This constraint does not support enforcement_literal. Just use a linear
322    // constraint if you need to enforce it. You also do not need to use it
323    // directly, we will extract it from the model in most situations.
324    BoolArgumentProto at_most_one = 26;
325
326    // The exactly_one constraint force exactly one literal to true and no more.
327    //
328    // Anytime a bool_or (it could have been called at_least_one) is included
329    // into an at_most_one, then the bool_or is actually an exactly one
330    // constraint, and the extra literal in the at_most_one can be set to false.
331    // So in this sense, this constraint is not really needed. it is just here
332    // for a better description of the problem structure and to facilitate some
333    // algorithm.
334    //
335    // This constraint does not support enforcement_literal. Just use a linear
336    // constraint if you need to enforce it. You also do not need to use it
337    // directly, we will extract it from the model in most situations.
338    BoolArgumentProto exactly_one = 29;
339
340    // The bool_xor constraint forces an odd number of the literals to be true.
341    BoolArgumentProto bool_xor = 5;
342
343    // The int_div constraint forces the target to equal exprs[0] / exprs[1].
344    // In particular, exprs[1] can never take the value 0. Also, as for now, we
345    // do not support exprs[1] spanning across 0.
346    LinearArgumentProto int_div = 7;
347
348    // The int_mod constraint forces the target to equal exprs[0] % exprs[1].
349    // The domain of exprs[1] must be strictly positive. The sign of the target
350    // is the same as the sign of exprs[0].
351    LinearArgumentProto int_mod = 8;
352
353    // The int_prod constraint forces the target to equal the product of all
354    // variables. By convention, because we can just remove term equal to one,
355    // the empty product forces the target to be one.
356    //
357    // Note that the solver checks for potential integer overflow. So it is
358    // recommended to limit the domain of the variables such that the product
359    // fits in [INT_MIN + 1..INT_MAX - 1].
360    //
361    // TODO(user): Support more than two terms in the product.
362    LinearArgumentProto int_prod = 11;
363
364    // The lin_max constraint forces the target to equal the maximum of all
365    // linear expressions.
366    // Note that this can model a minimum simply by negating all expressions.
367    LinearArgumentProto lin_max = 27;
368
369    // The linear constraint enforces a linear inequality among the variables,
370    // such as 0 <= x + 2y <= 10.
371    LinearConstraintProto linear = 12;
372
373    // The all_diff constraint forces all variables to take different values.
374    AllDifferentConstraintProto all_diff = 13;
375
376    // The element constraint forces the variable with the given index
377    // to be equal to the target.
378    ElementConstraintProto element = 14;
379
380    // The circuit constraint takes a graph and forces the arcs present
381    // (with arc presence indicated by a literal) to form a unique cycle.
382    CircuitConstraintProto circuit = 15;
383
384    // The routes constraint implements the vehicle routing problem.
385    RoutesConstraintProto routes = 23;
386
387    // The table constraint enforces what values a tuple of variables may
388    // take.
389    TableConstraintProto table = 16;
390
391    // The automaton constraint forces a sequence of variables to be accepted
392    // by an automaton.
393    AutomatonConstraintProto automaton = 17;
394
395    // The inverse constraint forces two arrays to be inverses of each other:
396    // the values of one are the indices of the other, and vice versa.
397    InverseConstraintProto inverse = 18;
398
399    // The reservoir constraint forces the sum of a set of active demands
400    // to always be between a specified minimum and maximum value during
401    // specific times.
402    ReservoirConstraintProto reservoir = 24;
403
404    // Constraints on intervals.
405    //
406    // The first constraint defines what an "interval" is and the other
407    // constraints use references to it. All the intervals that have an
408    // enforcement_literal set to false are ignored by these constraints.
409    //
410    // TODO(user): Explain what happen for intervals of size zero. Some
411    // constraints ignore them; others do take them into account.
412
413    // The interval constraint takes a start, end, and size, and forces
414    // start + size == end.
415    IntervalConstraintProto interval = 19;
416
417    // The no_overlap constraint prevents a set of intervals from
418    // overlapping; in scheduling, this is called a disjunctive
419    // constraint.
420    NoOverlapConstraintProto no_overlap = 20;
421
422    // The no_overlap_2d constraint prevents a set of boxes from overlapping.
423    NoOverlap2DConstraintProto no_overlap_2d = 21;
424
425    // The cumulative constraint ensures that for any integer point, the sum
426    // of the demands of the intervals containing that point does not exceed
427    // the capacity.
428    CumulativeConstraintProto cumulative = 22;
429
430    // This constraint is not meant to be used and will be rejected by the
431    // solver. It is meant to mark variable when testing the presolve code.
432    ListOfVariablesProto dummy_constraint = 30;
433  }
434}
435
436// Optimization objective.
437message CpObjectiveProto {
438  // The linear terms of the objective to minimize.
439  // For a maximization problem, one can negate all coefficients in the
440  // objective and set scaling_factor to -1.
441  repeated int32 vars = 1;
442  repeated int64 coeffs = 4;
443
444  // The displayed objective is always:
445  //   scaling_factor * (sum(coefficients[i] * objective_vars[i]) + offset).
446  // This is needed to have a consistent objective after presolve or when
447  // scaling a double problem to express it with integers.
448  //
449  // Note that if scaling_factor is zero, then it is assumed to be 1, so that by
450  // default these fields have no effect.
451  double offset = 2;
452  double scaling_factor = 3;
453
454  // If non-empty, only look for an objective value in the given domain.
455  // Note that this does not depend on the offset or scaling factor, it is a
456  // domain on the sum of the objective terms only.
457  repeated int64 domain = 5;
458
459  // Internal field. Do not set. When we scale a FloatObjectiveProto to a
460  // integer version, we set this to true if the scaling was exact (i.e. all
461  // original coeff were integer for instance).
462  //
463  // TODO(user): Put the error bounds we computed instead?
464  bool scaling_was_exact = 6;
465
466  // Internal field. This is only useful for inner_objective_lower_bound, It
467  // should never be set in most cases, so we have the simple:
468  //   sum(coefficients[i] * objective_vars[i]) >= inner_objective_lower_bound.
469  //
470  // This is similar to offset/scaling_factor but allows to stay in the integer
471  // domain. Note that the formula is not the same than for the floating point
472  // objective. If this is set, we have
473  //    linear_expression * scaling + offset >= inner_objective_lower_bound
474  int64 integer_offset = 7;
475  int64 integer_scaling_factor = 8;
476}
477
478// A linear floating point objective: sum coeffs[i] * vars[i] + offset.
479// Note that the variable can only still take integer value.
480message FloatObjectiveProto {
481  repeated int32 vars = 1;
482  repeated double coeffs = 2;
483  double offset = 3;
484
485  // The optimization direction. The default is to minimize
486  bool maximize = 4;
487}
488
489// Define the strategy to follow when the solver needs to take a new decision.
490// Note that this strategy is only defined on a subset of variables.
491message DecisionStrategyProto {
492  // The variables to be considered for the next decision. The order matter and
493  // is always used as a tie-breaker after the variable selection strategy
494  // criteria defined below.
495  repeated int32 variables = 1;
496
497  // The order in which the variables above should be considered. Note that only
498  // variables that are not already fixed are considered.
499  //
500  // TODO(user): extend as needed.
501  enum VariableSelectionStrategy {
502    CHOOSE_FIRST = 0;
503    CHOOSE_LOWEST_MIN = 1;
504    CHOOSE_HIGHEST_MAX = 2;
505    CHOOSE_MIN_DOMAIN_SIZE = 3;
506    CHOOSE_MAX_DOMAIN_SIZE = 4;
507  }
508  VariableSelectionStrategy variable_selection_strategy = 2;
509
510  // Once a variable has been chosen, this enum describe what decision is taken
511  // on its domain.
512  //
513  // TODO(user): extend as needed.
514  enum DomainReductionStrategy {
515    SELECT_MIN_VALUE = 0;
516    SELECT_MAX_VALUE = 1;
517    SELECT_LOWER_HALF = 2;
518    SELECT_UPPER_HALF = 3;
519    SELECT_MEDIAN_VALUE = 4;
520  }
521  DomainReductionStrategy domain_reduction_strategy = 3;
522
523  // Advanced usage. Some of the variable listed above may have been transformed
524  // by the presolve so this is needed to properly follow the given selection
525  // strategy. Instead of using a value X for variables[index], we will use
526  // positive_coeff * X + offset instead.
527  message AffineTransformation {
528    int32 index = 1;
529    int64 offset = 2;
530    int64 positive_coeff = 3;
531  }
532  repeated AffineTransformation transformations = 4;
533}
534
535// This message encodes a partial (or full) assignment of the variables of a
536// CpModelProto. The variable indices should be unique and valid variable
537// indices.
538message PartialVariableAssignment {
539  repeated int32 vars = 1;
540  repeated int64 values = 2;
541}
542
543// A permutation of integers encoded as a list of cycles, hence the "sparse"
544// format. The image of an element cycle[i] is cycle[(i + 1) % cycle_length].
545message SparsePermutationProto {
546  // Each cycle is listed one after the other in the support field.
547  // The size of each cycle is given (in order) in the cycle_sizes field.
548  repeated int32 support = 1;
549  repeated int32 cycle_sizes = 2;
550}
551
552// A dense matrix of numbers encoded in a flat way, row by row.
553// That is matrix[i][j] = entries[i * num_cols + j];
554message DenseMatrixProto {
555  int32 num_rows = 1;
556  int32 num_cols = 2;
557  repeated int32 entries = 3;
558}
559
560// EXPERIMENTAL. For now, this is meant to be used by the solver and not filled
561// by clients.
562//
563// Hold symmetry information about the set of feasible solutions. If we permute
564// the variable values of any feasible solution using one of the permutation
565// described here, we should always get another feasible solution.
566//
567// We usually also enforce that the objective of the new solution is the same.
568//
569// The group of permutations encoded here is usually computed from the encoding
570// of the model, so it is not meant to be a complete representation of the
571// feasible solution symmetries, just a valid subgroup.
572message SymmetryProto {
573  // A list of variable indices permutations that leave the feasible space of
574  // solution invariant. Usually, we only encode a set of generators of the
575  // group.
576  repeated SparsePermutationProto permutations = 1;
577
578  // An orbitope is a special symmetry structure of the solution space. If the
579  // variable indices are arranged in a matrix (with no duplicates), then any
580  // permutation of the columns will be a valid permutation of the feasible
581  // space.
582  //
583  // This arise quite often. The typical example is a graph coloring problem
584  // where for each node i, you have j booleans to indicate its color. If the
585  // variables color_of_i_is_j are arranged in a matrix[i][j], then any columns
586  // permutations leave the problem invariant.
587  repeated DenseMatrixProto orbitopes = 2;
588}
589
590// A constraint programming problem.
591message CpModelProto {
592  // For debug/logging only. Can be empty.
593  string name = 1;
594
595  // The associated Protos should be referred by their index in these fields.
596  repeated IntegerVariableProto variables = 2;
597  repeated ConstraintProto constraints = 3;
598
599  // The objective to minimize. Can be empty for pure decision problems.
600  CpObjectiveProto objective = 4;
601
602  // Advanced usage.
603  // It is invalid to have both an objective and a floating point objective.
604  //
605  // The objective of the model, in floating point format. The solver will
606  // automatically scale this to integer during expansion and thus convert it to
607  // a normal CpObjectiveProto. See the mip* parameters to control how this is
608  // scaled. In most situation the precision will be good enough, but you can
609  // see the logs to see what are the precision guaranteed when this is
610  // converted to a fixed point representation.
611  //
612  // Note that even if the precision is bad, the returned objective_value and
613  // best_objective_bound will be computed correctly. So at the end of the solve
614  // you can check the gap if you only want precise optimal.
615  FloatObjectiveProto floating_point_objective = 9;
616
617  // Defines the strategy that the solver should follow when the
618  // search_branching parameter is set to FIXED_SEARCH. Note that this strategy
619  // is also used as a heuristic when we are not in fixed search.
620  //
621  // Advanced Usage: if not all variables appears and the parameter
622  // "instantiate_all_variables" is set to false, then the solver will not try
623  // to instantiate the variables that do not appear. Thus, at the end of the
624  // search, not all variables may be fixed. Currently, we will set them to
625  // their lower bound in the solution.
626  repeated DecisionStrategyProto search_strategy = 5;
627
628  // Solution hint.
629  //
630  // If a feasible or almost-feasible solution to the problem is already known,
631  // it may be helpful to pass it to the solver so that it can be used. The
632  // solver will try to use this information to create its initial feasible
633  // solution.
634  //
635  // Note that it may not always be faster to give a hint like this to the
636  // solver. There is also no guarantee that the solver will use this hint or
637  // try to return a solution "close" to this assignment in case of multiple
638  // optimal solutions.
639  PartialVariableAssignment solution_hint = 6;
640
641  // A list of literals. The model will be solved assuming all these literals
642  // are true. Compared to just fixing the domain of these literals, using this
643  // mechanism is slower but allows in case the model is INFEASIBLE to get a
644  // potentially small subset of them that can be used to explain the
645  // infeasibility.
646  //
647  // Think (IIS), except when you are only concerned by the provided
648  // assumptions. This is powerful as it allows to group a set of logically
649  // related constraint under only one enforcement literal which can potentially
650  // give you a good and interpretable explanation for infeasiblity.
651  //
652  // Such infeasibility explanation will be available in the
653  // sufficient_assumptions_for_infeasibility response field.
654  repeated int32 assumptions = 7;
655
656  // For now, this is not meant to be filled by a client writing a model, but
657  // by our preprocessing step.
658  //
659  // Information about the symmetries of the feasible solution space.
660  // These usually leaves the objective invariant.
661  SymmetryProto symmetry = 8;
662}
663
664// The status returned by a solver trying to solve a CpModelProto.
665enum CpSolverStatus {
666  // The status of the model is still unknown. A search limit has been reached
667  // before any of the statuses below could be determined.
668  UNKNOWN = 0;
669
670  // The given CpModelProto didn't pass the validation step. You can get a
671  // detailed error by calling ValidateCpModel(model_proto).
672  MODEL_INVALID = 1;
673
674  // A feasible solution has been found. But the search was stopped before we
675  // could prove optimality or before we enumerated all solutions of a
676  // feasibility problem (if asked).
677  FEASIBLE = 2;
678
679  // The problem has been proven infeasible.
680  INFEASIBLE = 3;
681
682  // An optimal feasible solution has been found.
683  //
684  // More generally, this status represent a success. So we also return OPTIMAL
685  // if we find a solution for a pure feasiblity problem or if a gap limit has
686  // been specified and we return a solution within this limit. In the case
687  // where we need to return all the feasible solution, this status will only be
688  // returned if we enumerated all of them; If we stopped before, we will return
689  // FEASIBLE.
690  OPTIMAL = 4;
691}
692
693// Just a message used to store dense solution.
694// This is used by the additional_solutions field.
695message CpSolverSolution {
696  repeated int64 values = 1;
697}
698
699// The response returned by a solver trying to solve a CpModelProto.
700//
701// TODO(user): support returning multiple solutions. Look at the Stubby
702// streaming API as we probably wants to get them as they are found.
703// Next id: 30
704message CpSolverResponse {
705  // The status of the solve.
706  CpSolverStatus status = 1;
707
708  // A feasible solution to the given problem. Depending on the returned status
709  // it may be optimal or just feasible. This is in one-to-one correspondence
710  // with a CpModelProto::variables repeated field and list the values of all
711  // the variables.
712  repeated int64 solution = 2;
713
714  // Only make sense for an optimization problem. The objective value of the
715  // returned solution if it is non-empty. If there is no solution, then for a
716  // minimization problem, this will be an upper-bound of the objective of any
717  // feasible solution, and a lower-bound for a maximization problem.
718  double objective_value = 3;
719
720  // Only make sense for an optimization problem. A proven lower-bound on the
721  // objective for a minimization problem, or a proven upper-bound for a
722  // maximization problem.
723  double best_objective_bound = 4;
724
725  // If the parameter fill_additional_solutions_in_response is set, then we
726  // copy all the solutions from our internal solution pool here.
727  //
728  // Note that the one returned in the solution field will likely appear here
729  // too. Do not rely on the solutions order as it depends on our internal
730  // representation (after postsolve).
731  repeated CpSolverSolution additional_solutions = 27;
732
733  // Advanced usage.
734  //
735  // If the option fill_tightened_domains_in_response is set, then this field
736  // will be a copy of the CpModelProto.variables where each domain has been
737  // reduced using the information the solver was able to derive. Note that this
738  // is only filled with the info derived during a normal search and we do not
739  // have any dedicated algorithm to improve it.
740  //
741  // If the problem is a feasibility problem, then these bounds will be valid
742  // for any feasible solution. If the problem is an optimization problem, then
743  // these bounds will only be valid for any OPTIMAL solutions, it can exclude
744  // sub-optimal feasible ones.
745  repeated IntegerVariableProto tightened_variables = 21;
746
747  // A subset of the model "assumptions" field. This will only be filled if the
748  // status is INFEASIBLE. This subset of assumption will be enough to still get
749  // an infeasible problem.
750  //
751  // This is related to what is called the irreducible inconsistent subsystem or
752  // IIS. Except one is only concerned by the provided assumptions. There is
753  // also no guarantee that we return an irreducible (aka minimal subset).
754  // However, this is based on SAT explanation and there is a good chance it is
755  // not too large.
756  //
757  // If you really want a minimal subset, a possible way to get one is by
758  // changing your model to minimize the number of assumptions at false, but
759  // this is likely an harder problem to solve.
760  //
761  // Important: Currently, this is minimized only in single-thread and if the
762  // problem is not an optimization problem, otherwise, it will always include
763  // all the assumptions.
764  //
765  // TODO(user): Allows for returning multiple core at once.
766  repeated int32 sufficient_assumptions_for_infeasibility = 23;
767
768  // Contains the integer objective optimized internally. This is only filled if
769  // the problem had a floating point objective, and on the final response, not
770  // the ones given to callbacks.
771  CpObjectiveProto integer_objective = 28;
772
773  // Advanced usage.
774  //
775  // A lower bound on the inner integer expression of the objective. This is
776  // either a bound on the expression in the returned integer_objective or on
777  // the integer expression of the original objective if the problem already has
778  // an integer objective.
779  int64 inner_objective_lower_bound = 29;
780
781  // Some statistics about the solve.
782  // TODO(user): These are broken in multi-thread.
783  int64 num_booleans = 10;
784  int64 num_conflicts = 11;
785  int64 num_branches = 12;
786  int64 num_binary_propagations = 13;
787  int64 num_integer_propagations = 14;
788  int64 num_restarts = 24;
789  int64 num_lp_iterations = 25;
790
791  // The time counted from the beginning of the Solve() call.
792  double wall_time = 15;
793  double user_time = 16;
794  double deterministic_time = 17;
795
796  // The integral of log(1 + absolute_objective_gap) over time.
797  double gap_integral = 22;
798
799  // Additional information about how the solution was found. It also stores
800  // model or parameters errors that caused the model to be invalid.
801  string solution_info = 20;
802
803  // The solve log will be filled if the parameter log_to_response is set to
804  // true.
805  string solve_log = 26;
806}
807