Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
opb_reader.h
Go to the documentation of this file.
1// Copyright 2010-2025 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_SAT_OPB_READER_H_
15#define OR_TOOLS_SAT_OPB_READER_H_
16
17#include <algorithm>
18#include <cstdint>
19#include <limits>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "absl/base/attributes.h"
25#include "absl/container/flat_hash_map.h"
26#include "absl/container/flat_hash_set.h"
27#include "absl/log/check.h"
28#include "absl/log/log.h"
29#include "absl/strings/numbers.h"
30#include "absl/strings/str_split.h"
31#include "absl/strings/string_view.h"
32#include "absl/types/span.h"
38
39namespace operations_research {
40namespace sat {
41
42// This class loads a file in pbo file format into a LinearBooleanProblem.
43// The format is described here:
44// http://www.cril.univ-artois.fr/PB24/format.pdf
45class OpbReader {
46 public:
47 OpbReader() = default;
48 // This type is neither copyable nor movable.
49 OpbReader(const OpbReader&) = delete;
50 OpbReader& operator=(const OpbReader&) = delete;
51
52 // Returns the number of variables in the problem.
53 int num_variables() const { return num_variables_; }
54
55 // Returns true if the model is supported. A model is not supported if it
56 // contains an integer that does not fit in int64_t.
57 bool model_is_supported() const { return model_is_supported_; }
58
59 // Loads the given opb filename into the given problem.
60 // Returns true on success.
61 ABSL_MUST_USE_RESULT bool LoadAndValidate(const std::string& filename,
62 CpModelProto* model) {
63 model->Clear();
64 model->set_name(ExtractProblemName(filename));
65
66 num_variables_ = 0;
67 int num_lines = 0;
68 model_is_supported_ = true;
69
70 // Read constraints line by line (1 constraint per line).
71 // We process into a temporary structure to support non linear constraints
72 // and weighted constraints.
73 for (const std::string& line : FileLines(filename)) {
74 ++num_lines;
75 ProcessNewLine(line);
76
77 // Check if the model is supported. It is not supported if one constant
78 // contains an integer that does not fit in an int64_t.
79 if (!model_is_supported_) return false;
80 }
81 if (num_lines == 0) {
82 LOG(ERROR) << "File '" << filename << "' is empty or can't be read.";
83 return false;
84 }
85
86 LOG(INFO) << "Read " << num_lines << " lines from " << filename;
87 LOG(INFO) << "#variables: " << num_variables_;
88 LOG(INFO) << "#constraints: " << constraints_.size();
89 LOG(INFO) << "#objective: " << objective_.size();
90
91 const std::string error_message = ValidateModel();
92 if (!error_message.empty()) {
93 LOG(ERROR) << "Error while trying to parse '" << filename
94 << "': " << error_message;
95 return false;
96 }
97
98 BuildModel(model);
99 return true;
100 }
101
102 private:
103 // A term is coeff * Product(literals).
104 // Note that it is okay to have duplicate literals here, we will just merge
105 // them. Having a literal and its negation will always result in a product of
106 // zero.
107 struct PbTerm {
108 int64_t coeff;
109 std::vector<int> literals; // CpModelProto literals
110 };
111
112 enum PbConstraintType {
113 UNDEFINED_OPERATION,
114 GE_OPERATION,
115 EQ_OPERATION,
116 };
117
118 struct PbConstraint {
119 std::vector<PbTerm> terms;
120 PbConstraintType type = UNDEFINED_OPERATION;
121 int64_t rhs = std::numeric_limits<int64_t>::min();
122 int64_t soft_cost = std::numeric_limits<int64_t>::max();
123 };
124
125 // Since the problem name is not stored in the opb format, we infer it from
126 // the file name.
127 static std::string ExtractProblemName(const std::string& filename) {
128 const int found = filename.find_last_of('/');
129 const std::string problem_name =
130 found != std::string::npos ? filename.substr(found + 1) : filename;
131 return problem_name;
132 }
133
134 void ProcessNewLine(const std::string& line) {
135 const std::vector<std::string> words =
136 absl::StrSplit(line, absl::ByAnyChar(" ;"), absl::SkipEmpty());
137 if (words.empty() || words[0].empty() || words[0][0] == '*') {
138 // TODO(user): Parse comments.
139 return;
140 }
141
142 // We ignore the number of soft constraints.
143 if (words[0] == "soft:") return;
144
145 if (words[0] == "min:") {
146 for (int i = 1; i < words.size(); ++i) {
147 const std::string& word = words[i];
148 if (word.empty() || word[0] == ';') continue;
149 if (word[0] == 'x') {
150 const int index = ParseIndex(word.substr(1));
151 num_variables_ = std::max(num_variables_, index);
152 objective_.back().literals.push_back(
153 PbLiteralToCpModelLiteral(index));
154 } else if (word[0] == '~' && word[1] == 'x') {
155 const int index = ParseIndex(word.substr(2));
156 num_variables_ = std::max(num_variables_, index);
157 objective_.back().literals.push_back(
158 NegatedRef(PbLiteralToCpModelLiteral(index)));
159 } else {
160 // Note that coefficient always appear before the variable/variables.
161 PbTerm term;
162 if (!ParseInt64Into(word, &term.coeff)) return;
163 objective_.emplace_back(std::move(term));
164 }
165 }
166
167 // Normalize objective literals.
168 for (PbTerm& term : objective_) {
169 if (term.literals.size() <= 1) continue;
170 gtl::STLSortAndRemoveDuplicates(&term.literals);
171 CHECK_GT(term.literals.size(), 1);
172 }
173
174 return;
175 }
176
177 PbConstraint constraint;
178 for (int i = 0; i < words.size(); ++i) {
179 const std::string& word = words[i];
180 CHECK(!word.empty());
181 if (word[0] == '[') { // Soft constraint.
182 if (!ParseInt64Into(word.substr(1, word.size() - 2),
183 &constraint.soft_cost)) {
184 return;
185 }
186 } else if (word == ">=") {
187 CHECK_LT(i + 1, words.size());
188 constraint.type = GE_OPERATION;
189 if (!ParseInt64Into(words[i + 1], &constraint.rhs)) return;
190 break;
191 } else if (word == "=") {
192 CHECK_LT(i + 1, words.size());
193 constraint.type = EQ_OPERATION;
194 if (!ParseInt64Into(words[i + 1], &constraint.rhs)) return;
195 break;
196 } else if (word[0] == 'x') {
197 const int index = ParseIndex(word.substr(1));
198 num_variables_ = std::max(num_variables_, index);
199 constraint.terms.back().literals.push_back(
200 PbLiteralToCpModelLiteral(index));
201 } else if (word[0] == '~' && word[1] == 'x') {
202 const int index = ParseIndex(word.substr(2));
203 num_variables_ = std::max(num_variables_, index);
204 constraint.terms.back().literals.push_back(
205 NegatedRef(PbLiteralToCpModelLiteral(index)));
206 } else {
207 // Note that coefficient always appear before the variable/variables.
208 PbTerm term;
209 if (!ParseInt64Into(word, &term.coeff)) return;
210 constraint.terms.emplace_back(std::move(term));
211 }
212 }
213
214 // Normalize literals.
215 for (PbTerm& term : constraint.terms) {
216 if (term.literals.size() <= 1) continue;
217 gtl::STLSortAndRemoveDuplicates(&term.literals);
218 CHECK_GT(term.literals.size(), 1);
219 }
220
221 constraints_.push_back(std::move(constraint));
222 }
223
224 std::string ValidateModel() {
225 // Normalize and validate constraints.
226 for (const PbConstraint& constraint : constraints_) {
227 if (constraint.rhs == std::numeric_limits<int64_t>::min()) {
228 return "constraint error: undefined rhs";
229 }
230
231 if (constraint.type == UNDEFINED_OPERATION) {
232 return "constraint error: undefined operation";
233 }
234
235 for (const PbTerm& term : constraint.terms) {
236 if (term.coeff == 0) {
237 return "constraint error: coefficient cannot be zero";
238 }
239 if (term.literals.empty()) return "constraint error: empty literals";
240 if (term.literals.size() == 1) {
241 if (!RefIsPositive(term.literals[0])) {
242 return "constraint error: linear terms must use positive literals";
243 }
244 }
245 }
246 }
247
248 // Normalize and validate objective.
249 if (objective_.empty()) return ""; // No objective.
250
251 for (const PbTerm& term : objective_) {
252 if (term.coeff == 0) return "objective error: coefficient cannot be zero";
253 if (term.literals.empty()) return "objective error: empty literals";
254 if (term.literals.size() == 1) {
255 if (!RefIsPositive(term.literals[0])) {
256 return "objective error: linear terms must use positive literals";
257 }
258 return "";
259 }
260 }
261
262 return "";
263 }
264
265 static int PbLiteralToCpModelLiteral(int pb_literal) {
266 return pb_literal > 0 ? pb_literal - 1 : -pb_literal;
267 }
268
269 bool ParseInt64Into(const std::string& word, int64_t* value) {
270 if (!absl::SimpleAtoi(word, value)) {
271 VLOG(1) << "Failed to parse int64_t: " << word;
272 model_is_supported_ = false;
273 return false;
274 }
275 return true;
276 }
277
278 static int ParseIndex(absl::string_view word) {
279 int index;
280 CHECK(absl::SimpleAtoi(word, &index));
281 return index;
282 }
283
284 int GetVariable(const PbTerm& term, CpModelProto* model) {
285 CHECK(!term.literals.empty());
286 if (term.literals.size() == 1) {
287 CHECK(RefIsPositive(term.literals[0]));
288 return term.literals[0];
289 }
290
291 const auto it = product_to_var_.find(term.literals);
292 if (it != product_to_var_.end()) {
293 return it->second;
294 }
295
296 const int var_index = model->variables_size();
297 IntegerVariableProto* var_proto = model->add_variables();
298 var_proto->add_domain(0);
299 var_proto->add_domain(1);
300
301 product_to_var_[term.literals] = var_index;
302
303 // Link the new variable to the terms.
304 // var_index => and(literals).
305 ConstraintProto* var_to_literals = model->add_constraints();
306 var_to_literals->add_enforcement_literal(var_index);
307
308 // and(literals) => var_index.
309 ConstraintProto* literals_to_var = model->add_constraints();
310 literals_to_var->mutable_bool_and()->add_literals(var_index);
311
312 for (const int proto_literal : term.literals) {
313 var_to_literals->mutable_bool_and()->add_literals(proto_literal);
314 literals_to_var->add_enforcement_literal(proto_literal);
315 }
316
317 return var_index;
318 }
319
320 void BuildModel(CpModelProto* model) {
321 // We know how many variables we have, so we can add them all.
322 for (int i = 0; i < num_variables_; ++i) {
323 IntegerVariableProto* var = model->add_variables();
324 var->add_domain(0);
325 var->add_domain(1);
326 }
327
328 for (const PbConstraint& constraint : constraints_) {
329 ConstraintProto* ct = model->add_constraints();
330 LinearConstraintProto* lin = ct->mutable_linear();
331 for (const PbTerm& term : constraint.terms) {
332 lin->add_vars(GetVariable(term, model));
333 lin->add_coeffs(term.coeff);
334 }
335 if (constraint.type == GE_OPERATION) {
336 lin->add_domain(constraint.rhs);
337 lin->add_domain(std::numeric_limits<int64_t>::max());
338 } else if (constraint.type == EQ_OPERATION) {
339 lin->add_domain(constraint.rhs);
340 lin->add_domain(constraint.rhs);
341 } else {
342 LOG(FATAL) << "Unsupported operation: " << constraint.type;
343 }
344
345 if (constraint.soft_cost != std::numeric_limits<int64_t>::max()) {
346 const int violation_var_index = model->variables_size();
347 IntegerVariableProto* violation_var = model->add_variables();
348 violation_var->add_domain(0);
349 violation_var->add_domain(1);
350
351 // Update the objective.
352 model->mutable_objective()->add_vars(violation_var_index);
353 model->mutable_objective()->add_coeffs(constraint.soft_cost);
354
355 // Add the enforcement literal to ct.
356 ct->add_enforcement_literal(NegatedRef(violation_var_index));
357 }
358 }
359
360 if (!objective_.empty()) {
361 CpObjectiveProto* obj = model->mutable_objective();
362 for (const PbTerm& term : objective_) {
363 obj->add_vars(GetVariable(term, model));
364 obj->add_coeffs(term.coeff);
365 }
366 }
367 }
368
369 int num_variables_;
370 std::vector<PbTerm> objective_;
371 std::vector<PbConstraint> constraints_;
372 absl::flat_hash_map<absl::Span<const int>, int> product_to_var_;
373 bool model_is_supported_ = true;
374};
375
376} // namespace sat
377} // namespace operations_research
378
379#endif // OR_TOOLS_SAT_OPB_READER_H_
ABSL_ATTRIBUTE_REINITIALIZES void Clear() PROTOBUF_FINAL
void set_name(Arg_ &&arg, Args_... args)
int num_variables() const
Returns the number of variables in the problem.
Definition opb_reader.h:53
OpbReader(const OpbReader &)=delete
This type is neither copyable nor movable.
ABSL_MUST_USE_RESULT bool LoadAndValidate(const std::string &filename, CpModelProto *model)
Definition opb_reader.h:61
OpbReader & operator=(const OpbReader &)=delete
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition stl_util.h:55
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
In SWIG mode, we don't want anything besides these top-level includes.