OR-Tools  8.1
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"
19 #include "ortools/base/logging.h"
21 
22 namespace operations_research {
23 
24 LinearExpr::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 
66 LinearExpr LinearExpr::operator-() const { return (*this) * -1; }
67 
68 // static
70  var *= -1;
71  var += 1;
72  return var;
73 }
74 
75 double LinearExpr::SolutionValue() const {
76  double solution = offset_;
77  for (const auto& pair : terms_) {
78  solution += pair.first->solution_value() * pair.second;
79  }
80  return solution;
81 }
82 
83 namespace {
84 
85 void 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 
106 void 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 
119 std::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 
141 std::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 }
154 LinearExpr operator*(LinearExpr lhs, double rhs) {
155  lhs *= rhs;
156  return lhs;
157 }
158 LinearExpr operator/(LinearExpr lhs, double rhs) {
159  lhs /= rhs;
160  return lhs;
161 }
162 LinearExpr operator*(double lhs, LinearExpr rhs) {
163  rhs *= lhs;
164  return rhs;
165 }
166 
167 LinearRange::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 
177 LinearRange operator<=(const LinearExpr& lhs, const LinearExpr& rhs) {
178  return LinearRange(-std::numeric_limits<double>::infinity(), lhs - rhs, 0);
179 }
180 LinearRange operator==(const LinearExpr& lhs, const LinearExpr& rhs) {
181  return LinearRange(0, lhs - rhs, 0);
182 }
183 LinearRange operator>=(const LinearExpr& lhs, const LinearExpr& rhs) {
184  return LinearRange(0, lhs - rhs, std::numeric_limits<double>::infinity());
185 }
186 
187 } // namespace operations_research
operations_research::operator<=
LinearRange operator<=(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:177
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::LinearExpr
LinearExpr models a quantity that is linear in the decision variables (MPVariable) of an optimization...
Definition: linear_expr.h:114
operations_research::operator==
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:180
logging.h
operations_research::LinearExpr::offset
double offset() const
Definition: linear_expr.h:142
linear_expr.h
This file allows you to write natural code (like a mathematical equation) to model optimization probl...
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::operator-
LinearExpr operator-(LinearExpr lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:150
offset_
const int64 offset_
Definition: interval.cc:2076
DCHECK_NE
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
operations_research::LinearExpr::NotVar
static LinearExpr NotVar(LinearExpr var)
Returns 1-var.
Definition: linear_expr.cc:69
operations_research::LinearExpr::LinearExpr
LinearExpr()
Definition: linear_expr.cc:26
operations_research::LinearExpr::SolutionValue
double SolutionValue() const
Evaluates the value of this expression at the solution found.
Definition: linear_expr.cc:75
operations_research::operator<<
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
Definition: constraint_solver/assignment.cc:1089
operations_research::operator*
LinearExpr operator*(LinearExpr lhs, double rhs)
Definition: linear_expr.cc:154
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::LinearRange
An expression of the form:
Definition: linear_expr.h:192
operations_research::operator/
LinearExpr operator/(LinearExpr lhs, double rhs)
Definition: linear_expr.cc:158
operations_research::LinearExpr::operator/=
LinearExpr & operator/=(double rhs)
Definition: linear_expr.cc:61
operations_research::LinearExpr::operator-
LinearExpr operator-() const
Definition: linear_expr.cc:66
coef
int64 coef
Definition: expr_array.cc:1859
operations_research::LinearRange::LinearRange
LinearRange()
Definition: linear_expr.h:194
operations_research::MPVariable
The class for variables of a Mathematical Programming (MP) model.
Definition: linear_solver.h:1052
linear_solver.h
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
operations_research::operator>=
LinearRange operator>=(const LinearExpr &lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:183
operations_research::LinearExpr::operator-=
LinearExpr & operator-=(const LinearExpr &rhs)
Definition: linear_expr.cc:40
operations_research::LinearExpr::ToString
std::string ToString() const
A human readable representation of this.
Definition: linear_expr.cc:119
operations_research::operator+
LinearExpr operator+(LinearExpr lhs, const LinearExpr &rhs)
Definition: linear_expr.cc:146
operations_research::LinearExpr::operator*=
LinearExpr & operator*=(double rhs)
Definition: linear_expr.cc:48
operations_research::LinearExpr::operator+=
LinearExpr & operator+=(const LinearExpr &rhs)
Definition: linear_expr.cc:32