OR-Tools  8.2
linear_expr.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 <limits>
17
18#include "absl/strings/str_join.h"
21
22namespace operations_research {
23
24LinearExpr::LinearExpr(double constant) : offset_(constant), terms_() {}
25
27
29 terms_[var] = 1.0;
30}
31
33 for (const auto& kv : rhs.terms_) {
34 terms_[kv.first] += kv.second;
35 }
36 offset_ += rhs.offset_;
37 return *this;
38}
39
41 for (const auto& kv : rhs.terms_) {
42 terms_[kv.first] -= kv.second;
43 }
44 offset_ -= rhs.offset_;
45 return *this;
46}
47
49 if (rhs == 0) {
50 terms_.clear();
51 offset_ = 0;
52 } else if (rhs != 1) {
53 for (auto& kv : terms_) {
54 kv.second *= rhs;
55 }
56 offset_ *= rhs;
57 }
58 return *this;
59}
60
62 DCHECK_NE(rhs, 0);
63 return (*this) *= 1 / rhs;
64}
65
66LinearExpr LinearExpr::operator-() const { return (*this) * -1; }
67
68// static
70 var *= -1;
71 var += 1;
72 return var;
73}
74
76 double solution = offset_;
77 for (const auto& pair : terms_) {
78 solution += pair.first->solution_value() * pair.second;
79 }
80 return solution;
81}
82
83namespace {
84
85void AppendTerm(const double coef, const std::string& var_name,
86 const bool is_first, std::string* s) {
87 if (is_first) {
88 if (coef == 1.0) {
89 absl::StrAppend(s, var_name);
90 } else if (coef == -1.0) {
91 absl::StrAppend(s, "-", var_name);
92 } else {
93 absl::StrAppend(s, coef, "*", var_name);
94 }
95 } else {
96 const std::string op = coef < 0 ? "-" : "+";
97 const double abs_coef = std::abs(coef);
98 if (abs_coef == 1.0) {
99 absl::StrAppend(s, " ", op, " ", var_name);
100 } else {
101 absl::StrAppend(s, " ", op, " ", abs_coef, "*", var_name);
102 }
103 }
104}
105
106void AppendOffset(const double offset, const bool is_first, std::string* s) {
107 if (is_first) {
108 absl::StrAppend(s, offset);
109 } else {
110 if (offset != 0.0) {
111 const std::string op = offset < 0 ? "-" : "+";
112 absl::StrAppend(s, " ", op, " ", std::abs(offset));
113 }
114 }
115}
116
117} // namespace
118
119std::string LinearExpr::ToString() const {
120 std::vector<const MPVariable*> vars_in_order;
121 for (const auto& var_val_pair : terms_) {
122 vars_in_order.push_back(var_val_pair.first);
123 }
124 std::sort(vars_in_order.begin(), vars_in_order.end(),
125 [](const MPVariable* v, const MPVariable* u) {
126 return v->index() < u->index();
127 });
128 std::string result;
129 bool is_first = true;
130 for (const MPVariable* var : vars_in_order) {
131 // MPSolver gives names to all variables, even if you don't.
132 DCHECK(!var->name().empty());
133 AppendTerm(terms_.at(var), var->name(), is_first, &result);
134 is_first = false;
135 }
136 AppendOffset(offset_, is_first, &result);
137 // TODO(user): support optionally cropping long strings.
138 return result;
139}
140
141std::ostream& operator<<(std::ostream& stream, const LinearExpr& linear_expr) {
142 stream << linear_expr.ToString();
143 return stream;
144}
145
147 lhs += rhs;
148 return lhs;
149}
151 lhs -= rhs;
152 return lhs;
153}
155 lhs *= rhs;
156 return lhs;
157}
159 lhs /= rhs;
160 return lhs;
161}
163 rhs *= lhs;
164 return rhs;
165}
166
167LinearRange::LinearRange(double lower_bound, const LinearExpr& linear_expr,
168 double upper_bound)
169 : lower_bound_(lower_bound),
170 linear_expr_(linear_expr),
171 upper_bound_(upper_bound) {
172 lower_bound_ -= linear_expr_.offset();
173 upper_bound_ -= linear_expr_.offset();
174 linear_expr_ -= linear_expr_.offset();
175}
176
178 return LinearRange(-std::numeric_limits<double>::infinity(), lhs - rhs, 0);
179}
181 return LinearRange(0, lhs - rhs, 0);
182}
184 return LinearRange(0, lhs - rhs, std::numeric_limits<double>::infinity());
185}
186
187} // namespace operations_research
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK(condition)
Definition: base/logging.h:884
LinearExpr models a quantity that is linear in the decision variables (MPVariable) of an optimization...
Definition: linear_expr.h:114
double SolutionValue() const
Evaluates the value of this expression at the solution found.
Definition: linear_expr.cc:75
std::string ToString() const
A human readable representation of this.
Definition: linear_expr.cc:119
LinearExpr operator-() const
Definition: linear_expr.cc:66
LinearExpr & operator*=(double rhs)
Definition: linear_expr.cc:48
LinearExpr & operator+=(const LinearExpr &rhs)
Definition: linear_expr.cc:32
LinearExpr & operator-=(const LinearExpr &rhs)
Definition: linear_expr.cc:40
LinearExpr & operator/=(double rhs)
Definition: linear_expr.cc:61
static LinearExpr NotVar(LinearExpr var)
Returns 1-var.
Definition: linear_expr.cc:69
An expression of the form:
Definition: linear_expr.h:192
The class for variables of a Mathematical Programming (MP) model.
IntVar * var
Definition: expr_array.cc:1858
int64 coef
Definition: expr_array.cc:1859
const int64 offset_
Definition: interval.cc:2076
This file allows you to write natural code (like a mathematical equation) to model optimization probl...
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
LinearExpr operator+(LinearExpr lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:146
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
LinearExpr operator*(LinearExpr lhs, double rhs)
Definition: linear_expr.cc:154
LinearExpr operator/(LinearExpr lhs, double rhs)
Definition: linear_expr.cc:158
LinearExpr operator-(LinearExpr lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:150
LinearRange operator>=(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:183
LinearRange operator<=(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:177
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:180