package operations_research

Get desktop application:
View/edit binary Protocol Buffers messages

Acceptance strategy in which a solution is accepted only if it has less absences than the reference solution (see Slack Induction by String Removals for Vehicle Routing Problems" Christiaens and Vanden Berghe, Transportation Science 2020). In particular, for each node n, the number of solutions where n was not performed by any route is tracked by a counter absences[n]. A candidate is accepted if sum(absences[n]) < sum(absences[m]) with n in unperformed(candidate) m in unperformed(reference) The counter absences is increased after every ILS iteration for the unperformed nodes in the reference solution. In addition, when remove_route_with_lowest_absences is true and a new best found solution is found, the route with the lowest sum of absences is removed from the reference solution.

Used in: AcceptanceStrategy

• optional bool remove_route_with_lowest_absences = 1

  If true, when a new best solution is found, the route with the lowest sum of absences is removed from the reference solution.

Determines when a candidate solution replaces another one.

Used in: IteratedLocalSearchParameters

• oneof strategy

  • GreedyDescentAcceptanceStrategy greedy_descent = 1

  • SimulatedAnnealingAcceptanceStrategy simulated_annealing = 2

  • AllNodesPerformedAcceptanceStrategy all_nodes_performed = 3

  • MoreNodesPerformedAcceptanceStrategy more_nodes_performed = 4

  • AbsencesBasedAcceptanceStrategy absences_based = 5

Acceptance strategy in which a solution is accepted only if all nodes are performed. Disjunctions are respected when several nodes can be performed.

Used in: AcceptanceStrategy

(message has no fields)

Global container for all assignment variables and objective

• repeated IntVarAssignment int_var_assignment = 1

• repeated IntervalVarAssignment interval_var_assignment = 2

• repeated SequenceVarAssignment sequence_var_assignment = 6

• repeated IntVarAssignment objective = 3

• optional WorkerInfo worker_info = 4

• bool is_valid = 5

Represents a capacity constraint to be used in conjunction with a SetCoverProto. This constraint only considers one dimension. Such a capacity constraint mathematically looks like: min_capacity <= \sum_{e in elements} weight_e * x_e <= max_capacity where either `min_capacity` or `max_capacity` can be omitted. `x_e` indicates for a given solution `x` whether the element `e` is selected and counts for this capacity constraint (`x_e == 1`) or not (`x_e == 0`). The weights are given in `capacity_term`, each of them being a reference to an element being present in a subset (in set-covering parlance) and its weight. For instance, this constraint can be used together with a set-covering problem where parcels (element) must be covered by trucks (subsets) while respecting truck capacities (this object). Each element can be covered by a given set of trucks (set-covering problem); if an element is taken within a truck, it uses some capacity for this truck (such as weight). In particular, this representation does not imply that a given element must have the same weight in all the capacity constraints of a set-covering problem (e.g., the same parcel might have different weights depending on which truck is being considered).

• repeated CapacityConstraintProto.CapacityTerm capacity_term = 1

  The list of terms in the constraint. The list is supposed to be in canonical form, which means it is sorted first by increasing subset index then increasing element index. No duplicate term is allowed (two terms for the same element in the same subset).

• int64 min_capacity = 2

  The minimum amount of resource that must be consumed. At least one of `min_capacity` and `max_capacity` must be present.

• int64 max_capacity = 3

  The maximum amount of resource that can be consumed. At least one of `min_capacity` and `max_capacity` must be present.

Used in: CapacityConstraintProto

• int64 subset = 1

  The subset this weight corresponds to (index of the subset in the `subset` repeated field in `SetCoverProto`).

• repeated CapacityTerm.ElementWeightPair element_weights = 2

Used in: CapacityTerm

• int64 element = 1

  The element this weight corresponds to (value of `element` in `SetCoverProto.Subset`).

• int64 weight = 2

  The weight of the element.

Used in: CourseSchedulingResult

• int32 course_index = 1

  Index of the course in the CourseSchedulingModel.

• int32 section_number = 2

  Specific section of the course in the CourseSchedulingModel.

• repeated int32 time_slots = 3

  Time slots that this class has been assigned to in the CourseSchedulingModel.

• repeated int32 room_indices = 4

  Indices of the rooms that the class is assigned to in the CourseSchedulingModel. If this is not empty, then the number of indices must match the number of time slots.

• string constraint_id = 1

• repeated int64 initial_propagation_start_time = 2

• repeated int64 initial_propagation_end_time = 3

• int64 failures = 4

• repeated DemonRuns demons = 5

Solver parameters.

Used in: RoutingModelParameters

• ConstraintSolverParameters.TrailCompression compress_trail = 1

  This parameter indicates if the solver should compress the trail during the search. No compression means that the solver will be faster, but will use more memory.

• int32 trail_block_size = 2

  This parameter indicates the default size of a block of the trail. Compression applies at the block level.

• int32 array_split_size = 3

  When a sum/min/max operation is applied on a large array, this array is recursively split into blocks of size 'array_split_size'.

• bool store_names = 4

  This parameters indicates if the solver should store the names of the objets it manages.

• bool name_cast_variables = 5

  Create names for cast variables.

• bool name_all_variables = 6

  Should anonymous variables be given a name.

• bool profile_propagation = 7

  Activate propagation profiling.

• string profile_file = 8

  Export propagation profiling data to file.

• bool profile_local_search = 16

  Activate local search profiling.

• bool print_local_search_profile = 17

  Print local search profiling data after solving.

• bool trace_propagation = 9

  Activate propagate tracing.

• bool trace_search = 10

  Trace search.

• bool print_model = 11

  Print the model before solving.

• bool print_model_stats = 12

  Print model statistics before solving.

• bool print_added_constraints = 13

  Print added constraints.

• bool disable_solve = 15

• bool use_small_table = 101

  Control the implementation of the table constraint.

• bool use_cumulative_edge_finder = 105

  Control the propagation of the cumulative constraint.

• bool use_cumulative_time_table = 106

• bool use_cumulative_time_table_sync = 112

• bool use_sequence_high_demand_tasks = 107

• bool use_all_possible_disjunctions = 108

• int32 max_edge_finder_size = 109

• bool diffn_use_cumulative = 110

  Control the propagation of the diffn constraint.

• bool use_element_rmq = 111

  Control the implementation of the element constraint.

• bool skip_locally_optimal_paths = 113

  Skip locally optimal pairs of paths in PathOperators. Setting this parameter to true might skip valid neighbors if there are constraints linking paths together (such as precedences). In any other case this should only speed up the search without omitting any neighbors.

• int32 check_solution_period = 114

  Control the behavior of local search.

Internal parameters of the solver.

Used in: ConstraintSolverParameters

• NO_COMPRESSION = 0

• COMPRESS_WITH_ZLIB = 1

Statistics on the search in the constraint solver.

Used in: SearchStatistics

• int64 num_branches = 1

  Number of branches explored.

• int64 num_failures = 2

  Number of failures/backtracks.

• int64 num_solutions = 3

  Number of solutions found.

• int64 bytes_used = 4

  Memory usage of the solver.

• double duration_seconds = 5

  Total time spent in the solver.

The cooling schedule strategy defines how to compute the current simulated annealing temperature t given - the initial temperature t0 - the final temperature t1 - the current search progress 0 <= p <= 1 The value of t0 and t1 is defined by the initial_temperature and final_temperature in SimulatedAnnealingParameters, respectively. The search progress p is derived, at any given time, by the search limits. In particular, p measures how far we are in the search process w.r.t. to the number of explored solutions and the time limit. The temperature t, computed according to one of the strategies defined below, together with the selected AcceptanceStrategy, is used to guide the search trajectory. In particular, given a neighbor solution S', generated by the the application of the perturbation and improvement step to a reference solution S, we have that S will be replaced by S' iff cost(S') + t * log(U(0, 1)) < cost(S) where U(0, 1) is a random number sampled from a uniform distribution of real numbers in [0, 1].

(message has no fields)

Used in: SimulatedAnnealingAcceptanceStrategy

• UNSET = 0

  Unspecified value.

• EXPONENTIAL = 1

  Exponentially decreases the temperature as the search progresses. More precisely, t = t0 * (t1/t0)^p.

• LINEAR = 2

  Linearly decreases the temperature as the search progresses. More precisely, t = t0 - p * (t0 - t1).

Used in: CourseSchedulingModel

• string display_name = 1

  Course name, used only for logging purposes.

• int32 meetings_count = 2

  The number of times each section of this course needs to meet during a schedule rotation. Each section of the course meets no more than once a day. If the school system uses a block schedule, then this value should be 1.

• int32 max_capacity = 3

  The maximum number of students for this course. This value can be equal to +Infinity to encode a course has no maximum capacity.

• int32 min_capacity = 4

  The minimum number of students for this course.

• int32 consecutive_slots_count = 5

  The number of consecutive time slots that each section of this course needs to be scheduled for. This value can only be 1 or 2. If the value is 2, then 2 consecutive time slots in a day counts as 1 meeting time for the section.

• repeated int32 teacher_indices = 6

  List of indices for the teachers of this course. We are assuming that each teacher teaches separately. Must have the same number of elements as the number of sections list.

• repeated int32 teacher_section_counts = 7

  The number of sections each teacher teaches of this course. Must have the same number of elements as the teacher index list.

• repeated int32 room_indices = 8

  List of the possible rooms that this course can be assigned to. This can be empty.

Information required to create a schedule for a school system.

• string display_name = 1

  Schedule name, used only for logging purposes.

• int32 days_count = 2

  The number of days in a schedule rotation. If the school system uses a block schedule, this value should be 1.

• int32 daily_time_slot_count = 3

  The number of time slots each day in a schedule rotation. If the school system uses a block schedule, this value is the number of blocks.

• repeated Course courses = 4

  List of courses that need to be scheduled.

• repeated Teacher teachers = 5

  List of teachers.

• repeated Student students = 6

  List of students that need to be assigned to these courses.

• repeated Room rooms = 7

  List of rooms that the courses can be assigned to.

Holds the solution to the course scheduling problem.

• string message = 1

  Human readable message about the solver or given model.

• CourseSchedulingResultStatus solver_status = 2

  Status of the solver.

• repeated ClassAssignment class_assignments = 3

  List of the time slot and room assignments for each section of a course.

• repeated StudentAssignment student_assignments = 4

  List of course and section assignments for each student.

Status returned by the solver.

Used in: CourseSchedulingResult

• COURSE_SCHEDULING_RESULT_STATUS_UNSPECIFIED = 0

• SOLVER_FEASIBLE = 1

  The solver had enough time to find some solution that satisfies all constraints, but it did not prove optimality (which means it may or may not have reached the optimal). This can happen for large LP models (linear programming), and is a frequent response for time-limited MIPs (mixed integer programming). This is also what the CP (constraint programming) solver will return if there is no objective specified.

• SOLVER_OPTIMAL = 2

  The solver found the proven optimal solution.

• SOLVER_INFEASIBLE = 3

  The model does not have any solution, according to the solver (which "proved" it, with the caveat that numerical proofs aren't actual proofs), or based on trivial considerations (eg. a variable whose lower bound is strictly greater than its upper bound).

• SOLVER_MODEL_INVALID = 4

  Model errors. These are always deterministic and repeatable. They should be accompanied with a string description of the error.

• SOLVER_NOT_SOLVED = 5

  The model has not been solved in the given time or the solver was not able to solve the model given.

• ABNORMAL = 6

  An error (either numerical or from a bug in the code) occurred.

Used in: ConstraintRuns

• string demon_id = 1

• repeated int64 start_time = 2

• repeated int64 end_time = 3

• int64 failures = 4

First solution strategies, used as starting point of local search.

(message has no fields)

Used in: RecreateStrategy, RoutingSearchParameters

• UNSET = 0

  See the homonymous value in LocalSearchMetaheuristic.

• AUTOMATIC = 15

  Lets the solver detect which strategy to use according to the model being solved.

• PATH_CHEAPEST_ARC = 3

  --- Path addition heuristics --- Starting from a route "start" node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route.

• PATH_MOST_CONSTRAINED_ARC = 4

  Same as PATH_CHEAPEST_ARC, but arcs are evaluated with a comparison-based selector which will favor the most constrained arc first. To assign a selector to the routing model, see RoutingModel::ArcIsMoreConstrainedThanArc() in routing.h for details.

• EVALUATOR_STRATEGY = 5

  Same as PATH_CHEAPEST_ARC, except that arc costs are evaluated using the function passed to RoutingModel::SetFirstSolutionEvaluator() (cf. routing.h).

• SAVINGS = 10

  Savings algorithm (Clarke & Wright). Reference: Clarke, G. & Wright, J.W.: "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, pp. 568-581

• PARALLEL_SAVINGS = 17

  Parallel version of the Savings algorithm. Instead of extending a single route until it is no longer possible, the parallel version iteratively considers the next most improving feasible saving and possibly builds several routes in parallel.

• SWEEP = 11

  Sweep algorithm (Wren & Holliday). Reference: Anthony Wren & Alan Holliday: Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points Operational Research Quarterly (1970-1977), Vol. 23, No. 3 (Sep., 1972), pp. 333-344

• CHRISTOFIDES = 13

  Christofides algorithm (actually a variant of the Christofides algorithm using a maximal matching instead of a maximum matching, which does not guarantee the 3/2 factor of the approximation on a metric travelling salesman). Works on generic vehicle routing models by extending a route until no nodes can be inserted on it. Reference: Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

• ALL_UNPERFORMED = 6

  --- Path insertion heuristics --- Make all nodes inactive. Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost).

• BEST_INSERTION = 7

  Iteratively build a solution by inserting the cheapest node at its cheapest position; the cost of insertion is based on the global cost function of the routing model. As of 2/2012, only works on models with optional nodes (with finite penalty costs).

• PARALLEL_CHEAPEST_INSERTION = 8

  Iteratively build a solution by inserting the cheapest node at its cheapest position; the cost of insertion is based on the arc cost function. Is faster than BEST_INSERTION.

• SEQUENTIAL_CHEAPEST_INSERTION = 14

  Iteratively build a solution by constructing routes sequentially, for each route inserting the cheapest node at its cheapest position until the route is completed; the cost of insertion is based on the arc cost function. Is faster than PARALLEL_CHEAPEST_INSERTION.

• LOCAL_CHEAPEST_INSERTION = 9

  Iteratively build a solution by inserting each node at its cheapest position; the cost of insertion is based on the arc cost function. Differs from PARALLEL_CHEAPEST_INSERTION by the node selected for insertion; here nodes are considered in decreasing order of distance to the start/ends of the routes, i.e. farthest nodes are inserted first. Is faster than SEQUENTIAL_CHEAPEST_INSERTION.

• LOCAL_CHEAPEST_COST_INSERTION = 16

  Same as LOCAL_CHEAPEST_INSERTION except that the cost of insertion is based on the routing model cost function instead of arc costs only.

• GLOBAL_CHEAPEST_ARC = 1

  --- Variable-based heuristics --- Iteratively connect two nodes which produce the cheapest route segment.

• LOCAL_CHEAPEST_ARC = 2

  Select the first node with an unbound successor and connect it to the node which produces the cheapest route segment.

• FIRST_UNBOUND_MIN_VALUE = 12

  Select the first node with an unbound successor and connect it to the first available node. This is equivalent to the CHOOSE_FIRST_UNBOUND strategy combined with ASSIGN_MIN_VALUE (cf. constraint_solver.h).

Used in: FlowModelProto

• optional int64 tail = 1

  A directed arc goes from a tail node to a head node. Node ids must be non-negative (>= 0).

• optional int64 head = 2

• optional int64 capacity = 3

  Capacity of the arc. Must be non-negative (>= 0). If the capacity is zero, it is equivalent to not including the arc in the FlowModelProto.

• optional int64 unit_cost = 4

  Cost of this arc per unit of flow. Note that it can take any positive, negative or null value.

Holds a flow problem, see NodeProto and ArcProto for more details.

• repeated FlowNodeProto nodes = 1

• repeated FlowArcProto arcs = 2

• optional FlowModelProto.ProblemType problem_type = 3

The type of problem to solve.

Used in: FlowModelProto

• LINEAR_SUM_ASSIGNMENT = 0

• MAX_FLOW = 1

• MIN_COST_FLOW = 2

Used in: FlowModelProto

• optional int64 id = 1

  The ids must be non-negative (>= 0). They should be dense for good performance. Note that it is not mandatory to include nodes with no supply in a FlowModelProto.

• optional int64 supply = 2

  The supply can be positive or negative in which case it means demand. The sum of the supplies over all nodes must always be 0.

Used in: math_opt.SolveResultProto

• GScipOutput.Status status = 1

• string status_detail = 2

• optional GScipSolvingStats stats = 3

See https://scip.zib.de/doc/html/type__stat_8h.php

Used in: GScipOutput

• UNKNOWN = 0

• USER_INTERRUPT = 1

• NODE_LIMIT = 2

• TOTAL_NODE_LIMIT = 3

• STALL_NODE_LIMIT = 4

• TIME_LIMIT = 5

• MEM_LIMIT = 6

• GAP_LIMIT = 7

• SOL_LIMIT = 8

• BEST_SOL_LIMIT = 9

• RESTART_LIMIT = 10

• OPTIMAL = 11

• INFEASIBLE = 12

• UNBOUNDED = 13

• INF_OR_UNBD = 14

• TERMINATE = 15

• INVALID_SOLVER_PARAMETERS = 16

  WARNING(rander): we add some extra status values beyond SCIP here

Contains both the "SCIP parameters" and gSCIP only configuration. For the SCIP parameters, the order of application is: 1. Emphasis 2. Meta parameters (heuristics, presolve, separating) 3. Individual SCIP parameters (e.g. an entry in bool_params) Note that 1. and 2. both apply a combination of parameters from 3. For parameters that are marked as optional, the underlying solver default is used if they are not specified.

Used in: math_opt.SolveParametersProto

• GScipParameters.Emphasis emphasis = 1

• optional GScipParameters.MetaParamValue heuristics = 2

  See SCIPsetHeuristics() for details: https://scip.zib.de/doc/html/group__ParameterMethods.php#gaeccb7859066cadd01d0df7aca98e2c7d

• optional GScipParameters.MetaParamValue presolve = 3

  See SCIPsetPresolving() for details: https://scip.zib.de/doc/html/group__ParameterMethods.php#ga8365de8ab5ec5961c005e2d77965b182

• optional GScipParameters.MetaParamValue separating = 4

  See SCIPsetSeparating() for details: https://scip.zib.de/doc/html/group__ParameterMethods.php#gad0c64e3e9b8def72fd8a7d3d9dce7729

• map<string, bool> bool_params = 5

  See https://scip.zib.de/doc/html/PARAMETERS.php for a list of all SCIP parameters.

• map<string, int32> int_params = 6

• map<string, int64> long_params = 7

• map<string, double> real_params = 8

• map<string, string> char_params = 9

• map<string, string> string_params = 10

• optional bool silence_output = 11

  Disable all terminal output (override all logging parameters). To control only the search logs, see also the SCIP parameter display/verblevel and from gscip_parameters.h, SetLogLevel() and SetOutputEnabled().

• bool print_detailed_solving_stats = 12

  Log solver metrics to terminal when finished solving (unless silenced).

• bool print_scip_model = 13

  Write out the model in SCIP's text format before solving to the terminal (unless silenced).

• string search_logs_filename = 14

  If nonempty, search logs are written here INSTEAD OF out to terminal. See also the SCIP parameter display/verblevel and from gscip_parameters.h, the functions SetLogLevel() and SetOutputEnabled() for configuring the search logs. Does not use gfile, can only write to local disk.

• string detailed_solving_stats_filename = 15

  If non-empty, write detailed_solving_stats to a file. Can be set independently from print_detailed_solving_stats. Does not use gfile, can only write to local disk.

• string scip_model_filename = 16

  If nonempty, out the model in SCIP's text format to a file before solving. Can be set independently of print_scip_model. Does not use gfile, can only write to local disk.

• optional int32 num_solutions = 17

  How many solutions to retrieve from the solution pool (if this many exist). At least one solution will always be returned, even if num_solutions < 1.

• optional double objective_limit = 18

  If set, ignore all solutions worse than objective_limit, for details see SCIPsetObjlimit(). Note that the solution pool will still contain solutions worse than the limit as SCIP uses these to run improvement heuristics, and if you query all solutions at the end of the solve they will be present, even if you found no solution that met the limit and returned infeasible.

See SCIP documentation for details: https://scip.zib.de/doc/html/type__paramset_8h.php#a2e51a867a8ea3ea16f15e7cc935c3f32

Used in: GScipParameters

• DEFAULT_EMPHASIS = 0

• COUNTER = 1

• CP_SOLVER = 2

• EASY_CIP = 3

• FEASIBILITY = 4

• HARD_LP = 5

• OPTIMALITY = 6

• PHASE_FEAS = 7

• PHASE_IMPROVE = 8

• PHASE_PROOF = 9

See SCIP documentation for details: https://scip.zib.de/doc/html/type__paramset_8h.php#a083067d8e425d0d44e834095e82902ed

Used in: GScipParameters

• DEFAULT_META_PARAM_VALUE = 0

• AGGRESSIVE = 1

• FAST = 2

• OFF = 3

TODO(user): this should be machine generated by script and contain all of https://scip.zib.de/doc/html/group__PublicSolvingStatsMethods.php

Used in: GScipOutput

• double best_objective = 1

  The objective value of the best solution (or the cutoff). If no solution is found, returns +inf for minimization and -inf for maximization. Equivalent to SCIPgetPrimalbound().

• double best_bound = 2

  The best proven bound on the object (e.g. through the LP relaxation). Returns +inf for maximization and -inf for minimization if no bound was found. Equivalent to SCIPgetDualBound().

• int64 primal_simplex_iterations = 3

  nprimallpiterations in SCIP. The number of primal simplex LP iterations.

• int64 dual_simplex_iterations = 4

  nduallpiterations in SCIP. The number of dual simplex LP iterations.

• int64 barrier_iterations = 10

  nbarrierlpiterations. The number of barrier LP iterations.

• int64 total_lp_iterations = 5

  nlp_iterations in SCIP. The total number of LP steps taken. Note that this number be at least (and often strictly greater than) primal_simplex_iterations + dual simplex iterations + barrier iterations, as it includes other types of iterations (e.g. see ndivinglpiterations).

• int64 node_count = 6

  NTotalNodes in SCIP. This is the total number of nodes used in the solve, potentially across multiple branch-and-bound trees. Use limits/totalnodes (rather than limits/nodes) to control this value.

• double first_lp_relaxation_bound = 7

  FirstLPDualboundRoot in SCIP. The bound obtained from the first LP solve at the root node.

• double root_node_bound = 8

  DualboundRoot in SCIP. The bound obtained at the root node, possibly after multiple rounds of cuts.

• double deterministic_time = 9

  A deterministic measure of work done during the solve. The units of this field are specific to SCIP.

Parameters used to configure global cheapest insertion heuristics.

Used in: RecreateParameters, RoutingSearchParameters

• double farthest_seeds_ratio = 1

  Ratio (between 0 and 1) of available vehicles in the model on which farthest nodes of the model are inserted as seeds.

• double neighbors_ratio = 2

  Ratio (in ]0, 1]) of closest non start/end nodes to consider as neighbors for each node when creating new insertions in the parallel/sequential cheapest insertion heuristic. If not overridden, its default value is 1, meaning all neighbors will be considered. The neighborhood ratio is coupled with the corresponding min_neighbors integer, indicating the minimum number of neighbors to consider for each node: num_closest_neighbors = max(min_neighbors, neighbors_ratio * NUM_NON_START_END_NODES) This minimum number of neighbors must be greater or equal to 1, its default value.

• int32 min_neighbors = 3

• bool use_neighbors_ratio_for_initialization = 6

  Whether or not to only consider closest neighbors when initializing the assignment. More precisely, if true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion positions during initialization. Otherwise, all possible insertion positions are considered.

• bool add_unperformed_entries = 7

  Whether or not to consider entries making the nodes/pairs unperformed. More precisely, if true, entries are created for making the nodes/pairs unperformed, and when the cost of making a node unperformed is lower than all insertions, the node/pair will be made unperformed. If false, only entries making a node/pair performed are considered.

Acceptance strategy in which only improving solutions are accepted.

Used in: AcceptanceStrategy

(message has no fields)

The low 64 bits are stored in "low", and the high 64-bits (including the sign) are stored in "high".

Used in: SetCoverProto, SetCoverSolutionResponse

• int64 high = 1

• uint64 low = 2

Storage for IntVars.

Used in: AssignmentProto

• string var_id = 1

• int64 min = 2

• int64 max = 3

• bool active = 4

Storage for IntervalVars.

Used in: AssignmentProto

• string var_id = 1

• int64 start_min = 2

• int64 start_max = 3

• int64 duration_min = 4

• int64 duration_max = 5

• int64 end_min = 6

• int64 end_max = 7

• int64 performed_min = 8

• int64 performed_max = 9

• bool active = 10

Specifies the behavior of a search based on ILS.

Used in: RoutingSearchParameters

• PerturbationStrategy.Value perturbation_strategy = 1

  Determines how a reference solution S is perturbed to obtain a neighbor solution S'.

• optional RuinRecreateParameters ruin_recreate_parameters = 2

  Parameters to customize a ruin and recreate perturbation.

• optional bool improve_perturbed_solution = 3

  Determines whether solution S', obtained from the perturbation, should be optimized with a local search application.

• optional AcceptanceStrategy reference_solution_acceptance_strategy = 4

  Determines when the neighbor solution S', possibly improved if `improve_perturbed_solution` is true, replaces the reference solution S.

• optional AcceptanceStrategy best_solution_acceptance_strategy = 5

  Determines when the neighbor solution S' replaces the best solution found so far.

Parameters used to configure local cheapest insertion heuristics.

Used in: RecreateParameters, RoutingSearchParameters

• LocalCheapestInsertionParameters.PairInsertionStrategy pickup_delivery_strategy = 1

  Choice of insertion strategy for pickup/delivery pairs, used in local cheapest insertion, both first solution heuristic and LNS.

• repeated LocalCheapestInsertionParameters.InsertionSortingProperty insertion_sorting_properties = 2

  The properties used to sort insertion entries in the local cheapest insertion heuristic, in *decreasing* order of priority. The properties listed here are applied hierarchically, from highest to lowest priority. When no properties are provided (SORTING_PROPERTY_ALLOWED_VEHICLES, SORTING_PROPERTY_PENALTY) is used by default.

Properties used to select in which order nodes or node pairs are considered in insertion heuristics.

Used in: LocalCheapestInsertionParameters

• SORTING_PROPERTY_UNSPECIFIED = 0

  Invalid property.

• SORTING_PROPERTY_ALLOWED_VEHICLES = 1

  Selects nodes with the least number of allowed vehicles.

• SORTING_PROPERTY_PENALTY = 2

  Selects nodes with the highest penalty.

• SORTING_PROPERTY_PENALTY_OVER_ALLOWED_VEHICLES_RATIO = 3

  Selects nodes with the highest penalty / number of allowed vehicles ratio.

• SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS = 4

  Selects nodes that are on average the farthest from vehicles.

• SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS = 5

  Selects nodes that are on average the closest to vehicles.

• SORTING_PROPERTY_LOWEST_MIN_ARC_COST_TO_VEHICLE_START_ENDS = 6

  Select nodes with the smallest distance to the closest vehicle.

• SORTING_PROPERTY_HIGHEST_DIMENSION_USAGE = 7

  Selects nodes that have a higher dimension usage on average, where the usage is determined as the ratio of node demand over vehicle capacity. Currently, this property only supports unary dimensions.

• SORTING_PROPERTY_RANDOM = 8

  Selects nodes in random order. This property cannot be used in conjunction with other properties.

In insertion-based heuristics, describes what positions must be considered when inserting a pickup/delivery pair, and in what order they are considered.

Used in: LocalCheapestInsertionParameters

• AUTOMATIC = 0

  Let the solver decide the set of positions and its ordering.

• BEST_PICKUP_THEN_BEST_DELIVERY = 1

  Consider all positions, by increasing (cost(pickup), cost(delivery)).

• BEST_PICKUP_DELIVERY_PAIR = 2

  Consider all positions, by increasing by cost(pickup) + cost(delivery).

• BEST_PICKUP_DELIVERY_PAIR_MULTITOUR = 3

  Only consider insertion positions that are compatible with the multitour property, meaning a series of pickups may only start when the vehicle is not carrying any delivery. This setting is designed to explore much less possibilities than the full BEST_PICKUP_DELIVERY_PAIR. Order by increasing by cost(pickup) + cost(delivery).

Local search metaheuristics used to guide the search. Apart from greedy descent, they will try to escape local minima.

(message has no fields)

Used in: RoutingSearchParameters

• UNSET = 0

  Means "not set". If the solver sees that, it'll behave like for AUTOMATIC. But this value won't override others upon a proto MergeFrom(), whereas "AUTOMATIC" will.

• AUTOMATIC = 6

  Lets the solver select the metaheuristic.

• GREEDY_DESCENT = 1

  Accepts improving (cost-reducing) local search neighbors until a local minimum is reached.

• GUIDED_LOCAL_SEARCH = 2

  Uses guided local search to escape local minima (cf. http://en.wikipedia.org/wiki/Guided_Local_Search); this is generally the most efficient metaheuristic for vehicle routing.

• SIMULATED_ANNEALING = 3

  Uses simulated annealing to escape local minima (cf. http://en.wikipedia.org/wiki/Simulated_annealing).

• TABU_SEARCH = 4

  Uses tabu search to escape local minima (cf. http://en.wikipedia.org/wiki/Tabu_search).

• GENERIC_TABU_SEARCH = 5

  Uses tabu search on a list of variables to escape local minima. The list of variables to use must be provided via the SetTabuVarsCallback callback.

Statistics on local search.

Used in: SearchStatistics

• repeated LocalSearchStatistics.FirstSolutionStatistics first_solution_statistics = 6

  Statistics for each first solution called during the search.

• repeated LocalSearchStatistics.LocalSearchOperatorStatistics local_search_operator_statistics = 1

  Statistics for each operator called during the search.

• int64 total_num_neighbors = 3

  Total number of (filtered/accepted) neighbors created during the search.

• int64 total_num_filtered_neighbors = 4

• int64 total_num_accepted_neighbors = 5

• repeated LocalSearchStatistics.LocalSearchFilterStatistics local_search_filter_statistics = 2

  Statistics for each filter called during the search.

First solution statistics collected during search.

Used in: LocalSearchStatistics

• string strategy = 1

  Name of the strategy used.

• double duration_seconds = 2

  Time spent in the decision builder.

Statistics on local search filters called during the search.

Used in: LocalSearchStatistics

• string local_search_filter = 1

  Name of the filter.

• int64 num_calls = 2

  Number of times the filter was called.

• int64 num_rejects = 3

  Number of times the filter rejected a neighbor.

• double duration_seconds = 4

  Time spent in the filter.

• double num_rejects_per_second = 5

  Number of rejects per second.

• string context = 6

  Context within which the filter was called.

Statistics on local search operators called during the search.

Used in: LocalSearchStatistics

• string local_search_operator = 1

  Name of the operator.

• int64 num_neighbors = 2

  Number of neighbors generated by the operator.

• int64 num_filtered_neighbors = 3

  Number of neighbors which were filtered.

• int64 num_accepted_neighbors = 4

  Number of neighbors eventually accepted.

• double duration_seconds = 5

  Time spent in the operator.

• double make_next_neighbor_duration_seconds = 6

  Time spent in creating neighbors (calling MakeNextNeighbor).

• double accept_neighbor_duration_seconds = 7

  Time spent in accepting a neighbor (restoration and storage, not including filtering).

Sets a variable's value to the absolute value of another variable.

Used in: MPGeneralConstraintProto

• optional int32 var_index = 1

  Variable indices are relative to the "variable" field in MPModelProto. resultant_var = abs(var)

• optional int32 resultant_var_index = 2

Sets a variable's value equal to a function on a set of variables.

Used in: MPGeneralConstraintProto

• repeated int32 var_index = 1

  Variable indices are relative to the "variable" field in MPModelProto.

• optional int32 resultant_var_index = 2

Sets a variable's value equal to a function on a set of variables and, optionally, a constant.

Used in: MPGeneralConstraintProto

• repeated int32 var_index = 1

  Variable indices are relative to the "variable" field in MPModelProto. resultant_var = f(var_1, var_2, ..., constant)

• optional double constant = 2

• optional int32 resultant_var_index = 3

A linear constraint is always of the form: lower_bound <= sum of linear term elements <= upper_bound, where lower_bound and upper_bound: - Can form a singleton: lower_bound == upper_bound. The constraint is an equation. - Can form a finite interval [lower_bound, upper_bound]. The constraint is both lower- and upper-bounded, i.e. "boxed". - Can form a semi-infinite interval. lower_bound = -infinity: the constraint is upper-bounded. upper_bound = +infinity: the constraint is lower-bounded. - Can form the infinite interval: lower_bound = -infinity and upper_bound = +infinity. The constraint is free.

Used in: MPIndicatorConstraint, MPModelDeltaProto, MPModelProto

• repeated int32 var_index = 6

  var_index[i] is the variable index (w.r.t. to "variable" field of MPModelProto) of the i-th linear term involved in this constraint, and coefficient[i] is its coefficient. Only the terms with non-zero coefficients need to appear. var_index may not contain duplicates.

• repeated double coefficient = 7

  Must be finite.

• optional double lower_bound = 2

  lower_bound must be <= upper_bound.

• optional double upper_bound = 3

• optional string name = 4

  The name of the constraint.

• optional bool is_lazy = 5

  [Advanced usage: do not use this if you don't know what you're doing.] A lazy constraint is handled differently by the core solving engine, but it does not change the result. It may or may not impact the performance. For more info see: http://tinyurl.com/lazy-constraints.

General constraints. See each individual proto type for more information.

Used in: MPModelProto

• optional string name = 1

  The name of the constraint.

• oneof general_constraint

  • MPIndicatorConstraint indicator_constraint = 2

  • MPSosConstraint sos_constraint = 3

  • MPQuadraticConstraint quadratic_constraint = 4

  • MPAbsConstraint abs_constraint = 5

  • MPArrayConstraint and_constraint = 6

    All variables in "and" constraints must be Boolean. resultant_var = and(var_1, var_2... var_n)

  • MPArrayConstraint or_constraint = 7

    All variables in "or" constraints must be Boolean. resultant_var = or(var_1, var_2... var_n)

  • MPArrayWithConstantConstraint min_constraint = 8

    resultant_var = min(var_1, var_2, ..., constant)

  • MPArrayWithConstantConstraint max_constraint = 9

    resultant_var = max(var_1, var_2, ..., constant)

Indicator constraints encode the activation or deactivation of linear constraints given the value of one Boolean variable in the model. For example: y = 0 => 2 * x1 + 3 * x2 >= 42 The 2 * x1 + 3 * x2 >= 42 constraint is only active if the variable y is equal to 0. As of 2019/04, only SCIP, CP-SAT and Gurobi support this constraint type.

Used in: MPGeneralConstraintProto

• optional int32 var_index = 1

  Variable index (w.r.t. the "variable" field of MPModelProto) of the Boolean variable used as indicator.

• optional int32 var_value = 2

  Value the above variable should take. Must be 0 or 1.

• optional MPConstraintProto constraint = 3

  The constraint activated by the indicator variable.

Encodes a full MPModelProto by way of referencing to a "baseline" MPModelProto stored in a file, and a "delta" to apply to this model.

Used in: MPModelRequest

• optional string baseline_model_file_path = 1

• map<int32, MPVariableProto> variable_overrides = 2

  The variable protos listed here will override (via MergeFrom()) the ones in the baseline model: you only need to specify the fields that change. To add a new variable, add it with a new variable index (variable indices still need to span a dense integer interval). You can't "delete" a variable but you can "neutralize" it by fixing its value, setting its objective coefficient to zero, and by nullifying all the terms involving it in the constraints.

• map<int32, MPConstraintProto> constraint_overrides = 3

  Constraints can be changed (or added) in the same way as variables, see above. It's mostly like applying MergeFrom(), except that: - the "var_index" and "coefficient" fields will be overridden like a map: if a key pre-exists, we overwrite its value, otherwise we add it. - if you set the lower bound to -inf and the upper bound to +inf, thus effectively neutralizing the constraint, the solver will implicitly remove all of the constraint's terms.

MPModelProto contains all the information for a Linear Programming model.

Used in: MPModelRequest

• repeated MPVariableProto variable = 3

  All the variables appearing in the model.

• repeated MPConstraintProto constraint = 4

  All the constraints appearing in the model.

• repeated MPGeneralConstraintProto general_constraint = 7

  All the general constraints appearing in the model. Note that not all solvers support all types of general constraints.

• optional bool maximize = 1

  True if the problem is a maximization problem. Minimize by default.

• optional double objective_offset = 2

  Offset for the objective function. Must be finite.

• optional MPQuadraticObjective quadratic_objective = 8

  Optionally, a quadratic objective. As of 2019/06, only SCIP and Gurobi support quadratic objectives.

• optional string name = 5

  Name of the model.

• optional PartialVariableAssignment solution_hint = 6

  Solution hint. If a feasible or almost-feasible solution to the problem is already known, it may be helpful to pass it to the solver so that it can be used. A solver that supports this feature will try to use this information to create its initial feasible solution. Note that it may not always be faster to give a hint like this to the solver. There is also no guarantee that the solver will use this hint or try to return a solution "close" to this assignment in case of multiple optimal solutions.

• repeated MPModelProto.Annotation annotation = 9

Annotations can be freely added by users who want to attach arbitrary payload to the model's variables or constraints.

Used in: MPModelProto

• optional Annotation.TargetType target_type = 1

• optional int32 target_index = 2

  If both `target_index` and `target_name` are set, they must point to the same entity.

  Index in the MPModelProto.

• optional string target_name = 3

  Alternate to index. Assumes uniqueness.

• optional string payload_key = 4

  The payload is a (key, value) string pair. Depending on the use cases, one of the two may be omitted.

• optional string payload_value = 5

The target of an Annotation is a single entity (e.g. a variable). Several Annotations may apply to the same entity.

Used in: Annotation

• VARIABLE_DEFAULT = 0

• CONSTRAINT = 1

• GENERAL_CONSTRAINT = 2

Next id: 18.

• optional MPModelProto model = 1

  The model to be optimized by the server.

• optional MPModelRequest.SolverType solver_type = 2

• optional double solver_time_limit_seconds = 3

  Maximum time to be spent by the solver to solve 'model'. If the server is busy and the RPC's deadline_left is less than this, it will immediately give up and return an error, without even trying to solve. The client can use this to have a guarantee on how much time the solver will spend on the problem (unless it finds and proves an optimal solution more quickly). If not specified, the time limit on the solver is the RPC's deadline_left.

• optional bool enable_internal_solver_output = 4

  If this is set, then EnableOutput() will be set on the internal MPSolver that solves the model. WARNING: if you set this on a request to prod servers, it will be rejected and yield the RPC Application Error code MPSOLVER_SOLVER_TYPE_UNAVAILABLE.

• optional string solver_specific_parameters = 5

  Advanced usage. Solver-specific parameters in the solver's own format, different for each solver. For example, if you use SCIP and you want to stop the solve earlier than the time limit if it reached a solution that is at most 1% away from the optimal, you can set this to "limits/gap=0.01". Note however that there is no "security" mechanism in place so it is up to the client to make sure that the given options don't make the solve non thread safe or use up too much memory for instance. If the option format is not understood by the solver, the request will be rejected and yield an RPC Application error with code MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS, unless you have set ignore_solver_specific_parameters_failure=true (in which case they are simply ignored).

• optional bool ignore_solver_specific_parameters_failure = 9

• optional MPModelDeltaProto model_delta = 8

  Advanced usage: model "delta". If used, "model" must be unset. See the definition of MPModelDeltaProto.

• optional int32 populate_additional_solutions_up_to = 11

  Controls the recovery of additional solutions, if any, saved by the underlying solver back in the MPSolutionResponse.additional_solutions. The repeated field will be length min(populate_addition_solutions_up_to, #additional_solutions_available_in_underlying_solver) These additional solutions may have a worse objective than the main solution returned in the response.

The solver type, which will select a specific implementation, and will also impact the interpretation of the model (i.e. are we solving the problem as a mixed integer program or are we relaxing it as a continuous linear program?). This must remain consistent with MPSolver::OptimizationProblemType.

Used in: MPModelRequest

• CLP_LINEAR_PROGRAMMING = 0

• GLOP_LINEAR_PROGRAMMING = 2

  Recommended default for LP models.

• GLPK_LINEAR_PROGRAMMING = 1

• GUROBI_LINEAR_PROGRAMMING = 6

  Commercial, needs a valid license.

• XPRESS_LINEAR_PROGRAMMING = 101

  Commercial, needs a valid license. NOLINT

• CPLEX_LINEAR_PROGRAMMING = 10

  Commercial, needs a valid license. NOLINT

• HIGHS_LINEAR_PROGRAMMING = 15

• SCIP_MIXED_INTEGER_PROGRAMMING = 3

  Recommended default for MIP models.

• GLPK_MIXED_INTEGER_PROGRAMMING = 4

• CBC_MIXED_INTEGER_PROGRAMMING = 5

• GUROBI_MIXED_INTEGER_PROGRAMMING = 7

  Commercial, needs a valid license.

• XPRESS_MIXED_INTEGER_PROGRAMMING = 102

  Commercial, needs a valid license. NOLINT

• CPLEX_MIXED_INTEGER_PROGRAMMING = 11

  Commercial, needs a valid license. NOLINT

• HIGHS_MIXED_INTEGER_PROGRAMMING = 16

• BOP_INTEGER_PROGRAMMING = 12

• SAT_INTEGER_PROGRAMMING = 14

  WARNING: This solver will currently interpret all variables as integer, so any solution you get will be valid, but the optimal might be far away for the real one (when you authorise non-integer value for continuous variables).

  Recommended for pure integer problems.

• PDLP_LINEAR_PROGRAMMING = 8

  In-house linear programming solver based on the primal-dual hybrid gradient method. Sometimes faster than Glop for medium-size problems and scales to much larger problems than Glop.

• KNAPSACK_MIXED_INTEGER_PROGRAMMING = 13

Quadratic constraints of the form lb <= sum a_i x_i + sum b_ij x_i x_j <= ub, where a, b, lb and ub are constants, and x are the model's variables. Quadratic matrices that are Positive Semi-Definite, Second-Order Cones or rotated Second-Order Cones are always accepted. Other forms may or may not be accepted depending on the underlying solver used. See https://scip.zib.de/doc/html/cons__quadratic_8h.php and https://www.gurobi.com/documentation/9.0/refman/constraints.html#subsubsection:QuadraticConstraints

Used in: MPGeneralConstraintProto

• repeated int32 var_index = 1

  Sparse representation of linear terms in the quadratic constraint, where term i is var_index[i] * coefficient[i]. `var_index` are variable indices w.r.t the "variable" field in MPModelProto, and should be unique.

• repeated double coefficient = 2

  Must be finite.

• repeated int32 qvar1_index = 3

  Sparse representation of quadratic terms in the quadratic constraint, where term i is qvar1_index[i] * qvar2_index[i] * qcoefficient[i]. `qvar1_index` and `qvar2_index` are variable indices w.r.t the "variable" field in MPModelProto. `qvar1_index`, `qvar2_index` and `coefficients` must have the same size. If the same unordered pair (qvar1_index, qvar2_index) appears several times, the sum of all of the associated coefficients will be applied.

• repeated int32 qvar2_index = 4

• repeated double qcoefficient = 5

  Must be finite.

• optional double lower_bound = 6

  lower_bound must be <= upper_bound.

• optional double upper_bound = 7

Quadratic part of a model's objective. Added with other objectives (such as linear), this creates the model's objective function to be optimized. Note: the linear part of the objective currently needs to be specified in the MPVariableProto.objective_coefficient fields. If you'd rather have a dedicated linear array here, talk to or-core-team@

Used in: MPModelProto

• repeated int32 qvar1_index = 1

  Sparse representation of quadratic terms in the objective function, where term i is qvar1_index[i] * qvar2_index[i] * coefficient[i]. `qvar1_index` and `qvar2_index` are variable indices w.r.t the "variable" field in MPModelProto. `qvar1_index`, `qvar2_index` and `coefficients` must have the same size. If the same unordered pair (qvar1_index, qvar2_index) appears several times, the sum of all of the associated coefficients will be applied.

• repeated int32 qvar2_index = 2

• repeated double coefficient = 3

  Must be finite.

Used in: MPSolutionResponse

• optional double objective_value = 1

• repeated double variable_value = 2

Next id: 12.

• optional MPSolverResponseStatus status = 1

  Result of the optimization.

• optional string status_str = 7

  Human-readable string giving more details about the status. For example, when the status is MPSOLVER_INVALID_MODE, this can hold a description of why the model is invalid. This isn't always filled: don't depend on its value or even its presence.

• optional double objective_value = 2

  Objective value corresponding to the "variable_value" below, taking into account the source "objective_offset" and "objective_coefficient". This is set iff 'status' is OPTIMAL or FEASIBLE.

• optional double best_objective_bound = 5

  This field is only filled for MIP problems. For a minimization problem, this is a lower bound on the optimal objective value. For a maximization problem, it is an upper bound. It is only filled if the status is OPTIMAL or FEASIBLE. In the former case, best_objective_bound should be equal to objective_value (modulo numerical errors).

• repeated double variable_value = 3

  Variable values in the same order as the MPModelProto::variable field. This is a dense representation. These are set iff 'status' is OPTIMAL or FEASIBLE.

• optional MPSolveInfo solve_info = 10

  Contains extra information about the solve, populated if the underlying solver (and its interface) supports it. As of 2021/07/19 this is supported by SCIP and Gurobi proto solves.

• optional bytes solver_specific_info = 11

  Opaque solver-specific information. For the PDLP solver, this is a serialized pdlp::SolveLog proto.

• repeated double dual_value = 4

  [Advanced usage.] Values of the dual variables values in the same order as the MPModelProto::constraint field. This is a dense representation. These are not set if the problem was solved with a MIP solver (even if it is actually a linear program). These are set iff 'status' is OPTIMAL or FEASIBLE.

• repeated double reduced_cost = 6

  [Advanced usage.] Values of the reduced cost of the variables in the same order as the MPModelProto::variable. This is a dense representation. These are not set if the problem was solved with a MIP solver (even if it is actually a linear program). These are set iff 'status' is OPTIMAL or FEASIBLE.

• repeated MPSolution additional_solutions = 8

  [Advanced usage.] If `MPModelRequest.populate_additional_solutions_up_to` > 0, up to that number of additional solutions may be populated here, if available. These additional solutions are different than the main solution described by the above fields `objective_value` and `variable_value`.

Used in: MPSolutionResponse

• optional double solve_wall_time_seconds = 1

  How much wall time (resp. user time) elapsed during the Solve() of the underlying solver library. "wall" time and "user" time are to be interpreted like for the "time" command in bash (see "help time"). In particular, "user time" is CPU time and can be greater than wall time when using several threads.

• optional double solve_user_time_seconds = 2

MPSolverCommonParameters holds advanced usage parameters that apply to any of the solvers we support. All of the fields in this proto can have a value of unspecified. In this case each inner solver will use their own safe defaults. Some values won't be supported by some solvers. The behavior in that case is not defined yet.

• optional OptionalDouble relative_mip_gap = 1

  The solver stops if the relative MIP gap reaches this value or below. The relative MIP gap is an upper bound of the relative distance to the optimum, and it is defined as: abs(best_bound - incumbent) / abs(incumbent) [Gurobi] abs(best_bound - incumbent) / min(abs(best_bound), abs(incumbent)) [SCIP] where "incumbent" is the objective value of the best solution found so far (i.e., lowest when minimizing, highest when maximizing), and "best_bound" is the tightest bound of the objective determined so far (i.e., highest when minimizing, and lowest when maximizing). The MIP Gap is sensitive to objective offset. If the denominator is 0 the MIP Gap is INFINITY for SCIP and Gurobi. Of note, "incumbent" and "best bound" are called "primal bound" and "dual bound" in SCIP, respectively. Ask or-core-team@ for other solvers.

• optional OptionalDouble primal_tolerance = 2

  Tolerance for primal feasibility of basic solutions: this is the maximum allowed error in constraint satisfiability. For SCIP this includes integrality constraints. For Gurobi it does not, you need to set the custom parameter IntFeasTol.

• optional OptionalDouble dual_tolerance = 3

  Tolerance for dual feasibility. For SCIP and Gurobi this is the feasibility tolerance for reduced costs in LP solution: reduced costs must all be smaller than this value in the improving direction in order for a model to be declared optimal. Not supported for other solvers.

• optional MPSolverCommonParameters.LPAlgorithmValues lp_algorithm = 4

  Algorithm to solve linear programs. Ask or-core-team@ if you want to know what this does exactly.

• optional OptionalBoolean presolve = 5

  Gurobi and SCIP enable presolve by default. Ask or-core-team@ for other solvers.

• optional OptionalBoolean scaling = 7

  Enable automatic scaling of matrix coefficients and objective. Available for Gurobi and GLOP. Ask or-core-team@ if you want more details.

Used in: MPSolverCommonParameters

• LP_ALGO_UNSPECIFIED = 0

• LP_ALGO_DUAL = 1

  Dual simplex.

• LP_ALGO_PRIMAL = 2

  Primal simplex.

• LP_ALGO_BARRIER = 3

  Barrier algorithm.

Status returned by the solver. They follow a hierarchical nomenclature, to allow us to add more enum values in the future. Clients should use InCategory() to match these enums, with the following C++ pseudo-code: bool InCategory(MPSolverResponseStatus status, MPSolverResponseStatus cat) { if (cat == MPSOLVER_OPTIMAL) return status == MPSOLVER_OPTIMAL; while (status > cat) status >>= 4; return status == cat; }

Normal responses -- the model was valid, and the solver ran. These statuses should be "somewhat" repeatable, modulo the fact that the solver's time limit makes it undeterministic, and could change a FEASIBLE model to an OPTIMAL and vice-versa (the others, except NOT_SOLVED, should normally be deterministic). Also, the solver libraries can be buggy.

Used in: MPSolutionResponse

• MPSOLVER_OPTIMAL = 0

  The solver found the proven optimal solution. This is what should be returned in most cases. WARNING: for historical reason, the value is zero, which means that this value can't have any subcategories.

• MPSOLVER_FEASIBLE = 1

  The solver had enough time to find some solution that satisfies all constraints, but it did not prove optimality (which means it may or may not have reached the optimal). This can happen for large LP models (Linear Programming), and is a frequent response for time-limited MIPs (Mixed Integer Programming). In the MIP case, the difference between the solution 'objective_value' and 'best_objective_bound' fields of the MPSolutionResponse will give an indication of how far this solution is from the optimal one.

• MPSOLVER_INFEASIBLE = 2

  The model does not have any solution, according to the solver (which "proved" it, with the caveat that numerical proofs aren't actual proofs), or based on trivial considerations (eg. a variable whose lower bound is strictly greater than its upper bound).

• MPSOLVER_UNBOUNDED = 3

  There exist solutions that make the magnitude of the objective value as large as wanted (i.e. -infinity (resp. +infinity) for a minimization (resp. maximization) problem.

• MPSOLVER_ABNORMAL = 4

  An error (most probably numerical) occurred. One likely cause for such errors is a large numerical range among variable coefficients (eg. 1e-16, 1e20), in which case one should try to shrink it.

• MPSOLVER_NOT_SOLVED = 6

  The solver did not have a chance to diagnose the model in one of the categories above.

• MPSOLVER_MODEL_IS_VALID = 97

  Like "NOT_SOLVED", but typically used by model validation functions returning a "model status", to enhance readability of the client code.

• MPSOLVER_CANCELLED_BY_USER = 98

  The solve was interrupted by the user, and the solver didn't have time to return a proper status.

• MPSOLVER_UNKNOWN_STATUS = 99

  Special value: the solver status could not be properly translated and is unknown.

• MPSOLVER_MODEL_INVALID = 5

  Model errors. These are always deterministic and repeatable. They should be accompanied with a string description of the error.

• MPSOLVER_MODEL_INVALID_SOLUTION_HINT = 84

  Something is wrong with the fields "solution_hint_var_index" and/or "solution_hint_var_value".

• MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS = 85

  Something is wrong with the solver_specific_parameters request field.

• MPSOLVER_SOLVER_TYPE_UNAVAILABLE = 7

  Implementation error: the requested solver implementation is not available (see MPModelRequest.solver_type). The linear solver binary was probably not linked with the required library,

• MPSOLVER_INCOMPATIBLE_OPTIONS = 113

  Some of the selected options were incompatible, e.g. a cancellable solve was requested via SolverClient::SolveMipRemotely() with an underlying solver that doesn't support cancellation. status_str should contain a description of the issue.

Special Ordered Set (SOS) constraints of type 1 or 2. See https://en.wikipedia.org/wiki/Special_ordered_set As of 2019/04, only SCIP and Gurobi support this constraint type.

Used in: MPGeneralConstraintProto

• optional MPSosConstraint.Type type = 1

• repeated int32 var_index = 2

  Variable index (w.r.t. the "variable" field of MPModelProto) of the variables in the SOS.

• repeated double weight = 3

  Optional: SOS weights. If non-empty, must be of the same size as "var_index", and strictly increasing. If empty and required by the underlying solver, the 1..n sequence will be given as weights. SUBTLE: The weights can help the solver make branch-and-bound decisions that fit the underlying optimization model: after each LP relaxation, it will compute the "average weight" of the SOS variables, weighted by value (this is confusing: here we're using the values as weights), and the binary branch decision will be: is the non-zero variable above or below that? (weights are strictly monotonous, so the "cutoff" average weight corresponds to a "cutoff" index in the var_index sequence).

Used in: MPSosConstraint

• SOS1_DEFAULT = 0

  At most one variable in `var_index` must be non-zero.

• SOS2 = 1

  At most two consecutive variables from `var_index` can be non-zero (i.e. for some i, var_index[i] and var_index[i+1]). See https://en.wikipedia.org/wiki/Special_ordered_set#Types_of_SOS

A variable is always constrained in the form: lower_bound <= x <= upper_bound where lower_bound and upper_bound: - Can form a singleton: x = constant = lower_bound = upper_bound. - Can form a finite interval: lower_bound <= x <= upper_bound. (x is boxed.) - Can form a semi-infinite interval. - lower_bound = -infinity: x <= upper_bound. - upper_bound = +infinity: x >= lower_bound. - Can form the infinite interval: lower_bound = -infinity and upper_bound = +infinity, x is free. MPVariableProto furthermore stores: - The coefficient of the variable in the objective. - Whether the variable is integer.

Used in: MPModelDeltaProto, MPModelProto

• optional double lower_bound = 1

  lower_bound must be <= upper_bound.

• optional double upper_bound = 2

• optional double objective_coefficient = 3

  The coefficient of the variable in the objective. Must be finite.

• optional bool is_integer = 4

  True if the variable is constrained to be integer. Ignored if MPModelProto::solver_type is *LINEAR_PROGRAMMING*.

• optional string name = 5

  The name of the variable.

• optional int32 branching_priority = 6

Acceptance strategy in which a solution is accepted only if it performs at least one more node than the reference solution.

Used in: AcceptanceStrategy

(message has no fields)

A "three-way" boolean: unspecified, false or true. We don't use the value of 1 to increase the chance to catch bugs: eg. in python, a user may set a proto field of this type enum to a boolean value without type checks, if they set it to True, the proto validity code will catch it (because it'll be cast to 1, which is an invalid enum value). Note that if the user sets if to False (i.e. 0), it will be caught by the routing library's parameter validity check too.

Used in: MPSolverCommonParameters, RoutingSearchParameters, RoutingSearchParameters.LocalSearchNeighborhoodOperators

• BOOL_UNSPECIFIED = 0

• BOOL_FALSE = 2

• BOOL_TRUE = 3

To support 'unspecified' double value in proto3, the simplest is to wrap any double value in a nested message (has_XXX works for message fields).

Used in: MPSolverCommonParameters

• optional double value = 1

This message encodes a partial (or full) assignment of the variables of a MPModelProto problem. The indices in var_index should be unique and valid variable indices of the associated problem.

Used in: MPModelProto

• repeated int32 var_index = 1

• repeated double var_value = 2

Defines how a reference solution is perturbed.

(message has no fields)

Used in: IteratedLocalSearchParameters

• UNSET = 0

  Unspecified value.

• RUIN_AND_RECREATE = 1

  Performs a perturbation in a ruin and recreate fashion.

Ruin strategy that removes a number of nodes by performing a random walk on the underlying routing solution. More precisely, starting from a randomly selected seed visit, the walk is extended by either moving within the same route or by jumping to a visit served by a different neighboring route. Every active visit encountered along this random walk is made unperformed.

Used in: RuinStrategy

• optional uint32 num_removed_visits = 7

  Number of visits removed during a ruin application defined on visits. Note that pickup and delivery pairs are considered as a single entity, i.e., the removal of a pickup (respectively delivery) causes the removal of the associated delivery (respectively pickup) and it counts as a single removal.

Parameters to customize a recreate strategy.

Used in: RecreateStrategy

• oneof parameters

  • LocalCheapestInsertionParameters local_cheapest_insertion = 1

  • SavingsParameters savings = 2

  • GlobalCheapestInsertionParameters global_cheapest_insertion = 3

Strategy defining how a solution is recreated.

Used in: RuinRecreateParameters

• optional FirstSolutionStrategy.Value heuristic = 1

• optional RecreateParameters parameters = 2

  The selected parameters should match the chosen recreate heuristic. If not set, the default parameters from the RoutingModel are used.

A search limit The default values for int64 fields is the maxima value, i.e., 2^63-1

• int64 time = 1

  TODO(user): Specify the time units or switch to google.Duration proto.

• int64 branches = 2

• int64 failures = 3

• int64 solutions = 4

• bool smart_time_check = 5

• bool cumulative = 6

Used in: CourseSchedulingModel

• string display_name = 1

  Room name, used only for logging purposes.

• int32 capacity = 2

  Maximum number of students that can fit into this room.

Parameters which have to be set when creating a RoutingModel.

• optional ConstraintSolverParameters solver_parameters = 1

  Parameters to use in the underlying constraint solver.

• bool reduce_vehicle_cost_model = 2

  Advanced settings. If set to true reduction of the underlying constraint model will be attempted when all vehicles have exactly the same cost structure. This can result in significant speedups.

• int32 max_callback_cache_size = 3

  Cache callback calls if the number of nodes in the model is less or equal to this value.

Parameters defining the search used to solve vehicle routing problems. If a parameter is unset (or, equivalently, set to its default value), then the routing library will pick its preferred value for that parameter automatically: this should be the case for most parameters. To see those "default" parameters, call GetDefaultRoutingSearchParameters(). Next ID: 73

• FirstSolutionStrategy.Value first_solution_strategy = 1

  First solution strategies, used as starting point of local search.

• bool use_unfiltered_first_solution_strategy = 2

  --- Advanced first solutions strategy settings --- Don't touch these unless you know what you are doing. Use filtered version of first solution strategy if available.

• optional SavingsParameters savings_parameters = 70

  Parameters for the Savings heuristic.

• optional GlobalCheapestInsertionParameters global_cheapest_insertion_first_solution_parameters = 71

  Parameters for the global cheapest insertion heuristic when used as first solution heuristic.

• optional GlobalCheapestInsertionParameters global_cheapest_insertion_ls_operator_parameters = 72

  Parameters for the global cheapest insertion heuristic when used in a local search operator (see local_search_operators.use_global_cheapest_insertion_path_lns and local_search_operators.use_global_cheapest_insertion_chain_lns below).

• optional LocalCheapestInsertionParameters local_cheapest_insertion_parameters = 68

  Parameters for the local cheapest insertion heuristic.

• optional LocalCheapestInsertionParameters local_cheapest_cost_insertion_parameters = 69

  Parameters for the local cheapest cost insertion heuristic.

• bool christofides_use_minimum_matching = 30

  If true use minimum matching instead of minimal matching in the Christofides algorithm.

• int32 first_solution_optimization_period = 59

  If non zero, a period p indicates that every p node insertions or additions to a path, an optimization of the current partial solution will be performed. As of 12/2023: - this requires that a secondary routing model has been passed to the main one, - this is only supported by LOCAL_CHEAPEST_INSERTION and LOCAL_CHEAPEST_COST_INSERTION.

• optional RoutingSearchParameters.LocalSearchNeighborhoodOperators local_search_operators = 3

• double ls_operator_neighbors_ratio = 53

  Neighbors ratio and minimum number of neighbors considered in local search operators (see GlobalCheapestInsertionParameters.neighbors_ratio and GlobalCheapestInsertionParameters.min_neighbors for more information).

• int32 ls_operator_min_neighbors = 54

• bool use_multi_armed_bandit_concatenate_operators = 41

  If true, the solver will use multi-armed bandit concatenate operators. It dynamically chooses the next neighbor operator in order to get the best objective improvement.

• double multi_armed_bandit_compound_operator_memory_coefficient = 42

  Memory coefficient related to the multi-armed bandit compound operator. Sets how much the objective improvement of previous accepted neighbors influence the current average improvement. This parameter should be between 0 and 1.

• double multi_armed_bandit_compound_operator_exploration_coefficient = 43

  Positive parameter defining the exploration coefficient of the multi-armed bandit compound operator. Sets how often we explore rarely used and unsuccessful in the past operators

• int32 max_swap_active_chain_size = 66

  Maximum size of the chain to make inactive in SwapActiveChainOperator.

• int32 relocate_expensive_chain_num_arcs_to_consider = 20

  Number of expensive arcs to consider cutting in the RelocateExpensiveChain neighborhood operator (see LocalSearchNeighborhoodOperators.use_relocate_expensive_chain()). This parameter must be greater than 2. NOTE(user): The number of neighbors generated by the operator for relocate_expensive_chain_num_arcs_to_consider = K is around K*(K-1)/2 * number_of_routes * number_of_nodes.

• int32 heuristic_expensive_chain_lns_num_arcs_to_consider = 32

  Number of expensive arcs to consider cutting in the FilteredHeuristicExpensiveChainLNSOperator operator.

• int32 heuristic_close_nodes_lns_num_nodes = 35

  Number of closest nodes to consider for each node during the destruction phase of the FilteredHeuristicCloseNodesLNSOperator.

• LocalSearchMetaheuristic.Value local_search_metaheuristic = 4

  Local search metaheuristics used to guide the search.

• repeated LocalSearchMetaheuristic.Value local_search_metaheuristics = 63

  Local search metaheuristics alternatively used to guide the search. Every num_max_local_optima_before_metaheuristic_switch local minima found by a metaheurisitic, the solver will switch to the next metaheuristic. Cannot be defined if local_search_metaheuristic is different from UNSET or AUTOMATIC.

• int32 num_max_local_optima_before_metaheuristic_switch = 64

• double guided_local_search_lambda_coefficient = 5

  These are advanced settings which should not be modified unless you know what you are doing. Lambda coefficient used to penalize arc costs when GUIDED_LOCAL_SEARCH is used. Must be positive.

• bool guided_local_search_reset_penalties_on_new_best_solution = 51

  Whether to reset penalties when a new best solution is found. The effect is that a greedy descent is started before the next penalization phase.

• bool guided_local_search_penalize_with_vehicle_classes = 61

  When an arc leaving a vehicle start or arriving at a vehicle end is penalized, this field controls whether to penalize all other equivalent arcs with starts or ends in the same vehicle class.

• bool use_guided_local_search_penalties_in_local_search_operators = 62

  Whether to consider arc penalties in cost functions used in local search operators using arc costs.

• bool use_depth_first_search = 6

  --- Search control --- If true, the solver should use depth-first search rather than local search to solve the problem.

• OptionalBoolean use_cp = 28

  If true, use the CP solver to find a solution. Either local or depth-first search will be used depending on the value of use_depth_first_search. Will be run before the CP-SAT solver (cf. use_cp_sat).

• OptionalBoolean use_cp_sat = 27

  If true, use the CP-SAT solver to find a solution. If use_cp is also true, the CP-SAT solver will be run after the CP solver if there is time remaining and will use the CP solution as a hint for the CP-SAT search. As of 5/2019, only TSP models can be solved.

• OptionalBoolean use_generalized_cp_sat = 47

  If true, use the CP-SAT solver to find a solution on generalized routing model. If use_cp is also true, the CP-SAT solver will be run after the CP solver if there is time remaining and will use the CP solution as a hint for the CP-SAT search.

• optional sat.SatParameters sat_parameters = 48

  If use_cp_sat or use_generalized_cp_sat is true, contains the SAT algorithm parameters which will be used.

• bool report_intermediate_cp_sat_solutions = 56

  If use_cp_sat or use_generalized_cp_sat is true, will report intermediate solutions found by CP-SAT to solution listeners.

• int32 fallback_to_cp_sat_size_threshold = 52

  If model.Size() is less than the threshold and that no solution has been found, attempt a pass with CP-SAT.

• RoutingSearchParameters.SchedulingSolver continuous_scheduling_solver = 33

• RoutingSearchParameters.SchedulingSolver mixed_integer_scheduling_solver = 34

• optional bool disable_scheduling_beware_this_may_degrade_performance = 50

  Setting this to true completely disables the LP and MIP scheduling in the solver. This overrides the 2 SchedulingSolver options above.

• double optimization_step = 7

  Minimum step by which the solution must be improved in local search. 0 means "unspecified". If this value is fractional, it will get rounded to the nearest integer.

• int32 number_of_solutions_to_collect = 17

  Number of solutions to collect during the search. Corresponds to the best solutions found during the search. 0 means "unspecified".

• int64 solution_limit = 8

  -- Search limits -- Limit to the number of solutions generated during the search. 0 means "unspecified".

• optional google.protobuf.Duration time_limit = 9

  Limit to the time spent in the search.

• optional google.protobuf.Duration lns_time_limit = 10

  Limit to the time spent in the completion search for each local search neighbor.

• double secondary_ls_time_limit_ratio = 57

  Ratio of the overall time limit spent in a secondary LS phase with only intra-route and insertion operators, meant to "cleanup" the current solution before stopping the search. TODO(user): Since these operators are very fast, add a parameter to cap the max time allocated for this second phase (e.g. Duration max_secondary_ls_time_limit).

• optional RoutingSearchParameters.ImprovementSearchLimitParameters improvement_limit_parameters = 37

  The improvement search limit is added to the solver if the following parameters are set.

• bool use_full_propagation = 11

  --- Propagation control --- These are advanced settings which should not be modified unless you know what you are doing. Use constraints with full propagation in routing model (instead of 'light' propagation only). Full propagation is only necessary when using depth-first search or for models which require strong propagation to finalize the value of secondary variables. Changing this setting to true will slow down the search in most cases and increase memory consumption in all cases.

• bool log_search = 13

  --- Miscellaneous --- Some of these are advanced settings which should not be modified unless you know what you are doing. Activates search logging. For each solution found during the search, the following will be displayed: its objective value, the maximum objective value since the beginning of the search, the elapsed time since the beginning of the search, the number of branches explored in the search tree, the number of failures in the search tree, the depth of the search tree, the number of local search neighbors explored, the number of local search neighbors filtered by local search filters, the number of local search neighbors accepted, the total memory used and the percentage of the search done.

• double log_cost_scaling_factor = 22

  In logs, cost values will be scaled and offset by the given values in the following way: log_cost_scaling_factor * (cost + log_cost_offset)

• double log_cost_offset = 29

• string log_tag = 36

  In logs, this tag will be appended to each line corresponding to a new solution. Useful to sort out logs when several solves are run in parallel.

• bool use_iterated_local_search = 58

  Whether the solver should use an Iterated Local Search approach to solve the problem.

• optional IteratedLocalSearchParameters iterated_local_search_parameters = 60

  Iterated Local Search parameters.

Parameters required for the improvement search limit.

Used in: RoutingSearchParameters

• double improvement_rate_coefficient = 38

  Parameter that regulates exchange rate between objective improvement and number of neighbors spent. The smaller the value, the sooner the limit stops the search. Must be positive.

• int32 improvement_rate_solutions_distance = 39

  Parameter that specifies the distance between improvements taken into consideration for calculating the improvement rate. Example: For 5 objective improvements = (10, 8, 6, 4, 2), and the solutions_distance parameter of 2, then the improvement_rate will be computed for (10, 6), (8, 4), and (6, 2).

Local search neighborhood operators used to build a solutions neighborhood. Next ID: 41

Used in: RoutingSearchParameters

• OptionalBoolean use_relocate = 1

  --- Inter-route operators --- Operator which moves a single node to another position. Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 (where (1, 5) are first and last nodes of the path and can therefore not be moved): 1 -> 3 -> [2] -> 4 -> 5 1 -> 3 -> 4 -> [2] -> 5 1 -> 2 -> 4 -> [3] -> 5 1 -> [4] -> 2 -> 3 -> 5

• OptionalBoolean use_relocate_pair = 2

  Operator which moves a pair of pickup and delivery nodes to another position where the first node of the pair must be before the second node on the same path. Compared to the light_relocate_pair operator, tries all possible positions of insertion of a pair (not only after another pair). Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are first and last nodes of the path and can therefore not be moved, and (A, B) is a pair of nodes): 1 -> [A] -> 2 -> [B] -> 3 1 -> 2 -> [A] -> [B] -> 3

• OptionalBoolean use_light_relocate_pair = 24

  Operator which moves a pair of pickup and delivery nodes after another pair. Possible neighbors for paths 1 -> A -> B -> 2, 3 -> C -> D -> 4 (where (1, 2) and (3, 4) are first and last nodes of paths and can therefore not be moved, and (A, B) and (C, D) are pair of nodes): 1 -> 2, 3 -> C -> [A] -> D -> [B] -> 4 1 -> A -> [C] -> B -> [D] -> 2, 3 -> 4

• OptionalBoolean use_relocate_neighbors = 3

  Relocate neighborhood which moves chains of neighbors. The operator starts by relocating a node n after a node m, then continues moving nodes which were after n as long as the "cost" added is less than the "cost" of the arc (m, n). If the new chain doesn't respect the domain of next variables, it will try reordering the nodes until it finds a valid path. Possible neighbors for path 1 -> A -> B -> C -> D -> E -> 2 (where (1, 2) are first and last nodes of the path and can therefore not be moved, A must be performed before B, and A, D and E are located at the same place): 1 -> A -> C -> [B] -> D -> E -> 2 1 -> A -> C -> D -> [B] -> E -> 2 1 -> A -> C -> D -> E -> [B] -> 2 1 -> A -> B -> D -> [C] -> E -> 2 1 -> A -> B -> D -> E -> [C] -> 2 1 -> A -> [D] -> [E] -> B -> C -> 2 1 -> A -> B -> [D] -> [E] -> C -> 2 1 -> A -> [E] -> B -> C -> D -> 2 1 -> A -> B -> [E] -> C -> D -> 2 1 -> A -> B -> C -> [E] -> D -> 2 This operator is extremely useful to move chains of nodes which are located at the same place (for instance nodes part of a same stop).

• OptionalBoolean use_relocate_subtrip = 25

  Relocate neighborhood that moves subpaths all pickup and delivery pairs have both pickup and delivery inside the subpath or both outside the subpath. For instance, for given paths: 0 -> A -> B -> A' -> B' -> 5 -> 6 -> 8 7 -> 9 Pairs (A,A') and (B,B') are interleaved, so the expected neighbors are: 0 -> 5 -> A -> B -> A' -> B' -> 6 -> 8 7 -> 9 0 -> 5 -> 6 -> A -> B -> A' -> B' -> 8 7 -> 9 0 -> 5 -> 6 -> 8 7 -> A -> B -> A' -> B' -> 9

• OptionalBoolean use_exchange = 4

  Operator which exchanges the positions of two nodes. Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 (where (1, 5) are first and last nodes of the path and can therefore not be moved): 1 -> [3] -> [2] -> 4 -> 5 1 -> [4] -> 3 -> [2] -> 5 1 -> 2 -> [4] -> [3] -> 5

• OptionalBoolean use_exchange_pair = 22

  Operator which exchanges the positions of two pair of nodes. Pairs correspond to the pickup and delivery pairs defined in the routing model. Possible neighbor for the paths 1 -> A -> B -> 2 -> 3 and 4 -> C -> D -> 5 (where (1, 3) and (4, 5) are first and last nodes of the paths and can therefore not be moved, and (A, B) and (C,D) are pairs of nodes): 1 -> [C] -> [D] -> 2 -> 3, 4 -> [A] -> [B] -> 5

• OptionalBoolean use_exchange_subtrip = 26

  Operator which exchanges subtrips associated to two pairs of nodes, see use_relocate_subtrip for a definition of subtrips.

• OptionalBoolean use_cross = 5

  Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths. First and last nodes are not moved. Possible neighbors for the paths 1 -> 2 -> 3 -> 4 -> 5 and 6 -> 7 -> 8 (where (1, 5) and (6, 8) are first and last nodes of the paths and can therefore not be moved): 1 -> [7] -> 3 -> 4 -> 5 6 -> [2] -> 8 1 -> [7] -> 4 -> 5 6 -> [2 -> 3] -> 8 1 -> [7] -> 5 6 -> [2 -> 3 -> 4] -> 8

• OptionalBoolean use_cross_exchange = 6

  Not implemented yet. TODO(b/68128619): Implement.

• OptionalBoolean use_relocate_expensive_chain = 23

  Operator which detects the relocate_expensive_chain_num_arcs_to_consider most expensive arcs on a path, and moves the chain resulting from cutting pairs of arcs among these to another position. Possible neighbors for paths 1 -> 2 (empty) and 3 -> A ------> B --> C -----> D -> 4 (where A -> B and C -> D are the 2 most expensive arcs, and the chain resulting from breaking them is B -> C): 1 -> [B -> C] -> 2 3 -> A -> D -> 4 1 -> 2 3 -> [B -> C] -> A -> D -> 4 1 -> 2 3 -> A -> D -> [B -> C] -> 4

• OptionalBoolean use_two_opt = 7

  --- Intra-route operators --- Operator which reverses a subchain of a path. It is called TwoOpt because it breaks two arcs on the path; resulting paths are called two-optimal. Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 (where (1, 5) are first and last nodes of the path and can therefore not be moved): 1 -> [3 -> 2] -> 4 -> 5 1 -> [4 -> 3 -> 2] -> 5 1 -> 2 -> [4 -> 3] -> 5

• OptionalBoolean use_or_opt = 8

  Operator which moves sub-chains of a path of length 1, 2 and 3 to another position in the same path. When the length of the sub-chain is 1, the operator simply moves a node to another position. Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a sub-chain length of 2 (where (1, 5) are first and last nodes of the path and can therefore not be moved): 1 -> 4 -> [2 -> 3] -> 5 1 -> [3 -> 4] -> 2 -> 5 The OR_OPT operator is a limited version of 3-Opt (breaks 3 arcs on a path).

• OptionalBoolean use_lin_kernighan = 9

  Lin-Kernighan operator. While the accumulated local gain is positive, performs a 2-OPT or a 3-OPT move followed by a series of 2-OPT moves. Returns a neighbor for which the global gain is positive.

• OptionalBoolean use_tsp_opt = 10

  Sliding TSP operator. Uses an exact dynamic programming algorithm to solve the TSP corresponding to path sub-chains. For a subchain 1 -> 2 -> 3 -> 4 -> 5 -> 6, solves the TSP on nodes A, 2, 3, 4, 5, where A is a merger of nodes 1 and 6 such that cost(A,i) = cost(1,i) and cost(i,A) = cost(i,6).

• OptionalBoolean use_make_active = 11

  --- Operators on inactive nodes --- Operator which inserts an inactive node into a path. Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and 4 are first and last nodes of the path) are: 1 -> [5] -> 2 -> 3 -> 4 1 -> 2 -> [5] -> 3 -> 4 1 -> 2 -> 3 -> [5] -> 4

• OptionalBoolean use_relocate_and_make_active = 21

  Operator which relocates a node while making an inactive one active. As of 3/2017, the operator is limited to two kinds of moves: - Relocating a node and replacing it by an inactive node. Possible neighbor for path 1 -> 5, 2 -> 3 -> 6 and 4 inactive (where 1,2 and 5,6 are first and last nodes of paths) is: 1 -> 3 -> 5, 2 -> 4 -> 6. - Relocating a node and inserting an inactive node next to it. Possible neighbor for path 1 -> 5, 2 -> 3 -> 6 and 4 inactive (where 1,2 and 5,6 are first and last nodes of paths) is: 1 -> 4 -> 3 -> 5, 2 -> 6.

• OptionalBoolean use_exchange_and_make_active = 37

  Operator which exchanges two nodes and inserts an inactive node. Possible neighbors for paths 0 -> 2 -> 4, 1 -> 3 -> 6 and 5 inactive are: 0 -> 3 -> 4, 1 -> 5 -> 2 -> 6 0 -> 3 -> 5 -> 4, 1 -> 2 -> 6 0 -> 5 -> 3 -> 4, 1 -> 2 -> 6 0 -> 3 -> 4, 1 -> 2 -> 5 -> 6

• OptionalBoolean use_exchange_path_start_ends_and_make_active = 38

  Operator which exchanges the first and last nodes of two paths and makes a node active. Possible neighbors for paths 0 -> 1 -> 2 -> 7, 6 -> 3 -> 4 -> 8 and 5 inactive are: 0 -> 5 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 8 0 -> 3 -> 4 -> 7, 6 -> 1 -> 5 -> 2 -> 8 0 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 5 -> 8 0 -> 3 -> 5 -> 4 -> 7, 6 -> 1 -> 2 -> 8 0 -> 3 -> 4 -> 5 -> 7, 6 -> 1 -> 2 -> 8

• OptionalBoolean use_make_inactive = 12

  Operator which makes path nodes inactive. Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first and last nodes of the path) are: 1 -> 3 -> 4 with 2 inactive 1 -> 2 -> 4 with 3 inactive

• OptionalBoolean use_make_chain_inactive = 13

  Operator which makes a "chain" of path nodes inactive. Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first and last nodes of the path) are: 1 -> 3 -> 4 with 2 inactive 1 -> 2 -> 4 with 3 inactive 1 -> 4 with 2 and 3 inactive

• OptionalBoolean use_swap_active = 14

  Operator which replaces an active node by an inactive one. Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and 4 are first and last nodes of the path) are: 1 -> [5] -> 3 -> 4 with 2 inactive 1 -> 2 -> [5] -> 4 with 3 inactive

• OptionalBoolean use_swap_active_chain = 35

  Operator which replaces a chain of active nodes by an inactive one. Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and 4 are first and last nodes of the path) are: 1 -> [5] -> 3 -> 4 with 2 inactive 1 -> 2 -> [5] -> 4 with 3 inactive 1 -> [5] -> 4 with 2 and 3 inactive

• OptionalBoolean use_extended_swap_active = 15

  Operator which makes an inactive node active and an active one inactive. It is similar to SwapActiveOperator excepts that it tries to insert the inactive node in all possible positions instead of just the position of the node made inactive. Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and 4 are first and last nodes of the path) are: 1 -> [5] -> 3 -> 4 with 2 inactive 1 -> 3 -> [5] -> 4 with 2 inactive 1 -> [5] -> 2 -> 4 with 3 inactive 1 -> 2 -> [5] -> 4 with 3 inactive

• OptionalBoolean use_shortest_path_swap_active = 34

  Swaps active nodes from node alternatives in sequence. Considers chains of nodes with alternatives, builds a DAG from the chain, each "layer" of the DAG being composed of the set of alternatives of the node at a given rank in the chain, fully connected to the next layer. A neighbor is built from the shortest path starting from the node before the chain (source), through the DAG to the node following the chain.

• OptionalBoolean use_shortest_path_two_opt = 36

  Similar to use_two_opt but returns the shortest path on the DAG of node alternatives of the reversed chain (cf. use_shortest_path_swap_active).

• OptionalBoolean use_node_pair_swap_active = 20

  Operator which makes an inactive node active and an active pair of nodes inactive OR makes an inactive pair of nodes active and an active node inactive. Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and 4 are first and last nodes of the path and (2,3) is a pair of nodes) are: 1 -> [5] -> 4 with (2,3) inactive Possible neighbors for the path 1 -> 2 -> 3 with (4,5) inactive (where 1 and 3 are first and last nodes of the path and (4,5) is a pair of nodes) are: 1 -> [4] -> [5] -> 3 with 2 inactive

• OptionalBoolean use_path_lns = 16

  --- Large neighborhood search operators --- Operator which relaxes two sub-chains of three consecutive arcs each. Each sub-chain is defined by a start node and the next three arcs. Those six arcs are relaxed to build a new neighbor. PATH_LNS explores all possible pairs of starting nodes and so defines n^2 neighbors, n being the number of nodes. Note that the two sub-chains can be part of the same path; they even may overlap.

• OptionalBoolean use_full_path_lns = 17

  Operator which relaxes one entire path and all inactive nodes.

• OptionalBoolean use_tsp_lns = 18

  TSP-base LNS. Randomly merges consecutive nodes until n "meta"-nodes remain and solves the corresponding TSP. This defines an "unlimited" neighborhood which must be stopped by search limits. To force diversification, the operator iteratively forces each node to serve as base of a meta-node.

• OptionalBoolean use_inactive_lns = 19

  Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs. That way the path can be improved by inserting inactive nodes or swapping arcs.

• OptionalBoolean use_global_cheapest_insertion_path_lns = 27

  --- LNS-like large neighborhood search operators using heuristics --- Operator which makes all nodes on a route unperformed, and reinserts them using the GlobalCheapestInsertion heuristic.

• OptionalBoolean use_local_cheapest_insertion_path_lns = 28

  Same as above but using LocalCheapestInsertion as a heuristic.

• OptionalBoolean use_relocate_path_global_cheapest_insertion_insert_unperformed = 33

  The following operator relocates an entire route to an empty path and then tries to insert the unperformed nodes using the global cheapest insertion heuristic.

• OptionalBoolean use_global_cheapest_insertion_expensive_chain_lns = 29

  This operator finds heuristic_expensive_chain_lns_num_arcs_to_consider most expensive arcs on a route, makes the nodes in between pairs of these expensive arcs unperformed, and reinserts them using the GlobalCheapestInsertion heuristic.

• OptionalBoolean use_local_cheapest_insertion_expensive_chain_lns = 30

  Same as above but using LocalCheapestInsertion as a heuristic for insertion.

• OptionalBoolean use_global_cheapest_insertion_close_nodes_lns = 31

  The following operator makes a node and its heuristic_close_nodes_lns_num_nodes closest neighbors unperformed along with each of their corresponding performed pickup/delivery pairs, and then reinserts them using the GlobalCheapestInsertion heuristic.

• OptionalBoolean use_local_cheapest_insertion_close_nodes_lns = 32

  Same as above, but insertion positions for nodes are determined by the LocalCheapestInsertion heuristic.

• OptionalBoolean use_global_cheapest_insertion_visit_types_lns = 39

  The following operator removes all nodes of a visit type connected component from their current route and reinserts them to an empty route using the GlobalCheapestInsertion heuristic.

• OptionalBoolean use_local_cheapest_insertion_visit_types_lns = 40

  Same as above, but insertion positions for nodes are determined by the LocalCheapestInsertion heuristic.

Underlying solver to use in dimension scheduling, respectively for continuous and mixed models.

Used in: RoutingSearchParameters

• SCHEDULING_UNSET = 0

• SCHEDULING_GLOP = 1

• SCHEDULING_CP_SAT = 2

Used by `RoutingModel` to report the status of the search for a solution.

(message has no fields)

• ROUTING_NOT_SOLVED = 0

  Problem not solved yet (before calling RoutingModel::Solve()).

• ROUTING_SUCCESS = 1

  Problem solved successfully after calling RoutingModel::Solve().

• ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED = 2

  Problem solved successfully after calling RoutingModel::Solve(), except that a local optimum has not been reached. Leaving more time would allow improving the solution.

• ROUTING_FAIL = 3

  No solution found to the problem after calling RoutingModel::Solve().

• ROUTING_FAIL_TIMEOUT = 4

  Time limit reached before finding a solution with RoutingModel::Solve().

• ROUTING_INVALID = 5

  Model, model parameters or flags are not valid.

• ROUTING_INFEASIBLE = 6

  Problem proven to be infeasible.

• ROUTING_OPTIMAL = 7

  Problem has been solved to optimality.

The ruin composition strategies specifies how ruin are selected at every ILS iteration.

(message has no fields)

Used in: RuinRecreateParameters

• UNSET = 0

  Unspecified value.

• RUN_ALL_SEQUENTIALLY = 1

  Execute all ruin strategies sequentially in the same order provided in input.

• RUN_ALL_RANDOMLY = 2

  Execute all ruin strategies in a random order.

• RUN_ONE_RANDOMLY = 3

  Execute a randomly selected ruin.

Parameters to configure a perturbation based on a ruin and recreate approach.

Used in: IteratedLocalSearchParameters

• repeated RuinStrategy ruin_strategies = 1

  List of ruin strategies determining how a reference solution is ruined.

• RuinCompositionStrategy.Value ruin_composition_strategy = 2

  The composition strategy to use when combining the given 'ruin_strategies'. Has no effect when ruin_strategies is composed of a single strategy.

• optional RecreateStrategy recreate_strategy = 3

  Strategy defining how a reference solution is recreated.

• optional double route_selection_neighbors_ratio = 4

  Ratio in [0, 1] of non start/end nodes to consider as neighbors for the identification of routes spatially close to a non start/end seed node. In particular, given a non start/end seed node s served by route r, we say that a route r' is spatially close to the seed node s if there is at least one non start/end node s' among the neighbors of s, such that s' is served by r'. The neighbors_ratio is coupled with the corresponding min_neighbors and max_neighbors values, defining the minimum and maximum number of neighbor nodes considered for a given seed node: num_neighbors = min(max_neighbors, max(min_neighbors, neighbors_ratio * NUM_NON_START_END_NODES)) Neighbors ratio, and minimum and maximum number of non start/end neighbor nodes for the identification of spatially close routes.

• optional uint32 route_selection_min_neighbors = 5

• optional uint32 route_selection_max_neighbors = 6

Ruin strategies, used in perturbation based on ruin and recreate approaches.

Used in: RuinRecreateParameters

• oneof strategy

  • SpatiallyCloseRoutesRuinStrategy spatially_close_routes = 1

  • RandomWalkRuinStrategy random_walk = 2

  • SISRRuinStrategy sisr = 3

Ruin strategy based on the "Slack Induction by String Removals for Vehicle Routing Problems" by Jan Christiaens and Greet Vanden Berghe, Transportation Science 2020. Note that, in this implementation, the notion of "string" is replaced by "sequence". The main idea of this ruin is to remove a number of geographically close sequences of nodes. In particular, at every ruin application, a maximum number max_ruined_routes of routes are disrupted. The value for max_ruined_routes is defined as (4 * avg_num_removed_visits) / (1 + max_sequence_size) + 1 with - avg_num_removed_visits: user-defined parameter ruling the average number of visits that are removed in face of several ruin applications (see also the proto message below) - max_sequence_size is defined as min{max_removed_sequence_size, average_route_size} with - max_removed_sequence_size: user-defined parameter that specifies the maximum number of visits removed from a single route (see also the proto message below) - average_route_size: the average size of a non-empty route in the current solution The actual number of ruined routes is then obtained as floor(U(1, max_ruined_routes + 1)) where U is a continuous uniform distribution of real values in the given interval. The routes affected by the ruin procedure are selected as follows. First, a non start/end seed node is randomly selected. The route serving this node is the first ruined route. Then, until the required number of routes has been ruined, neighbor nodes of the initial seed node are scanned and the associated not yet ruined routes are disrupted. Nodes defining the selected routes are designated as seed nodes for the "sequence" and "split sequence" removal procedures described below. For every selected route, a maximum number route_max_sequence_size of nodes are removed. In particular, route_max_sequence_size is defined as min{route_size, max_sequence_size} with route_size being the size of the current route. Then, the actual number of removed nodes num_removed_nodes is defined as floor(U(1, route_max_sequence_size + 1)) where U is a continuous uniform distribution of real values in the given interval. As mentioned above, the selected num_removed_nodes number of nodes is removed either via the "sequence" removal or "split sequence" removal procedures. The two removal procedures are executed with equal probabilities. The "sequence" removal procedure removes a randomly selected sequence of size num_removed_nodes that includes the seed node. The "split sequence" removal procedure also removes a randomly selected sequence of size num_removed_nodes that includes the seed node, but it can possibly preserve a subsequence of contiguous nodes. In particular, the procedure first selects a sequence of size num_removed_nodes + num_bypassed, then num_bypassed contiguous nodes in the selected sequence are preserved while the others removed. The definition of num_bypassed is as follows. First num_bypassed = 1. The current value of num_bypassed is maintaned if U(0, 1) < bypass_factor * U(0, 1) or the maximum value for num_bypassed, equal to route_size - num_removed_nodes is reached. The value is incremented of a unit otherwise, and the process is repeated. The value assigned to bypass_factor affects the number of preserved visits (see also the proto message below).

Used in: RuinStrategy

• optional uint32 max_removed_sequence_size = 1

  Maximum number of removed visits per sequence. The parameter name in the paper is L^{max} and the suggested value is 10.

• optional uint32 avg_num_removed_visits = 2

  Number of visits that are removed on average. The parameter name in the paper is \bar{c} and the suggested value is 10.

• optional double bypass_factor = 3

  Value in [0, 1] ruling the number of preserved nodes in the split sequence removal. The parameter name in the paper is \alpha and the suggested value is 0.01.

Parameters used to configure savings heuristics.

Used in: RecreateParameters, RoutingSearchParameters

• double neighbors_ratio = 1

  Ratio (in ]0, 1]) of neighbors to consider for each node when constructing the savings. If unspecified, its value is considered to be 1.0.

• double max_memory_usage_bytes = 2

  The number of neighbors considered for each node in the Savings heuristic is chosen so that the space used to store the savings doesn't exceed max_memory_usage_bytes, which must be in ]0, 1e10]. NOTE: If both neighbors_ratio and max_memory_usage_bytes are specified, the number of neighbors considered for each node will be the minimum of the two numbers determined by these parameters.

• bool add_reverse_arcs = 3

  Add savings related to reverse arcs when finding the nearest neighbors of the nodes.

• double arc_coefficient = 4

  Coefficient of the cost of the arc for which the saving value is being computed: Saving(a-->b) = Cost(a-->end) + Cost(start-->b) - arc_coefficient * Cost(a-->b) This parameter must be greater than 0, and its default value is 1.

Search statistics.

• repeated LocalSearchStatistics local_search_statistics = 1

  Local search statistics for each solver context.

• repeated ConstraintSolverStatistics constraint_solver_statistics = 2

  Constraint solver statistics.

• repeated SubSolverStatistics sub_solver_statistics = 3

  Sub-solver statistics.

Storage for SequenceVars.

Used in: AssignmentProto

• string var_id = 1

• repeated int32 forward_sequence = 2

• repeated int32 backward_sequence = 3

• repeated int32 unperformed = 4

• bool active = 5

TODO(user): use uint64 instead of int32 for indices, as the solver supports it.

• repeated SetCoverProto.Subset subset = 1

  The list of subsets in the model.

• optional string name = 2

  A user-defined name for the model.

• optional Int128 fingerprint = 3

  An automatically fingerprint for the model. TODO(user): Implement.

Used in: SetCoverProto

• optional double cost = 1

  The cost for using the given subset.

• repeated int64 element = 2

  The list of elements in the subset.

• optional SetCoverSolutionResponse.Status status = 1

  For future use. TODO(user): Implement.

• optional int64 num_subsets = 2

  The number of subsets that are selected in the solution. This is used to decompress their indices below.

• repeated int64 subset = 3

  The list of the subsets selected in the solution.

• optional double cost = 4

  The cost of the solution, as computed by the algorithm.

• optional double cost_lower_bound = 5

  A lower bound of the solution, as computed by the algorithm.

• optional Int128 fingerprint = 6

  An automatically fingerprint for the solution. TODO(user): Implement.

• optional Int128 model_fingerprint = 7

  A reference to the model the solution applies to. TODO(user): Implement.

Result of the optimization.

Used in: SetCoverSolutionResponse

• UNDEFINED = 0

  Undefined.

• OPTIMAL = 1

  The solver found the proven optimal solution.

• FEASIBLE = 2

  The solver had enough time to find some solution that satisfied all constraints, but it did not reach the optimal.

• INFEASIBLE = 3

  The model does not have any solution.

• INVALID = 4

  The model is invalid.

Acceptance strategy in which solutions are accepted with a probability that depends on its quality and on the current state of the search.

Used in: AcceptanceStrategy

• CoolingScheduleStrategy.Value cooling_schedule_strategy = 1

  Determines the speed at which the temperature changes from initial to final.

• optional double initial_temperature = 2

  The initial temperature. See CoolingScheduleStrategy for its usage.

• optional double final_temperature = 3

  The final temperature. See CoolingScheduleStrategy for its usage.

• optional bool automatic_temperatures = 4

  Automatically define the value for the temperatures as follows. First, a reference temperature t is defined as w1 * c1 + w2 * c2 + ... + wK * cK where 0 < wJ <= 1 is the fraction of vehicles of cost class J and cJ is the average arc cost for the cost class J. The value of cJ is identified by randomly sampling N arc costs for the cost class J, where N is equal to the number of instance nodes. The initial and final temperatures are then defined as - initial_temperature: 0.1 * t - final_temperature: 0.001 * t

Ruin strategy that removes a number of spatially close routes.

Used in: RuinStrategy

• optional uint32 num_ruined_routes = 3

  Number of spatially close routes ruined at each ruin application.

Used in: CourseSchedulingModel

• string display_name = 1

  Student name, used only for logging purposes.

• repeated int32 course_indices = 2

  List of course indices that the student needs to be enrolled in.

Used in: CourseSchedulingResult

• int32 student_index = 1

  Index of the student in the CourseSchedulingModel.

• repeated int32 course_indices = 2

  Course indices in the CourseSchedulingModel that this student has been assigned to. The number of indices must match the number of section indices.

• repeated int32 section_indices = 3

  Section indices for each Course in the CourseSchedulingModel this this student has been assigned to. The number of indices must match the number of course indices.

Statistics on sub-solvers.

Used in: SearchStatistics

• int64 num_glop_calls_in_lp_scheduling = 1

  Number of calls to Glop in LP scheduling.

• int64 num_cp_sat_calls_in_lp_scheduling = 2

  Number of calls to CP-SAT in LP scheduling.

• int64 num_min_cost_flow_calls = 3

  Number of calls to min cost flow.

Used in: CourseSchedulingModel

• string display_name = 1

  Teacher name, used only for logging purposes.

• repeated int32 restricted_time_slots = 2

  List of time slots that the teacher cannot be scheduled for. These time slot values index to the accumulative number of time slots starting at 0. For example, if a schedule rotation has 5 days and 8 time slots per day, and a teacher cannot be scheduled for the last time slot of the fourth day, the number here would be 31.

This message indicates how the assignment was produced.

Used in: AssignmentProto

• int32 worker_id = 1

• string bns = 2