OR-Tools  8.2
cp_model_objective.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 
17 
18 namespace operations_research {
19 namespace sat {
20 
21 void EncodeObjectiveAsSingleVariable(CpModelProto* cp_model) {
22  if (!cp_model->has_objective()) return;
23 
24  if (cp_model->objective().vars_size() == 1) {
25  // Canonicalize the objective to make it easier on us by always making the
26  // coefficient equal to 1.0.
27  const int old_ref = cp_model->objective().vars(0);
28  const int64 old_coeff = cp_model->objective().coeffs(0);
29  const double muliplier = static_cast<double>(std::abs(old_coeff));
30  if (old_coeff < 0) {
31  cp_model->mutable_objective()->set_vars(0, NegatedRef(old_ref));
32  }
33  if (muliplier != 1.0) {
34  // TODO(user): deal with this case.
35  CHECK(cp_model->objective().domain().empty());
36 
37  double old_factor = cp_model->objective().scaling_factor();
38  if (old_factor == 0.0) old_factor = 1.0;
39  const double old_offset = cp_model->objective().offset();
40  cp_model->mutable_objective()->set_scaling_factor(old_factor * muliplier);
41  cp_model->mutable_objective()->set_offset(old_offset / muliplier);
42  }
43  cp_model->mutable_objective()->set_coeffs(0, 1.0);
44  return;
45  }
46 
47  // Compute trivial bounds on the objective, this is needed otherwise the
48  // overflow checker might not be happy with the new constraint we are about
49  // to create. Note that the model validator should make sure that there is no
50  // overflow in the computation below.
51  int64 min_obj = 0;
52  int64 max_obj = 0;
53  for (int i = 0; i < cp_model->objective().vars_size(); ++i) {
54  const int ref = cp_model->objective().vars(i);
55  const int var = PositiveRef(ref);
56  const int64 coeff =
57  cp_model->objective().coeffs(i) * (RefIsPositive(ref) ? 1 : -1);
58  const int64 value1 = cp_model->variables(var).domain(0) * coeff;
59  const int64 value2 = cp_model->variables(var).domain(
60  cp_model->variables(var).domain_size() - 1) *
61  coeff;
62  min_obj += std::min(value1, value2);
63  max_obj += std::max(value1, value2);
64  }
65 
66  // Create the new objective var.
67  const int obj_ref = cp_model->variables_size();
68  {
69  IntegerVariableProto* obj = cp_model->add_variables();
70  Domain obj_domain(min_obj, max_obj);
71  if (!cp_model->objective().domain().empty()) {
72  obj_domain = obj_domain.IntersectionWith(
73  ReadDomainFromProto(cp_model->objective()));
74  }
75  FillDomainInProto(obj_domain, obj);
76  }
77 
78  // Add the linear constraint.
79  LinearConstraintProto* ct = cp_model->add_constraints()->mutable_linear();
80  ct->add_domain(0);
81  ct->add_domain(0);
82  *(ct->mutable_vars()) = cp_model->objective().vars();
83  *(ct->mutable_coeffs()) = cp_model->objective().coeffs();
84  ct->add_vars(obj_ref);
85  ct->add_coeffs(-1);
86 
87  // Update the objective.
88  cp_model->mutable_objective()->clear_vars();
89  cp_model->mutable_objective()->clear_coeffs();
90  cp_model->mutable_objective()->add_vars(obj_ref);
91  cp_model->mutable_objective()->add_coeffs(1);
92  cp_model->mutable_objective()->clear_domain();
93 }
94 
95 } // namespace sat
96 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
We call domain any subset of Int64 = [kint64min, kint64max].
Domain IntersectionWith(const Domain &domain) const
Returns the intersection of D and domain.
const Constraint * ct
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
bool RefIsPositive(int ref)
void EncodeObjectiveAsSingleVariable(CpModelProto *cp_model)
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...