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