OR-Tools  8.2
bop_solver.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_BOP_BOP_SOLVER_H_
15 #define OR_TOOLS_BOP_BOP_SOLVER_H_
16 
17 // Solver for Boolean Optimization Problems built on top of the SAT solver.
18 // To optimize a problem the solver uses several optimization strategies like
19 // Local Search (LS), Large Neighborhood Search (LNS), and Linear
20 // Programming (LP). See bop_parameters.proto to tune the strategies.
21 //
22 // Note that the BopSolver usage is limited to:
23 // - Boolean variables,
24 // - Linear constraints and linear optimization objective,
25 // - Integral weights for both constraints and objective,
26 // - Minimization.
27 // To deal with maximization, integral variables and floating weights, one can
28 // use the bop::IntegralSolver.
29 //
30 // Usage example:
31 // const LinearBooleanProblem problem = BuildProblem();
32 // BopSolver bop_solver(problem);
33 // BopParameters bop_parameters;
34 // bop_parameters.set_max_deterministic_time(10);
35 // bop_solver.SetParameters(bop_parameters);
36 // const BopSolveStatus solve_status = bop_solver.Solve();
37 // if (solve_status == BopSolveStatus::OPTIMAL_SOLUTION_FOUND) { ... }
38 
39 #include <string>
40 #include <vector>
41 
43 #include "ortools/base/int_type.h"
45 #include "ortools/base/logging.h"
46 #include "ortools/base/macros.h"
47 #include "ortools/bop/bop_base.h"
48 #include "ortools/bop/bop_parameters.pb.h"
50 #include "ortools/bop/bop_types.h"
51 #include "ortools/glop/lp_solver.h"
52 #include "ortools/sat/boolean_problem.pb.h"
53 #include "ortools/sat/sat_solver.h"
54 #include "ortools/util/stats.h"
56 
57 namespace operations_research {
58 namespace bop {
59 // Solver of Boolean Optimization Problems based on Local Search.
60 class BopSolver {
61  public:
62  explicit BopSolver(const sat::LinearBooleanProblem& problem);
63  virtual ~BopSolver();
64 
65  // Parameters management.
66  void SetParameters(const BopParameters& parameters) {
67  parameters_ = parameters;
68  }
69 
70  // Returns the status of the optimization.
72  BopSolveStatus Solve(const BopSolution& first_solution);
73 
74  // Runs the solver with an external time limit.
76  BopSolveStatus SolveWithTimeLimit(const BopSolution& first_solution,
78 
79  const BopSolution& best_solution() const { return problem_state_.solution(); }
80  bool GetSolutionValue(VariableIndex var_id) const {
81  return problem_state_.solution().Value(var_id);
82  }
83 
84  // Returns the scaled best bound.
85  // In case of minimization (resp. maximization), the best bound is defined as
86  // the lower bound (resp. upper bound).
87  double GetScaledBestBound() const;
88  double GetScaledGap() const;
89 
90  private:
91  void UpdateParameters();
92  BopSolveStatus InternalMonothreadSolver(TimeLimit* time_limit);
93  BopSolveStatus InternalMultithreadSolver(TimeLimit* time_limit);
94 
95  const sat::LinearBooleanProblem& problem_;
96  ProblemState problem_state_;
97  BopParameters parameters_;
98 
99  mutable StatsGroup stats_;
100 };
101 } // namespace bop
102 } // namespace operations_research
103 #endif // OR_TOOLS_BOP_BOP_SOLVER_H_
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
bool Value(VariableIndex var) const
Definition: bop_solution.h:46
BopSolveStatus SolveWithTimeLimit(TimeLimit *time_limit)
Definition: bop_solver.cc:86
BopSolver(const sat::LinearBooleanProblem &problem)
Definition: bop_solver.cc:70
bool GetSolutionValue(VariableIndex var_id) const
Definition: bop_solver.h:80
const BopSolution & best_solution() const
Definition: bop_solver.h:79
void SetParameters(const BopParameters &parameters)
Definition: bop_solver.h:66
const BopSolution & solution() const
Definition: bop_base.h:196
SatParameters parameters
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...