OR-Tools  8.2
bop_solution.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 <cstdint>
17
18namespace operations_research {
19namespace bop {
20
21using ::operations_research::sat::LinearBooleanConstraint;
22using ::operations_research::sat::LinearBooleanProblem;
23using ::operations_research::sat::LinearObjective;
24
25//------------------------------------------------------------------------------
26// BopSolution
27//------------------------------------------------------------------------------
28BopSolution::BopSolution(const LinearBooleanProblem& problem,
29 const std::string& name)
30 : problem_(&problem),
31 name_(name),
32 values_(problem.num_variables(), false),
33 recompute_cost_(true),
34 recompute_is_feasible_(true),
35 cost_(0),
36 is_feasible_(false) {
37 // Try the lucky assignment, i.e. the optimal one if feasible.
38 const LinearObjective& objective = problem.objective();
39 for (int i = 0; i < objective.coefficients_size(); ++i) {
40 const VariableIndex var(objective.literals(i) - 1);
41 values_[var] = objective.coefficients(i) < 0;
42 }
43}
44
45int64_t BopSolution::ComputeCost() const {
46 recompute_cost_ = false;
47 int64_t sum = 0;
48 const LinearObjective& objective = problem_->objective();
49 const size_t num_sparse_vars = objective.literals_size();
50 CHECK_EQ(num_sparse_vars, objective.coefficients_size());
51 for (int i = 0; i < num_sparse_vars; ++i) {
52 CHECK_GT(objective.literals(i), 0);
53 const VariableIndex var(abs(objective.literals(i)) - 1);
54 if (values_[var]) {
55 sum += objective.coefficients(i);
56 }
57 }
58 return sum;
59}
60
61bool BopSolution::ComputeIsFeasible() const {
62 recompute_is_feasible_ = false;
63 for (const LinearBooleanConstraint& constraint : problem_->constraints()) {
64 int64_t sum = 0;
65 const size_t num_sparse_vars = constraint.literals_size();
66 CHECK_EQ(num_sparse_vars, constraint.coefficients_size());
67
68 for (int i = 0; i < num_sparse_vars; ++i) {
69 // The solver doesn't support negative literals yet.
70 CHECK_GT(constraint.literals(i), 0);
71 const VariableIndex var(abs(constraint.literals(i)) - 1);
72 if (values_[var]) {
73 sum += constraint.coefficients(i);
74 }
75 }
76
77 if ((constraint.has_upper_bound() && sum > constraint.upper_bound()) ||
78 (constraint.has_lower_bound() && sum < constraint.lower_bound())) {
79 return false;
80 }
81 }
82 return true;
83}
84} // namespace bop
85} // namespace operations_research
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
BopSolution(const sat::LinearBooleanProblem &problem, const std::string &name)
Definition: bop_solution.cc:28
const std::string name
IntVar * var
Definition: expr_array.cc:1858
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...