1// Copyright 2010-2021 Google LLC 2// Licensed under the Apache License, Version 2.0 (the "License"); 3// you may not use this file except in compliance with the License. 4// You may obtain a copy of the License at 5// 6// http://www.apache.org/licenses/LICENSE-2.0 7// 8// Unless required by applicable law or agreed to in writing, software 9// distributed under the License is distributed on an "AS IS" BASIS, 10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11// See the License for the specific language governing permissions and 12// limitations under the License. 13 14syntax = "proto2"; 15 16package operations_research.bop; 17 18// Method used to optimize a solution in Bop. 19// 20// NEXT TAG: 16 21message BopOptimizerMethod { 22 enum OptimizerType { 23 SAT_CORE_BASED = 0; 24 SAT_LINEAR_SEARCH = 15; 25 LINEAR_RELAXATION = 1; 26 LOCAL_SEARCH = 2; 27 RANDOM_FIRST_SOLUTION = 3; 28 RANDOM_CONSTRAINT_LNS = 4; 29 RANDOM_VARIABLE_LNS = 5; 30 COMPLETE_LNS = 7; 31 LP_FIRST_SOLUTION = 8; 32 OBJECTIVE_FIRST_SOLUTION = 9; 33 USER_GUIDED_FIRST_SOLUTION = 14; 34 RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP = 11; 35 RANDOM_VARIABLE_LNS_GUIDED_BY_LP = 12; 36 37 RELATION_GRAPH_LNS = 16; 38 RELATION_GRAPH_LNS_GUIDED_BY_LP = 17; 39 } 40 optional OptimizerType type = 1; 41} 42 43// Set of optimizer methods to be run by an instance of the portfolio optimizer. 44// Note that in the current implementation, all the methods specified in the 45// repeated field methods will run on the same solver / thread. 46message BopSolverOptimizerSet { 47 repeated BopOptimizerMethod methods = 1; 48} 49 50// Contains the definitions for all the bop algorithm parameters and their 51// default values. 52// 53// NEXT TAG: 42 54message BopParameters { 55 // Maximum time allowed in seconds to solve a problem. 56 // The counter will starts as soon as Solve() is called. 57 optional double max_time_in_seconds = 1 [default = inf]; 58 59 // Maximum time allowed in deterministic time to solve a problem. 60 // The deterministic time should be correlated with the real time used by the 61 // solver, the time unit being roughly the order of magnitude of a second. 62 // The counter will starts as soon as SetParameters() or SolveWithTimeLimit() 63 // is called. 64 optional double max_deterministic_time = 27 [default = inf]; 65 66 // The max deterministic time given to the LP solver each time it is called. 67 // If this is not enough to solve the LP at hand, it will simply be called 68 // again later (and the solve will resume from where it stopped). 69 optional double lp_max_deterministic_time = 37 [default = 1.0]; 70 71 // Maximum number of consecutive optimizer calls without improving the 72 // current solution. If this number is reached, the search will be aborted. 73 // Note that this parameter only applies when an initial solution has been 74 // found or is provided. Also note that there is no limit to the number of 75 // calls, when the parameter is not set. 76 optional int32 max_number_of_consecutive_failing_optimizer_calls = 35; 77 78 // Limit used to stop the optimization as soon as the relative gap is smaller 79 // than the given value. 80 // The relative gap is defined as: 81 // abs(solution_cost - best_bound) 82 // / max(abs(solution_cost), abs(best_bound)). 83 optional double relative_gap_limit = 28 [default = 1e-4]; 84 85 // Maximum number of cascading decisions the solver might use to repair the 86 // current solution in the LS. 87 optional int32 max_num_decisions_in_ls = 2 [default = 4]; 88 89 // Abort the LS search tree as soon as strictly more than this number of 90 // constraints are broken. The default is a large value which basically 91 // disable this heuristic. 92 optional int32 max_num_broken_constraints_in_ls = 38 [default = 0x7FFFFFFF]; 93 94 // Whether the solver should log the search progress to LOG(INFO). 95 optional bool log_search_progress = 14 [default = false]; 96 97 // Compute estimated impact at each iteration when true; only once when false. 98 optional bool compute_estimated_impact = 3 [default = true]; 99 100 // Avoid exploring both branches (b, a, ...) and (a, b, ...). 101 optional bool prune_search_tree = 4 [default = false]; 102 103 // Sort constraints by increasing total number of terms instead of number of 104 // contributing terms. 105 optional bool sort_constraints_by_num_terms = 5 [default = false]; 106 107 // Use the random Large Neighborhood Search instead of the exhaustive one. 108 optional bool use_random_lns = 6 [default = true]; 109 110 // The seed used to initialize the random generator. 111 // 112 // TODO(user): Some of our client test fail depending on this value! we need 113 // to fix them and ideally randomize our behavior from on test to the next so 114 // that this doesn't happen in the future. 115 optional int32 random_seed = 7 [default = 8]; 116 117 // Number of variables to relax in the exhaustive Large Neighborhood Search. 118 optional int32 num_relaxed_vars = 8 [default = 10]; 119 120 // The number of conflicts the SAT solver has to solve a random LNS 121 // subproblem. 122 optional int32 max_number_of_conflicts_in_random_lns = 9 [default = 2500]; 123 124 // Number of tries in the random lns. 125 optional int32 num_random_lns_tries = 10 [default = 1]; 126 127 // Maximum number of backtracks times the number of variables in Local Search, 128 // ie. max num backtracks == max_number_of_backtracks_in_ls / num variables. 129 optional int64 max_number_of_backtracks_in_ls = 11 [default = 100000000]; 130 131 // Use Large Neighborhood Search based on the LP relaxation. 132 optional bool use_lp_lns = 12 [default = true]; 133 134 135 // Whether we use sat propagation to choose the lns neighbourhood. 136 optional bool use_sat_to_choose_lns_neighbourhood = 15 [default = true]; 137 138 // The number of conflicts the SAT solver has to solve a random LNS 139 // subproblem for the quick check of infeasibility. 140 optional int32 max_number_of_conflicts_for_quick_check = 16 [default = 10]; 141 142 // If true, find and exploit the eventual symmetries of the problem. 143 // 144 // TODO(user): turn this on by default once the symmetry finder becomes fast 145 // enough to be negligeable for most problem. Or at least support a time 146 // limit. 147 optional bool use_symmetry = 17 [default = false]; 148 149 // If true, find and exploit symmetries in proving satisfiability in the first 150 // problem. 151 // This feature is experimental. On some problems, computing symmetries may 152 // run forever. You may also run into unforseen problems as this feature was 153 // not extensively tested. 154 optional bool exploit_symmetry_in_sat_first_solution = 40 [default = false]; 155 156 // The number of conflicts the SAT solver has to generate a random solution. 157 optional int32 max_number_of_conflicts_in_random_solution_generation = 20 158 [default = 500]; 159 160 // The maximum number of assignments the Local Search iterates on during one 161 // try. Note that if the Local Search is called again on the same solution 162 // it will not restart from scratch but will iterate on the next 163 // max_number_of_explored_assignments_per_try_in_ls assignments. 164 optional int64 max_number_of_explored_assignments_per_try_in_ls = 21 165 [default = 10000]; 166 167 // Whether we use an hash set during the LS to avoid exploring more than once 168 // the "same" state. Note that because the underlying SAT solver may learn 169 // information in the middle of the LS, this may make the LS slightly less 170 // "complete", but it should be faster. 171 optional bool use_transposition_table_in_ls = 22 [default = true]; 172 173 // Wheter we keep a list of variable that can potentially repair in one flip 174 // all the current infeasible constraints (such variable must at least appear 175 // in all the infeasible constraints for this to happen). 176 optional bool use_potential_one_flip_repairs_in_ls = 39 [default = false]; 177 178 // Whether we use the learned binary clauses in the Linear Relaxation. 179 optional bool use_learned_binary_clauses_in_lp = 23 [default = true]; 180 181 // The number of solvers used to run Bop. Note that one thread will be created 182 // per solver. The type of communication between solvers is specified by the 183 // synchronization_type parameter. 184 optional int32 number_of_solvers = 24 [default = 1]; 185 186 // Defines how the different solvers are synchronized during the search. 187 // Note that the synchronization (if any) occurs before each call to an 188 // optimizer (the smallest granularity of the solver in a parallel context). 189 enum ThreadSynchronizationType { 190 // No synchronization. The solvers run independently until the time limit 191 // is reached; Then learned information from each solver are aggregated. 192 // The final solution is the best of all found solutions. 193 // Pros: - No need to wait for another solver to complete its task, 194 // - Adding a new solver always improves the final solution (In the 195 // current implementation it still depends on the machine load and 196 // the time limit). 197 // Cons: - No learning between solvers. 198 NO_SYNCHRONIZATION = 0; 199 200 // Synchronize all solvers. Each solver waits for all other solvers to 201 // complete the previous optimizer run, before running again. 202 // The final solution is the best of all found solutions. 203 // Pros: - Full learning between solvers. 204 // Cons: - A lot of waiting time when solvers don't run at the exact same 205 // speed, 206 // - The quality of the final solution depends on the number of 207 // solvers, adding one more solver might lead to poorer results 208 // because the search goes on a different path. 209 SYNCHRONIZE_ALL = 1; 210 211 // Solver i synchronizes with solvers 0..i-1. 212 // This is a good tradeoff between NO_SYNCHRONIZATION and SYNCHRONIZE_ALL: 213 // communication while keeping a relative determinism on the result even 214 // when the number of solvers increases. 215 // The final solution is the best of all found solutions. 216 // Pros: - Solver i learns from i different solvers, 217 // - Adding a new solver always improves the final solution (In the 218 // current implementation it still depends on the machine load and 219 // the time limit). 220 // Cons: - No full learning, 221 // - Some solvers need to wait for synchronization. 222 SYNCHRONIZE_ON_RIGHT = 2; 223 } 224 optional ThreadSynchronizationType synchronization_type = 25 225 [default = NO_SYNCHRONIZATION]; 226 227 // List of set of optimizers to be run by the solvers. 228 // Note that the i_th solver will run the 229 // min(i, solver_optimizer_sets_size())_th optimizer set. 230 // The default is defined by default_solver_optimizer_sets (only one set). 231 repeated BopSolverOptimizerSet solver_optimizer_sets = 26; 232 optional string default_solver_optimizer_sets = 33 233 [default = "methods:{type:LOCAL_SEARCH } " 234 "methods:{type:RANDOM_FIRST_SOLUTION } " 235 "methods:{type:LINEAR_RELAXATION } " 236 "methods:{type:LP_FIRST_SOLUTION } " 237 "methods:{type:OBJECTIVE_FIRST_SOLUTION } " 238 "methods:{type:USER_GUIDED_FIRST_SOLUTION } " 239 "methods:{type:RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP } " 240 "methods:{type:RANDOM_VARIABLE_LNS_GUIDED_BY_LP } " 241 "methods:{type:RELATION_GRAPH_LNS } " 242 "methods:{type:RELATION_GRAPH_LNS_GUIDED_BY_LP } " 243 "methods:{type:RANDOM_CONSTRAINT_LNS } " 244 "methods:{type:RANDOM_VARIABLE_LNS } " 245 "methods:{type:SAT_CORE_BASED } " 246 "methods:{type:COMPLETE_LNS } "]; 247 248 // Use strong branching in the linear relaxation optimizer. 249 // The strong branching is a what-if analysis on each variable v, i.e. 250 // compute the best bound when v is assigned to true, compute the best bound 251 // when v is assigned to false, and then use those best bounds to improve the 252 // overall best bound. 253 // This is useful to improve the best_bound, but also to fix some variables 254 // during search. 255 // Note that using probing might be time consuming as it runs the LP solver 256 // 2 * num_variables times. 257 optional bool use_lp_strong_branching = 29 [default = false]; 258 259 // Only try to decompose the problem when the number of variables is greater 260 // than the threshold. 261 optional int32 decomposer_num_variables_threshold = 30 [default = 50]; 262 263 // The number of BopSolver created (thread pool workers) used by the integral 264 // solver to solve a decomposed problem. 265 // TODO(user): Merge this with the number_of_solvers parameter. 266 optional int32 num_bop_solvers_used_by_decomposition = 31 [default = 1]; 267 268 // HACK. To avoid spending too little time on small problems, spend at least 269 // this time solving each of the decomposed sub-problem. This only make sense 270 // if num_bop_solvers_used_by_decomposition is greater than 1 so that the 271 // overhead can be "absorbed" by the other threads. 272 optional double decomposed_problem_min_time_in_seconds = 36 [default = 0.0]; 273 274 275 // The first solutions based on guided SAT will work in chunk of that many 276 // conflicts at the time. This allows to simulate parallelism between the 277 // different guiding strategy on a single core. 278 optional int32 guided_sat_conflicts_chunk = 34 [default = 1000]; 279 280 // The maximum number of time the LP solver will run to feasibility for pure 281 // feasibility problems (with a constant-valued objective function). Set this 282 // to a small value, e.g., 1, if fractional solutions offer useful guidance to 283 // other solvers in the portfolio. A negative value means no limit. 284 optional int32 max_lp_solve_for_feasibility_problems = 41 [default = 0]; 285} 286