 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
#include <mps_reader_template.h>
Public Types | |
| using | IndexType = typename DataWrapper::IndexType |
Type for row and column indices, as provided by DataWrapper. | |
Public Member Functions | |
| MPSReaderTemplate () | |
| absl::StatusOr< MPSReaderFormat > | ParseFile (absl::string_view file_name, DataWrapper *data, MPSReaderFormat form=MPSReaderFormat::kAutoDetect) |
| absl::StatusOr< MPSReaderFormat > | ParseString (absl::string_view source, DataWrapper *data, MPSReaderFormat form=MPSReaderFormat::kAutoDetect) |
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A templated-reader for MPS (Mathematical Programming System) format.
From Wikipedia https://en.wikipedia.org/wiki/MPS_(format): ``` The format was named after an early IBM LP product[1] and has emerged as a de facto standard ASCII medium among most of the commercial LP solvers.
MPS is column-oriented (as opposed to entering the model as equations), and all model components (variables, rows, etc.) receive names. MPS is an old format, so it is set up for punch cards: Fields start in column 2, 5, 15, 25, 40 and 50. Sections of an MPS file are marked by so-called header cards, which are distinguished by their starting in column 1. Although it is typical to use upper-case throughout the file for historical reasons, many MPS-readers will accept mixed-case for anything except the header cards, and some allow mixed-case anywhere. The names that you choose for the individual entities (constraints or variables) are not important to the solver; one should pick meaningful names, or easy names for a post-processing code to read. ```
For example: NAME TESTPROB ROWS N COST L LIM1 G LIM2 E MYEQN COLUMNS XONE COST 1 LIM1 1 XONE LIM2 1 YTWO COST 4 LIM1 1 YTWO MYEQN -1 ZTHREE COST 9 LIM2 1 ZTHREE MYEQN 1 RHS RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7 BOUNDS UP BND1 XONE 4 LO BND1 YTWO -1 UP BND1 YTWO 1 ENDATA
section marker must start at column 1.A common alternative is the so-called free format; where names can have (in principle) arbitrary length, but no white space, and where each data or section line can start with or without white space. In both cases the number of fields in each line remain unchanged. This implementation supports both fixed and free (width) format.
Although there is no one format (as many solvers have expanded it over time to support their own generalizations to MIP; i.e. Mixed Integer (Linear) Programming; most support the sections shown in the previous example.
In what follows, we describe the format and requirements for each of the supported sections. Note that sections must appear in the order in this description, and that optional sections can be skipped altogether, but if they do appear, the must do so in the order in this description.
Section order and data within each section:
This optional section has the format: 'NAME <optional_name>‘ / In fixed format, <optional_name> must start at column 15. / / - OBJSENSE / / This optional section specifies the objective direction of the problem (min / or max), by a single line containing either 'MIN’ or 'MAX'. In fixed format, / this field must start at column 2. If no OBJSENSE section is present, the / problem should be treated as a minimization problem (this is the most widely / used convention, but the actual behavior is implementation defined). / / - ROWS / / This is mandatory section, and each following data line is composed of / lines with two fields: / ' T RowName' / where T is one of: / - N: for no constraint type, usually used to describe objective / coefficients. The first row of type N is used as objective function. If / no row is of type N, then the objective function is zero, and the / problem can be seen a feasibility problem. / - L: for less than or equal, / - G: for greater than or equal, / - E: for equality constraints. / Right hand side of constraints are zero by default (these can be overridden / in sections RHS and RANGES). Repeating a 'RowName' is undefined behavior. In / fixed format, the type appears in column 2 and the row name starts in / column 5. / / - LAZYCONS / / This section is optional, and has the same format (and meaning) as the ROWS / section, i.e. each constraint mentioned here must be new, and each one of / them defines a constraint of the problem. The only difference is that / constraints defined in this section are marked as 'lazy', meaning that there / might be an advantage, when solving the problem, to dynamically add them to / the solving process on the fly. / / - COLUMNS / / This is a mandatory section, and each of the following data lines is / composed of three or five fields with the format: / ' <ColName> <RowName>
<RowName2> <Value2>' / where 'RowName' and 'RowName2' are constraints defined in the ROWS or / LAZYCONS section; 'Value' and 'Value2' are finite values; 'RowName2' and / 'Value2' are optional. The triplet <RowName,ColName,Value> is added to / constraint matrix; and, if present, the triplet <RowName2,ColName,Value2> is / added to the constraint matrix. Note that there is no explicit requirement / that triplets are unique (and how to treat duplicates is / implementation-defined) nor sorted. / / In fixed format, the column name starts in column 5, the row name for the / first non-zero starts in column 15, and the value for the first non-zero / starts in column 25. If a second non-zero is present, the row name starts in / column 40 and the value starts in column 50. / / The COLUMNS section can optionally include (possibly multiple) integrality / markers. Variables mentioned between a pair of markers are assigned type / 'Integer' with binary bounds by default (even if the variable appears for the / first time outside a pair of integrality markers, thus changing its default / bounds). Refer to the BOUNDS section for how to change these bounds. / / The format of these markers is (excluding double quotes): / - " <IgnoredField> 'MARKER' 'INTORG'", / - " <ColName> <RowName> <Value> <RowName2> <Value2>" / ... / - " <ColName> <RowName> <Value> <RowName2> <Value2>" / - " <IgnoredField> 'MARKER' 'INTEND'", / Where the first field is ignored. In fixed format, the fields start in / columns 5, 15 and 40, respectively. Note that the second field must exactly / match 'MARKER', and the third field must be 'INTORG' for opening an integer / section, and 'INTEND' for closing an integer section. / / - RHS / / This is a mandatory section, and each of the following data lines is / composed of three or five fields with the format: / ' <Ignored_Field> <RowName1> <Value1> <OptionalRow2> <OptionalValue2>', / where the first field is ignored, and <RowName> must have been defined in / sections ROWS or LAZYCONS with type E, L or G, and where <Value1> is the / right hand side of <RowName>, and must be a finite value. If <OptionalRow2> / and <OptionalValue2> are present, the same constraints and behavior applies. / In fixed format fields start at columns 2, 5, 15, 40 and 50. / / You can specify an objective 'Offset' by adding the pair <Objective_Name> / <Minus_Offset> in one of the data lines of the RHS section. / / - RANGES / / This is an optional section, and each of the following data lines is / composed of three or five fields: / ' <IgnoredField> <RowName> <Range1> <OptionalRowName2> <OptionalRange2>', / where the first field is ignored, and <RowName> must have been defined in / sections ROWS or LAZYCONS with type E, L or G, and <Range1> must be a finite / value. In fixed format fields must start in columns 2, 5, 15, 40 and 50. / / The effect of specifying a range depends on the sense of the / specified row and whether the range has a positive or negative <Range1>: / ~~~ / Row_type Range_value_sign rhs_lower_limit rhs_upper_limit / G + or - rhs rhs + range / L + or - rhs - range rhs / E + rhs rhs + range / E - rhs + range rhs / ~~~ / If <OptionalRowName2> and <OptionalRange2> are present, the same constraints / and behavior applies. / / - BOUNDS / / Each variable has by default a lower bound of zero, and an upper bound of / infinity, except if the variable is mentioned between integrality markers and / is not mentioned in this section, in which case its lower bound is zero, and / its upper bound is one. / / This is a mandatory section, and each of the following data lines is composed / of three or four fields with the format: / ' <BoundType> <IgnoredField> <ColName>
', / - LO: lower bound for variable,
is mandatory, and / the data line has the effect of setting
<= <ColName>, / - UP: upper bound for variable,
is mandatory, and the / data line has the effect of setting <ColName> <=
, / - FX: for fixed variable,
is mandatory, and the data line has the / effect of setting
<= <ColName> <=
, / - FR: for free variable,
is optional and ignored if present, and / the data line has the effect of setting −∞ <= <ColName> <= ∞, / - MI: infinity lower bound,
is optional and ignored if present, and / the data line has the effect of setting −∞ <= <ColName>, / - PL: infinity upper bound,
is optional and ignored if present, and / the data line has the effect of setting <ColName> <= ∞, / - BV: binary variable,
is optional and ignored if present, and the / data line has the effect of setting 0 <= <ColName> <= 1, / - LI: lower bound for integer variables, same constraints and effect as LO. / - UI: upper bound for integer variables, same constraints and effect as UP. / - SC: stands for semi-continuous and indicates that the variable may be zero, / but if not must be equal to at least the value given (this is not a / common type of variable, and can easily be described in terms of a / binary plus a continuous variable and a constraint linking the two, an / implementation may choose not to support this kind of variable); /
is mandatory, and is only meaningful if it is strictly / positive. / No extra constraints or assumptions are imposed on the order, or the number / of bound constraints on a variable. Each data line is processed sequentially / and its effects enforced; regardless of previously set bounds, explicitly or / by default. / / In fixed format, fields start in columns 2, 5, 15 and 25. / / - INDICATORS / / This is an optional section, and each of the following data lines is / composed of four fields with the format: / ' IF <RowName> <ColName> <BinaryValue>', / where <RowName> is a row defined either in the ROWS or LAZYCONS sections, / <ColName> is forced to be a binary variable (intersecting previously set / bounds with the interval [0,1], and requiring it to be integer); the effect / of the data line is to remove <RowName> from the set of common linear / constraints (which must be satisfied for all feasible solutions), and / instead require the constraint to be satisfied only if the binary variable / <ColName> holds the value <BinaryValue>. /
namespace operations_research {
/ Forms of MPS format supported, either detected automatically, or free / format, or fixed (width) format. enum class MPSReaderFormat { kAutoDetect, kFree, kFixed };
/ Implementation details. namespace internal {
/ Maximum number of 'fields' in an MPS line, either in fixed or free format. static constexpr int kNumMpsFields = 6;
/ Enum for MPS section ids. enum class MPSSectionId { kUnknownSection, kName, kObjsense, kRows, kLazycons, kColumns, kRhs, kRanges, kBounds, kIndicators, kEndData };
/ Represents a single line of an MPS file (or string), and its corresponding / fields. class MPSLineInfo { public: / Creates an MPSLineInfo for line, which should outlive this object. If / the line is a comment line, does not split the line into fields. Returns / InvalidArgumentError if: / * free_form == false and line contains a forbidden character ('\t') / after stripping trailing whitespace, / * free_form == false and line is not in fixed format, or / * if when splitting the line into fields too many fields are detected. static absl::StatusOr<MPSLineInfo> Create(int64_t line_num, bool free_form,
absl::string_view line);
/ Returns a view of the line. absl::string_view GetLine() const { return line_; }
/
free_form. / Returns true if the line defines a new section. bool IsNewSection() const { return line_[0] != '\0' && line_[0] != ' '; }/ Returns the number of fields in the line. What constitutes a 'field' / depends on the format (fixed or free) used at creation time. See the / previous description of MPS fixed and free formats for more details. int GetFieldsSize() const { return fields_.size(); }
/ Returns the word starting at position 0 in the line. If the line is empty, / or if the line starts with a space, returns "". absl::string_view GetFirstWord() const;
/ Returns true if the line contains a comment (starting with '*') or / if it is a blank line. bool IsCommentOrBlank() const;
/ Helper function that returns the index-th field in the line. /
index must be smaller than / GetFieldsSize() and non negative, otherwise the behavior is undefined. / Furthermore, until SplitLineIntoFields is called, GetFieldsSize() is / always zero. absl::string_view GetField(int index) const { return fields_[index]; }/ After calling SplitLineIntoFields has been called, returns the offset at / which to start the parsing of fields within the line. See the preceding / discussion on free and fixed MPS format for details on what constitutes a / field in a line. / If in fixed form, the offset is 0. / If in fixed form and the number of fields is odd, it is 1, / otherwise it is 0. / This is useful when processing RANGES and RHS sections. / If SplitLineIntoFields has not been called before, returns 0. int GetFieldOffset() const { return free_form_ ? fields_.size() & 1 : 0; }
/ Returns an absl::InvalidArgumentError with the given error message, / postfixed by the line of the .mps file (number and contents). absl::Status InvalidArgumentError(absl::string_view error_message) const;
/ Appends the line of the .mps file (number and contents) to the / status if it's an error message. absl::Status AppendLineToError(const absl::Status& status) const;
private: MPSLineInfo(int64_t line_num, bool free_form, absl::string_view line) : free_form_{free_form}, line_num_{line_num}, line_{line} {}
/ Splits into fields the line. absl::Status SplitLineIntoFields();
/ Returns true if the line matches the fixed format. bool IsFixedFormat() const;
/ Boolean set to true if the reader expects a free-form MPS file. const bool free_form_;
/ Storage of the fields for the line. absl::InlinedVector<absl::string_view, internal::kNumMpsFields> fields_;
/ The current line number (passed at construction time). const int64_t line_num_;
/ The line being parsed (with ASCII trailing white space removed, that / includes windows end of line, new line, space, vertical tab and horizontal / tab). const absl::string_view line_; };
} // namespace internal
/ Templated MPS reader. The template class DataWrapper must provide: / type: / - IndexType: for indices of rows and columns. / functions: / - void SetUp(): Called before parsing. After this function call, the / internal state of the object should be the same as in creation. /
MPSReaderFormat::kAutoDetect format. / - void CleanUp(): Called once, after parsing has been successful, to / perform any internal clean up if needed. / - double ConstraintLowerBound(IndexType index): Returns the (currently / stored) lower bound for 'Constraint[index]'; where 'index' is / a value previously returned by FindOrCreateConstraint. / - double ConstraintUpperBound(IndexType index): Returns the (currently / stored) upper bound for 'Constraint[index]'; where 'index' is / a value previously returned by FindOrCreateConstraint. / - IndexType FindOrCreateConstraint(absl::string_view row_name): Returns / the (internally assigned) index to the constraint of the given / name. If row_name is new, the constraint must be created with / a zero lower bound and a zero upper bound. / - IndexType FindOrCreateVariable(absl::string_view col_name): Returns the / (internally assigned) index to the variable of the given name. / Newly created variables should have a zero objective, zero / lower bound, infinity upper bound, and be considered as / 'continuous'. If col_name is new, the variable must be / created with a zero objective coefficient, a zero lower bound, / and an infinity upper bound. / - void SetConstraintBounds(IndexType index,double lower_bound, double
upper_bound): Stores lower and upper bounds for / 'Constraint[index]'. index is a value previously returned by / FindOrCreateConstraint. / - void SetConstraintCoefficient(IndexType row_index, IndexType col_index,
double coefficient): Stores/Adds a new coefficient for the / constraint matrix entry (row_index,col_index); where / row_index is a value previously returned by / FindOrCreateConstraint, and col_index is a value / previously returned by FindOrCreateVariable. / - void SetIsLazy(IndexType row_index): Marks 'Constraint[row_index]' as a / lazy constraint, meaning that the constraint is part of the / problem definition, but it might be advantageous to add them / as 'cuts' when solving the problem; where row_index is a / value previously returned by FindOrCreateConstraint. / - void SetName(absl::string_view): Stores the model's name. / - 'void SetObjectiveCoefficient(IndexType index, double coefficient): Storescoefficient‘ as the new objective coefficient for 'Variable[index]’; where index is a value previously returned by FindOrCreateVariable.void SetObjectiveDirection(bool maximize): If maximize==true the parsed model represents a maximization problem, otherwise, or if the function is never called, the model is a minimization problem.void SetObjectiveOffset(double): Stores the objective offset of the model.void SetVariableTypeToInteger(IndexType index): Marks 'Variable[index]' as 'integer'; where index is a value previously returned by FindOrCreateVariable.void SetVariableTypeToSemiContinuous(IndexType index): Marks 'Variable[index]' as 'semi continuous'; where index is a value previously returned by FindOrCreateVariable.void SetVariableBounds(IndexType index, double lower_bound, double / upper_bound): Stores the lower and upper bounds for 'Variable[index]'; where index is a value previously returned by FindOrCreateVariable.double VariableLowerBound(IndexType index): Returns the (currently) stored lower bound for 'Variable[index'; where index is a value previously returned by FindOrCreateVariable.double VariableUpperBound(IndexType index): Returns the (currently) stored upper bound for 'Variable[index'; where index is a value previously returned by FindOrCreateVariable.absl::Status CreateIndicatorConstraint(absl::string_view row_name, / IndexType col_index, bool var_value): Marks constraint named row_name to be an 'indicator constraint', that should hold if 'Variable[col_index]' holds value 0 if var_value==false, or when 'Variable[col_index]' holds value 1 if var_value==true. Where row_name must have been an argument in a previous call to FindOrCreateConstraint, and col_index is a value previously returned by FindOrCreateVariable. Note that 'Variable[col_index]' should be marked as integer and have bounds in {0,1}. Definition at line 494 of file mps_reader_template.h.
| using MPSReaderTemplate< DataWrapper >::IndexType = typename DataWrapper::IndexType |
Type for row and column indices, as provided by DataWrapper.
Definition at line 497 of file mps_reader_template.h.
| MPSReaderTemplate< DataWrapper >::MPSReaderTemplate | ( | ) |
Definition at line 1144 of file mps_reader_template.h.
| absl::StatusOr< MPSReaderFormat > MPSReaderTemplate< DataWrapper >::ParseFile | ( | absl::string_view | file_name, |
| DataWrapper * | data, | ||
| MPSReaderFormat | form = MPSReaderFormat::kAutoDetect ) |
Parses a file in MPS format; if successful, returns the type of MPS format detected (one of kFree or kFixed). If form is either kFixed or kFree, the function will either return kFixed (or kFree respectivelly) if the input data satisfies the format, or an absl::InvalidArgumentError otherwise.
Definition at line 653 of file mps_reader_template.h.
| absl::StatusOr< MPSReaderFormat > MPSReaderTemplate< DataWrapper >::ParseString | ( | absl::string_view | source, |
| DataWrapper * | data, | ||
| MPSReaderFormat | form = MPSReaderFormat::kAutoDetect ) |
Parses a string in MPS format; if successful, returns the type of MPS format detected (one of kFree or kFixed). If form is either kFixed or kFree, the function will either return kFixed (or kFree respectivelly) if the input data satisfies the format, or an absl::InvalidArgumentError otherwise.
Definition at line 683 of file mps_reader_template.h.
1.12.0