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
20
#include "
ortools/base/integral_types.h
"
21
#include "
ortools/data/set_covering_data.h
"
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
{
39
INIT
,
40
COSTS
,
41
COLUMN
,
42
NUM_COLUMNS_IN_ROW
,
43
ROW
,
44
NUM_NON_ZEROS
,
45
END
,
46
ERROR
,
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.
60
SCP_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.
69
RAILROAD_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.
78
TRIPLET_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.
89
SPP_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_
operations_research::scp::ScpData
Definition:
set_covering_data.h:24
operations_research::scp::ScpParser
Definition:
set_covering_parser.h:36
operations_research::scp::ScpParser::ScpParser
ScpParser()
Definition:
set_covering_parser.cc:23
operations_research::scp::ScpParser::Section
Section
Definition:
set_covering_parser.h:38
operations_research::scp::ScpParser::INIT
@ INIT
Definition:
set_covering_parser.h:39
operations_research::scp::ScpParser::ERROR
@ ERROR
Definition:
set_covering_parser.h:46
operations_research::scp::ScpParser::COSTS
@ COSTS
Definition:
set_covering_parser.h:40
operations_research::scp::ScpParser::NUM_COLUMNS_IN_ROW
@ NUM_COLUMNS_IN_ROW
Definition:
set_covering_parser.h:42
operations_research::scp::ScpParser::ROW
@ ROW
Definition:
set_covering_parser.h:43
operations_research::scp::ScpParser::NUM_NON_ZEROS
@ NUM_NON_ZEROS
Definition:
set_covering_parser.h:44
operations_research::scp::ScpParser::COLUMN
@ COLUMN
Definition:
set_covering_parser.h:41
operations_research::scp::ScpParser::END
@ END
Definition:
set_covering_parser.h:45
operations_research::scp::ScpParser::LoadProblem
bool LoadProblem(const std::string &filename, Format format, ScpData *data)
Definition:
set_covering_parser.cc:25
operations_research::scp::ScpParser::Format
Format
Definition:
set_covering_parser.h:49
operations_research::scp::ScpParser::RAILROAD_FORMAT
@ RAILROAD_FORMAT
Definition:
set_covering_parser.h:69
operations_research::scp::ScpParser::TRIPLET_FORMAT
@ TRIPLET_FORMAT
Definition:
set_covering_parser.h:78
operations_research::scp::ScpParser::SPP_FORMAT
@ SPP_FORMAT
Definition:
set_covering_parser.h:89
operations_research::scp::ScpParser::SCP_FORMAT
@ SCP_FORMAT
Definition:
set_covering_parser.h:60
integral_types.h
int64
int64_t int64
Definition:
integral_types.h:34
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition:
dense_doubly_linked_list.h:21
set_covering_data.h
ortools
data
set_covering_parser.h
Generated by
1.9.4