64 model->
set_name(ExtractProblemName(filename));
68 model_is_supported_ =
true;
73 for (
const std::string& line :
FileLines(filename)) {
79 if (!model_is_supported_)
return false;
82 LOG(ERROR) <<
"File '" << filename <<
"' is empty or can't be read.";
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();
91 const std::string error_message = ValidateModel();
92 if (!error_message.empty()) {
93 LOG(ERROR) <<
"Error while trying to parse '" << filename
94 <<
"': " << error_message;
109 std::vector<int> literals;
112 enum PbConstraintType {
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();
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;
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] ==
'*') {
143 if (words[0] ==
"soft:")
return;
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)));
162 if (!ParseInt64Into(word, &term.coeff))
return;
163 objective_.emplace_back(std::move(term));
168 for (PbTerm& term : objective_) {
169 if (term.literals.size() <= 1)
continue;
171 CHECK_GT(term.literals.size(), 1);
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] ==
'[') {
182 if (!ParseInt64Into(word.substr(1, word.size() - 2),
183 &constraint.soft_cost)) {
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;
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;
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)));
209 if (!ParseInt64Into(word, &term.coeff))
return;
210 constraint.terms.emplace_back(std::move(term));
215 for (PbTerm& term : constraint.terms) {
216 if (term.literals.size() <= 1)
continue;
218 CHECK_GT(term.literals.size(), 1);
221 constraints_.push_back(std::move(constraint));
224 std::string ValidateModel() {
226 for (
const PbConstraint& constraint : constraints_) {
227 if (constraint.rhs == std::numeric_limits<int64_t>::min()) {
228 return "constraint error: undefined rhs";
231 if (constraint.type == UNDEFINED_OPERATION) {
232 return "constraint error: undefined operation";
235 for (
const PbTerm& term : constraint.terms) {
236 if (term.coeff == 0) {
237 return "constraint error: coefficient cannot be zero";
239 if (term.literals.empty())
return "constraint error: empty literals";
240 if (term.literals.size() == 1) {
242 return "constraint error: linear terms must use positive literals";
249 if (objective_.empty())
return "";
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) {
256 return "objective error: linear terms must use positive literals";
265 static int PbLiteralToCpModelLiteral(
int pb_literal) {
266 return pb_literal > 0 ? pb_literal - 1 : -pb_literal;
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;
278 static int ParseIndex(absl::string_view word) {
280 CHECK(absl::SimpleAtoi(word, &index));
284 int GetVariable(
const PbTerm& term, CpModelProto* model) {
285 CHECK(!term.literals.empty());
286 if (term.literals.size() == 1) {
288 return term.literals[0];
291 const auto it = product_to_var_.find(term.literals);
292 if (it != product_to_var_.end()) {
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);
301 product_to_var_[term.literals] = var_index;
305 ConstraintProto* var_to_literals = model->add_constraints();
306 var_to_literals->add_enforcement_literal(var_index);
309 ConstraintProto* literals_to_var = model->add_constraints();
310 literals_to_var->mutable_bool_and()->add_literals(var_index);
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);
320 void BuildModel(CpModelProto* model) {
322 for (
int i = 0;
i < num_variables_; ++
i) {
323 IntegerVariableProto* var = model->add_variables();
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);
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);
342 LOG(FATAL) <<
"Unsupported operation: " << constraint.type;
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);
352 model->mutable_objective()->add_vars(violation_var_index);
353 model->mutable_objective()->add_coeffs(constraint.soft_cost);
356 ct->add_enforcement_literal(
NegatedRef(violation_var_index));
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);
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;