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
46#include "ortools/base/macros.h"
48#include "ortools/bop/bop_parameters.pb.h"
52#include "ortools/sat/boolean_problem.pb.h"
54#include "ortools/util/stats.h"
56
57namespace operations_research {
58namespace bop {
59// Solver of Boolean Optimization Problems based on Local Search.
60class 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
const BopSolution & best_solution() const
Definition: bop_solver.h:79
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
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...