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