OR-Tools  8.2
bop_solver.cc
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
15
16#include <string>
17#include <vector>
18
19#include "google/protobuf/text_format.h"
22#include "ortools/bop/bop_fs.h"
23#include "ortools/bop/bop_lns.h"
24#include "ortools/bop/bop_ls.h"
33#include "ortools/util/bitset.h"
34
35namespace operations_research {
36namespace bop {
37
38using ::operations_research::sat::LinearBooleanProblem;
39
40namespace {
41
42using ::operations_research::glop::ColIndex;
44
45// Updates the problem_state when the solution is proved optimal or the problem
46// is proved infeasible.
47// Returns true when the problem_state has been changed.
48bool UpdateProblemStateBasedOnStatus(BopOptimizerBase::Status status,
49 ProblemState* problem_state) {
50 CHECK(nullptr != problem_state);
51
53 problem_state->MarkAsOptimal();
54 return true;
55 }
56
57 if (BopOptimizerBase::INFEASIBLE == status) {
58 problem_state->MarkAsInfeasible();
59 return true;
60 }
61
62 return false;
63}
64
65} // anonymous namespace
66
67//------------------------------------------------------------------------------
68// BopSolver
69//------------------------------------------------------------------------------
70BopSolver::BopSolver(const LinearBooleanProblem& problem)
71 : problem_(problem),
72 problem_state_(problem),
73 parameters_(),
74 stats_("BopSolver") {
75 SCOPED_TIME_STAT(&stats_);
76}
77
79
81 std::unique_ptr<TimeLimit> time_limit =
82 TimeLimit::FromParameters(parameters_);
83 return SolveWithTimeLimit(time_limit.get());
84}
85
87 CHECK(time_limit != nullptr);
88 SCOPED_TIME_STAT(&stats_);
89
90 absl::Status valid = sat::ValidateBooleanProblem(problem_);
91 if (!valid.ok()) {
92 LOG(ERROR) << "Invalid Boolean problem: " << valid.message();
94 }
95
96 UpdateParameters();
97
98 return parameters_.number_of_solvers() > 1
99 ? InternalMultithreadSolver(time_limit)
100 : InternalMonothreadSolver(time_limit);
101}
102
103BopSolveStatus BopSolver::InternalMonothreadSolver(TimeLimit* time_limit) {
104 CHECK(time_limit != nullptr);
105 LearnedInfo learned_info(problem_state_.original_problem());
106 PortfolioOptimizer optimizer(problem_state_, parameters_,
107 parameters_.solver_optimizer_sets(0),
108 "Portfolio");
109 while (!time_limit->LimitReached()) {
110 const BopOptimizerBase::Status optimization_status = optimizer.Optimize(
111 parameters_, problem_state_, &learned_info, time_limit);
112 problem_state_.MergeLearnedInfo(learned_info, optimization_status);
113
114 if (optimization_status == BopOptimizerBase::SOLUTION_FOUND) {
115 CHECK(problem_state_.solution().IsFeasible());
116 VLOG(1) << problem_state_.solution().GetScaledCost()
117 << " New solution! ";
118 }
119
120 if (problem_state_.IsOptimal()) {
121 CHECK(problem_state_.solution().IsFeasible());
123 } else if (problem_state_.IsInfeasible()) {
125 }
126
127 if (optimization_status == BopOptimizerBase::ABORT) {
128 break;
129 }
130 learned_info.Clear();
131 }
132
133 return problem_state_.solution().IsFeasible()
136}
137
138BopSolveStatus BopSolver::InternalMultithreadSolver(TimeLimit* time_limit) {
139 CHECK(time_limit != nullptr);
140 // Not implemented.
142}
143
145 std::unique_ptr<TimeLimit> time_limit =
146 TimeLimit::FromParameters(parameters_);
147 return SolveWithTimeLimit(first_solution, time_limit.get());
148}
149
152 SCOPED_TIME_STAT(&stats_);
153
154 if (first_solution.IsFeasible()) {
155 VLOG(1) << "First solution is feasible.";
156 LearnedInfo learned_info(problem_);
157 learned_info.solution = first_solution;
158 if (problem_state_.MergeLearnedInfo(learned_info,
160 problem_state_.IsOptimal()) {
162 }
163 } else {
164 VLOG(1)
165 << "First solution is infeasible. Using it as assignment preference.";
166 std::vector<bool> assignment_preference;
167 for (int i = 0; i < first_solution.Size(); ++i) {
168 assignment_preference.push_back(first_solution.Value(VariableIndex(i)));
169 }
170 problem_state_.set_assignment_preference(assignment_preference);
171 }
173}
174
177 problem_, sat::Coefficient(problem_state_.lower_bound()));
178}
179
181 return 100.0 *
182 std::abs(problem_state_.solution().GetScaledCost() -
184 std::abs(problem_state_.solution().GetScaledCost());
185}
186
187void BopSolver::UpdateParameters() {
188 if (parameters_.solver_optimizer_sets_size() == 0) {
189 // No user defined optimizers, use the default string to define the
190 // behavior.
191 CHECK(::google::protobuf::TextFormat::ParseFromString(
192 parameters_.default_solver_optimizer_sets(),
193 parameters_.add_solver_optimizer_sets()));
194 }
195
196 problem_state_.SetParameters(parameters_);
197}
198} // namespace bop
199} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
std::string StatString() const
Definition: stats.cc:71
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
Definition: time_limit.h:159
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
const BopSolution & solution() const
Definition: bop_base.h:196
bool MergeLearnedInfo(const LearnedInfo &learned_info, BopOptimizerBase::Status optimization_status)
Definition: bop_base.cc:92
const sat::LinearBooleanProblem & original_problem() const
Definition: bop_base.h:201
void SetParameters(const BopParameters &parameters)
Definition: bop_base.h:119
void set_assignment_preference(const std::vector< bool > &a)
Definition: bop_base.h:127
SharedTimeLimit * time_limit
const int ERROR
Definition: log_severity.h:32
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
absl::Status ValidateBooleanProblem(const LinearBooleanProblem &problem)
double AddOffsetAndScaleObjectiveValue(const LinearBooleanProblem &problem, Coefficient v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define IF_STATS_ENABLED(instructions)
Definition: stats.h:437
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:438