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
18namespace operations_research {
19namespace sat {
20
21void 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
void EncodeObjectiveAsSingleVariable(CpModelProto *cp_model)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
bool RefIsPositive(int ref)
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...