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"
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"
42
43namespace operations_research {
44namespace glop {
45
46class 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.
64 IMPLIED_INTEGER
65 };
66
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_; }
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.
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.
469
470 // Scales the problem using the given 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.
529
530 // Returns true if all integer constraints in the linear program have strictly
531 // integer bounds.
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_;
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.
683inline 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
const std::string & name() const
Definition: lp_data.h:74
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
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
ColIndex FindOrCreateVariable(const std::string &variable_id)
Definition: lp_data.cc:204
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 DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
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
const DenseRow & variable_upper_bounds() const
Definition: lp_data.h:231
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
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
void SetName(const std::string &name)
Definition: lp_data.h:73
const DenseRow & objective_coefficients() const
Definition: lp_data.h:222
void AddSlackVariablesWhereNecessary(bool detect_integer_constraints)
Definition: lp_data.cc:695
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
const StrictITIVector< ColIndex, VariableType > variable_types() const
Definition: lp_data.h:236
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
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 SparseMatrix & GetSparseMatrix() const
Definition: lp_data.h:174
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
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 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