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 
18 namespace operations_research {
19 namespace bop {
20 
21 using ::operations_research::sat::LinearBooleanConstraint;
22 using ::operations_research::sat::LinearBooleanProblem;
23 using ::operations_research::sat::LinearObjective;
24 
25 //------------------------------------------------------------------------------
26 // BopSolution
27 //------------------------------------------------------------------------------
28 BopSolution::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 
45 int64_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 
61 bool 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...