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"
28 #include "ortools/base/logging.h"
29 #include "ortools/base/map_util.h"
30 #include "ortools/linear_solver/linear_solver.pb.h"
31 #include "ortools/util/fp_utils.h"
32 
33 ABSL_FLAG(bool, lp_log_invalid_name, false, "DEPRECATED.");
34 
35 namespace operations_research {
36 namespace {
37 
38 constexpr double kInfinity = std::numeric_limits<double>::infinity();
39 
40 class 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 
69 void 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 
78 class 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 
214 absl::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 
231 absl::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 
244 namespace {
245 MPModelProtoExporter::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 
252 namespace {
253 class 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 
263 std::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 
277 std::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 
298 template <class ListOfProtosWithNameFields>
299 std::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 
346 void 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 
366 namespace {
367 
368 std::string DoubleToStringWithForcedSign(double d) {
369  return absl::StrCat((d < 0 ? "" : "+"), (d));
370 }
371 
372 std::string DoubleToString(double d) { return absl::StrCat((d)); }
373 
374 } // namespace
375 
376 bool 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 
428 bool 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 
442 namespace {
443 bool IsBoolean(const MPVariableProto& var) {
444  return var.is_integer() && ceil(var.lower_bound()) == 0.0 &&
445  floor(var.upper_bound()) == 1.0;
446 }
447 
448 void UpdateMaxSize(const std::string& new_string, int* size) {
449  if (new_string.size() > *size) *size = new_string.size();
450 }
451 
452 void UpdateMaxSize(double new_number, int* size) {
453  UpdateMaxSize(DoubleToString(new_number), size);
454 }
455 } // namespace
456 
457 void 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 
477 void 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 
663 void MPModelProtoExporter::AppendMpsPair(const std::string& name, double value,
664  std::string* output) const {
665  absl::StrAppendFormat(output, *mps_format_, name, DoubleToString(value));
666 }
667 
668 void 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 
674 void 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 
681 void 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 
691 void 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 
700 void 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 
709 void 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