OR-Tools  8.2
gscip_ext.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
18
19namespace operations_research {
20
21namespace {
22
23std::string MaybeExtendName(const std::string& base_name,
24 const std::string& extension) {
25 if (base_name.empty()) {
26 return "";
27 }
28 return absl::StrCat(base_name, "/", extension);
29}
30
31} // namespace
32
33GScipLinearExpr::GScipLinearExpr(SCIP_VAR* variable) { terms[variable] = 1.0; }
34
35GScipLinearExpr::GScipLinearExpr(double offset) : offset(offset) {}
36
38 const GScipLinearExpr& right) {
39 left.offset -= right.offset;
40 for (const auto& term : right.terms) {
41 left.terms[term.first] -= term.second;
42 }
43 return left;
44}
45
47 expr.offset = -expr.offset;
48 for (auto& term : expr.terms) {
49 term.second = -term.second;
50 }
51 return expr;
52}
53
54// Returns the range -inf <= left.terms - right.terms <= right.offset -
55// left.offset
57 const GScipLinearExpr& right) {
58 GScipLinearExpr diff = GScipDifference(left, right);
59 GScipLinearRange result;
60 result.lower_bound = -std::numeric_limits<double>::infinity();
61 result.upper_bound = -diff.offset;
62 for (const auto& term : diff.terms) {
63 result.variables.push_back(term.first);
64 result.coefficients.push_back(term.second);
65 }
66 return result;
67}
68
69absl::Status GScipCreateAbs(GScip* gscip, SCIP_Var* x, SCIP_Var* abs_x,
70 const std::string& name) {
71 return GScipCreateMaximum(
72 gscip, GScipLinearExpr(abs_x),
74}
75
76absl::Status GScipCreateMaximum(GScip* gscip, const GScipLinearExpr& resultant,
77 const std::vector<GScipLinearExpr>& terms,
78 const std::string& name) {
79 // TODO(user): it may be better to write this in terms of the disjuntive
80 // constraint, we need to support disjunctions in gscip.h to do this.
81 //
82 // z_i in {0,1}, indicates if y = x_i
83 //
84 // x_i <= y
85 // z_i => y <= x_i
86 // \sum_i z_i == 1
87 std::vector<SCIP_VAR*> indicators;
88 for (int i = 0; i < terms.size(); ++i) {
89 auto z = gscip->AddVariable(0.0, 1.0, 0.0, GScipVarType::kInteger,
90 MaybeExtendName(name, absl::StrCat("z_", i)));
91 RETURN_IF_ERROR(z.status());
92 indicators.push_back(*z);
93 }
94
95 for (int i = 0; i < terms.size(); ++i) {
96 // x_i <= y
98 gscip
99 ->AddLinearConstraint(
100 GScipLe(terms.at(i), resultant),
101 MaybeExtendName(name, absl::StrCat("x_", i, "_le_y")))
102 .status());
103 // z_i => y <= x_i
104 {
105 GScipLinearRange y_less_x = GScipLe(resultant, terms.at(i));
106 CHECK_EQ(y_less_x.lower_bound, -std::numeric_limits<double>::infinity());
108 ind.indicator_variable = indicators.at(i);
109 ind.variables = y_less_x.variables;
110 ind.coefficients = y_less_x.coefficients;
111 ind.upper_bound = y_less_x.upper_bound;
113 gscip
114 ->AddIndicatorConstraint(
115 ind, MaybeExtendName(
116 name, absl::StrCat("y_le__x_", i, "_if_z_", i)))
117 .status());
118 }
119 }
120
121 // sum_i z_i = 1.
122 GScipLinearRange z_use;
123 z_use.upper_bound = 1.0;
124 z_use.lower_bound = 1.0;
125 z_use.variables = indicators;
126 z_use.coefficients = std::vector<double>(indicators.size(), 1.0);
127
128 return gscip->AddLinearConstraint(z_use, MaybeExtendName(name, "one_z"))
129 .status();
130}
131
132absl::Status GScipCreateMinimum(GScip* gscip, const GScipLinearExpr& resultant,
133 const std::vector<GScipLinearExpr>& terms,
134 const std::string& name) {
135 std::vector<GScipLinearExpr> negated_terms;
136 negated_terms.reserve(terms.size());
137 for (const GScipLinearExpr& e : terms) {
138 negated_terms.push_back(GScipNegate(e));
139 }
140 return GScipCreateMaximum(gscip, GScipNegate(resultant), negated_terms, name);
141}
142
144 GScip* gscip, std::vector<SCIP_Var*> quadratic_variables1,
145 std::vector<SCIP_Var*> quadratic_variables2,
146 std::vector<double> quadratic_coefficients, const std::string& name) {
147 constexpr double kInf = std::numeric_limits<double>::infinity();
148 auto obj_term =
149 gscip->AddVariable(-kInf, kInf, 1.0, GScipVarType::kContinuous,
150 MaybeExtendName(name, "obj"));
151 RETURN_IF_ERROR(obj_term.status());
153 range.quadratic_variables1 = quadratic_variables1;
154 range.quadratic_variables2 = quadratic_variables2;
155 range.quadratic_coefficients = quadratic_coefficients;
156 range.linear_coefficients = {-1.0};
157 range.linear_variables = {*obj_term};
158 if (gscip->ObjectiveIsMaximize()) {
159 // maximize z
160 // z <= Q(x, y)
161 // => 0 <= Q(x, y) - z <= inf
162 range.lower_bound = 0.0;
163 } else {
164 // minimize z
165 // z >= Q(x, y)
166 // => 0 >= Q(x, y) - z >= -inf
167 range.upper_bound = 0.0;
168 }
169 return gscip->AddQuadraticConstraint(range, MaybeExtendName(name, "cons"))
170 .status();
171}
172
174 GScip* gscip, const GScipIndicatorRangeConstraint& indicator_range,
175 const std::string& name, const GScipConstraintOptions& options) {
176 if (std::isfinite(indicator_range.range.upper_bound)) {
177 GScipIndicatorConstraint ub_constraint;
178 ub_constraint.upper_bound = indicator_range.range.upper_bound;
179 ub_constraint.variables = indicator_range.range.variables;
180 ub_constraint.coefficients = indicator_range.range.coefficients;
181 ub_constraint.indicator_variable = indicator_range.indicator_variable;
182 ub_constraint.negate_indicator = indicator_range.negate_indicator;
183 RETURN_IF_ERROR(gscip
184 ->AddIndicatorConstraint(
185 ub_constraint, MaybeExtendName(name, "ub"), options)
186 .status());
187 }
188 if (std::isfinite(indicator_range.range.lower_bound)) {
189 // want z -> lb <= a * x
190 // <=> z -> -lb >= -a * x
191 GScipIndicatorConstraint lb_constraint;
192 lb_constraint.upper_bound = -indicator_range.range.lower_bound;
193 lb_constraint.variables = indicator_range.range.variables;
194 for (const double c : indicator_range.range.coefficients) {
195 lb_constraint.coefficients.push_back(-c);
196 }
197 lb_constraint.indicator_variable = indicator_range.indicator_variable;
198 lb_constraint.negate_indicator = indicator_range.negate_indicator;
199 RETURN_IF_ERROR(gscip
200 ->AddIndicatorConstraint(
201 lb_constraint, MaybeExtendName(name, "lb"), options)
202 .status());
203 }
204 return absl::OkStatus();
205}
206
207} // namespace operations_research
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
absl::StatusOr< SCIP_VAR * > AddVariable(double lb, double ub, double obj_coef, GScipVarType var_type, const std::string &var_name="", const GScipVariableOptions &options=DefaultGScipVariableOptions())
Definition: gscip.cc:280
absl::StatusOr< SCIP_CONS * > AddLinearConstraint(const GScipLinearRange &range, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:312
absl::StatusOr< SCIP_CONS * > AddQuadraticConstraint(const GScipQuadraticRange &range, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:338
const std::string name
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
GScipLinearRange GScipLe(const GScipLinearExpr left, const GScipLinearExpr &right)
Definition: gscip_ext.cc:56
GScipLinearExpr GScipDifference(GScipLinearExpr left, const GScipLinearExpr &right)
Definition: gscip_ext.cc:37
absl::Status GScipCreateMaximum(GScip *gscip, const GScipLinearExpr &resultant, const std::vector< GScipLinearExpr > &terms, const std::string &name)
Definition: gscip_ext.cc:76
absl::Status GScipCreateAbs(GScip *gscip, SCIP_Var *x, SCIP_Var *abs_x, const std::string &name)
Definition: gscip_ext.cc:69
absl::Status GScipAddQuadraticObjectiveTerm(GScip *gscip, std::vector< SCIP_Var * > quadratic_variables1, std::vector< SCIP_Var * > quadratic_variables2, std::vector< double > quadratic_coefficients, const std::string &name)
Definition: gscip_ext.cc:143
absl::Status GScipCreateMinimum(GScip *gscip, const GScipLinearExpr &resultant, const std::vector< GScipLinearExpr > &terms, const std::string &name)
Definition: gscip_ext.cc:132
absl::Status GScipCreateIndicatorRange(GScip *gscip, const GScipIndicatorRangeConstraint &indicator_range, const std::string &name, const GScipConstraintOptions &options)
Definition: gscip_ext.cc:173
GScipLinearExpr GScipNegate(GScipLinearExpr expr)
Definition: gscip_ext.cc:46
#define RETURN_IF_ERROR(expr)
Definition: status_macros.h:27
std::vector< SCIP_Var * > variables
Definition: gscip.h:428
absl::flat_hash_map< SCIP_VAR *, double > terms
Definition: gscip_ext.h:47
std::vector< SCIP_VAR * > variables
Definition: gscip.h:95
std::vector< double > coefficients
Definition: gscip.h:96
std::vector< SCIP_Var * > quadratic_variables1
Definition: gscip.h:388
std::vector< SCIP_Var * > quadratic_variables2
Definition: gscip.h:389
std::vector< SCIP_Var * > linear_variables
Definition: gscip.h:375
std::vector< double > linear_coefficients
Definition: gscip.h:376
std::vector< double > quadratic_coefficients
Definition: gscip.h:390