OR-Tools  8.2
mps_reader.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 "absl/status/status.h"
17#include "absl/status/statusor.h"
18#include "absl/strings/match.h"
19#include "absl/strings/str_split.h"
22
23namespace operations_research {
24namespace glop {
25
27 public:
29
30 // Parses instance from a file. We currently support LinearProgram and
31 // MpModelProto for the Data type, but it should be easy to add more.
32 template <class Data>
33 absl::Status ParseFile(const std::string& file_name, Data* data,
34 MPSReader::Form form);
35
36 private:
37 // Number of fields in one line of MPS file.
38 static const int kNumFields;
39
40 // Starting positions of each of the fields for fixed format.
41 static const int kFieldStartPos[];
42
43 // Lengths of each of the fields for fixed format.
44 static const int kFieldLength[];
45
46 // Positions where there should be spaces for fixed format.
47 static const int kSpacePos[];
48
49 // Resets the object to its initial value before reading a new file.
50 void Reset();
51
52 // Displays some information on the last loaded file.
53 void DisplaySummary();
54
55 // Get each field for a given line.
56 absl::Status SplitLineIntoFields();
57
58 // Returns true if the line matches the fixed format.
59 bool IsFixedFormat();
60
61 // Get the first word in a line.
62 std::string GetFirstWord() const;
63
64 // Returns true if the line contains a comment (starting with '*') or
65 // if it is a blank line.
66 bool IsCommentOrBlank() const;
67
68 // Helper function that returns fields_[offset + index].
69 const std::string& GetField(int offset, int index) const {
70 return fields_[offset + index];
71 }
72
73 // Returns the offset at which to start the parsing of fields_.
74 // If in fixed form, the offset is 0.
75 // If in fixed form and the number of fields is odd, it is 1,
76 // otherwise it is 0.
77 // This is useful when processing RANGES and RHS sections.
78 int GetFieldOffset() const { return free_form_ ? fields_.size() & 1 : 0; }
79
80 // Line processor.
81 template <class DataWrapper>
82 absl::Status ProcessLine(const std::string& line, DataWrapper* data);
83
84 // Process section OBJSENSE in MPS file.
85 template <class DataWrapper>
86 absl::Status ProcessObjectiveSenseSection(DataWrapper* data);
87
88 // Process section ROWS in the MPS file.
89 template <class DataWrapper>
90 absl::Status ProcessRowsSection(bool is_lazy, DataWrapper* data);
91
92 // Process section COLUMNS in the MPS file.
93 template <class DataWrapper>
94 absl::Status ProcessColumnsSection(DataWrapper* data);
95
96 // Process section RHS in the MPS file.
97 template <class DataWrapper>
98 absl::Status ProcessRhsSection(DataWrapper* data);
99
100 // Process section RANGES in the MPS file.
101 template <class DataWrapper>
102 absl::Status ProcessRangesSection(DataWrapper* data);
103
104 // Process section BOUNDS in the MPS file.
105 template <class DataWrapper>
106 absl::Status ProcessBoundsSection(DataWrapper* data);
107
108 // Process section INDICATORS in the MPS file.
109 template <class DataWrapper>
110 absl::Status ProcessIndicatorsSection(DataWrapper* data);
111
112 // Process section SOS in the MPS file.
113 absl::Status ProcessSosSection();
114
115 // Safely converts a string to a numerical type. Returns an error if the
116 // string passed as parameter is ill-formed.
117 absl::StatusOr<double> GetDoubleFromString(const std::string& str);
118 absl::StatusOr<bool> GetBoolFromString(const std::string& str);
119
120 // Different types of variables, as defined in the MPS file specification.
121 // Note these are more precise than the ones in PrimalSimplex.
122 enum BoundTypeId {
123 UNKNOWN_BOUND_TYPE,
124 LOWER_BOUND,
125 UPPER_BOUND,
126 FIXED_VARIABLE,
127 FREE_VARIABLE,
128 NEGATIVE,
129 POSITIVE,
130 BINARY
131 };
132
133 // Different types of constraints for a given row.
134 enum RowTypeId {
135 UNKNOWN_ROW_TYPE,
136 EQUALITY,
137 LESS_THAN,
138 GREATER_THAN,
139 OBJECTIVE,
140 NONE
141 };
142
143 // Stores a bound value of a given type, for a given column name.
144 template <class DataWrapper>
145 absl::Status StoreBound(const std::string& bound_type_mnemonic,
146 const std::string& column_name,
147 const std::string& bound_value, DataWrapper* data);
148
149 // Stores a coefficient value for a column number and a row name.
150 template <class DataWrapper>
151 absl::Status StoreCoefficient(int col, const std::string& row_name,
152 const std::string& row_value,
153 DataWrapper* data);
154
155 // Stores a right-hand-side value for a row name.
156 template <class DataWrapper>
157 absl::Status StoreRightHandSide(const std::string& row_name,
158 const std::string& row_value,
159 DataWrapper* data);
160
161 // Stores a range constraint of value row_value for a row name.
162 template <class DataWrapper>
163 absl::Status StoreRange(const std::string& row_name,
164 const std::string& range_value, DataWrapper* data);
165
166 // Returns an InvalidArgumentError with the given error message, postfixed by
167 // the current line of the .mps file (number and contents).
168 absl::Status InvalidArgumentError(const std::string& error_message);
169
170 // Appends the current line of the .mps file (number and contents) to the
171 // status if it's an error message.
172 absl::Status AppendLineToError(const absl::Status& status);
173
174 // Boolean set to true if the reader expects a free-form MPS file.
175 bool free_form_;
176
177 // Storage of the fields for a line of the MPS file.
178 std::vector<std::string> fields_;
179
180 // Stores the name of the objective row.
181 std::string objective_name_;
182
183 // Enum for section ids.
184 typedef enum {
185 UNKNOWN_SECTION,
186 COMMENT,
187 NAME,
188 OBJSENSE,
189 ROWS,
190 LAZYCONS,
191 COLUMNS,
192 RHS,
193 RANGES,
194 BOUNDS,
195 INDICATORS,
196 SOS,
197 ENDATA
198 } SectionId;
199
200 // Id of the current section of MPS file.
201 SectionId section_;
202
203 // Maps section mnemonic --> section id.
204 absl::flat_hash_map<std::string, SectionId> section_name_to_id_map_;
205
206 // Maps row type mnemonic --> row type id.
207 absl::flat_hash_map<std::string, RowTypeId> row_name_to_id_map_;
208
209 // Maps bound type mnemonic --> bound type id.
210 absl::flat_hash_map<std::string, BoundTypeId> bound_name_to_id_map_;
211
212 // Set of bound type mnemonics that constrain variables to be integer.
213 absl::flat_hash_set<std::string> integer_type_names_set_;
214
215 // The current line number in the file being parsed.
216 int64 line_num_;
217
218 // The current line in the file being parsed.
219 std::string line_;
220
221 // A row of Booleans. is_binary_by_default_[col] is true if col
222 // appeared within a scope started by INTORG and ended with INTEND markers.
223 std::vector<bool> is_binary_by_default_;
224
225 // True if the next variable has to be interpreted as an integer variable.
226 // This is used to support the marker INTORG that starts an integer section
227 // and INTEND that ends it.
228 bool in_integer_section_;
229
230 // We keep track of the number of unconstrained rows so we can display it to
231 // the user because other solvers usually ignore them and we don't (they will
232 // be removed in the preprocessor).
233 int num_unconstrained_rows_;
234
235 DISALLOW_COPY_AND_ASSIGN(MPSReaderImpl);
236};
237
238// Data templates.
239
240template <class Data>
241class DataWrapper {};
242
243template <>
245 public:
246 explicit DataWrapper(LinearProgram* data) { data_ = data; }
247
248 void SetUp() {
249 data_->SetDcheckBounds(false);
250 data_->Clear();
251 }
252
253 void SetName(const std::string& name) { data_->SetName(name); }
254
255 void SetObjectiveDirection(bool maximize) {
256 data_->SetMaximizationProblem(maximize);
257 }
258
259 int FindOrCreateConstraint(const std::string& name) {
260 return data_->FindOrCreateConstraint(name).value();
261 }
262 void SetConstraintBounds(int index, double lower_bound, double upper_bound) {
263 data_->SetConstraintBounds(RowIndex(index), lower_bound, upper_bound);
264 }
265 void SetConstraintCoefficient(int row_index, int col_index,
266 double coefficient) {
267 data_->SetCoefficient(RowIndex(row_index), ColIndex(col_index),
269 }
270 void SetIsLazy(int row_index) {
272 << "LAZYCONS section detected. It will be handled as an extension of "
273 "the ROWS section.";
274 }
275 double ConstraintLowerBound(int row_index) {
276 return data_->constraint_lower_bounds()[RowIndex(row_index)];
277 }
278 double ConstraintUpperBound(int row_index) {
279 return data_->constraint_upper_bounds()[RowIndex(row_index)];
280 }
281
282 int FindOrCreateVariable(const std::string& name) {
283 return data_->FindOrCreateVariable(name).value();
284 }
286 data_->SetVariableType(ColIndex(index),
288 }
289 void SetVariableBounds(int index, double lower_bound, double upper_bound) {
290 data_->SetVariableBounds(ColIndex(index), lower_bound, upper_bound);
291 }
293 data_->SetObjectiveCoefficient(ColIndex(index), coefficient);
294 }
296 return data_->IsVariableInteger(ColIndex(index));
297 }
299 return data_->variable_lower_bounds()[ColIndex(index)];
300 }
302 return data_->variable_upper_bounds()[ColIndex(index)];
303 }
304
305 absl::Status CreateIndicatorConstraint(std::string row_name, int col_index,
306 bool col_value) {
307 return absl::UnimplementedError(
308 "LinearProgram does not support indicator constraints.");
309 }
310
311 void CleanUp() { data_->CleanUp(); }
312
313 private:
314 LinearProgram* data_;
315};
316
317template <>
318class DataWrapper<MPModelProto> {
319 public:
320 explicit DataWrapper(MPModelProto* data) { data_ = data; }
321
322 void SetUp() { data_->Clear(); }
323
324 void SetName(const std::string& name) { data_->set_name(name); }
325
326 void SetObjectiveDirection(bool maximize) { data_->set_maximize(maximize); }
327
328 int FindOrCreateConstraint(const std::string& name) {
329 const auto it = constraint_indices_by_name_.find(name);
330 if (it != constraint_indices_by_name_.end()) return it->second;
331
332 const int index = data_->constraint_size();
333 MPConstraintProto* const constraint = data_->add_constraint();
334 constraint->set_lower_bound(0.0);
335 constraint->set_upper_bound(0.0);
336 constraint->set_name(name);
337 constraint_indices_by_name_[name] = index;
338 return index;
339 }
340 void SetConstraintBounds(int index, double lower_bound, double upper_bound) {
341 data_->mutable_constraint(index)->set_lower_bound(lower_bound);
342 data_->mutable_constraint(index)->set_upper_bound(upper_bound);
343 }
344 void SetConstraintCoefficient(int row_index, int col_index,
345 double coefficient) {
346 // Note that we assume that there is no duplicate in the mps file format. If
347 // there is, we will just add more than one entry from the same variable in
348 // a constraint, and we let any program that ingests an MPModelProto handle
349 // it.
350 MPConstraintProto* const constraint = data_->mutable_constraint(row_index);
351 constraint->add_var_index(col_index);
352 constraint->add_coefficient(coefficient);
353 }
354 void SetIsLazy(int row_index) {
355 data_->mutable_constraint(row_index)->set_is_lazy(true);
356 }
357 double ConstraintLowerBound(int row_index) {
358 return data_->constraint(row_index).lower_bound();
359 }
360 double ConstraintUpperBound(int row_index) {
361 return data_->constraint(row_index).upper_bound();
362 }
363
364 int FindOrCreateVariable(const std::string& name) {
365 const auto it = variable_indices_by_name_.find(name);
366 if (it != variable_indices_by_name_.end()) return it->second;
367
368 const int index = data_->variable_size();
369 MPVariableProto* const variable = data_->add_variable();
370 variable->set_lower_bound(0.0);
371 variable->set_name(name);
372 variable_indices_by_name_[name] = index;
373 return index;
374 }
376 data_->mutable_variable(index)->set_is_integer(true);
377 }
378 void SetVariableBounds(int index, double lower_bound, double upper_bound) {
379 data_->mutable_variable(index)->set_lower_bound(lower_bound);
380 data_->mutable_variable(index)->set_upper_bound(upper_bound);
381 }
383 data_->mutable_variable(index)->set_objective_coefficient(coefficient);
384 }
386 return data_->variable(index).is_integer();
387 }
389 return data_->variable(index).lower_bound();
390 }
392 return data_->variable(index).upper_bound();
393 }
394
395 absl::Status CreateIndicatorConstraint(std::string cst_name, int var_index,
396 bool var_value) {
397 const auto it = constraint_indices_by_name_.find(cst_name);
398 if (it == constraint_indices_by_name_.end()) {
399 return absl::InvalidArgumentError(
400 absl::StrCat("Constraint \"", cst_name, "\" doesn't exist."));
401 }
402 const int cst_index = it->second;
403
404 MPGeneralConstraintProto* const constraint =
405 data_->add_general_constraint();
406 constraint->set_name(
407 absl::StrCat("ind_", data_->constraint(cst_index).name()));
408 MPIndicatorConstraint* const indicator =
409 constraint->mutable_indicator_constraint();
410 *indicator->mutable_constraint() = data_->constraint(cst_index);
411 indicator->set_var_index(var_index);
412 indicator->set_var_value(var_value);
413 constraints_to_delete_.insert(cst_index);
414
415 return absl::OkStatus();
416 }
417
418 void CleanUp() {
419 google::protobuf::util::RemoveAt(data_->mutable_constraint(),
420 constraints_to_delete_);
421 }
422
423 private:
424 MPModelProto* data_;
425
426 absl::flat_hash_map<std::string, int> variable_indices_by_name_;
427 absl::flat_hash_map<std::string, int> constraint_indices_by_name_;
428 absl::node_hash_set<int> constraints_to_delete_;
429};
430
431template <class Data>
432absl::Status MPSReaderImpl::ParseFile(const std::string& file_name, Data* data,
433 MPSReader::Form form) {
434 if (data == nullptr) {
435 return absl::InvalidArgumentError("NULL pointer passed as argument.");
436 }
437
438 if (form == MPSReader::AUTO_DETECT) {
439 if (ParseFile(file_name, data, MPSReader::FIXED).ok()) {
440 return absl::OkStatus();
441 }
442 return ParseFile(file_name, data, MPSReader::FREE);
443 }
444
445 // TODO(user): Use the form directly.
446 free_form_ = form == MPSReader::FREE;
447 Reset();
448 DataWrapper<Data> data_wrapper(data);
449 data_wrapper.SetUp();
450 for (const std::string& line :
452 RETURN_IF_ERROR(ProcessLine(line, &data_wrapper));
453 }
454 data_wrapper.CleanUp();
455 DisplaySummary();
456 return absl::OkStatus();
457}
458
459template <class DataWrapper>
460absl::Status MPSReaderImpl::ProcessLine(const std::string& line,
461 DataWrapper* data) {
462 ++line_num_;
463 line_ = line;
464 if (IsCommentOrBlank()) {
465 return absl::OkStatus(); // Skip blank lines and comments.
466 }
467 if (!free_form_ && line_.find('\t') != std::string::npos) {
468 return InvalidArgumentError("File contains tabs.");
469 }
470 std::string section;
471 if (line[0] != '\0' && line[0] != ' ') {
472 section = GetFirstWord();
473 section_ =
474 gtl::FindWithDefault(section_name_to_id_map_, section, UNKNOWN_SECTION);
475 if (section_ == UNKNOWN_SECTION) {
476 return InvalidArgumentError("Unknown section.");
477 }
478 if (section_ == COMMENT) {
479 return absl::OkStatus();
480 }
481 if (section_ == OBJSENSE) {
482 return absl::OkStatus();
483 }
484 if (section_ == NAME) {
485 RETURN_IF_ERROR(SplitLineIntoFields());
486 // NOTE(user): The name may differ between fixed and free forms. In
487 // fixed form, the name has at most 8 characters, and starts at a specific
488 // position in the NAME line. For MIPLIB2010 problems (eg, air04, glass4),
489 // the name in fixed form ends up being preceded with a whitespace.
490 // TODO(user,user): Return an error for fixed form if the problem name
491 // does not fit.
492 if (free_form_) {
493 if (fields_.size() >= 2) {
494 data->SetName(fields_[1]);
495 }
496 } else {
497 const std::vector<std::string> free_fields =
498 absl::StrSplit(line_, absl::ByAnyChar(" \t"), absl::SkipEmpty());
499 const std::string free_name =
500 free_fields.size() >= 2 ? free_fields[1] : "";
501 const std::string fixed_name = fields_.size() >= 3 ? fields_[2] : "";
502 if (free_name != fixed_name) {
503 return InvalidArgumentError(
504 "Fixed form invalid: name differs between free and fixed "
505 "forms.");
506 }
507 data->SetName(fixed_name);
508 }
509 }
510 return absl::OkStatus();
511 }
512 RETURN_IF_ERROR(SplitLineIntoFields());
513 switch (section_) {
514 case NAME:
515 return InvalidArgumentError("Second NAME field.");
516 case OBJSENSE:
517 return ProcessObjectiveSenseSection(data);
518 case ROWS:
519 return ProcessRowsSection(/*is_lazy=*/false, data);
520 case LAZYCONS:
521 return ProcessRowsSection(/*is_lazy=*/true, data);
522 case COLUMNS:
523 return ProcessColumnsSection(data);
524 case RHS:
525 return ProcessRhsSection(data);
526 case RANGES:
527 return ProcessRangesSection(data);
528 case BOUNDS:
529 return ProcessBoundsSection(data);
530 case INDICATORS:
531 return ProcessIndicatorsSection(data);
532 case SOS:
533 return ProcessSosSection();
534 case ENDATA: // Do nothing.
535 break;
536 default:
537 return InvalidArgumentError("Unknown section.");
538 }
539 return absl::OkStatus();
540}
541
542template <class DataWrapper>
543absl::Status MPSReaderImpl::ProcessObjectiveSenseSection(DataWrapper* data) {
544 if (fields_.size() != 1 && fields_[0] != "MIN" && fields_[0] != "MAX") {
545 return InvalidArgumentError("Expected objective sense (MAX or MIN).");
546 }
547 data->SetObjectiveDirection(/*maximize=*/fields_[0] == "MAX");
548 return absl::OkStatus();
549}
550
551template <class DataWrapper>
552absl::Status MPSReaderImpl::ProcessRowsSection(bool is_lazy,
553 DataWrapper* data) {
554 if (fields_.size() < 2) {
555 return InvalidArgumentError("Not enough fields in ROWS section.");
556 }
557 const std::string row_type_name = fields_[0];
558 const std::string row_name = fields_[1];
559 RowTypeId row_type = gtl::FindWithDefault(row_name_to_id_map_, row_type_name,
560 UNKNOWN_ROW_TYPE);
561 if (row_type == UNKNOWN_ROW_TYPE) {
562 return InvalidArgumentError("Unknown row type.");
563 }
564
565 // The first NONE constraint is used as the objective.
566 if (objective_name_.empty() && row_type == NONE) {
567 row_type = OBJECTIVE;
568 objective_name_ = row_name;
569 } else {
570 if (row_type == NONE) {
571 ++num_unconstrained_rows_;
572 }
573 const int row = data->FindOrCreateConstraint(row_name);
574 if (is_lazy) data->SetIsLazy(row);
575
576 // The initial row range is [0, 0]. We encode the type in the range by
577 // setting one of the bounds to +/- infinity.
578 switch (row_type) {
579 case LESS_THAN:
580 data->SetConstraintBounds(row, -kInfinity,
581 data->ConstraintUpperBound(row));
582 break;
583 case GREATER_THAN:
584 data->SetConstraintBounds(row, data->ConstraintLowerBound(row),
585 kInfinity);
586 break;
587 case NONE:
588 data->SetConstraintBounds(row, -kInfinity, kInfinity);
589 break;
590 case EQUALITY:
591 default:
592 break;
593 }
594 }
595 return absl::OkStatus();
596}
597
598template <class DataWrapper>
599absl::Status MPSReaderImpl::ProcessColumnsSection(DataWrapper* data) {
600 // Take into account the INTORG and INTEND markers.
601 if (absl::StrContains(line_, "'MARKER'")) {
602 if (absl::StrContains(line_, "'INTORG'")) {
603 VLOG(2) << "Entering integer marker.\n" << line_;
604 if (in_integer_section_) {
605 return InvalidArgumentError("Found INTORG inside the integer section.");
606 }
607 in_integer_section_ = true;
608 } else if (absl::StrContains(line_, "'INTEND'")) {
609 VLOG(2) << "Leaving integer marker.\n" << line_;
610 if (!in_integer_section_) {
611 return InvalidArgumentError(
612 "Found INTEND without corresponding INTORG.");
613 }
614 in_integer_section_ = false;
615 }
616 return absl::OkStatus();
617 }
618 const int start_index = free_form_ ? 0 : 1;
619 if (fields_.size() < start_index + 3) {
620 return InvalidArgumentError("Not enough fields in COLUMNS section.");
621 }
622 const std::string& column_name = GetField(start_index, 0);
623 const std::string& row1_name = GetField(start_index, 1);
624 const std::string& row1_value = GetField(start_index, 2);
625 const int col = data->FindOrCreateVariable(column_name);
626 is_binary_by_default_.resize(col + 1, false);
627 if (in_integer_section_) {
628 data->SetVariableTypeToInteger(col);
629 // The default bounds for integer variables are [0, 1].
630 data->SetVariableBounds(col, 0.0, 1.0);
631 is_binary_by_default_[col] = true;
632 } else {
633 data->SetVariableBounds(col, 0.0, kInfinity);
634 }
635 RETURN_IF_ERROR(StoreCoefficient(col, row1_name, row1_value, data));
636 if (fields_.size() == start_index + 4) {
637 return InvalidArgumentError("Unexpected number of fields.");
638 }
639 if (fields_.size() - start_index > 4) {
640 const std::string& row2_name = GetField(start_index, 3);
641 const std::string& row2_value = GetField(start_index, 4);
642 RETURN_IF_ERROR(StoreCoefficient(col, row2_name, row2_value, data));
643 }
644 return absl::OkStatus();
645}
646
647template <class DataWrapper>
648absl::Status MPSReaderImpl::ProcessRhsSection(DataWrapper* data) {
649 const int start_index = free_form_ ? 0 : 2;
650 const int offset = start_index + GetFieldOffset();
651 if (fields_.size() < offset + 2) {
652 return InvalidArgumentError("Not enough fields in RHS section.");
653 }
654 // const std::string& rhs_name = fields_[0]; is not used
655 const std::string& row1_name = GetField(offset, 0);
656 const std::string& row1_value = GetField(offset, 1);
657 RETURN_IF_ERROR(StoreRightHandSide(row1_name, row1_value, data));
658 if (fields_.size() - start_index >= 4) {
659 const std::string& row2_name = GetField(offset, 2);
660 const std::string& row2_value = GetField(offset, 3);
661 RETURN_IF_ERROR(StoreRightHandSide(row2_name, row2_value, data));
662 }
663 return absl::OkStatus();
664}
665
666template <class DataWrapper>
667absl::Status MPSReaderImpl::ProcessRangesSection(DataWrapper* data) {
668 const int start_index = free_form_ ? 0 : 2;
669 const int offset = start_index + GetFieldOffset();
670 if (fields_.size() < offset + 2) {
671 return InvalidArgumentError("Not enough fields in RHS section.");
672 }
673 // const std::string& range_name = fields_[0]; is not used
674 const std::string& row1_name = GetField(offset, 0);
675 const std::string& row1_value = GetField(offset, 1);
676 RETURN_IF_ERROR(StoreRange(row1_name, row1_value, data));
677 if (fields_.size() - start_index >= 4) {
678 const std::string& row2_name = GetField(offset, 2);
679 const std::string& row2_value = GetField(offset, 3);
680 RETURN_IF_ERROR(StoreRange(row2_name, row2_value, data));
681 }
682 return absl::OkStatus();
683}
684
685template <class DataWrapper>
686absl::Status MPSReaderImpl::ProcessBoundsSection(DataWrapper* data) {
687 if (fields_.size() < 3) {
688 return InvalidArgumentError("Not enough fields in BOUNDS section.");
689 }
690 const std::string bound_type_mnemonic = fields_[0];
691 const std::string bound_row_name = fields_[1];
692 const std::string column_name = fields_[2];
693 std::string bound_value;
694 if (fields_.size() >= 4) {
695 bound_value = fields_[3];
696 }
697 return StoreBound(bound_type_mnemonic, column_name, bound_value, data);
698}
699
700template <class DataWrapper>
701absl::Status MPSReaderImpl::ProcessIndicatorsSection(DataWrapper* data) {
702 // TODO(user): Enforce section order. This section must come after
703 // anything related to constraints, or we'll have partial data inside the
704 // indicator constraints.
705 if (fields_.size() < 4) {
706 return InvalidArgumentError("Not enough fields in INDICATORS section.");
707 }
708
709 const std::string type = fields_[0];
710 if (type != "IF") {
711 return InvalidArgumentError(
712 "Indicator constraints must start with \"IF\".");
713 }
714 const std::string row_name = fields_[1];
715 const std::string column_name = fields_[2];
716 const std::string column_value = fields_[3];
717
718 bool value;
719 ASSIGN_OR_RETURN(value, GetBoolFromString(column_value));
720
721 const int col = data->FindOrCreateVariable(column_name);
722 // Variables used in indicator constraints become Boolean by default.
723 data->SetVariableTypeToInteger(col);
724 data->SetVariableBounds(col, std::max(0.0, data->VariableLowerBound(col)),
725 std::min(1.0, data->VariableUpperBound(col)));
726
728 AppendLineToError(data->CreateIndicatorConstraint(row_name, col, value)));
729
730 return absl::OkStatus();
731}
732
733template <class DataWrapper>
734absl::Status MPSReaderImpl::StoreCoefficient(int col,
735 const std::string& row_name,
736 const std::string& row_value,
737 DataWrapper* data) {
738 if (row_name.empty() || row_name == "$") {
739 return absl::OkStatus();
740 }
741
742 double value;
743 ASSIGN_OR_RETURN(value, GetDoubleFromString(row_value));
744 if (value == kInfinity || value == -kInfinity) {
745 return InvalidArgumentError("Constraint coefficients cannot be infinity.");
746 }
747 if (value == 0.0) return absl::OkStatus();
748 if (row_name == objective_name_) {
749 data->SetObjectiveCoefficient(col, value);
750 } else {
751 const int row = data->FindOrCreateConstraint(row_name);
752 data->SetConstraintCoefficient(row, col, value);
753 }
754 return absl::OkStatus();
755}
756
757template <class DataWrapper>
758absl::Status MPSReaderImpl::StoreRightHandSide(const std::string& row_name,
759 const std::string& row_value,
760 DataWrapper* data) {
761 if (row_name.empty()) return absl::OkStatus();
762
763 if (row_name != objective_name_) {
764 const int row = data->FindOrCreateConstraint(row_name);
766 ASSIGN_OR_RETURN(value, GetDoubleFromString(row_value));
767
768 // The row type is encoded in the bounds, so at this point we have either
769 // (-kInfinity, 0.0], [0.0, 0.0] or [0.0, kInfinity). We use the right
770 // hand side to change any finite bound.
771 const Fractional lower_bound =
772 (data->ConstraintLowerBound(row) == -kInfinity) ? -kInfinity : value;
773 const Fractional upper_bound =
774 (data->ConstraintUpperBound(row) == kInfinity) ? kInfinity : value;
775 data->SetConstraintBounds(row, lower_bound, upper_bound);
776 }
777 return absl::OkStatus();
778}
779
780template <class DataWrapper>
781absl::Status MPSReaderImpl::StoreRange(const std::string& row_name,
782 const std::string& range_value,
783 DataWrapper* data) {
784 if (row_name.empty()) return absl::OkStatus();
785
786 const int row = data->FindOrCreateConstraint(row_name);
787 Fractional range;
788 ASSIGN_OR_RETURN(range, GetDoubleFromString(range_value));
789
790 Fractional lower_bound = data->ConstraintLowerBound(row);
791 Fractional upper_bound = data->ConstraintUpperBound(row);
792 if (lower_bound == upper_bound) {
793 if (range < 0.0) {
794 lower_bound += range;
795 } else {
796 upper_bound += range;
797 }
798 }
799 if (lower_bound == -kInfinity) {
800 lower_bound = upper_bound - fabs(range);
801 }
802 if (upper_bound == kInfinity) {
803 upper_bound = lower_bound + fabs(range);
804 }
805 data->SetConstraintBounds(row, lower_bound, upper_bound);
806 return absl::OkStatus();
807}
808
809template <class DataWrapper>
810absl::Status MPSReaderImpl::StoreBound(const std::string& bound_type_mnemonic,
811 const std::string& column_name,
812 const std::string& bound_value,
813 DataWrapper* data) {
814 const BoundTypeId bound_type_id = gtl::FindWithDefault(
815 bound_name_to_id_map_, bound_type_mnemonic, UNKNOWN_BOUND_TYPE);
816 if (bound_type_id == UNKNOWN_BOUND_TYPE) {
817 return InvalidArgumentError("Unknown bound type.");
818 }
819 const int col = data->FindOrCreateVariable(column_name);
820 if (integer_type_names_set_.count(bound_type_mnemonic) != 0) {
821 data->SetVariableTypeToInteger(col);
822 }
823 if (is_binary_by_default_.size() <= col) {
824 // This is the first time that this column has been encountered.
825 is_binary_by_default_.resize(col + 1, false);
826 }
827 // Check that "binary by default" implies "integer".
828 DCHECK(!is_binary_by_default_[col] || data->VariableIsInteger(col));
829 Fractional lower_bound = data->VariableLowerBound(col);
830 Fractional upper_bound = data->VariableUpperBound(col);
831 // If a variable is binary by default, its status is reset if any bound
832 // is set on it. We take care to restore the default bounds for general
833 // integer variables.
834 if (is_binary_by_default_[col]) {
835 lower_bound = Fractional(0.0);
836 upper_bound = kInfinity;
837 }
838 switch (bound_type_id) {
839 case LOWER_BOUND: {
840 ASSIGN_OR_RETURN(lower_bound, GetDoubleFromString(bound_value));
841 // LI with the value 0.0 specifies general integers with no upper bound.
842 if (bound_type_mnemonic == "LI" && lower_bound == 0.0) {
843 upper_bound = kInfinity;
844 }
845 break;
846 }
847 case UPPER_BOUND: {
848 ASSIGN_OR_RETURN(upper_bound, GetDoubleFromString(bound_value));
849 break;
850 }
851 case FIXED_VARIABLE: {
852 ASSIGN_OR_RETURN(lower_bound, GetDoubleFromString(bound_value));
853 upper_bound = lower_bound;
854 break;
855 }
856 case FREE_VARIABLE:
857 lower_bound = -kInfinity;
858 upper_bound = +kInfinity;
859 break;
860 case NEGATIVE:
861 lower_bound = -kInfinity;
862 upper_bound = Fractional(0.0);
863 break;
864 case POSITIVE:
865 lower_bound = Fractional(0.0);
866 upper_bound = +kInfinity;
867 break;
868 case BINARY:
869 lower_bound = Fractional(0.0);
870 upper_bound = Fractional(1.0);
871 break;
872 case UNKNOWN_BOUND_TYPE:
873 default:
874 return InvalidArgumentError("Unknown bound type.");
875 }
876 is_binary_by_default_[col] = false;
877 data->SetVariableBounds(col, lower_bound, upper_bound);
878 return absl::OkStatus();
879}
880
881const int MPSReaderImpl::kNumFields = 6;
882const int MPSReaderImpl::kFieldStartPos[kNumFields] = {1, 4, 14, 24, 39, 49};
883const int MPSReaderImpl::kFieldLength[kNumFields] = {2, 8, 8, 12, 8, 12};
884const int MPSReaderImpl::kSpacePos[12] = {12, 13, 22, 23, 36, 37,
885 38, 47, 48, 61, 62, 63};
886
888 : free_form_(true),
889 fields_(kNumFields),
890 section_(UNKNOWN_SECTION),
891 section_name_to_id_map_(),
892 row_name_to_id_map_(),
893 bound_name_to_id_map_(),
894 integer_type_names_set_(),
895 line_num_(0),
896 line_(),
897 in_integer_section_(false),
898 num_unconstrained_rows_(0) {
899 section_name_to_id_map_["*"] = COMMENT;
900 section_name_to_id_map_["NAME"] = NAME;
901 section_name_to_id_map_["OBJSENSE"] = OBJSENSE;
902 section_name_to_id_map_["ROWS"] = ROWS;
903 section_name_to_id_map_["LAZYCONS"] = LAZYCONS;
904 section_name_to_id_map_["COLUMNS"] = COLUMNS;
905 section_name_to_id_map_["RHS"] = RHS;
906 section_name_to_id_map_["RANGES"] = RANGES;
907 section_name_to_id_map_["BOUNDS"] = BOUNDS;
908 section_name_to_id_map_["INDICATORS"] = INDICATORS;
909 section_name_to_id_map_["ENDATA"] = ENDATA;
910 row_name_to_id_map_["E"] = EQUALITY;
911 row_name_to_id_map_["L"] = LESS_THAN;
912 row_name_to_id_map_["G"] = GREATER_THAN;
913 row_name_to_id_map_["N"] = NONE;
914 bound_name_to_id_map_["LO"] = LOWER_BOUND;
915 bound_name_to_id_map_["UP"] = UPPER_BOUND;
916 bound_name_to_id_map_["FX"] = FIXED_VARIABLE;
917 bound_name_to_id_map_["FR"] = FREE_VARIABLE;
918 bound_name_to_id_map_["MI"] = NEGATIVE;
919 bound_name_to_id_map_["PL"] = POSITIVE;
920 bound_name_to_id_map_["BV"] = BINARY;
921 bound_name_to_id_map_["LI"] = LOWER_BOUND;
922 bound_name_to_id_map_["UI"] = UPPER_BOUND;
923 integer_type_names_set_.insert("BV");
924 integer_type_names_set_.insert("LI");
925 integer_type_names_set_.insert("UI");
926}
927
928void MPSReaderImpl::Reset() {
929 fields_.resize(kNumFields);
930 line_num_ = 0;
931 in_integer_section_ = false;
932 num_unconstrained_rows_ = 0;
933 objective_name_.clear();
934}
935
936void MPSReaderImpl::DisplaySummary() {
937 if (num_unconstrained_rows_ > 0) {
938 VLOG(1) << "There are " << num_unconstrained_rows_ + 1
939 << " unconstrained rows. The first of them (" << objective_name_
940 << ") was used as the objective.";
941 }
942}
943
944bool MPSReaderImpl::IsFixedFormat() {
945 for (const int i : kSpacePos) {
946 if (i >= line_.length()) break;
947 if (line_[i] != ' ') return false;
948 }
949 return true;
950}
951
952absl::Status MPSReaderImpl::SplitLineIntoFields() {
953 if (free_form_) {
954 fields_ = absl::StrSplit(line_, absl::ByAnyChar(" \t"), absl::SkipEmpty());
955 if (fields_.size() > kNumFields) {
956 return InvalidArgumentError("Found too many fields.");
957 }
958 } else {
959 // Note: the name should also comply with the fixed format guidelines
960 // (maximum 8 characters) but in practice there are many problem files in
961 // our netlib archive that are in fixed format and have a long name. We
962 // choose to ignore these cases and treat them as fixed format anyway.
963 if (section_ != NAME && !IsFixedFormat()) {
964 return InvalidArgumentError("Line is not in fixed format.");
965 }
966 const int length = line_.length();
967 for (int i = 0; i < kNumFields; ++i) {
968 if (kFieldStartPos[i] < length) {
969 fields_[i] = line_.substr(kFieldStartPos[i], kFieldLength[i]);
970 fields_[i].erase(fields_[i].find_last_not_of(" ") + 1);
971 } else {
972 fields_[i] = "";
973 }
974 }
975 }
976 return absl::OkStatus();
977}
978
979std::string MPSReaderImpl::GetFirstWord() const {
980 if (line_[0] == ' ') {
981 return std::string("");
982 }
983 const int first_space_pos = line_.find(' ');
984 const std::string first_word = line_.substr(0, first_space_pos);
985 return first_word;
986}
987
988bool MPSReaderImpl::IsCommentOrBlank() const {
989 const char* line = line_.c_str();
990 if (*line == '*') {
991 return true;
992 }
993 for (; *line != '\0'; ++line) {
994 if (*line != ' ' && *line != '\t') {
995 return false;
996 }
997 }
998 return true;
999}
1000
1001absl::StatusOr<double> MPSReaderImpl::GetDoubleFromString(
1002 const std::string& str) {
1003 double result;
1004 if (!absl::SimpleAtod(str, &result)) {
1005 return InvalidArgumentError(
1006 absl::StrCat("Failed to convert \"", str, "\" to double."));
1007 }
1008 if (std::isnan(result)) {
1009 return InvalidArgumentError("Found NaN value.");
1010 }
1011 return result;
1012}
1013
1014absl::StatusOr<bool> MPSReaderImpl::GetBoolFromString(const std::string& str) {
1015 int result;
1016 if (!absl::SimpleAtoi(str, &result) || result < 0 || result > 1) {
1017 return InvalidArgumentError(
1018 absl::StrCat("Failed to convert \"", str, "\" to bool."));
1019 }
1020 return result;
1021}
1022
1023absl::Status MPSReaderImpl::ProcessSosSection() {
1024 return InvalidArgumentError("Section SOS currently not supported.");
1025}
1026
1027absl::Status MPSReaderImpl::InvalidArgumentError(
1028 const std::string& error_message) {
1029 return AppendLineToError(absl::InvalidArgumentError(error_message));
1030}
1031
1032absl::Status MPSReaderImpl::AppendLineToError(const absl::Status& status) {
1033 return util::StatusBuilder(status).SetAppend()
1034 << " Line " << line_num_ << ": \"" << line_ << "\".";
1035}
1036
1037// Parses instance from a file.
1038absl::Status MPSReader::ParseFile(const std::string& file_name,
1039 LinearProgram* data, Form form) {
1040 return MPSReaderImpl().ParseFile(file_name, data, form);
1041}
1042
1043absl::Status MPSReader::ParseFile(const std::string& file_name,
1044 MPModelProto* data, Form form) {
1045 return MPSReaderImpl().ParseFile(file_name, data, form);
1046}
1047
1048} // namespace glop
1049} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define LOG_FIRST_N(severity, n)
Definition: base/logging.h:849
#define DCHECK(condition)
Definition: base/logging.h:884
#define VLOG(verboselevel)
Definition: base/logging.h:978
void SetConstraintBounds(int index, double lower_bound, double upper_bound)
Definition: mps_reader.cc:262
void SetObjectiveCoefficient(int index, double coefficient)
Definition: mps_reader.cc:292
void SetConstraintCoefficient(int row_index, int col_index, double coefficient)
Definition: mps_reader.cc:265
absl::Status CreateIndicatorConstraint(std::string row_name, int col_index, bool col_value)
Definition: mps_reader.cc:305
void SetVariableBounds(int index, double lower_bound, double upper_bound)
Definition: mps_reader.cc:289
void SetConstraintBounds(int index, double lower_bound, double upper_bound)
Definition: mps_reader.cc:340
void SetObjectiveCoefficient(int index, double coefficient)
Definition: mps_reader.cc:382
void SetConstraintCoefficient(int row_index, int col_index, double coefficient)
Definition: mps_reader.cc:344
absl::Status CreateIndicatorConstraint(std::string cst_name, int var_index, bool var_value)
Definition: mps_reader.cc:395
void SetVariableBounds(int index, double lower_bound, double upper_bound)
Definition: mps_reader.cc:378
absl::Status ParseFile(const std::string &file_name, LinearProgram *data, Form form=AUTO_DETECT)
Definition: mps_reader.cc:1038
absl::Status ParseFile(const std::string &file_name, Data *data, MPSReader::Form form)
Definition: mps_reader.cc:432
StatusBuilder & SetAppend()
const std::string name
int64 value
int64_t int64
const int WARNING
Definition: log_severity.h:31
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
int RemoveAt(RepeatedType *array, const IndexContainer &indices)
Definition: protobuf_util.h:40
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
const double kInfinity
Definition: lp_types.h:83
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
int64 coefficient
#define ASSIGN_OR_RETURN(lhs, rexpr)
Definition: status_macros.h:59
#define RETURN_IF_ERROR(expr)
Definition: status_macros.h:27