bop_parameters.proto

// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

syntax = "proto2";

package operations_research.bop;

option java_package = "com.google.ortools.bop";
option java_multiple_files = true;
option csharp_namespace = "Google.OrTools.Bop";
// Method used to optimize a solution in Bop.
//
// NEXT TAG: 16
message BopOptimizerMethod {
  enum OptimizerType {
    SAT_CORE_BASED = 0;
    SAT_LINEAR_SEARCH = 15;
    LINEAR_RELAXATION = 1;
    LOCAL_SEARCH = 2;
    RANDOM_FIRST_SOLUTION = 3;
    RANDOM_CONSTRAINT_LNS = 4;
    RANDOM_VARIABLE_LNS = 5;
    COMPLETE_LNS = 7;
    LP_FIRST_SOLUTION = 8;
    OBJECTIVE_FIRST_SOLUTION = 9;
    USER_GUIDED_FIRST_SOLUTION = 14;
    RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP = 11;
    RANDOM_VARIABLE_LNS_GUIDED_BY_LP = 12;

    RELATION_GRAPH_LNS = 16;
    RELATION_GRAPH_LNS_GUIDED_BY_LP = 17;
  }
  optional OptimizerType type = 1;
}

// Set of optimizer methods to be run by an instance of the portfolio optimizer.
// Note that in the current implementation, all the methods specified in the
// repeated field methods will run on the same solver / thread.
message BopSolverOptimizerSet {
  repeated BopOptimizerMethod methods = 1;
}

// Contains the definitions for all the bop algorithm parameters and their
// default values.
//
// NEXT TAG: 42
message BopParameters {
  // Maximum time allowed in seconds to solve a problem.
  // The counter will starts as soon as Solve() is called.
  optional double max_time_in_seconds = 1 [default = inf];

  // Maximum time allowed in deterministic time to solve a problem.
  // The deterministic time should be correlated with the real time used by the
  // solver, the time unit being roughly the order of magnitude of a second.
  // The counter will starts as soon as SetParameters() or SolveWithTimeLimit()
  // is called.
  optional double max_deterministic_time = 27 [default = inf];

  // The max deterministic time given to the LP solver each time it is called.
  // If this is not enough to solve the LP at hand, it will simply be called
  // again later (and the solve will resume from where it stopped).
  optional double lp_max_deterministic_time = 37 [default = 1.0];

  // Maximum number of consecutive optimizer calls without improving the
  // current solution. If this number is reached, the search will be aborted.
  // Note that this parameter only applies when an initial solution has been
  // found or is provided. Also note that there is no limit to the number of
  // calls, when the parameter is not set.
  optional int32 max_number_of_consecutive_failing_optimizer_calls = 35;

  // Limit used to stop the optimization as soon as the relative gap is smaller
  // than the given value.
  // The relative gap is defined as:
  //   abs(solution_cost - best_bound)
  //        / max(abs(solution_cost), abs(best_bound)).
  optional double relative_gap_limit = 28 [default = 1e-4];

  // Maximum number of cascading decisions the solver might use to repair the
  // current solution in the LS.
  optional int32 max_num_decisions_in_ls = 2 [default = 4];

  // Abort the LS search tree as soon as strictly more than this number of
  // constraints are broken. The default is a large value which basically
  // disable this heuristic.
  optional int32 max_num_broken_constraints_in_ls = 38 [default = 0x7FFFFFFF];

  // Whether the solver should log the search progress to LOG(INFO).
  optional bool log_search_progress = 14 [default = false];

  // Compute estimated impact at each iteration when true; only once when false.
  optional bool compute_estimated_impact = 3 [default = true];

  // Avoid exploring both branches (b, a, ...) and (a, b, ...).
  optional bool prune_search_tree = 4 [default = false];

  // Sort constraints by increasing total number of terms instead of number of
  // contributing terms.
  optional bool sort_constraints_by_num_terms = 5 [default = false];

  // Use the random Large Neighborhood Search instead of the exhaustive one.
  optional bool use_random_lns = 6 [default = true];

  // The seed used to initialize the random generator.
  //
  // TODO(user): Some of our client test fail depending on this value! we need
  // to fix them and ideally randomize our behavior from on test to the next so
  // that this doesn't happen in the future.
  optional int32 random_seed = 7 [default = 8];

  // Number of variables to relax in the exhaustive Large Neighborhood Search.
  optional int32 num_relaxed_vars = 8 [default = 10];

  // The number of conflicts the SAT solver has to solve a random LNS
  // subproblem.
  optional int32 max_number_of_conflicts_in_random_lns = 9 [default = 2500];

  // Number of tries in the random lns.
  optional int32 num_random_lns_tries = 10 [default = 1];

  // Maximum number of backtracks times the number of variables in Local Search,
  // ie. max num backtracks == max_number_of_backtracks_in_ls / num variables.
  optional int64 max_number_of_backtracks_in_ls = 11 [default = 100000000];

  // Use Large Neighborhood Search based on the LP relaxation.
  optional bool use_lp_lns = 12 [default = true];

  // Whether we use sat propagation to choose the lns neighbourhood.
  optional bool use_sat_to_choose_lns_neighbourhood = 15 [default = true];

  // The number of conflicts the SAT solver has to solve a random LNS
  // subproblem for the quick check of infeasibility.
  optional int32 max_number_of_conflicts_for_quick_check = 16 [default = 10];

  // If true, find and exploit the eventual symmetries of the problem.
  //
  // TODO(user): turn this on by default once the symmetry finder becomes fast
  // enough to be negligeable for most problem. Or at least support a time
  // limit.
  optional bool use_symmetry = 17 [default = false];

  // If true, find and exploit symmetries in proving satisfiability in the first
  // problem.
  // This feature is experimental. On some problems, computing symmetries may
  // run forever. You may also run into unforseen problems as this feature was
  // not extensively tested.
  optional bool exploit_symmetry_in_sat_first_solution = 40 [default = false];

  // The number of conflicts the SAT solver has to generate a random solution.
  optional int32 max_number_of_conflicts_in_random_solution_generation = 20
      [default = 500];

  // The maximum number of assignments the Local Search iterates on during one
  // try. Note that if the Local Search is called again on the same solution
  // it will not restart from scratch but will iterate on the next
  // max_number_of_explored_assignments_per_try_in_ls assignments.
  optional int64 max_number_of_explored_assignments_per_try_in_ls = 21
      [default = 10000];

  // Whether we use an hash set during the LS to avoid exploring more than once
  // the "same" state. Note that because the underlying SAT solver may learn
  // information in the middle of the LS, this may make the LS slightly less
  // "complete", but it should be faster.
  optional bool use_transposition_table_in_ls = 22 [default = true];

  // Whether we keep a list of variable that can potentially repair in one flip
  // all the current infeasible constraints (such variable must at least appear
  // in all the infeasible constraints for this to happen).
  optional bool use_potential_one_flip_repairs_in_ls = 39 [default = false];

  // Whether we use the learned binary clauses in the Linear Relaxation.
  optional bool use_learned_binary_clauses_in_lp = 23 [default = true];

  // The number of solvers used to run Bop. Note that one thread will be created
  // per solver. The type of communication between solvers is specified by the
  // synchronization_type parameter.
  optional int32 number_of_solvers = 24 [default = 1];

  // Defines how the different solvers are synchronized during the search.
  // Note that the synchronization (if any) occurs before each call to an
  // optimizer (the smallest granularity of the solver in a parallel context).
  enum ThreadSynchronizationType {
    // No synchronization. The solvers run independently until the time limit
    // is reached; Then learned information from each solver are aggregated.
    // The final solution is the best of all found solutions.
    // Pros: - No need to wait for another solver to complete its task,
    //       - Adding a new solver always improves the final solution (In the
    //         current implementation it still depends on the machine load and
    //         the time limit).
    // Cons: - No learning between solvers.
    NO_SYNCHRONIZATION = 0;

    // Synchronize all solvers. Each solver waits for all other solvers to
    // complete the previous optimizer run, before running again.
    // The final solution is the best of all found solutions.
    // Pros: - Full learning between solvers.
    // Cons: - A lot of waiting time when solvers don't run at the exact same
    //         speed,
    //       - The quality of the final solution depends on the number of
    //         solvers, adding one more solver might lead to poorer results
    //         because the search goes on a different path.
    SYNCHRONIZE_ALL = 1;

    // Solver i synchronizes with solvers 0..i-1.
    // This is a good tradeoff between NO_SYNCHRONIZATION and SYNCHRONIZE_ALL:
    // communication while keeping a relative determinism on the result even
    // when the number of solvers increases.
    // The final solution is the best of all found solutions.
    // Pros: - Solver i learns from i different solvers,
    //       - Adding a new solver always improves the final solution (In the
    //         current implementation it still depends on the machine load and
    //         the time limit).
    // Cons: - No full learning,
    //       - Some solvers need to wait for synchronization.
    SYNCHRONIZE_ON_RIGHT = 2;
  }
  optional ThreadSynchronizationType synchronization_type = 25
      [default = NO_SYNCHRONIZATION];

  // List of set of optimizers to be run by the solvers.
  // Note that the i_th solver will run the
  // min(i, solver_optimizer_sets_size())_th optimizer set.
  // The default is defined by default_solver_optimizer_sets (only one set).
  repeated BopSolverOptimizerSet solver_optimizer_sets = 26;
  optional string default_solver_optimizer_sets = 33
      [default = "methods:{type:LOCAL_SEARCH }                       "
                 "methods:{type:RANDOM_FIRST_SOLUTION }              "
                 "methods:{type:LINEAR_RELAXATION }                  "
                 "methods:{type:LP_FIRST_SOLUTION }                  "
                 "methods:{type:OBJECTIVE_FIRST_SOLUTION }           "
                 "methods:{type:USER_GUIDED_FIRST_SOLUTION }         "
                 "methods:{type:RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP } "
                 "methods:{type:RANDOM_VARIABLE_LNS_GUIDED_BY_LP }   "
                 "methods:{type:RELATION_GRAPH_LNS }                 "
                 "methods:{type:RELATION_GRAPH_LNS_GUIDED_BY_LP }    "
                 "methods:{type:RANDOM_CONSTRAINT_LNS }              "
                 "methods:{type:RANDOM_VARIABLE_LNS }                "
                 "methods:{type:SAT_CORE_BASED }                     "
                 "methods:{type:COMPLETE_LNS }                       "];

  // Use strong branching in the linear relaxation optimizer.
  // The strong branching is a what-if analysis on each variable v, i.e.
  // compute the best bound when v is assigned to true, compute the best bound
  // when v is assigned to false, and then use those best bounds to improve the
  // overall best bound.
  // This is useful to improve the best_bound, but also to fix some variables
  // during search.
  // Note that using probing might be time consuming as it runs the LP solver
  // 2 * num_variables times.
  optional bool use_lp_strong_branching = 29 [default = false];

  // Only try to decompose the problem when the number of variables is greater
  // than the threshold.
  optional int32 decomposer_num_variables_threshold = 30 [default = 50];

  // The number of BopSolver created (thread pool workers) used by the integral
  // solver to solve a decomposed problem.
  // TODO(user): Merge this with the number_of_solvers parameter.
  optional int32 num_bop_solvers_used_by_decomposition = 31 [default = 1];

  // HACK. To avoid spending too little time on small problems, spend at least
  // this time solving each of the decomposed sub-problem. This only make sense
  // if num_bop_solvers_used_by_decomposition is greater than 1 so that the
  // overhead can be "absorbed" by the other threads.
  optional double decomposed_problem_min_time_in_seconds = 36 [default = 0.0];

  // The first solutions based on guided SAT will work in chunk of that many
  // conflicts at the time. This allows to simulate parallelism between the
  // different guiding strategy on a single core.
  optional int32 guided_sat_conflicts_chunk = 34 [default = 1000];

  // The maximum number of time the LP solver will run to feasibility for pure
  // feasibility problems (with a constant-valued objective function). Set this
  // to a small value, e.g., 1, if fractional solutions offer useful guidance to
  // other solvers in the portfolio. A negative value means no limit.
  optional int32 max_lp_solve_for_feasibility_problems = 41 [default = 0];
}