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"
43using StringPiece = ::re2::StringPiece;
44using ::absl::StatusOr;
59bool TokenIsBound(TokenType token_type) {
60 if (token_type == TokenType::VALUE || token_type == TokenType::INF) {
72 ABSL_MUST_USE_RESULT
bool Parse(absl::string_view model, LinearProgram* lp);
75 bool ParseEmptyLine(StringPiece line);
76 bool ParseObjective(StringPiece objective);
77 bool ParseIntegerVariablesList(StringPiece line);
79 TokenType ConsumeToken(StringPiece* sp);
88 std::string consumed_name_;
91 std::set<ColIndex> bounded_variables_;
94bool LPParser::Parse(absl::string_view model,
LinearProgram* lp) {
96 bounded_variables_.clear();
99 std::vector<StringPiece> lines =
100 absl::StrSplit(model,
';', absl::SkipEmpty());
101 bool has_objective =
false;
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;
116 if (bounded_variables_.find(col) == bounded_variables_.end()) {
125bool LPParser::ParseEmptyLine(StringPiece line) {
126 if (ConsumeToken(&line) == TokenType::END)
return true;
130bool LPParser::ParseObjective(StringPiece objective) {
132 if (ConsumeToken(&objective) != TokenType::NAME)
return false;
133 if (absl::EqualsIgnoreCase(consumed_name_,
"min")) {
135 }
else if (absl::EqualsIgnoreCase(consumed_name_,
"max")) {
142 TokenType token_type = ConsumeToken(&objective);
143 if (token_type == TokenType::VALUE) {
145 token_type = ConsumeToken(&objective);
151 while (token_type == TokenType::ADDAND) {
155 token_type = ConsumeToken(&objective);
157 return token_type == TokenType::END;
160bool LPParser::ParseIntegerVariablesList(StringPiece line) {
162 bool binary_list =
false;
163 if (ConsumeToken(&line) != TokenType::NAME)
return false;
164 if (absl::EqualsIgnoreCase(consumed_name_,
"bin")) {
166 }
else if (!absl::EqualsIgnoreCase(consumed_name_,
"int")) {
171 TokenType token_type = ConsumeToken(&line);
172 while (token_type == TokenType::ADDAND) {
173 if (consumed_coeff_ != 1.0)
return false;
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);
184 if (token_type != TokenType::END)
return false;
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();
196 if (parsed_constraint.name.empty() &&
197 parsed_constraint.coefficients.size() == 1 &&
198 parsed_constraint.coefficients[0] == 1.0) {
201 if (!SetVariableBounds(col, parsed_constraint.lower_bound,
202 parsed_constraint.upper_bound)) {
206 const RowIndex num_constraints_before_adding_variable =
214 parsed_constraint.name.empty()
217 if (lp_->
num_constraints() == num_constraints_before_adding_variable) {
219 LOG(INFO) <<
"Two constraints with the same name: "
220 << parsed_constraint.name;
224 parsed_constraint.upper_bound)) {
228 parsed_constraint.upper_bound);
229 for (
int i = 0;
i < parsed_constraint.variable_names.size(); ++
i) {
230 const ColIndex variable =
232 lp_->
SetCoefficient(row, variable, parsed_constraint.coefficients[i]);
241constexpr bool dependent_false =
false;
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);
250 static_assert(dependent_false<T>,
"Unsupported fractional type");
257 if (bounded_variables_.find(col) == bounded_variables_.end()) {
259 bounded_variables_.insert(col);
270TokenType ConsumeToken(StringPiece* sp, std::string* consumed_name,
272 DCHECK(consumed_name !=
nullptr);
273 DCHECK(consumed_coeff !=
nullptr);
277 static const LazyRE2 kEndPattern = {R
"(\s*)"};
280 if (sp->empty() || RE2::FullMatch(*sp, *kEndPattern)) {
281 return TokenType::END;
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;
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;
302 static const LazyRE2 kComaPattern = {R
"(\s*\,)"};
303 if (RE2::Consume(sp, *kComaPattern))
return TokenType::COMA;
308 static const LazyRE2 kSignPattern = {R
"(\s*([-+]{1}))"};
309 while (RE2::Consume(sp, *kSignPattern, &sign)) {
310 if (sign ==
"-") minus_count++;
314 static const LazyRE2 kInfPattern = {R
"((?i)\s*inf)"};
315 if (RE2::Consume(sp, *kInfPattern)) {
317 return TokenType::INF;
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)) {
329 LOG(ERROR) <<
"Text: " << coeff <<
" was matched by RE2 to be "
330 <<
"a floating point number, but absl::SimpleAtod() failed.";
331 return TokenType::ERROR;
334 VLOG(1) <<
"Value " << coeff <<
" treated as infinite.";
335 return TokenType::INF;
339 *consumed_coeff = 1.0;
341 if (minus_count % 2 == 1) *consumed_coeff *= -1.0;
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;
355 return TokenType::ERROR;
358TokenType LPParser::ConsumeToken(StringPiece* sp) {
359 using ::operations_research::glop::ConsumeToken;
360 return ConsumeToken(sp, &consumed_name_, &consumed_coeff_);
368 StringPiece constraint_copy{constraint};
369 std::string consumed_name;
371 if (ConsumeToken(&constraint_copy, &consumed_name, &consumed_coeff) ==
373 parsed_constraint.
name = consumed_name;
374 constraint = constraint_copy;
379 TokenType left_sign(TokenType::END);
380 TokenType right_sign(TokenType::END);
381 absl::flat_hash_set<std::string> used_variables;
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.");
394 token_type = ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
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));
403 used_variables.insert(consumed_name);
405 parsed_constraint.
coefficients.push_back(consumed_coeff);
406 token_type = ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
410 if (left_sign == TokenType::SIGN_EQ && token_type != TokenType::END) {
411 return absl::InvalidArgumentError(
412 "Equality constraints can have only one bound.");
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.");
424 if (left_sign != TokenType::END && right_sign == TokenType::SIGN_EQ) {
425 return absl::InvalidArgumentError(
426 "Equality constraints can have only one bound.");
429 ConsumeToken(&constraint, &consumed_name, &consumed_coeff))) {
430 return absl::InvalidArgumentError(
"Bound value was expected.");
432 right_bound = consumed_coeff;
433 if (ConsumeToken(&constraint, &consumed_name, &consumed_coeff) !=
435 return absl::InvalidArgumentError(
436 absl::StrCat(
"End of input was expected, found: ", constraint));
441 if (left_sign == TokenType::END && right_sign == TokenType::END) {
442 return absl::InvalidArgumentError(
"The input constraint was empty.");
448 if (left_sign == TokenType::SIGN_LE || left_sign == TokenType::SIGN_EQ) {
451 if (left_sign == TokenType::SIGN_GE || left_sign == TokenType::SIGN_EQ) {
454 if (right_sign == TokenType::SIGN_LE || right_sign == TokenType::SIGN_EQ) {
456 std::min(parsed_constraint.
upper_bound, right_bound);
458 if (right_sign == TokenType::SIGN_GE || right_sign == TokenType::SIGN_EQ) {
460 std::max(parsed_constraint.
lower_bound, right_bound);
462 return parsed_constraint;
467 return parser.Parse(model, lp);
475 return absl::InvalidArgumentError(
"Parsing error, see LOGs for details.");
477 MPModelProto model_proto;
const DenseRow & objective_coefficients() const
Returns the objective coefficients (or cost) of variables as a row vector.
void Clear()
Clears, i.e. reset the object to its initial value.
void SetObjectiveOffset(Fractional objective_offset)
void SetObjectiveCoefficient(ColIndex col, Fractional value)
const DenseRow & variable_lower_bounds() const
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
void SetVariableType(ColIndex col, VariableType type)
Set the type of the variable.
ColIndex FindOrCreateVariable(absl::string_view variable_id)
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Defines the coefficient for col / row.
const DenseRow & variable_upper_bounds() const
RowIndex CreateNewConstraint()
ColIndex num_variables() const
Returns the number of variables.
RowIndex num_constraints() const
Returns the number of constraints.
RowIndex FindOrCreateConstraint(absl::string_view constraint_id)
void SetMaximizationProblem(bool maximize)
bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound)
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.
StatusOr< ParsedConstraint > ParseConstraint(absl::string_view constraint)
bool IsFinite(Fractional value)
constexpr Fractional kInfinity
Infinity for type Fractional.
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.
std::string name
The name of the constraint. Empty if the constraint has no name.
std::vector< std::string > variable_names
std::vector< Fractional > coefficients