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