Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
model_exporter.cc
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
15
16#include <algorithm>
17#include <cmath>
18#include <limits>
19#include <memory>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "absl/container/flat_hash_set.h"
25#include "absl/flags/flag.h"
26#include "absl/status/status.h"
27#include "absl/status/statusor.h"
28#include "absl/strings/ascii.h"
29#include "absl/strings/match.h"
30#include "absl/strings/str_cat.h"
31#include "absl/strings/str_format.h"
32#include "absl/strings/string_view.h"
33#include "absl/types/span.h"
38#include "ortools/linear_solver/linear_solver.pb.h"
39
40ABSL_RETIRED_FLAG(bool, lp_log_invalid_name, false, "DEPRECATED.");
41
42namespace operations_research {
43namespace {
44
45constexpr double kInfinity = std::numeric_limits<double>::infinity();
46
47class LineBreaker {
48 public:
49 explicit LineBreaker(int max_line_size)
50 : max_line_size_(max_line_size), line_size_(0), output_() {}
51 // Lines are broken in such a way that:
52 // - Strings that are given to Append() are never split.
53 // - Lines are split so that their length doesn't exceed the max length;
54 // unless a single string given to Append() exceeds that length (in which
55 // case it will be put alone on a single unsplit line).
56 void Append(absl::string_view s);
57
58 // Returns true if string s will fit on the current line without adding a
59 // carriage return.
60 bool WillFit(absl::string_view s) {
61 return line_size_ + static_cast<int>(s.size()) < max_line_size_;
62 }
63
64 // "Consumes" size characters on the line. Used when starting the constraint
65 // lines.
66 void Consume(int size) { line_size_ += size; }
67
68 std::string GetOutput() const { return output_; }
69
70 private:
71 int max_line_size_;
72 int line_size_;
73 std::string output_;
74};
75
76void LineBreaker::Append(absl::string_view s) {
77 line_size_ += s.size();
78 if (line_size_ > max_line_size_) {
79 line_size_ = s.size();
80 absl::StrAppend(&output_, "\n ");
81 }
82 absl::StrAppend(&output_, s);
83}
84
85class MPModelProtoExporter {
86 public:
87 explicit MPModelProtoExporter(const MPModelProto& model);
88
89 // This type is neither copyable nor movable.
90 MPModelProtoExporter(const MPModelProtoExporter&) = delete;
91 MPModelProtoExporter& operator=(const MPModelProtoExporter&) = delete;
92
93 bool ExportModelAsLpFormat(const MPModelExportOptions& options,
94 std::string* output);
95 bool ExportModelAsMpsFormat(const MPModelExportOptions& options,
96 std::string* output);
97
98 private:
99 // Computes the number of continuous, integer and binary variables.
100 // Called by ExportModelAsLpFormat() and ExportModelAsMpsFormat().
101 void Setup();
102
103 // Computes smart column widths for free MPS format.
104 void ComputeMpsSmartColumnWidths(bool obfuscated);
105
106 // Processes all the proto.name() fields and returns the result in a vector.
107 //
108 // If 'obfuscate' is true, none of names are actually used, and this just
109 // returns a vector of 'prefix' + proto index (1-based).
110 //
111 // If it is false, this tries to keep the original names, but:
112 // - if the first character is forbidden (or name is empty), '_' is added at
113 // the beginning of name.
114 // - all the other forbidden characters are replaced by '_'.
115 // To avoid name conflicts, a '_' followed by an integer is appended to the
116 // result.
117 //
118 // If a name is longer than the maximum allowed name length, the obfuscated
119 // name is used.
120 //
121 // Therefore, a name "$20<=40" for proto #3 could be "_$20__40_1".
122 template <class ListOfProtosWithNameFields>
123 std::vector<std::string> ExtractAndProcessNames(
124 const ListOfProtosWithNameFields& proto, absl::string_view prefix,
125 bool obfuscate, bool log_invalid_names,
126 const std::string& forbidden_first_chars,
127 const std::string& forbidden_chars);
128
129 // Appends a general "Comment" section with useful metadata about the model
130 // to "output".
131 // Note(user): there may be less variables in output than in the original
132 // model, as unused variables are not shown by default. Similarly, there
133 // may be more constraints in a .lp file as in the original model as
134 // a constraint lhs <= term <= rhs will be output as the two constraints
135 // term >= lhs and term <= rhs.
136 void AppendComments(const std::string& separator, std::string* output) const;
137
138 // Appends an MPConstraintProto to the output text. If the constraint has
139 // both an upper and lower bound that are not equal, it splits the constraint
140 // into two constraints, one for the left hand side (_lhs) and one for right
141 // hand side (_rhs).
142 bool AppendConstraint(const MPConstraintProto& ct_proto,
143 absl::string_view name, LineBreaker& line_breaker,
144 std::vector<bool>& show_variable, std::string* output);
145
146 // Clears "output" and writes a term to it, in "LP" format. Returns false on
147 // error (for example, var_index is out of range).
148 bool WriteLpTerm(int var_index, double coefficient,
149 std::string* output) const;
150 bool WriteLpQuadraticTerm(int var1_index, int var2_index, double coefficient,
151 std::string* output) const;
152
153 // Appends a pair name, value to "output", formatted to comply with the MPS
154 // standard.
155 void AppendMpsPair(absl::string_view name, double value,
156 std::string* output) const;
157
158 // Appends the head of a line, consisting of an id and a name to output.
159 void AppendMpsLineHeader(absl::string_view id, absl::string_view name,
160 std::string* output) const;
161
162 // Same as AppendMpsLineHeader. Appends an extra new-line at the end the
163 // string pointed to by output.
164 void AppendMpsLineHeaderWithNewLine(absl::string_view id,
165 absl::string_view name,
166 std::string* output) const;
167
168 // Appends an MPS term in various contexts. The term consists of a head name,
169 // a name, and a value. If the line is not empty, then only the pair
170 // (name, value) is appended. The number of columns, limited to 2 by the MPS
171 // format is also taken care of.
172 void AppendMpsTermWithContext(absl::string_view head_name,
173 absl::string_view name, double value,
174 std::string* output);
175
176 // Appends a new-line if two columns are already present on the MPS line.
177 // Used by and in complement to AppendMpsTermWithContext.
178 void AppendNewLineIfTwoColumns(std::string* output);
179
180 // When 'integrality' is true, appends columns corresponding to integer
181 // variables. Appends the columns for non-integer variables otherwise.
182 // The sparse matrix must be passed as a vector of columns ('transpose').
183 void AppendMpsColumns(
184 bool integrality,
185 absl::Span<const std::vector<std::pair<int, double>>> transpose,
186 std::string* output);
187
188 // Appends a line describing the bound of a variablenew-line if two columns
189 // are already present on the MPS line.
190 // Used by and in complement to AppendMpsTermWithContext.
191 void AppendMpsBound(absl::string_view bound_type, absl::string_view name,
192 double value, std::string* output) const;
193
194 const MPModelProto& proto_;
195
196 // Vector of variable names as they will be exported.
197 std::vector<std::string> exported_variable_names_;
198
199 // Vector of constraint names as they will be exported.
200 std::vector<std::string> exported_constraint_names_;
201
202 // Vector of general constraint names as they will be exported.
203 std::vector<std::string> exported_general_constraint_names_;
204
205 // Number of integer variables in proto_.
206 int num_integer_variables_;
207
208 // Number of binary variables in proto_.
209 int num_binary_variables_;
210
211 // Number of continuous variables in proto_.
212 int num_continuous_variables_;
213
214 // Current MPS file column number.
215 int current_mps_column_;
216
217 // Format for MPS file lines.
218 std::unique_ptr<absl::ParsedFormat<'s', 's'>> mps_header_format_;
219 std::unique_ptr<absl::ParsedFormat<'s', 's'>> mps_format_;
220};
221
222} // namespace
223
224absl::StatusOr<std::string> ExportModelAsLpFormat(
225 const MPModelProto& model, const MPModelExportOptions& options) {
226 for (const MPGeneralConstraintProto& general_constraint :
227 model.general_constraint()) {
228 if (!general_constraint.has_indicator_constraint()) {
229 return absl::InvalidArgumentError(
230 "Non-indicator general constraints are not supported.");
231 }
232 }
233 MPModelProtoExporter exporter(model);
234 std::string output;
235 if (!exporter.ExportModelAsLpFormat(options, &output)) {
236 return absl::InvalidArgumentError("Unable to export model.");
237 }
238 return output;
239}
240
241absl::StatusOr<std::string> ExportModelAsMpsFormat(
242 const MPModelProto& model, const MPModelExportOptions& options) {
243 if (model.general_constraint_size() > 0) {
244 return absl::InvalidArgumentError("General constraints are not supported.");
245 }
246 MPModelProtoExporter exporter(model);
247 std::string output;
248 if (!exporter.ExportModelAsMpsFormat(options, &output)) {
249 return absl::InvalidArgumentError("Unable to export model.");
250 }
251 return output;
252}
253
254absl::Status WriteModelToMpsFile(absl::string_view filename,
255 const MPModelProto& model,
256 const MPModelExportOptions& options) {
257 ASSIGN_OR_RETURN(std::string mps_data,
258 ExportModelAsMpsFormat(model, options));
259 return file::SetContents(filename, mps_data, file::Defaults());
260}
261
262namespace {
263MPModelProtoExporter::MPModelProtoExporter(const MPModelProto& model)
264 : proto_(model),
265 num_integer_variables_(0),
266 num_binary_variables_(0),
267 num_continuous_variables_(0),
268 current_mps_column_(0) {}
269
270namespace {
271class NameManager {
272 public:
273 NameManager() : names_set_(), last_n_(1) {}
274 std::string MakeUniqueName(absl::string_view name);
275
276 private:
277 absl::flat_hash_set<std::string> names_set_;
278 int last_n_;
279};
280
281std::string NameManager::MakeUniqueName(absl::string_view name) {
282 std::string result(name);
283 // Find the 'n' so that "name_n" does not already exist.
284 int n = last_n_;
285 while (!names_set_.insert(result).second) {
286 result = absl::StrCat(name, "_", n);
287 ++n;
288 }
289 // We keep the last n used to avoid a quadratic behavior in case
290 // all the names are the same initially.
291 last_n_ = n;
292 return result;
293}
294
295// NOTE: As a special case, an empty name is treated as started with a forbidden
296// character (\0).
297std::string MakeExportableName(const std::string& name,
298 const std::string& forbidden_first_chars,
299 const std::string& forbidden_chars,
300 bool* found_forbidden_char) {
301 // Prepend with "_" all the names starting with a forbidden character.
302 *found_forbidden_char =
303 name.empty() || absl::StrContains(forbidden_first_chars, name[0]);
304 std::string exportable_name =
305 *found_forbidden_char ? absl::StrCat("_", name) : name;
306
307 // Replace all the other forbidden characters with "_".
308 for (char& c : exportable_name) {
309 if (absl::StrContains(forbidden_chars, c)) {
310 c = '_';
311 *found_forbidden_char = true;
312 }
313 }
314 return exportable_name;
315}
316} // namespace
317
318template <class ListOfProtosWithNameFields>
319std::vector<std::string> MPModelProtoExporter::ExtractAndProcessNames(
320 const ListOfProtosWithNameFields& proto, absl::string_view prefix,
321 bool obfuscate, bool log_invalid_names,
322 const std::string& forbidden_first_chars,
323 const std::string& forbidden_chars) {
324 const int num_items = proto.size();
325 std::vector<std::string> result(num_items);
326 NameManager namer;
327 const int num_digits = absl::StrCat(num_items).size();
328 int i = 0;
329 for (const auto& item : proto) {
330 const std::string obfuscated_name =
331 absl::StrFormat("%s%0*d", prefix, num_digits, i);
332 if (obfuscate || !item.has_name()) {
333 result[i] = namer.MakeUniqueName(obfuscated_name);
334 LOG_IF(WARNING, log_invalid_names && !item.has_name())
335 << "Empty name detected, created new name: " << result[i];
336 } else {
337 bool found_forbidden_char = false;
338 const std::string exportable_name =
339 MakeExportableName(item.name(), forbidden_first_chars,
340 forbidden_chars, &found_forbidden_char);
341 result[i] = namer.MakeUniqueName(exportable_name);
342 LOG_IF(WARNING, log_invalid_names && found_forbidden_char)
343 << "Invalid character detected in " << item.name() << ". Changed to "
344 << result[i];
345 // If the name is too long, use the obfuscated name that is guaranteed
346 // to fit. If ever we are able to solve problems with 2^64 variables,
347 // their obfuscated names would fit within 20 characters.
348 const int kMaxNameLength = 255;
349 // Take care of "_rhs" or "_lhs" that may be added in the case of
350 // constraints with both right-hand side and left-hand side.
351 const int kMargin = 4;
352 if (result[i].size() > kMaxNameLength - kMargin) {
353 const std::string old_name = std::move(result[i]);
354 result[i] = namer.MakeUniqueName(obfuscated_name);
355 LOG_IF(WARNING, log_invalid_names) << "Name is too long: " << old_name
356 << " exported as: " << result[i];
357 }
358 }
359
360 // Prepare for the next round.
361 ++i;
362 }
363 return result;
364}
365
366void MPModelProtoExporter::AppendComments(const std::string& separator,
367 std::string* output) const {
368 const char* const sep = separator.c_str();
369 absl::StrAppendFormat(output, "%s Generated by MPModelProtoExporter\n", sep);
370 absl::StrAppendFormat(output, "%s %-16s : %s\n", sep, "Name",
371 proto_.has_name() ? proto_.name().c_str() : "NoName");
372 absl::StrAppendFormat(output, "%s %-16s : %s\n", sep, "Format", "Free");
373 absl::StrAppendFormat(
374 output, "%s %-16s : %d\n", sep, "Constraints",
375 proto_.constraint_size() + proto_.general_constraint_size());
376 absl::StrAppendFormat(output, "%s %-16s : %d\n", sep, "Variables",
377 proto_.variable_size());
378 absl::StrAppendFormat(output, "%s %-14s : %d\n", sep, "Binary",
379 num_binary_variables_);
380 absl::StrAppendFormat(output, "%s %-14s : %d\n", sep, "Integer",
381 num_integer_variables_);
382 absl::StrAppendFormat(output, "%s %-14s : %d\n", sep, "Continuous",
383 num_continuous_variables_);
384}
385
386namespace {
387
388std::string DoubleToStringWithForcedSign(double d) {
389 return absl::StrCat((d < 0 ? "" : "+"), (d));
390}
391
392std::string DoubleToString(double d) { return absl::StrCat((d)); }
393
394} // namespace
395
396bool MPModelProtoExporter::AppendConstraint(const MPConstraintProto& ct_proto,
397 absl::string_view name,
398 LineBreaker& line_breaker,
399 std::vector<bool>& show_variable,
400 std::string* output) {
401 for (int i = 0; i < ct_proto.var_index_size(); ++i) {
402 const int var_index = ct_proto.var_index(i);
403 const double coeff = ct_proto.coefficient(i);
404 std::string term;
405 if (!WriteLpTerm(var_index, coeff, &term)) {
406 return false;
407 }
408 line_breaker.Append(term);
409 show_variable[var_index] = coeff != 0.0 || show_variable[var_index];
410 }
411
412 const double lb = ct_proto.lower_bound();
413 const double ub = ct_proto.upper_bound();
414 if (lb == ub) {
415 line_breaker.Append(absl::StrCat(" = ", DoubleToString(ub), "\n"));
416 absl::StrAppend(output, " ", name, ": ", line_breaker.GetOutput());
417 } else {
418 if (ub != +kInfinity) {
419 std::string rhs_name(name);
420 if (lb != -kInfinity) {
421 absl::StrAppend(&rhs_name, "_rhs");
422 }
423 absl::StrAppend(output, " ", rhs_name, ": ", line_breaker.GetOutput());
424 const std::string relation =
425 absl::StrCat(" <= ", DoubleToString(ub), "\n");
426 // Here we have to make sure we do not add the relation to the contents
427 // of line_breaker, which may be used in the subsequent clause.
428 if (!line_breaker.WillFit(relation)) absl::StrAppend(output, "\n ");
429 absl::StrAppend(output, relation);
430 }
431 if (lb != -kInfinity) {
432 std::string lhs_name(name);
433 if (ub != +kInfinity) {
434 absl::StrAppend(&lhs_name, "_lhs");
435 }
436 absl::StrAppend(output, " ", lhs_name, ": ", line_breaker.GetOutput());
437 const std::string relation =
438 absl::StrCat(" >= ", DoubleToString(lb), "\n");
439 if (!line_breaker.WillFit(relation)) absl::StrAppend(output, "\n ");
440 absl::StrAppend(output, relation);
441 }
442 }
443
444 return true;
445}
446
447bool MPModelProtoExporter::WriteLpTerm(int var_index, double coefficient,
448 std::string* output) const {
449 output->clear();
450 if (var_index < 0 || var_index >= proto_.variable_size()) {
451 LOG(DFATAL) << "Reference to out-of-bounds variable index # " << var_index;
452 return false;
453 }
454 if (coefficient != 0.0) {
455 *output = absl::StrCat(DoubleToStringWithForcedSign(coefficient), " ",
456 exported_variable_names_[var_index], " ");
457 }
458 return true;
459}
460
461bool MPModelProtoExporter::WriteLpQuadraticTerm(int var1_index, int var2_index,
462 double coefficient,
463 std::string* output) const {
464 output->clear();
465 if (var1_index < 0 || var1_index >= proto_.variable_size()) {
466 LOG(DFATAL) << "Reference to out-of-bounds variable index # " << var1_index;
467 return false;
468 }
469 if (var2_index < 0 || var2_index >= proto_.variable_size()) {
470 LOG(DFATAL) << "Reference to out-of-bounds variable index # " << var2_index;
471 return false;
472 }
473 auto variable_product =
474 var1_index == var2_index
475 ? absl::StrCat(exported_variable_names_[var1_index], "^2")
476 : absl::StrCat(exported_variable_names_[var1_index], " * ",
477 exported_variable_names_[var2_index]);
478 if (coefficient != 0.0) {
479 *output = absl::StrCat(DoubleToStringWithForcedSign(coefficient), " ",
480 variable_product, " ");
481 }
482 return true;
483}
484
485namespace {
486bool IsBoolean(const MPVariableProto& var) {
487 return var.is_integer() && ceil(var.lower_bound()) == 0.0 &&
488 floor(var.upper_bound()) == 1.0;
489}
490
491void UpdateMaxSize(absl::string_view new_string, int* size) {
492 const int new_size = new_string.size();
493 if (new_size > *size) *size = new_size;
494}
495
496void UpdateMaxSize(double new_number, int* size) {
497 UpdateMaxSize(DoubleToString(new_number), size);
498}
499} // namespace
500
501void MPModelProtoExporter::Setup() {
502 num_binary_variables_ = 0;
503 num_integer_variables_ = 0;
504 for (const MPVariableProto& var : proto_.variable()) {
505 if (var.is_integer()) {
506 if (IsBoolean(var)) {
507 ++num_binary_variables_;
508 } else {
509 ++num_integer_variables_;
510 }
511 }
512 }
513 num_continuous_variables_ =
514 proto_.variable_size() - num_binary_variables_ - num_integer_variables_;
515}
516
517void MPModelProtoExporter::ComputeMpsSmartColumnWidths(bool obfuscated) {
518 // Minimum values for aesthetics (if columns are too narrow, MPS files are
519 // difficult to read).
520 int string_field_size = 6;
521 int number_field_size = 6;
522
523 for (const MPVariableProto& var : proto_.variable()) {
524 UpdateMaxSize(var.name(), &string_field_size);
525 UpdateMaxSize(var.objective_coefficient(), &number_field_size);
526 UpdateMaxSize(var.lower_bound(), &number_field_size);
527 UpdateMaxSize(var.upper_bound(), &number_field_size);
528 }
529
530 for (const MPConstraintProto& cst : proto_.constraint()) {
531 UpdateMaxSize(cst.name(), &string_field_size);
532 UpdateMaxSize(cst.lower_bound(), &number_field_size);
533 UpdateMaxSize(cst.upper_bound(), &number_field_size);
534 for (const double coeff : cst.coefficient()) {
535 UpdateMaxSize(coeff, &number_field_size);
536 }
537 }
538
539 // Maximum values for aesthetics. These are also the values used by other
540 // solvers.
541 string_field_size = std::min(string_field_size, 255);
542 number_field_size = std::min(number_field_size, 255);
543
544 // If the model is obfuscated, all names will have the same size, which we
545 // compute here.
546 if (obfuscated) {
547 int max_digits =
548 absl::StrCat(
549 std::max(proto_.variable_size(), proto_.constraint_size()) - 1)
550 .size();
551 string_field_size = std::max(6, max_digits + 1);
552 }
553
554 mps_header_format_ = absl::ParsedFormat<'s', 's'>::New(
555 absl::StrCat(" %-2s %-", string_field_size, "s"));
556 mps_format_ = absl::ParsedFormat<'s', 's'>::New(
557 absl::StrCat(" %-", string_field_size, "s %", number_field_size, "s"));
558}
559
560bool MPModelProtoExporter::ExportModelAsLpFormat(
561 const MPModelExportOptions& options, std::string* output) {
562 output->clear();
563 Setup();
564 const std::string kForbiddenFirstChars = "$.0123456789";
565 const std::string kForbiddenChars = " +-*/<>=:\\";
566 exported_constraint_names_ = ExtractAndProcessNames(
567 proto_.constraint(), "C", options.obfuscate, options.log_invalid_names,
568 kForbiddenFirstChars, kForbiddenChars);
569 exported_general_constraint_names_ = ExtractAndProcessNames(
570 proto_.general_constraint(), "C", options.obfuscate,
571 options.log_invalid_names, kForbiddenFirstChars, kForbiddenChars);
572 exported_variable_names_ = ExtractAndProcessNames(
573 proto_.variable(), "V", options.obfuscate, options.log_invalid_names,
574 kForbiddenFirstChars, kForbiddenChars);
575
576 // Comments section.
577 AppendComments("\\", output);
578 if (options.show_unused_variables) {
579 absl::StrAppendFormat(output, "\\ Unused variables are shown\n");
580 }
581
582 // Objective
583 absl::StrAppend(output, proto_.maximize() ? "Maximize\n" : "Minimize\n");
584 LineBreaker obj_line_breaker(options.max_line_length);
585 obj_line_breaker.Append(" Obj: ");
586 if (proto_.objective_offset() != 0.0) {
587 obj_line_breaker.Append(absl::StrCat(
588 DoubleToStringWithForcedSign(proto_.objective_offset()), " Constant "));
589 }
590 std::vector<bool> show_variable(proto_.variable_size(),
591 options.show_unused_variables);
592 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
593 const double coeff = proto_.variable(var_index).objective_coefficient();
594 std::string term;
595 if (!WriteLpTerm(var_index, coeff, &term)) {
596 return false;
597 }
598 obj_line_breaker.Append(term);
599 show_variable[var_index] = coeff != 0.0 || show_variable[var_index];
600 }
601 if (proto_.has_quadratic_objective()) {
602 obj_line_breaker.Append(" + [ ");
603 for (int i_term = 0;
604 i_term < proto_.quadratic_objective().qvar1_index_size(); ++i_term) {
605 const int qvar1 = proto_.quadratic_objective().qvar1_index(i_term);
606 const int qvar2 = proto_.quadratic_objective().qvar2_index(i_term);
607 const double coeff = proto_.quadratic_objective().coefficient(i_term);
608
609 std::string term;
610 if (!WriteLpQuadraticTerm(qvar1, qvar2, 2 * coeff, &term)) {
611 return false;
612 }
613 obj_line_breaker.Append(term);
614 show_variable[qvar1] = coeff != 0.0 || show_variable[qvar1];
615 show_variable[qvar2] = coeff != 0.0 || show_variable[qvar2];
616 }
617 obj_line_breaker.Append(" ] / 2");
618 }
619 // Linear Constraints
620 absl::StrAppend(output, obj_line_breaker.GetOutput(), "\nSubject to\n");
621 for (int cst_index = 0; cst_index < proto_.constraint_size(); ++cst_index) {
622 const MPConstraintProto& ct_proto = proto_.constraint(cst_index);
623 const std::string& name = exported_constraint_names_[cst_index];
624 LineBreaker line_breaker(options.max_line_length);
625 const int kNumFormattingChars = 10; // Overevaluated.
626 // Account for the size of the constraint name + possibly "_rhs" +
627 // the formatting characters here.
628 line_breaker.Consume(kNumFormattingChars + name.size());
629 if (!AppendConstraint(ct_proto, name, line_breaker, show_variable,
630 output)) {
631 return false;
632 }
633 }
634
635 // General Constraints
636 for (int cst_index = 0; cst_index < proto_.general_constraint_size();
637 ++cst_index) {
638 const MPGeneralConstraintProto& ct_proto =
639 proto_.general_constraint(cst_index);
640 const std::string& name = exported_general_constraint_names_[cst_index];
641 LineBreaker line_breaker(options.max_line_length);
642 const int kNumFormattingChars = 10; // Overevaluated.
643 // Account for the size of the constraint name + possibly "_rhs" +
644 // the formatting characters here.
645 line_breaker.Consume(kNumFormattingChars + name.size());
646
647 if (!ct_proto.has_indicator_constraint()) return false;
648 const MPIndicatorConstraint& indicator_ct = ct_proto.indicator_constraint();
649 const int binary_var_index = indicator_ct.var_index();
650 const int binary_var_value = indicator_ct.var_value();
651 if (binary_var_index < 0 || binary_var_index >= proto_.variable_size()) {
652 return false;
653 }
654 show_variable[binary_var_index] = true;
655 line_breaker.Append(absl::StrFormat(
656 "%s = %d -> ", exported_variable_names_[binary_var_index],
657 binary_var_value));
658 if (!AppendConstraint(indicator_ct.constraint(), name, line_breaker,
659 show_variable, output)) {
660 return false;
661 }
662 }
663
664 // Bounds
665 absl::StrAppend(output, "Bounds\n");
666 if (proto_.objective_offset() != 0.0) {
667 absl::StrAppend(output, " 1 <= Constant <= 1\n");
668 }
669 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
670 if (!show_variable[var_index]) continue;
671 const MPVariableProto& var_proto = proto_.variable(var_index);
672 const double lb = var_proto.lower_bound();
673 const double ub = var_proto.upper_bound();
674 if (var_proto.is_integer() && lb == round(lb) && ub == round(ub)) {
675 absl::StrAppendFormat(output, " %.0f <= %s <= %.0f\n", lb,
676 exported_variable_names_[var_index], ub);
677 } else {
678 absl::StrAppend(output, " ");
679 if (lb == -kInfinity && ub == kInfinity) {
680 absl::StrAppend(output, exported_variable_names_[var_index], " free");
681 } else {
682 if (lb != -kInfinity) {
683 absl::StrAppend(output, DoubleToString(lb), " <= ");
684 }
685 absl::StrAppend(output, exported_variable_names_[var_index]);
686 if (ub != kInfinity) {
687 absl::StrAppend(output, " <= ", DoubleToString(ub));
688 }
689 }
690 absl::StrAppend(output, "\n");
691 }
692 }
693
694 // Binaries
695 if (num_binary_variables_ > 0) {
696 absl::StrAppend(output, "Binaries\n");
697 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
698 if (!show_variable[var_index]) continue;
699 const MPVariableProto& var_proto = proto_.variable(var_index);
700 if (IsBoolean(var_proto)) {
701 absl::StrAppendFormat(output, " %s\n",
702 exported_variable_names_[var_index]);
703 }
704 }
705 }
706
707 // Generals
708 if (num_integer_variables_ > 0) {
709 absl::StrAppend(output, "Generals\n");
710 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
711 if (!show_variable[var_index]) continue;
712 const MPVariableProto& var_proto = proto_.variable(var_index);
713 if (var_proto.is_integer() && !IsBoolean(var_proto)) {
714 absl::StrAppend(output, " ", exported_variable_names_[var_index], "\n");
715 }
716 }
717 }
718 absl::StrAppend(output, "End\n");
719 return true;
720}
721
722void MPModelProtoExporter::AppendMpsPair(absl::string_view name, double value,
723 std::string* output) const {
724 absl::StrAppendFormat(output, *mps_format_, name, DoubleToString(value));
725}
726
727void MPModelProtoExporter::AppendMpsLineHeader(absl::string_view id,
728 absl::string_view name,
729 std::string* output) const {
730 absl::StrAppendFormat(output, *mps_header_format_, id, name);
731}
732
733void MPModelProtoExporter::AppendMpsLineHeaderWithNewLine(
734 absl::string_view id, absl::string_view name, std::string* output) const {
735 AppendMpsLineHeader(id, name, output);
736 absl::StripTrailingAsciiWhitespace(output);
737 absl::StrAppend(output, "\n");
738}
739
740void MPModelProtoExporter::AppendMpsTermWithContext(absl::string_view head_name,
741 absl::string_view name,
742 double value,
743 std::string* output) {
744 if (current_mps_column_ == 0) {
745 AppendMpsLineHeader("", head_name, output);
746 }
747 AppendMpsPair(name, value, output);
748 AppendNewLineIfTwoColumns(output);
749}
750
751void MPModelProtoExporter::AppendMpsBound(absl::string_view bound_type,
752 absl::string_view name, double value,
753 std::string* output) const {
754 AppendMpsLineHeader(bound_type, "BOUND", output);
755 AppendMpsPair(name, value, output);
756 absl::StripTrailingAsciiWhitespace(output);
757 absl::StrAppend(output, "\n");
758}
759
760void MPModelProtoExporter::AppendNewLineIfTwoColumns(std::string* output) {
761 ++current_mps_column_;
762 if (current_mps_column_ == 2) {
763 absl::StripTrailingAsciiWhitespace(output);
764 absl::StrAppend(output, "\n");
765 current_mps_column_ = 0;
766 }
767}
768
769void MPModelProtoExporter::AppendMpsColumns(
770 bool integrality,
771 absl::Span<const std::vector<std::pair<int, double>>> transpose,
772 std::string* output) {
773 current_mps_column_ = 0;
774 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
775 const MPVariableProto& var_proto = proto_.variable(var_index);
776 if (var_proto.is_integer() != integrality) continue;
777 const std::string& var_name = exported_variable_names_[var_index];
778 current_mps_column_ = 0;
779 if (var_proto.objective_coefficient() != 0.0) {
780 AppendMpsTermWithContext(var_name, "COST",
781 var_proto.objective_coefficient(), output);
782 }
783 for (const std::pair<int, double>& cst_index_and_coeff :
784 transpose[var_index]) {
785 const std::string& cst_name =
786 exported_constraint_names_[cst_index_and_coeff.first];
787 AppendMpsTermWithContext(var_name, cst_name, cst_index_and_coeff.second,
788 output);
789 }
790 AppendNewLineIfTwoColumns(output);
791 }
792}
793
794bool MPModelProtoExporter::ExportModelAsMpsFormat(
795 const MPModelExportOptions& options, std::string* output) {
796 output->clear();
797 Setup();
798 ComputeMpsSmartColumnWidths(options.obfuscate);
799 const std::string kForbiddenFirstChars = "";
800 const std::string kForbiddenChars = " ";
801 exported_constraint_names_ = ExtractAndProcessNames(
802 proto_.constraint(), "C", options.obfuscate, options.log_invalid_names,
803 kForbiddenFirstChars, kForbiddenChars);
804 exported_variable_names_ = ExtractAndProcessNames(
805 proto_.variable(), "V", options.obfuscate, options.log_invalid_names,
806 kForbiddenFirstChars, kForbiddenChars);
807
808 // Comments.
809 AppendComments("*", output);
810
811 // NAME section.
812 // TODO(user): Obfuscate the model name too if `obfuscate` is true.
813 absl::StrAppendFormat(output, "%-14s%s\n", "NAME", proto_.name());
814
815 if (proto_.maximize()) {
816 absl::StrAppendFormat(output, "OBJSENSE\n MAX\n");
817 }
818
819 // ROWS section.
820 current_mps_column_ = 0;
821 std::string rows_section;
822 AppendMpsLineHeaderWithNewLine("N", "COST", &rows_section);
823 for (int cst_index = 0; cst_index < proto_.constraint_size(); ++cst_index) {
824 const MPConstraintProto& ct_proto = proto_.constraint(cst_index);
825 const double lb = ct_proto.lower_bound();
826 const double ub = ct_proto.upper_bound();
827 const std::string& cst_name = exported_constraint_names_[cst_index];
828 if (lb == -kInfinity && ub == kInfinity) {
829 AppendMpsLineHeaderWithNewLine("N", cst_name, &rows_section);
830 } else if (lb == ub) {
831 AppendMpsLineHeaderWithNewLine("E", cst_name, &rows_section);
832 } else if (lb == -kInfinity) {
833 AppendMpsLineHeaderWithNewLine("L", cst_name, &rows_section);
834 } else {
835 AppendMpsLineHeaderWithNewLine("G", cst_name, &rows_section);
836 }
837 }
838 if (!rows_section.empty()) {
839 absl::StrAppend(output, "ROWS\n", rows_section);
840 }
841
842 // As the information regarding a column needs to be contiguous, we create
843 // a vector associating a variable index to a vector containing the indices
844 // of the constraints where this variable appears.
845 std::vector<std::vector<std::pair<int, double>>> transpose(
846 proto_.variable_size());
847 for (int cst_index = 0; cst_index < proto_.constraint_size(); ++cst_index) {
848 const MPConstraintProto& ct_proto = proto_.constraint(cst_index);
849 for (int k = 0; k < ct_proto.var_index_size(); ++k) {
850 const int var_index = ct_proto.var_index(k);
851 if (var_index < 0 || var_index >= proto_.variable_size()) {
852 LOG(DFATAL) << "In constraint #" << cst_index << ", var_index #" << k
853 << " is " << var_index << ", which is out of bounds.";
854 return false;
855 }
856 const double coeff = ct_proto.coefficient(k);
857 if (coeff != 0.0) {
858 transpose[var_index].push_back(
859 std::pair<int, double>(cst_index, coeff));
860 }
861 }
862 }
863
864 // COLUMNS section.
865 std::string columns_section;
866 AppendMpsColumns(/*integrality=*/true, transpose, &columns_section);
867 if (!columns_section.empty()) {
868 constexpr const char kIntMarkerFormat[] = " %-10s%-36s%-8s\n";
869 columns_section =
870 absl::StrFormat(kIntMarkerFormat, "INTSTART", "'MARKER'", "'INTORG'") +
871 columns_section;
872 absl::StrAppendFormat(&columns_section, kIntMarkerFormat, "INTEND",
873 "'MARKER'", "'INTEND'");
874 }
875 AppendMpsColumns(/*integrality=*/false, transpose, &columns_section);
876 if (!columns_section.empty()) {
877 absl::StrAppend(output, "COLUMNS\n", columns_section);
878 }
879
880 // RHS (right-hand-side) section.
881 current_mps_column_ = 0;
882 std::string rhs_section;
883 // Follow Gurobi's MPS format for objective offsets.
884 // See https://www.gurobi.com/documentation/9.1/refman/mps_format.html
885 if (proto_.objective_offset() != 0) {
886 AppendMpsTermWithContext("RHS", "COST", -proto_.objective_offset(),
887 &rhs_section);
888 }
889 for (int cst_index = 0; cst_index < proto_.constraint_size(); ++cst_index) {
890 const MPConstraintProto& ct_proto = proto_.constraint(cst_index);
891 const double lb = ct_proto.lower_bound();
892 const double ub = ct_proto.upper_bound();
893 const std::string& cst_name = exported_constraint_names_[cst_index];
894 if (lb != -kInfinity) {
895 AppendMpsTermWithContext("RHS", cst_name, lb, &rhs_section);
896 } else if (ub != +kInfinity) {
897 AppendMpsTermWithContext("RHS", cst_name, ub, &rhs_section);
898 }
899 }
900 AppendNewLineIfTwoColumns(&rhs_section);
901 if (!rhs_section.empty()) {
902 absl::StrAppend(output, "RHS\n", rhs_section);
903 }
904
905 // RANGES section.
906 current_mps_column_ = 0;
907 std::string ranges_section;
908 for (int cst_index = 0; cst_index < proto_.constraint_size(); ++cst_index) {
909 const MPConstraintProto& ct_proto = proto_.constraint(cst_index);
910 const double range = fabs(ct_proto.upper_bound() - ct_proto.lower_bound());
911 if (range != 0.0 && range != +kInfinity) {
912 const std::string& cst_name = exported_constraint_names_[cst_index];
913 AppendMpsTermWithContext("RANGE", cst_name, range, &ranges_section);
914 }
915 }
916 AppendNewLineIfTwoColumns(&ranges_section);
917 if (!ranges_section.empty()) {
918 absl::StrAppend(output, "RANGES\n", ranges_section);
919 }
920
921 // BOUNDS section.
922 current_mps_column_ = 0;
923 std::string bounds_section;
924 for (int var_index = 0; var_index < proto_.variable_size(); ++var_index) {
925 const MPVariableProto& var_proto = proto_.variable(var_index);
926 const double lb = var_proto.lower_bound();
927 const double ub = var_proto.upper_bound();
928 const std::string& var_name = exported_variable_names_[var_index];
929
930 if (lb == -kInfinity && ub == +kInfinity) {
931 AppendMpsLineHeader("FR", "BOUND", &bounds_section);
932 absl::StrAppendFormat(&bounds_section, " %s\n", var_name);
933 continue;
934 }
935
936 if (var_proto.is_integer()) {
937 if (IsBoolean(var_proto)) {
938 AppendMpsLineHeader("BV", "BOUND", &bounds_section);
939 absl::StrAppendFormat(&bounds_section, " %s\n", var_name);
940 } else {
941 if (lb == ub) {
942 AppendMpsBound("FX", var_name, lb, &bounds_section);
943 } else {
944 if (lb == -kInfinity) {
945 AppendMpsLineHeader("MI", "BOUND", &bounds_section);
946 absl::StrAppendFormat(&bounds_section, " %s\n", var_name);
947 } else if (lb != 0.0 || ub == kInfinity) {
948 // "LI" can be skipped if it's 0.
949 // There is one exception to that rule: if UI=+inf, we can't skip
950 // LI=0 or the variable will be parsed as binary.
951 AppendMpsBound("LI", var_name, lb, &bounds_section);
952 }
953 if (ub != kInfinity) {
954 AppendMpsBound("UI", var_name, ub, &bounds_section);
955 }
956 }
957 }
958 } else {
959 if (lb == ub) {
960 AppendMpsBound("FX", var_name, lb, &bounds_section);
961 } else {
962 if (lb == -kInfinity) {
963 AppendMpsLineHeader("MI", "BOUND", &bounds_section);
964 absl::StrAppendFormat(&bounds_section, " %s\n", var_name);
965 } else if (lb != 0.0) {
966 AppendMpsBound("LO", var_name, lb, &bounds_section);
967 }
968 if (lb == 0.0 && ub == +kInfinity) {
969 AppendMpsLineHeader("PL", "BOUND", &bounds_section);
970 absl::StrAppendFormat(&bounds_section, " %s\n", var_name);
971 } else if (ub != +kInfinity) {
972 AppendMpsBound("UP", var_name, ub, &bounds_section);
973 }
974 }
975 }
976 }
977 if (!bounds_section.empty()) {
978 absl::StrAppend(output, "BOUNDS\n", bounds_section);
979 }
980
981 absl::StrAppend(output, "ENDATA\n");
982 return true;
983}
984
985} // namespace
986} // namespace operations_research
#define ASSIGN_OR_RETURN(lhs, rexpr)
ABSL_RETIRED_FLAG(bool, lp_log_invalid_name, false, "DEPRECATED.")
Options Defaults()
Definition file.h:85
absl::Status SetContents(absl::string_view file_name, absl::string_view contents, Options options)
Definition file.cc:388
In SWIG mode, we don't want anything besides these top-level includes.
absl::Status WriteModelToMpsFile(absl::string_view filename, const MPModelProto &model, const MPModelExportOptions &options)
static constexpr double kInfinity
absl::StatusOr< std::string > ExportModelAsLpFormat(const MPModelProto &model, const MPModelExportOptions &options)
absl::StatusOr< std::string > ExportModelAsMpsFormat(const MPModelProto &model, const MPModelExportOptions &options)