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
23namespace operations_research {
24namespace 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
36class ScpParser {
37 public:
38 enum Section {
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...