OR-Tools  8.2
lp_data.h
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 
14 //
15 // Storage classes for Linear Programs.
16 //
17 // LinearProgram stores the complete data for a Linear Program:
18 // - objective coefficients and offset,
19 // - cost coefficients,
20 // - coefficient matrix,
21 // - bounds for each variable,
22 // - bounds for each constraint.
23 
24 #ifndef OR_TOOLS_LP_DATA_LP_DATA_H_
25 #define OR_TOOLS_LP_DATA_LP_DATA_H_
26 
27 #include <algorithm> // for max
28 #include <map>
29 #include <string> // for string
30 #include <vector> // for vector
31 
32 #include "absl/container/flat_hash_map.h"
33 #include "absl/container/flat_hash_set.h"
34 #include "ortools/base/hash.h"
35 #include "ortools/base/int_type.h"
36 #include "ortools/base/logging.h" // for CHECK*
37 #include "ortools/base/macros.h" // for DISALLOW_COPY_AND_ASSIGN, NULL
38 #include "ortools/glop/parameters.pb.h"
40 #include "ortools/lp_data/sparse.h"
41 #include "ortools/util/fp_utils.h"
42 
43 namespace operations_research {
44 namespace glop {
45 
46 class SparseMatrixScaler;
47 
48 // The LinearProgram class is used to store a linear problem in a form
49 // accepted by LPSolver.
50 //
51 // In addition to the simple setter functions used to create such problems, the
52 // class also contains a few more advanced modification functions used primarily
53 // by preprocessors. A client shouldn't need to use them directly.
55  public:
56  enum class VariableType {
57  // The variable can take any value between and including its lower and upper
58  // bound.
59  CONTINUOUS,
60  // The variable must only take integer values.
61  INTEGER,
62  // The variable is implied integer variable i.e. it was continuous variable
63  // in the LP and was detected to take only integer values.
65  };
66 
67  LinearProgram();
68 
69  // Clears, i.e. reset the object to its initial value.
70  void Clear();
71 
72  // Name setter and getter.
73  void SetName(const std::string& name) { name_ = name; }
74  const std::string& name() const { return name_; }
75 
76  // Creates a new variable and returns its index.
77  // By default, the column bounds will be [0, infinity).
78  ColIndex CreateNewVariable();
79 
80  // Creates a new slack variable and returns its index. Do not use this method
81  // to create non-slack variables.
82  ColIndex CreateNewSlackVariable(bool is_integer_slack_variable,
83  Fractional lower_bound,
84  Fractional upper_bound,
85  const std::string& name);
86 
87  // Creates a new constraint and returns its index.
88  // By default, the constraint bounds will be [0, 0].
89  RowIndex CreateNewConstraint();
90 
91  // Same as CreateNewVariable() or CreateNewConstraint() but also assign an
92  // immutable id to the variable or constraint so they can be retrieved later.
93  // By default, the name is also set to this id, but it can be changed later
94  // without changing the id.
95  //
96  // Note that these ids are NOT copied over by the Populate*() functions.
97  //
98  // TODO(user): Move these and the two corresponding hash_table into a new
99  // LinearProgramBuilder class to simplify the code of some functions like
100  // DeleteColumns() here and make the behavior on copy clear? or simply remove
101  // them as it is almost as easy to maintain a hash_table on the client side.
102  ColIndex FindOrCreateVariable(const std::string& variable_id);
103  RowIndex FindOrCreateConstraint(const std::string& constraint_id);
104 
105  // Functions to set the name of a variable or constraint. Note that you
106  // won't be able to find those named variables/constraints with
107  // FindOrCreate{Variable|Constraint}().
108  // TODO(user): Add PopulateIdsFromNames() so names added via
109  // Set{Variable|Constraint}Name() can be found.
110  void SetVariableName(ColIndex col, absl::string_view name);
111  void SetConstraintName(RowIndex row, absl::string_view name);
112 
113  // Set the type of the variable.
114  void SetVariableType(ColIndex col, VariableType type);
115 
116  // Returns whether the variable at column col is constrained to be integer.
117  bool IsVariableInteger(ColIndex col) const;
118 
119  // Returns whether the variable at column col must take binary values or not.
120  bool IsVariableBinary(ColIndex col) const;
121 
122  // Defines lower and upper bounds for the variable at col. Note that the
123  // bounds may be set to +/- infinity. The variable must have been created
124  // before or this will crash in non-debug mode.
125  void SetVariableBounds(ColIndex col, Fractional lower_bound,
126  Fractional upper_bound);
127 
128  // Defines lower and upper bounds for the constraint at row. Note that the
129  // bounds may be set to +/- infinity. If the constraint wasn't created before,
130  // all the rows from the current GetNumberOfRows() to the given row will be
131  // created with a range [0,0].
132  void SetConstraintBounds(RowIndex row, Fractional lower_bound,
133  Fractional upper_bound);
134 
135  // Defines the coefficient for col / row.
136  void SetCoefficient(RowIndex row, ColIndex col, Fractional value);
137 
138  // Defines the objective coefficient of column col.
139  // It is set to 0.0 by default.
141 
142  // Define the objective offset (0.0 by default) and scaling factor (positive
143  // and equal to 1.0 by default). This is mainly used for displaying purpose
144  // and the real objective is factor * (objective + offset).
147 
148  // Defines the optimization direction. When maximize is true (resp. false),
149  // the objective is maximized (resp. minimized). The default is false.
150  void SetMaximizationProblem(bool maximize);
151 
152  // Calls CleanUp() on each columns.
153  // That is, removes duplicates, zeros, and orders the coefficients by row.
154  void CleanUp();
155 
156  // Returns true if all the columns are ordered by rows and contain no
157  // duplicates or zero entries (i.e. if IsCleanedUp() is true for all columns).
158  bool IsCleanedUp() const;
159 
160  // Functions that return the name of a variable or constraint. If the name is
161  // empty, they return a special name that depends on the index.
162  std::string GetVariableName(ColIndex col) const;
163  std::string GetConstraintName(RowIndex row) const;
164 
165  // Returns the type of variable.
166  VariableType GetVariableType(ColIndex col) const;
167 
168  // Returns true (resp. false) when the problem is a maximization
169  // (resp. minimization) problem.
170  bool IsMaximizationProblem() const { return maximize_; }
171 
172  // Returns the underlying SparseMatrix or its transpose (which may need to be
173  // computed).
174  const SparseMatrix& GetSparseMatrix() const { return matrix_; }
175  const SparseMatrix& GetTransposeSparseMatrix() const;
176 
177  // Some transformations are better done on the transpose representation. These
178  // two functions are here for that. Note that calling the first function and
179  // modifying the matrix does not change the result of any function in this
180  // class until UseTransposeMatrixAsReference() is called. This is because the
181  // transpose matrix is only used by GetTransposeSparseMatrix() and this
182  // function will recompute the whole transpose from the matrix. In particular,
183  // do not call GetTransposeSparseMatrix() while you modify the matrix returned
184  // by GetMutableTransposeSparseMatrix() otherwise all your changes will be
185  // lost.
186  //
187  // IMPORTANT: The matrix dimension cannot change. Otherwise this will cause
188  // problems. This is checked in debug mode when calling
189  // UseTransposeMatrixAsReference().
192 
193  // Release the memory used by the transpose matrix.
194  void ClearTransposeMatrix();
195 
196  // Gets the underlying SparseColumn with the given index.
197  // This is the same as GetSparseMatrix().column(col);
198  const SparseColumn& GetSparseColumn(ColIndex col) const;
199 
200  // Gets a pointer to the underlying SparseColumn with the given index.
202 
203  // Returns the number of variables.
204  ColIndex num_variables() const { return matrix_.num_cols(); }
205 
206  // Returns the number of constraints.
207  RowIndex num_constraints() const { return matrix_.num_rows(); }
208 
209  // Returns the number of entries in the linear program matrix.
210  EntryIndex num_entries() const { return matrix_.num_entries(); }
211 
212  // Return the lower bounds (resp. upper bounds) of constraints as a column
213  // vector. Note that the bound values may be +/- infinity.
215  return constraint_lower_bounds_;
216  }
218  return constraint_upper_bounds_;
219  }
220 
221  // Returns the objective coefficients (or cost) of variables as a row vector.
223  return objective_coefficients_;
224  }
225 
226  // Return the lower bounds (resp. upper bounds) of variables as a row vector.
227  // Note that the bound values may be +/- infinity.
229  return variable_lower_bounds_;
230  }
232  return variable_upper_bounds_;
233  }
234 
235  // Returns a row vector of VariableType representing types of variables.
237  return variable_types_;
238  }
239 
240  // Returns a list (technically a vector) of the ColIndices of the integer
241  // variables. This vector is lazily computed.
242  const std::vector<ColIndex>& IntegerVariablesList() const;
243 
244  // Returns a list (technically a vector) of the ColIndices of the binary
245  // integer variables. This vector is lazily computed.
246  const std::vector<ColIndex>& BinaryVariablesList() const;
247 
248  // Returns a list (technically a vector) of the ColIndices of the non-binary
249  // integer variables. This vector is lazily computed.
250  const std::vector<ColIndex>& NonBinaryVariablesList() const;
251 
252  // Returns the objective coefficient (or cost) of the given variable for the
253  // minimization version of the problem. That is, this is the same as
254  // GetObjectiveCoefficient() for a minimization problem and the opposite for a
255  // maximization problem.
257 
258  // Returns the objective offset and scaling factor.
259  Fractional objective_offset() const { return objective_offset_; }
261  return objective_scaling_factor_;
262  }
263 
264  // Checks if each variable respects its bounds, nothing else.
265  bool SolutionIsWithinVariableBounds(const DenseRow& solution,
266  Fractional absolute_tolerance) const;
267 
268  // Tests if the solution is LP-feasible within the given tolerance,
269  // i.e., satisfies all linear constraints within the absolute tolerance level.
270  // The solution does not need to satisfy the integer constraints.
271  bool SolutionIsLPFeasible(const DenseRow& solution,
272  Fractional absolute_tolerance) const;
273 
274  // Tests if the solution is integer within the given tolerance, i.e., all
275  // integer variables have integer values within the absolute tolerance level.
276  // The solution does not need to satisfy the linear constraints.
277  bool SolutionIsInteger(const DenseRow& solution,
278  Fractional absolute_tolerance) const;
279 
280  // Tests if the solution is both LP-feasible and integer within the tolerance.
281  bool SolutionIsMIPFeasible(const DenseRow& solution,
282  Fractional absolute_tolerance) const;
283 
284  // Fills the value of the slack from the other variable values.
285  // This requires that the slack have been added.
286  void ComputeSlackVariableValues(DenseRow* solution) const;
287 
288  // Functions to translate the sum(solution * objective_coefficients()) to
289  // the real objective of the problem and back. Note that these can also
290  // be used to translate bounds of the objective in the same way.
293 
294  // A short string with the problem dimension.
295  std::string GetDimensionString() const;
296 
297  // A short line with some stats on the problem coefficients.
298  std::string GetObjectiveStatsString() const;
299  std::string GetBoundsStatsString() const;
300 
301  // Returns a stringified LinearProgram. We use the LP file format used by
302  // lp_solve (see http://lpsolve.sourceforge.net/5.1/index.htm).
303  std::string Dump() const;
304 
305  // Returns a string that contains the provided solution of the LP in the
306  // format var1 = X, var2 = Y, var3 = Z, ...
307  std::string DumpSolution(const DenseRow& variable_values) const;
308 
309  // Returns a comma-separated string of integers containing (in that order)
310  // num_constraints_, num_variables_in_file_, num_entries_,
311  // num_objective_non_zeros_, num_rhs_non_zeros_, num_less_than_constraints_,
312  // num_greater_than_constraints_, num_equal_constraints_,
313  // num_range_constraints_, num_non_negative_variables_, num_boxed_variables_,
314  // num_free_variables_, num_fixed_variables_, num_other_variables_
315  // Very useful for reporting in the way used in journal articles.
316  std::string GetProblemStats() const;
317 
318  // Returns a string containing the same information as with GetProblemStats(),
319  // but in a much more human-readable form, for example:
320  // Number of rows : 27
321  // Number of variables in file : 32
322  // Number of entries (non-zeros) : 83
323  // Number of entries in the objective : 5
324  // Number of entries in the right-hand side : 7
325  // Number of <= constraints : 19
326  // Number of >= constraints : 0
327  // Number of = constraints : 8
328  // Number of range constraints : 0
329  // Number of non-negative variables : 32
330  // Number of boxed variables : 0
331  // Number of free variables : 0
332  // Number of fixed variables : 0
333  // Number of other variables : 0
334  std::string GetPrettyProblemStats() const;
335 
336  // Returns a comma-separated string of numbers containing (in that order)
337  // fill rate, max number of entries (length) in a row, average row length,
338  // standard deviation of row length, max column length, average column length,
339  // standard deviation of column length
340  // Useful for profiling algorithms.
341  //
342  // TODO(user): Theses are statistics about the underlying matrix and should be
343  // moved to SparseMatrix.
344  std::string GetNonZeroStats() const;
345 
346  // Returns a string containing the same information as with GetNonZeroStats(),
347  // but in a much more human-readable form, for example:
348  // Fill rate : 9.61%
349  // Entries in row (Max / average / std, dev.) : 9 / 3.07 / 1.94
350  // Entries in column (Max / average / std, dev.): 4 / 2.59 / 0.96
351  std::string GetPrettyNonZeroStats() const;
352 
353  // Adds slack variables to the problem for all rows which don't have slack
354  // variables. The new slack variables have bounds set to opposite of the
355  // bounds of the corresponding constraint, and changes all constraints to
356  // equality constraints with both bounds set to 0.0. If a constraint uses only
357  // integer variables and all their coefficients are integer, it will mark the
358  // slack variable as integer too.
359  //
360  // It is an error to call CreateNewVariable() or CreateNewConstraint() on a
361  // linear program on which this method was called.
362  //
363  // Note that many of the slack variables may not be useful at all, but in
364  // order not to recompute the matrix from one Solve() to the next, we always
365  // include all of them for a given lp matrix.
366  //
367  // TODO(user): investigate the impact on the running time. It seems low
368  // because we almost never iterate on fixed variables.
369  void AddSlackVariablesWhereNecessary(bool detect_integer_constraints);
370 
371  // Returns the index of the first slack variable in the linear program.
372  // Returns kInvalidCol if slack variables were not injected into the problem
373  // yet.
374  ColIndex GetFirstSlackVariable() const;
375 
376  // Returns the index of the slack variable corresponding to the given
377  // constraint. Returns kInvalidCol if slack variables were not injected into
378  // the problem yet.
379  ColIndex GetSlackVariable(RowIndex row) const;
380 
381  // Populates the calling object with the dual of the LinearProgram passed as
382  // parameter.
383  // For the general form that we solve,
384  // min c.x
385  // s.t. A_1 x = b_1
386  // A_2 x <= b_2
387  // A_3 x >= b_3
388  // l <= x <= u
389  // With x: n-column of unknowns
390  // l,u: n-columns of bound coefficients
391  // c: n-row of cost coefficients
392  // A_i: m_i×n-matrix of coefficients
393  // b_i: m_i-column of right-hand side coefficients
394  //
395  // The dual is
396  //
397  // max b_1.y_1 + b_2.y_2 + b_3.y_3 + l.v + u.w
398  // s.t. y_1 A_1 + y_2 A_2 + y_3 A_3 + v + w = c
399  // y_1 free, y_2 <= 0, y_3 >= 0, v >= 0, w <= 0
400  // With:
401  // y_i: m_i-row of unknowns
402  // v,w: n-rows of unknowns
403  //
404  // If range constraints are present, each of the corresponding row is
405  // duplicated (with one becoming lower bounded and the other upper bounded).
406  // For such ranged row in the primal, duplicated_rows[row] is set to the
407  // column index in the dual of the corresponding column duplicate. For
408  // non-ranged row, duplicated_rows[row] is set to kInvalidCol.
409  //
410  // IMPORTANT: The linear_program argument must not have any free constraints.
411  //
412  // IMPORTANT: This function always interprets the argument in its minimization
413  // form. So the dual solution of the dual needs to be negated if we want to
414  // compute the solution of a maximization problem given as an argument.
415  //
416  // TODO(user): Do not interpret as a minimization problem?
417  void PopulateFromDual(const LinearProgram& dual,
418  RowToColMapping* duplicated_rows);
419 
420  // Populates the calling object with the given LinearProgram.
421  void PopulateFromLinearProgram(const LinearProgram& linear_program);
422 
423  // Populates the calling object with the given LinearProgram while permuting
424  // variables and constraints. This is useful mainly for testing to generate
425  // a model with the same optimal objective value.
427  const LinearProgram& lp, const RowPermutation& row_permutation,
428  const ColumnPermutation& col_permutation);
429 
430  // Populates the calling object with the variables of the given LinearProgram.
431  // The function preserves the bounds, the integrality, the names of the
432  // variables and their objective coefficients. No constraints are copied (the
433  // matrix in the destination has 0 rows).
434  void PopulateFromLinearProgramVariables(const LinearProgram& linear_program);
435 
436  // Adds constraints to the linear program. The constraints are specified using
437  // a sparse matrix of the coefficients, and vectors that represent the
438  // left-hand side and the right-hand side of the constraints, i.e.
439  // left_hand_sides <= coefficients * variables <= right_hand_sides.
440  // The sizes of the columns and the names must be the same as the number of
441  // rows of the sparse matrix; the number of columns of the matrix must be
442  // equal to the number of variables of the linear program.
444  const DenseColumn& left_hand_sides,
445  const DenseColumn& right_hand_sides,
447 
448  // Calls the AddConstraints method. After adding the constraints it adds slack
449  // variables to the constraints.
451  const SparseMatrix& coefficients, const DenseColumn& left_hand_sides,
452  const DenseColumn& right_hand_sides,
454  bool detect_integer_constraints_for_slack);
455 
456  // Swaps the content of this LinearProgram with the one passed as argument.
457  // Works in O(1).
458  void Swap(LinearProgram* linear_program);
459 
460  // Removes the given column indices from the LinearProgram.
461  // This needs to allocate O(num_variables) memory to update variable_table_.
462  void DeleteColumns(const DenseBooleanRow& columns_to_delete);
463 
464  // Removes slack variables from the linear program. The method restores the
465  // bounds on constraints from the bounds of the slack variables, resets the
466  // index of the first slack variable, and removes the relevant columns from
467  // the matrix.
468  void DeleteSlackVariables();
469 
470  // Scales the problem using the given scaler.
471  void Scale(SparseMatrixScaler* scaler);
472 
473  // While Scale() makes sure the coefficients inside the linear program matrix
474  // are in [-1, 1], the objective coefficients, variable bounds and constraint
475  // bounds can still take large values (originally or due to the matrix
476  // scaling).
477  //
478  // It makes a lot of sense to also scale them given that internally we use
479  // absolute tolerances, and that it is nice to have the same behavior if users
480  // scale their problems. For instance one could change the unit of ALL the
481  // variables from Bytes to MBytes if they denote memory quantities. Or express
482  // a cost in dollars instead of thousands of dollars.
483  //
484  // Here, we are quite prudent and just make sure that the range of the
485  // non-zeros magnitudes contains one. So for instance if all non-zeros costs
486  // are in [1e4, 1e6], we will divide them by 1e4 so that the new range is
487  // [1, 1e2].
488  //
489  // TODO(user): Another more aggressive idea is to set the median/mean/geomean
490  // of the magnitudes to one. Investigate if this leads to better results. It
491  // does look more robust.
492  //
493  // Both functions update objective_scaling_factor()/objective_offset() and
494  // return the scaling coefficient so that:
495  // - For ScaleObjective(), the old coefficients can be retrieved by
496  // multiplying the new ones by the returned factor.
497  // - For ScaleBounds(), the old variable and constraint bounds can be
498  // retrieved by multiplying the new ones by the returned factor.
499  Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method);
501 
502  // Removes the given row indices from the LinearProgram.
503  // This needs to allocate O(num_variables) memory.
504  void DeleteRows(const DenseBooleanColumn& rows_to_delete);
505 
506  // Does basic checking on the linear program:
507  // - returns false if some coefficient are NaNs.
508  // - returns false if some coefficient other than the bounds are +/- infinity.
509  // Note that these conditions are also guarded by DCHECK on each of the
510  // SetXXX() function above.
511  bool IsValid() const;
512 
513  // Updates the bounds of the variables to the intersection of their original
514  // bounds and the bounds specified by variable_lower_bounds and
515  // variable_upper_bounds. If the new bounds of all variables are non-empty,
516  // returns true; otherwise, returns false.
520 
521  // Returns true if the linear program is in equation form Ax = 0 and all slack
522  // variables have been added. This is also called "computational form" in some
523  // of the literature.
524  bool IsInEquationForm() const;
525 
526  // Returns true if all integer variables in the linear program have strictly
527  // integer bounds.
528  bool BoundsOfIntegerVariablesAreInteger(Fractional tolerance) const;
529 
530  // Returns true if all integer constraints in the linear program have strictly
531  // integer bounds.
532  bool BoundsOfIntegerConstraintsAreInteger(Fractional tolerance) const;
533 
534  // Advanced usage. Bypass the costly call to CleanUp() when we known that the
535  // change we made kept the matrix columns "clean" (see the comment of
536  // CleanUp()). This is unsafe but can save a big chunk of the running time
537  // when one does a small amount of incremental changes to the problem (like
538  // adding a new row with no duplicates or zero entries).
540  DCHECK(matrix_.IsCleanedUp());
541  columns_are_known_to_be_clean_ = true;
542  }
543 
544  // If true, checks bound validity in debug mode.
545  void SetDcheckBounds(bool dcheck_bounds) { dcheck_bounds_ = dcheck_bounds; }
546 
547  private:
548  // A helper function that updates the vectors integer_variables_list_,
549  // binary_variables_list_, and non_binary_variables_list_.
550  void UpdateAllIntegerVariableLists() const;
551 
552  // A helper function to format problem statistics. Used by GetProblemStats()
553  // and GetPrettyProblemStats().
554  std::string ProblemStatFormatter(const absl::string_view format) const;
555 
556  // A helper function to format non-zero statistics. Used by GetNonZeroStats()
557  // and GetPrettyNonZeroStats().
558  std::string NonZeroStatFormatter(const absl::string_view format) const;
559 
560  // Resizes all row vectors to include index 'row'.
561  void ResizeRowsIfNeeded(RowIndex row);
562 
563  // Populates the definitions of variables, name and objective in the calling
564  // linear program with the data from the given linear program. The method does
565  // not touch the data structures for storing constraints.
566  void PopulateNameObjectiveAndVariablesFromLinearProgram(
567  const LinearProgram& linear_program);
568 
569  // Stores the linear program coefficients.
570  SparseMatrix matrix_;
571 
572  // The transpose of matrix_. This will be lazily recomputed by
573  // GetTransposeSparseMatrix() if transpose_matrix_is_consistent_ is false.
574  mutable SparseMatrix transpose_matrix_;
575 
576  // Constraint related quantities.
577  DenseColumn constraint_lower_bounds_;
578  DenseColumn constraint_upper_bounds_;
579  StrictITIVector<RowIndex, std::string> constraint_names_;
580 
581  // Variable related quantities.
582  DenseRow objective_coefficients_;
583  DenseRow variable_lower_bounds_;
584  DenseRow variable_upper_bounds_;
587 
588  // The vector of the indices of variables constrained to be integer.
589  // Note(user): the set of indices in integer_variables_list_ is the union
590  // of the set of indices in binary_variables_list_ and of the set of indices
591  // in non_binary_variables_list_ below.
592  mutable std::vector<ColIndex> integer_variables_list_;
593 
594  // The vector of the indices of variables constrained to be binary.
595  mutable std::vector<ColIndex> binary_variables_list_;
596 
597  // The vector of the indices of variables constrained to be integer, but not
598  // binary.
599  mutable std::vector<ColIndex> non_binary_variables_list_;
600 
601  // Map used to find the index of a variable based on its id.
602  absl::flat_hash_map<std::string, ColIndex> variable_table_;
603 
604  // Map used to find the index of a constraint based on its id.
605  absl::flat_hash_map<std::string, RowIndex> constraint_table_;
606 
607  // Offset of the objective, i.e. value of the objective when all variables
608  // are set to zero.
609  Fractional objective_offset_;
610  Fractional objective_scaling_factor_;
611 
612  // Boolean true (resp. false) when the problem is a maximization
613  // (resp. minimization) problem.
614  bool maximize_;
615 
616  // Boolean to speed-up multiple calls to IsCleanedUp() or
617  // CleanUp(). Mutable so IsCleanedUp() can be const.
618  mutable bool columns_are_known_to_be_clean_;
619 
620  // Whether transpose_matrix_ is guaranteed to be the transpose of matrix_.
621  mutable bool transpose_matrix_is_consistent_;
622 
623  // Whether integer_variables_list_ is consistent with the current
624  // LinearProgram.
625  mutable bool integer_variables_list_is_consistent_;
626 
627  // The name of the LinearProgram.
628  std::string name_;
629 
630  // The index of the first slack variable added to the linear program by
631  // LinearProgram::AddSlackVariablesForAllRows().
632  ColIndex first_slack_variable_;
633 
634  // If true, checks bounds in debug mode.
635  bool dcheck_bounds_ = true;
636 
637  friend void Scale(LinearProgram* lp, SparseMatrixScaler* scaler,
638  GlopParameters::ScalingAlgorithm scaling_method);
639 
640  DISALLOW_COPY_AND_ASSIGN(LinearProgram);
641 };
642 
643 // --------------------------------------------------------
644 // ProblemSolution
645 // --------------------------------------------------------
646 // Contains the solution of a LinearProgram as returned by a preprocessor.
648  ProblemSolution(RowIndex num_rows, ColIndex num_cols)
650  primal_values(num_cols, 0.0),
651  dual_values(num_rows, 0.0),
654  // The solution status.
656 
657  // The actual primal/dual solution values. This is what most clients will
658  // need, and this is enough for LPSolver to easily check the optimality.
661 
662  // The status of the variables and constraints which is difficult to
663  // reconstruct from the solution values alone. Some remarks:
664  // - From this information alone, by factorizing the basis, it is easy to
665  // reconstruct the primal and dual values.
666  // - The main difficulty to construct this from the solution values is to
667  // reconstruct the optimal basis if some basic variables are exactly at
668  // one of their bounds (and their reduced costs are close to zero).
669  // - The non-basic information (VariableStatus::FIXED_VALUE,
670  // VariableStatus::AT_LOWER_BOUND, VariableStatus::AT_UPPER_BOUND,
671  // VariableStatus::FREE) is easy to construct for variables (because
672  // they are at their exact bounds). They can be guessed for constraints
673  // (here a small precision error is unavoidable). However, it is useful to
674  // carry this exact information during post-solve.
677 
678  std::string DebugString() const;
679 };
680 
681 // Helper function to check the bounds of the SetVariableBounds() and
682 // SetConstraintBounds() functions.
683 inline bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound) {
684  if (std::isnan(lower_bound)) return false;
685  if (std::isnan(upper_bound)) return false;
686  if (lower_bound == kInfinity && upper_bound == kInfinity) return false;
687  if (lower_bound == -kInfinity && upper_bound == -kInfinity) return false;
688  if (lower_bound > upper_bound) return false;
689  return true;
690 }
691 
692 } // namespace glop
693 } // namespace operations_research
694 
695 #endif // OR_TOOLS_LP_DATA_LP_DATA_H_
#define DCHECK(condition)
Definition: base/logging.h:884
SparseMatrix * GetMutableTransposeSparseMatrix()
Definition: lp_data.cc:385
std::string GetObjectiveStatsString() const
Definition: lp_data.cc:450
void SetObjectiveScalingFactor(Fractional objective_scaling_factor)
Definition: lp_data.cc:335
void PopulateFromPermutedLinearProgram(const LinearProgram &lp, const RowPermutation &row_permutation, const ColumnPermutation &col_permutation)
Definition: lp_data.cc:881
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
std::string GetVariableName(ColIndex col) const
Definition: lp_data.cc:359
void SetConstraintName(RowIndex row, absl::string_view name)
Definition: lp_data.cc:244
const SparseMatrix & GetTransposeSparseMatrix() const
Definition: lp_data.cc:375
bool SolutionIsWithinVariableBounds(const DenseRow &solution, Fractional absolute_tolerance) const
Definition: lp_data.cc:479
bool BoundsOfIntegerConstraintsAreInteger(Fractional tolerance) const
Definition: lp_data.cc:1498
void SetObjectiveOffset(Fractional objective_offset)
Definition: lp_data.cc:330
void PopulateFromLinearProgram(const LinearProgram &linear_program)
Definition: lp_data.cc:860
void Scale(SparseMatrixScaler *scaler)
std::string GetPrettyProblemStats() const
Definition: lp_data.cc:662
bool SolutionIsMIPFeasible(const DenseRow &solution, Fractional absolute_tolerance) const
Definition: lp_data.cc:527
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
const SparseMatrix & GetSparseMatrix() const
Definition: lp_data.h:174
bool BoundsOfIntegerVariablesAreInteger(Fractional tolerance) const
Definition: lp_data.cc:1482
void SetVariableName(ColIndex col, absl::string_view name)
Definition: lp_data.cc:231
std::string DumpSolution(const DenseRow &variable_values) const
Definition: lp_data.cc:645
ColIndex GetSlackVariable(RowIndex row) const
Definition: lp_data.cc:753
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
ColIndex FindOrCreateVariable(const std::string &variable_id)
Definition: lp_data.cc:204
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
std::string GetBoundsStatsString() const
Definition: lp_data.cc:463
Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method)
Definition: lp_data.cc:1186
const std::vector< ColIndex > & BinaryVariablesList() const
Definition: lp_data.cc:284
const DenseRow & objective_coefficients() const
Definition: lp_data.h:222
Fractional RemoveObjectiveScalingAndOffset(Fractional value) const
Definition: lp_data.cc:553
const std::vector< ColIndex > & IntegerVariablesList() const
Definition: lp_data.cc:279
Fractional GetObjectiveCoefficientForMinimizationVersion(ColIndex col) const
Definition: lp_data.cc:418
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
ColIndex CreateNewSlackVariable(bool is_integer_slack_variable, Fractional lower_bound, Fractional upper_bound, const std::string &name)
Definition: lp_data.cc:175
VariableType GetVariableType(ColIndex col) const
Definition: lp_data.cc:371
RowIndex FindOrCreateConstraint(const std::string &constraint_id)
Definition: lp_data.cc:217
void SetDcheckBounds(bool dcheck_bounds)
Definition: lp_data.h:545
void Swap(LinearProgram *linear_program)
Definition: lp_data.cc:1029
void AddConstraints(const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names)
Definition: lp_data.cc:970
std::string GetPrettyNonZeroStats() const
Definition: lp_data.cc:688
void SetVariableType(ColIndex col, VariableType type)
Definition: lp_data.cc:235
const std::vector< ColIndex > & NonBinaryVariablesList() const
Definition: lp_data.cc:289
bool SolutionIsInteger(const DenseRow &solution, Fractional absolute_tolerance) const
Definition: lp_data.cc:515
SparseColumn * GetMutableSparseColumn(ColIndex col)
Definition: lp_data.cc:412
std::string GetConstraintName(RowIndex row) const
Definition: lp_data.cc:365
void SetName(const std::string &name)
Definition: lp_data.h:73
void AddSlackVariablesWhereNecessary(bool detect_integer_constraints)
Definition: lp_data.cc:695
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
void ComputeSlackVariableValues(DenseRow *solution) const
Definition: lp_data.cc:533
bool SolutionIsLPFeasible(const DenseRow &solution, Fractional absolute_tolerance) const
Definition: lp_data.cc:495
bool IsVariableInteger(ColIndex col) const
Definition: lp_data.cc:294
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
bool IsVariableBinary(ColIndex col) const
Definition: lp_data.cc:299
Fractional ApplyObjectiveScalingAndOffset(Fractional value) const
Definition: lp_data.cc:548
void DeleteRows(const DenseBooleanColumn &rows_to_delete)
Definition: lp_data.cc:1256
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
Definition: lp_data.cc:1063
const DenseRow & variable_upper_bounds() const
Definition: lp_data.h:231
bool UpdateVariableBoundsToIntersection(const DenseRow &variable_lower_bounds, const DenseRow &variable_upper_bounds)
Definition: lp_data.cc:1004
void PopulateFromDual(const LinearProgram &dual, RowToColMapping *duplicated_rows)
Definition: lp_data.cc:762
const std::string & name() const
Definition: lp_data.h:74
void PopulateFromLinearProgramVariables(const LinearProgram &linear_program)
Definition: lp_data.cc:933
std::string GetDimensionString() const
Definition: lp_data.cc:424
Fractional objective_scaling_factor() const
Definition: lp_data.h:260
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
void AddConstraintsWithSlackVariables(const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names, bool detect_integer_constraints_for_slack)
Definition: lp_data.cc:995
const StrictITIVector< ColIndex, VariableType > variable_types() const
Definition: lp_data.h:236
const SparseColumn & GetSparseColumn(ColIndex col) const
Definition: lp_data.cc:408
int64 value
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.h:683
const double kInfinity
Definition: lp_types.h:83
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > coefficients
ProblemSolution(RowIndex num_rows, ColIndex num_cols)
Definition: lp_data.h:648
ConstraintStatusColumn constraint_statuses
Definition: lp_data.h:676