OR-Tools  8.2
set_covering_parser.h
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 
14 #ifndef OR_TOOLS_DATA_SET_COVERING_PARSER_H_
15 #define OR_TOOLS_DATA_SET_COVERING_PARSER_H_
16 
17 #include <string>
18 #include <vector>
19 
22 
23 namespace operations_research {
24 namespace scp {
25 
26 // Set covering problem.
27 //
28 // We have a list of subsets of a set. Each subset has a cost. The
29 // goal is to select of solution set of subsets such that (1) all elements
30 // of the set belongs to at least one subset of the solution set, and (2)
31 // the sum of the cost of each subset in the solution set is minimal.
32 //
33 // To follow the standard literature, each element is called a row, and each
34 // subset is called a column.
35 
36 class ScpParser {
37  public:
38  enum Section {
43  ROW,
45  END,
47  };
48 
49  enum Format {
50  // The original scp format of these problem is:
51  //
52  // number of rows (m), number of columns (n)
53  //
54  // the cost of each column c(j),j=1,...,n
55  //
56  // for each row i (i=1,...,m): the number of columns which cover row
57  // i followed by a list of the columns which cover row i.
58  //
59  // The original problems (scp*) from the OR-LIB follow this format.
61  // The railroad format is:
62  // number of rows (m), number of columns (n)
63  //
64  // for each column j (j=1,...,n): the cost of the column, the number
65  // of rows that it covers followed by a list of the rows that it
66  // covers.
67  //
68  // The railroad problems follow this format.
70  // The triplet format is:
71  //
72  // number of rows (m), number of columns (n)
73  //
74  // for each column, the 3 rows it contains. Note that the cost of
75  // each column is 1.
76  //
77  // The Steiner triple covering problems follow this format.
79  // The spp format is:
80  // number of rows (m), number of columns (n)
81  //
82  // for each column j (j=1,...,n): the cost of the column, the number
83  // of rows that it covers followed by a list of the rows that it
84  // covers.
85  //
86  // number of non_zeros
87  //
88  // The set partitioning problems follow this format.
90  };
91 
92  ScpParser();
93 
94  // This will clear the data before importing the file.
95  bool LoadProblem(const std::string& filename, Format format, ScpData* data);
96 
97  private:
98  void ProcessLine(const std::string& line, Format format, ScpData* data);
99  void LogError(const std::string& line, const std::string& error_message);
100  int strtoint32(const std::string& word);
101  int64 strtoint64(const std::string& word);
102 
103  Section section_;
104  int line_;
105  int remaining_;
106  int current_;
107 };
108 
109 } // namespace scp
110 } // namespace operations_research
111 
112 #endif // OR_TOOLS_DATA_SET_COVERING_PARSER_H_
bool LoadProblem(const std::string &filename, Format format, ScpData *data)
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...