Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
lp_parser.cc
Go to the documentation of this file.
1// Copyright 2010-2025 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 <algorithm>
17#include <set>
18#include <string>
19#include <vector>
20
21#include "absl/base/attributes.h"
22#include "absl/container/flat_hash_set.h"
23#include "absl/log/check.h"
24#include "absl/log/log.h"
25#include "absl/status/status.h"
26#include "absl/status/statusor.h"
27#include "absl/strings/match.h"
28#include "absl/strings/numbers.h"
29#include "absl/strings/str_cat.h"
30#include "absl/strings/str_split.h"
31#include "absl/strings/string_view.h"
32#include "ortools/linear_solver/linear_solver.pb.h"
36#include "re2/re2.h"
37
38namespace operations_research {
39namespace glop {
40
41namespace {
42
43using StringPiece = ::re2::StringPiece;
44using ::absl::StatusOr;
45
46enum class TokenType {
47 ERROR,
48 END,
49 ADDAND,
50 VALUE,
51 INF,
52 NAME,
53 SIGN_LE,
54 SIGN_EQ,
55 SIGN_GE,
56 COMA,
57};
58
59bool TokenIsBound(TokenType token_type) {
60 if (token_type == TokenType::VALUE || token_type == TokenType::INF) {
61 return true;
62 }
63 return false;
64}
65
66// Not thread safe.
67class LPParser {
68 public:
69 // Accepts the string in LP file format (used by LinearProgram::Dump()).
70 // On success, populates the linear program *lp and returns true. Otherwise,
71 // returns false and leaves *lp in an unspecified state.
72 ABSL_MUST_USE_RESULT bool Parse(absl::string_view model, LinearProgram* lp);
73
74 private:
75 bool ParseEmptyLine(StringPiece line);
76 bool ParseObjective(StringPiece objective);
77 bool ParseIntegerVariablesList(StringPiece line);
78 bool ParseConstraint(StringPiece constraint);
79 TokenType ConsumeToken(StringPiece* sp);
80 bool SetVariableBounds(ColIndex col, Fractional lb, Fractional ub);
81
82 // Linear program populated by the Parse() method. Not owned.
83 LinearProgram* lp_;
84
85 // Contains the last consumed coefficient and name. The name can be the
86 // optimization direction, a constraint name, or a variable name.
87 Fractional consumed_coeff_;
88 std::string consumed_name_;
89
90 // To remember whether the variable bounds had already been set.
91 std::set<ColIndex> bounded_variables_;
92};
93
94bool LPParser::Parse(absl::string_view model, LinearProgram* lp) {
95 lp_ = lp;
96 bounded_variables_.clear();
97 lp_->Clear();
98
99 std::vector<StringPiece> lines =
100 absl::StrSplit(model, ';', absl::SkipEmpty());
101 bool has_objective = false;
102
103 for (StringPiece line : lines) {
104 if (!has_objective && ParseObjective(line)) {
105 has_objective = true;
106 } else if (!ParseConstraint(line) && !ParseIntegerVariablesList(line) &&
107 !ParseEmptyLine(line)) {
108 LOG(INFO) << "Error in line: " << line;
109 return false;
110 }
111 }
112
113 // Bound the non-bounded variables between -inf and +inf. We need to do this,
114 // as glop bounds a variable by default between 0 and +inf.
115 for (ColIndex col(0); col < lp_->num_variables(); ++col) {
116 if (bounded_variables_.find(col) == bounded_variables_.end()) {
117 lp_->SetVariableBounds(col, -kInfinity, +kInfinity);
118 }
119 }
120
121 lp_->CleanUp();
122 return true;
123}
124
125bool LPParser::ParseEmptyLine(StringPiece line) {
126 if (ConsumeToken(&line) == TokenType::END) return true;
127 return false;
128}
129
130bool LPParser::ParseObjective(StringPiece objective) {
131 // Get the required optimization direction.
132 if (ConsumeToken(&objective) != TokenType::NAME) return false;
133 if (absl::EqualsIgnoreCase(consumed_name_, "min")) {
134 lp_->SetMaximizationProblem(false);
135 } else if (absl::EqualsIgnoreCase(consumed_name_, "max")) {
136 lp_->SetMaximizationProblem(true);
137 } else {
138 return false;
139 }
140
141 // Get the optional offset.
142 TokenType token_type = ConsumeToken(&objective);
143 if (token_type == TokenType::VALUE) {
144 lp_->SetObjectiveOffset(consumed_coeff_);
145 token_type = ConsumeToken(&objective);
146 } else {
147 lp_->SetObjectiveOffset(0.0);
148 }
149
150 // Get the addands.
151 while (token_type == TokenType::ADDAND) {
152 const ColIndex col = lp_->FindOrCreateVariable(consumed_name_);
153 if (lp_->objective_coefficients()[col] != 0.0) return false;
154 lp_->SetObjectiveCoefficient(col, consumed_coeff_);
155 token_type = ConsumeToken(&objective);
156 }
157 return token_type == TokenType::END;
158}
159
160bool LPParser::ParseIntegerVariablesList(StringPiece line) {
161 // Get the required "int" or "bin" keyword.
162 bool binary_list = false;
163 if (ConsumeToken(&line) != TokenType::NAME) return false;
164 if (absl::EqualsIgnoreCase(consumed_name_, "bin")) {
165 binary_list = true;
166 } else if (!absl::EqualsIgnoreCase(consumed_name_, "int")) {
167 return false;
168 }
169
170 // Get the list of integer variables, separated by optional comas.
171 TokenType token_type = ConsumeToken(&line);
172 while (token_type == TokenType::ADDAND) {
173 if (consumed_coeff_ != 1.0) return false;
174 const ColIndex col = lp_->FindOrCreateVariable(consumed_name_);
175 lp_->SetVariableType(col, LinearProgram::VariableType::INTEGER);
176 if (binary_list && !SetVariableBounds(col, 0.0, 1.0)) return false;
177 token_type = ConsumeToken(&line);
178 if (token_type == TokenType::COMA) {
179 token_type = ConsumeToken(&line);
180 }
181 }
182
183 // The last token must be END.
184 if (token_type != TokenType::END) return false;
185 return true;
186}
187
188bool LPParser::ParseConstraint(StringPiece constraint) {
189 const StatusOr<ParsedConstraint> parsed_constraint_or_status =
191 if (!parsed_constraint_or_status.ok()) return false;
192 const ParsedConstraint& parsed_constraint =
193 parsed_constraint_or_status.value();
194
195 // Set the variables bounds without creating new constraints.
196 if (parsed_constraint.name.empty() &&
197 parsed_constraint.coefficients.size() == 1 &&
198 parsed_constraint.coefficients[0] == 1.0) {
199 const ColIndex col =
200 lp_->FindOrCreateVariable(parsed_constraint.variable_names[0]);
201 if (!SetVariableBounds(col, parsed_constraint.lower_bound,
202 parsed_constraint.upper_bound)) {
203 return false;
204 }
205 } else {
206 const RowIndex num_constraints_before_adding_variable =
207 lp_->num_constraints();
208 // The constaint has a name, or there are more than variable, or the
209 // coefficient is not 1. Thus, create and fill a new constraint.
210 // We don't use SetConstraintName() because constraints named that way
211 // cannot be found via FindOrCreateConstraint() (see comment on
212 // SetConstraintName()), which can be useful for tests using ParseLP.
213 const RowIndex row =
214 parsed_constraint.name.empty()
215 ? lp_->CreateNewConstraint()
216 : lp_->FindOrCreateConstraint(parsed_constraint.name);
217 if (lp_->num_constraints() == num_constraints_before_adding_variable) {
218 // No constraints were added, meaning we found one.
219 LOG(INFO) << "Two constraints with the same name: "
220 << parsed_constraint.name;
221 return false;
222 }
223 if (!AreBoundsValid(parsed_constraint.lower_bound,
224 parsed_constraint.upper_bound)) {
225 return false;
226 }
227 lp_->SetConstraintBounds(row, parsed_constraint.lower_bound,
228 parsed_constraint.upper_bound);
229 for (int i = 0; i < parsed_constraint.variable_names.size(); ++i) {
230 const ColIndex variable =
231 lp_->FindOrCreateVariable(parsed_constraint.variable_names[i]);
232 lp_->SetCoefficient(row, variable, parsed_constraint.coefficients[i]);
233 }
234 }
235 return true;
236}
237
238namespace {
239
240template <class>
241constexpr bool dependent_false = false; // workaround before CWG2518/P2593R1
242
243template <typename T>
244bool SimpleAtoFractional(absl::string_view str, T* value) {
245 if constexpr (std::is_same_v<T, double>) {
246 return absl::SimpleAtod(str, value);
247 } else if constexpr (std::is_same_v<T, float>) {
248 return absl::SimpleAtof(str, value);
249 } else {
250 static_assert(dependent_false<T>, "Unsupported fractional type");
251 return false;
252 }
253}
254} // namespace
255
256bool LPParser::SetVariableBounds(ColIndex col, Fractional lb, Fractional ub) {
257 if (bounded_variables_.find(col) == bounded_variables_.end()) {
258 // The variable was not bounded yet, thus reset its bounds.
259 bounded_variables_.insert(col);
260 lp_->SetVariableBounds(col, -kInfinity, kInfinity);
261 }
262 // Set the bounds only if their stricter and valid.
263 lb = std::max(lb, lp_->variable_lower_bounds()[col]);
264 ub = std::min(ub, lp_->variable_upper_bounds()[col]);
265 if (!AreBoundsValid(lb, ub)) return false;
266 lp_->SetVariableBounds(col, lb, ub);
267 return true;
268}
269
270TokenType ConsumeToken(StringPiece* sp, std::string* consumed_name,
271 Fractional* consumed_coeff) {
272 DCHECK(consumed_name != nullptr);
273 DCHECK(consumed_coeff != nullptr);
274 // We use LazyRE2 everywhere so that all the patterns are just compiled once
275 // when they are needed for the first time. This speed up the code
276 // significantly. Note that the use of LazyRE2 is thread safe.
277 static const LazyRE2 kEndPattern = {R"(\s*)"};
278
279 // There is nothing more to consume.
280 if (sp->empty() || RE2::FullMatch(*sp, *kEndPattern)) {
281 return TokenType::END;
282 }
283
284 // Return NAME if the next token is a line name, or integer variable list
285 // indicator.
286 static const LazyRE2 kNamePattern1 = {R"(\s*(\w[\w[\]]*):)"};
287 static const LazyRE2 kNamePattern2 = {R"((?i)\s*(int)\s*:?)"};
288 static const LazyRE2 kNamePattern3 = {R"((?i)\s*(bin)\s*:?)"};
289 if (RE2::Consume(sp, *kNamePattern1, consumed_name)) return TokenType::NAME;
290 if (RE2::Consume(sp, *kNamePattern2, consumed_name)) return TokenType::NAME;
291 if (RE2::Consume(sp, *kNamePattern3, consumed_name)) return TokenType::NAME;
292
293 // Return SIGN_* if the next token is a relation sign.
294 static const LazyRE2 kLePattern = {R"(\s*<=?)"};
295 if (RE2::Consume(sp, *kLePattern)) return TokenType::SIGN_LE;
296 static const LazyRE2 kEqPattern = {R"(\s*=)"};
297 if (RE2::Consume(sp, *kEqPattern)) return TokenType::SIGN_EQ;
298 static const LazyRE2 kGePattern = {R"(\s*>=?)"};
299 if (RE2::Consume(sp, *kGePattern)) return TokenType::SIGN_GE;
300
301 // Return COMA if the next token is a coma.
302 static const LazyRE2 kComaPattern = {R"(\s*\,)"};
303 if (RE2::Consume(sp, *kComaPattern)) return TokenType::COMA;
304
305 // Consume all plus and minus signs.
306 std::string sign;
307 int minus_count = 0;
308 static const LazyRE2 kSignPattern = {R"(\s*([-+]{1}))"};
309 while (RE2::Consume(sp, *kSignPattern, &sign)) {
310 if (sign == "-") minus_count++;
311 }
312
313 // Return INF if the next token is an infinite value.
314 static const LazyRE2 kInfPattern = {R"((?i)\s*inf)"};
315 if (RE2::Consume(sp, *kInfPattern)) {
316 *consumed_coeff = minus_count % 2 == 0 ? kInfinity : -kInfinity;
317 return TokenType::INF;
318 }
319
320 // Check if the next token is a value. If it is infinite return INF.
321 std::string coeff;
322 bool has_value = false;
323 static const LazyRE2 kValuePattern = {
324 R"(\s*([0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?))"};
325 if (RE2::Consume(sp, *kValuePattern, &coeff)) {
326 if (!SimpleAtoFractional(coeff, consumed_coeff)) {
327 // Note: If absl::SimpleAtod(), Consume(), and kValuePattern are correct,
328 // this should never happen.
329 LOG(ERROR) << "Text: " << coeff << " was matched by RE2 to be "
330 << "a floating point number, but absl::SimpleAtod() failed.";
331 return TokenType::ERROR;
332 }
333 if (!IsFinite(*consumed_coeff)) {
334 VLOG(1) << "Value " << coeff << " treated as infinite.";
335 return TokenType::INF;
336 }
337 has_value = true;
338 } else {
339 *consumed_coeff = 1.0;
340 }
341 if (minus_count % 2 == 1) *consumed_coeff *= -1.0;
342
343 // Return ADDAND (coefficient and name) if the next token is a variable name.
344 // Otherwise, if we found a finite value previously, return VALUE.
345 // Otherwise, return ERROR.
346 std::string multiplication;
347 static const LazyRE2 kAddandPattern = {R"(\s*(\*?)\s*([a-zA-Z_)][\w[\])]*))"};
348 if (RE2::Consume(sp, *kAddandPattern, &multiplication, consumed_name)) {
349 if (!multiplication.empty() && !has_value) return TokenType::ERROR;
350 return TokenType::ADDAND;
351 } else if (has_value) {
352 return TokenType::VALUE;
353 }
354
355 return TokenType::ERROR;
356}
357
358TokenType LPParser::ConsumeToken(StringPiece* sp) {
359 using ::operations_research::glop::ConsumeToken;
360 return ConsumeToken(sp, &consumed_name_, &consumed_coeff_);
361}
362
363} // namespace
364
365StatusOr<ParsedConstraint> ParseConstraint(absl::string_view constraint) {
366 ParsedConstraint parsed_constraint;
367 // Get the name, if present.
368 StringPiece constraint_copy{constraint};
369 std::string consumed_name;
370 Fractional consumed_coeff;
371 if (ConsumeToken(&constraint_copy, &consumed_name, &consumed_coeff) ==
372 TokenType::NAME) {
373 parsed_constraint.name = consumed_name;
374 constraint = constraint_copy;
375 }
376
377 Fractional left_bound;
378 Fractional right_bound;
379 TokenType left_sign(TokenType::END);
380 TokenType right_sign(TokenType::END);
381 absl::flat_hash_set<std::string> used_variables;
382
383 // Get the left bound and the relation sign, if present.
384 TokenType token_type =
385 ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
386 if (TokenIsBound(token_type)) {
387 left_bound = consumed_coeff;
388 left_sign = ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
389 if (left_sign != TokenType::SIGN_LE && left_sign != TokenType::SIGN_EQ &&
390 left_sign != TokenType::SIGN_GE) {
391 return absl::InvalidArgumentError(
392 "Expected an equality/inequality sign for the left bound.");
393 }
394 token_type = ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
395 }
396
397 // Get the addands, if present.
398 while (token_type == TokenType::ADDAND) {
399 if (used_variables.contains(consumed_name)) {
400 return absl::InvalidArgumentError(
401 absl::StrCat("Duplicate variable name: ", consumed_name));
402 }
403 used_variables.insert(consumed_name);
404 parsed_constraint.variable_names.push_back(consumed_name);
405 parsed_constraint.coefficients.push_back(consumed_coeff);
406 token_type = ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
407 }
408
409 // If the left sign was EQ there can be no right side.
410 if (left_sign == TokenType::SIGN_EQ && token_type != TokenType::END) {
411 return absl::InvalidArgumentError(
412 "Equality constraints can have only one bound.");
413 }
414
415 // Get the right sign and the right bound, if present.
416 if (token_type != TokenType::END) {
417 right_sign = token_type;
418 if (right_sign != TokenType::SIGN_LE && right_sign != TokenType::SIGN_EQ &&
419 right_sign != TokenType::SIGN_GE) {
420 return absl::InvalidArgumentError(
421 "Expected an equality/inequality sign for the right bound.");
422 }
423 // If the right sign is EQ, there can be no left side.
424 if (left_sign != TokenType::END && right_sign == TokenType::SIGN_EQ) {
425 return absl::InvalidArgumentError(
426 "Equality constraints can have only one bound.");
427 }
428 if (!TokenIsBound(
429 ConsumeToken(&constraint, &consumed_name, &consumed_coeff))) {
430 return absl::InvalidArgumentError("Bound value was expected.");
431 }
432 right_bound = consumed_coeff;
433 if (ConsumeToken(&constraint, &consumed_name, &consumed_coeff) !=
434 TokenType::END) {
435 return absl::InvalidArgumentError(
436 absl::StrCat("End of input was expected, found: ", constraint));
437 }
438 }
439
440 // There was no constraint!
441 if (left_sign == TokenType::END && right_sign == TokenType::END) {
442 return absl::InvalidArgumentError("The input constraint was empty.");
443 }
444
445 // Calculate bounds to set.
446 parsed_constraint.lower_bound = -kInfinity;
447 parsed_constraint.upper_bound = kInfinity;
448 if (left_sign == TokenType::SIGN_LE || left_sign == TokenType::SIGN_EQ) {
449 parsed_constraint.lower_bound = left_bound;
450 }
451 if (left_sign == TokenType::SIGN_GE || left_sign == TokenType::SIGN_EQ) {
452 parsed_constraint.upper_bound = left_bound;
453 }
454 if (right_sign == TokenType::SIGN_LE || right_sign == TokenType::SIGN_EQ) {
455 parsed_constraint.upper_bound =
456 std::min(parsed_constraint.upper_bound, right_bound);
457 }
458 if (right_sign == TokenType::SIGN_GE || right_sign == TokenType::SIGN_EQ) {
459 parsed_constraint.lower_bound =
460 std::max(parsed_constraint.lower_bound, right_bound);
461 }
462 return parsed_constraint;
463}
464
465bool ParseLp(absl::string_view model, LinearProgram* lp) {
466 LPParser parser;
467 return parser.Parse(model, lp);
468}
469
470} // namespace glop
471
472absl::StatusOr<MPModelProto> ModelProtoFromLpFormat(absl::string_view model) {
474 if (!ParseLp(model, &lp)) {
475 return absl::InvalidArgumentError("Parsing error, see LOGs for details.");
476 }
477 MPModelProto model_proto;
478 LinearProgramToMPModelProto(lp, &model_proto);
479 return model_proto;
480}
481
482} // namespace operations_research
const DenseRow & objective_coefficients() const
Returns the objective coefficients (or cost) of variables as a row vector.
Definition lp_data.h:231
void Clear()
Clears, i.e. reset the object to its initial value.
Definition lp_data.cc:143
void SetObjectiveOffset(Fractional objective_offset)
Definition lp_data.cc:340
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition lp_data.cc:335
const DenseRow & variable_lower_bounds() const
Definition lp_data.h:237
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition lp_data.cc:258
void SetVariableType(ColIndex col, VariableType type)
Set the type of the variable.
Definition lp_data.cc:245
ColIndex FindOrCreateVariable(absl::string_view variable_id)
Definition lp_data.cc:214
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition lp_data.cc:318
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Defines the coefficient for col / row.
Definition lp_data.cc:326
const DenseRow & variable_upper_bounds() const
Definition lp_data.h:240
ColIndex num_variables() const
Returns the number of variables.
Definition lp_data.h:213
RowIndex num_constraints() const
Returns the number of constraints.
Definition lp_data.h:216
RowIndex FindOrCreateConstraint(absl::string_view constraint_id)
Definition lp_data.cc:227
void SetMaximizationProblem(bool maximize)
Definition lp_data.cc:352
bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound)
Definition lp_data.h:707
void LinearProgramToMPModelProto(const LinearProgram &input, MPModelProto *output)
Converts a LinearProgram to a MPModelProto.
bool ParseLp(absl::string_view model, LinearProgram *lp)
Like ModelProtoFromLpFormat(), but outputs a glop::LinearProgram.
Definition lp_parser.cc:465
StatusOr< ParsedConstraint > ParseConstraint(absl::string_view constraint)
Definition lp_parser.cc:365
bool IsFinite(Fractional value)
Definition lp_types.h:94
constexpr Fractional kInfinity
Infinity for type Fractional.
Definition lp_types.h:87
In SWIG mode, we don't want anything besides these top-level includes.
absl::StatusOr< MPModelProto > ModelProtoFromLpFormat(absl::string_view model)
This calls ParseLp() under the hood. See below.
Definition lp_parser.cc:472
std::string name
The name of the constraint. Empty if the constraint has no name.
Definition lp_parser.h:102
std::vector< std::string > variable_names
Definition lp_parser.h:105
std::vector< Fractional > coefficients
Definition lp_parser.h:109