OR-Tools  8.2
preprocessor.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// This file contains the presolving code for a LinearProgram.
16//
17// A classical reference is:
18// E. D. Andersen, K. D. Andersen, "Presolving in linear programming.",
19// Mathematical Programming 71 (1995) 221-245.
20
21#ifndef OR_TOOLS_GLOP_PREPROCESSOR_H_
22#define OR_TOOLS_GLOP_PREPROCESSOR_H_
23
24#include <memory>
25
27#include "ortools/glop/parameters.pb.h"
32
33namespace operations_research {
34namespace glop {
35
36// --------------------------------------------------------
37// Preprocessor
38// --------------------------------------------------------
39// This is the base class for preprocessors.
40//
41// TODO(user): On most preprocessors, calling Run() more than once will not work
42// as expected. Fix? or document and crash in debug if this happens.
44 public:
45 explicit Preprocessor(const GlopParameters* parameters);
46 Preprocessor(const Preprocessor&) = delete;
48 virtual ~Preprocessor();
49
50 // Runs the preprocessor by modifying the given linear program. Returns true
51 // if a postsolve step will be needed (i.e. RecoverSolution() is not the
52 // identity function). Also updates status_ to something different from
53 // ProblemStatus::INIT if the problem was solved (including bad statuses
54 // like ProblemStatus::ABNORMAL, ProblemStatus::INFEASIBLE, etc.).
55 virtual bool Run(LinearProgram* lp) = 0;
56
57 // Stores the optimal solution of the linear program that was passed to
58 // Run(). The given solution needs to be set to the optimal solution of the
59 // linear program "modified" by Run().
60 virtual void RecoverSolution(ProblemSolution* solution) const = 0;
61
62 // Returns the status of the preprocessor.
63 // A status different from ProblemStatus::INIT means that the problem is
64 // solved and there is not need to call subsequent preprocessors.
65 ProblemStatus status() const { return status_; }
66
67 // Some preprocessors only need minimal changes when used with integer
68 // variables in a MIP context. Setting this to true allows to consider integer
69 // variables as integer in these preprocessors.
70 //
71 // Not all preprocessors handle integer variables correctly, calling this
72 // function on them will cause a LOG(FATAL).
73 virtual void UseInMipContext() { in_mip_context_ = true; }
74
76
77 protected:
78 // Returns true if a is less than b (or slighlty greater than b with a given
79 // tolerance).
82 a, b, parameters_.solution_feasibility_tolerance());
83 }
85 Fractional b) const {
86 // TODO(user): use an absolute tolerance here to be even more defensive?
88 a, b, parameters_.preprocessor_zero_tolerance());
89 }
90
92 const GlopParameters& parameters_;
94 std::unique_ptr<TimeLimit> infinite_time_limit_;
96};
97
98// --------------------------------------------------------
99// MainLpPreprocessor
100// --------------------------------------------------------
101// This is the main LP preprocessor responsible for calling all the other
102// preprocessors in this file, possibly more than once.
104 public:
105 explicit MainLpPreprocessor(const GlopParameters* parameters)
110
111 bool Run(LinearProgram* lp) final;
112 void RecoverSolution(ProblemSolution* solution) const override;
113
114 private:
115 // Runs the given preprocessor and push it on preprocessors_ for the postsolve
116 // step when needed.
117 void RunAndPushIfRelevant(std::unique_ptr<Preprocessor> preprocessor,
118 const std::string& name, TimeLimit* time_limit,
119 LinearProgram* lp);
120
121 // Stack of preprocessors currently applied to the lp that needs postsolve.
122 //
123 // TODO(user): This is mutable so that the preprocessor can be freed as soon
124 // as their RecoverSolution() is called. Make RecoverSolution() non-const or
125 // remove this optimization?
126 mutable std::vector<std::unique_ptr<Preprocessor>> preprocessors_;
127
128 // Initial dimension of the lp given to Run(), for displaying purpose.
129 EntryIndex initial_num_entries_;
130 RowIndex initial_num_rows_;
131 ColIndex initial_num_cols_;
132};
133
134// --------------------------------------------------------
135// ColumnDeletionHelper
136// --------------------------------------------------------
137// Help preprocessors deal with column deletion.
139 public:
143
144 // Remember the given column as "deleted" so that it can later be restored
145 // by RestoreDeletedColumns(). Optionally, the caller may indicate the
146 // value and status of the corresponding variable so that it is automatically
147 // restored; if they don't then the restored value and status will be junk
148 // and must be set by the caller.
149 //
150 // The actual deletion is done by LinearProgram::DeleteColumns().
151 void MarkColumnForDeletion(ColIndex col);
153 VariableStatus status);
154
155 // From a solution omitting the deleted column, expands it and inserts the
156 // deleted columns. If values and statuses for the corresponding variables
157 // were saved, they'll be restored.
158 void RestoreDeletedColumns(ProblemSolution* solution) const;
159
160 // Returns whether or not the given column is marked for deletion.
161 bool IsColumnMarked(ColIndex col) const {
162 return col < is_column_deleted_.size() && is_column_deleted_[col];
163 }
164
165 // Returns a Boolean vector of the column to be deleted.
166 const DenseBooleanRow& GetMarkedColumns() const { return is_column_deleted_; }
167
168 // Returns true if no columns have been marked for deletion.
169 bool IsEmpty() const { return is_column_deleted_.empty(); }
170
171 // Restores the class to its initial state.
172 void Clear();
173
174 // Returns the value that will be restored by
175 // RestoreDeletedColumnInSolution(). Note that only the marked position value
176 // make sense.
177 const DenseRow& GetStoredValue() const { return stored_value_; }
178
179 private:
180 DenseBooleanRow is_column_deleted_;
181
182 // Note that this vector has the same size as is_column_deleted_ and that
183 // the value of the variable corresponding to a deleted column col is stored
184 // at position col. Values of columns not deleted are not used. We use this
185 // data structure so columns can be deleted in any order if needed.
186 DenseRow stored_value_;
187 VariableStatusRow stored_status_;
188};
189
190// --------------------------------------------------------
191// RowDeletionHelper
192// --------------------------------------------------------
193// Help preprocessors deal with row deletion.
195 public:
199
200 // Returns true if no rows have been marked for deletion.
201 bool IsEmpty() const { return is_row_deleted_.empty(); }
202
203 // Restores the class to its initial state.
204 void Clear();
205
206 // Adds a deleted row to the helper.
207 void MarkRowForDeletion(RowIndex row);
208
209 // If the given row was marked for deletion, unmark it.
210 void UnmarkRow(RowIndex row);
211
212 // Returns a Boolean vector of the row to be deleted.
213 const DenseBooleanColumn& GetMarkedRows() const;
214
215 // Returns whether or not the given row is marked for deletion.
216 bool IsRowMarked(RowIndex row) const {
217 return row < is_row_deleted_.size() && is_row_deleted_[row];
218 }
219
220 // From a solution without the deleted rows, expand it by restoring
221 // the deleted rows to a VariableStatus::BASIC status with 0.0 value.
222 // This latter value is important, many preprocessors rely on it.
223 void RestoreDeletedRows(ProblemSolution* solution) const;
224
225 private:
226 DenseBooleanColumn is_row_deleted_;
227};
228
229// --------------------------------------------------------
230// EmptyColumnPreprocessor
231// --------------------------------------------------------
232// Removes the empty columns from the problem.
234 public:
235 explicit EmptyColumnPreprocessor(const GlopParameters* parameters)
240 bool Run(LinearProgram* lp) final;
241 void RecoverSolution(ProblemSolution* solution) const final;
242
243 private:
244 ColumnDeletionHelper column_deletion_helper_;
245};
246
247// --------------------------------------------------------
248// ProportionalColumnPreprocessor
249// --------------------------------------------------------
250// Removes the proportional columns from the problem when possible. Two columns
251// are proportional if one is a non-zero scalar multiple of the other.
252//
253// Note that in the linear programming literature, two proportional columns are
254// usually called duplicates. The notion is the same once the problem has been
255// scaled. However, during presolve the columns can't be assumed to be scaled,
256// so it makes sense to use the more general notion of proportional columns.
258 public:
259 explicit ProportionalColumnPreprocessor(const GlopParameters* parameters)
262 delete;
264 const ProportionalColumnPreprocessor&) = delete;
266 bool Run(LinearProgram* lp) final;
267 void RecoverSolution(ProblemSolution* solution) const final;
268 void UseInMipContext() final { LOG(FATAL) << "Not implemented."; }
269
270 private:
271 // Postsolve information about proportional columns with the same scaled cost
272 // that were merged during presolve.
273
274 // The proportionality factor of each column. If two columns are proportional
275 // with factor p1 and p2 then p1 times the first column is the same as p2
276 // times the second column.
277 DenseRow column_factors_;
278
279 // If merged_columns_[col] != kInvalidCol, then column col has been merged
280 // into the column merged_columns_[col].
281 ColMapping merged_columns_;
282
283 // The old and new variable bounds.
284 DenseRow lower_bounds_;
285 DenseRow upper_bounds_;
286 DenseRow new_lower_bounds_;
287 DenseRow new_upper_bounds_;
288
289 ColumnDeletionHelper column_deletion_helper_;
290};
291
292// --------------------------------------------------------
293// ProportionalRowPreprocessor
294// --------------------------------------------------------
295// Removes the proportional rows from the problem.
296// The linear programming literature also calls such rows duplicates, see the
297// same remark above for columns in ProportionalColumnPreprocessor.
299 public:
300 explicit ProportionalRowPreprocessor(const GlopParameters* parameters)
304 delete;
306 bool Run(LinearProgram* lp) final;
307 void RecoverSolution(ProblemSolution* solution) const final;
308
309 private:
310 // Informations about proportional rows, only filled for such rows.
311 DenseColumn row_factors_;
312 RowMapping upper_bound_sources_;
313 RowMapping lower_bound_sources_;
314
315 bool lp_is_maximization_problem_;
316 RowDeletionHelper row_deletion_helper_;
317};
318
319// --------------------------------------------------------
320// SingletonPreprocessor
321// --------------------------------------------------------
322// Removes as many singleton rows and singleton columns as possible from the
323// problem. Note that not all types of singleton columns can be removed. See the
324// comments below on the SingletonPreprocessor functions for more details.
325//
326// TODO(user): Generalize the design used in this preprocessor to a general
327// "propagation" framework in order to apply as many reductions as possible in
328// an efficient manner.
329
330// Holds a triplet (row, col, coefficient).
331struct MatrixEntry {
332 MatrixEntry(RowIndex _row, ColIndex _col, Fractional _coeff)
333 : row(_row), col(_col), coeff(_coeff) {}
334 RowIndex row;
335 ColIndex col;
337};
338
339// Stores the information needed to undo a singleton row/column deletion.
341 public:
342 // The type of a given operation.
343 typedef enum {
349
350 // Stores the information, which together with the field deleted_columns_ and
351 // deleted_rows_ of SingletonPreprocessor, are needed to undo an operation
352 // with the given type. Note that all the arguments must refer to the linear
353 // program BEFORE the operation is applied.
354 SingletonUndo(OperationType type, const LinearProgram& lp, MatrixEntry e,
355 ConstraintStatus status);
356
357 // Undo the operation saved in this class, taking into account the deleted
358 // columns and rows passed by the calling instance of SingletonPreprocessor.
359 // Note that the operations must be undone in the reverse order of the one
360 // in which they were applied.
361 void Undo(const GlopParameters& parameters,
362 const SparseMatrix& deleted_columns,
363 const SparseMatrix& deleted_rows, ProblemSolution* solution) const;
364
365 private:
366 // Actual undo functions for each OperationType.
367 // Undo() just calls the correct one.
368 void SingletonRowUndo(const SparseMatrix& deleted_columns,
369 ProblemSolution* solution) const;
370 void ZeroCostSingletonColumnUndo(const GlopParameters& parameters,
371 const SparseMatrix& deleted_rows,
372 ProblemSolution* solution) const;
373 void SingletonColumnInEqualityUndo(const GlopParameters& parameters,
374 const SparseMatrix& deleted_rows,
375 ProblemSolution* solution) const;
376 void MakeConstraintAnEqualityUndo(ProblemSolution* solution) const;
377
378 // All the information needed during undo.
379 OperationType type_;
380 bool is_maximization_;
381 MatrixEntry e_;
382 Fractional cost_;
383
384 // TODO(user): regroup the pair (lower bound, upper bound) in a bound class?
385 Fractional variable_lower_bound_;
386 Fractional variable_upper_bound_;
387 Fractional constraint_lower_bound_;
388 Fractional constraint_upper_bound_;
389
390 // This in only used with MAKE_CONSTRAINT_AN_EQUALITY undo.
391 // TODO(user): Clean that up using many Undo classes and virtual functions.
392 ConstraintStatus constraint_status_;
393};
394
395// Deletes as many singleton rows or singleton columns as possible. Note that
396// each time we delete a row or a column, new singletons may be created.
398 public:
399 explicit SingletonPreprocessor(const GlopParameters* parameters)
404 bool Run(LinearProgram* lp) final;
405 void RecoverSolution(ProblemSolution* solution) const final;
406
407 private:
408 // Returns the MatrixEntry of the given singleton row or column, taking into
409 // account the rows and columns that were already deleted.
410 MatrixEntry GetSingletonColumnMatrixEntry(ColIndex col,
411 const SparseMatrix& matrix);
412 MatrixEntry GetSingletonRowMatrixEntry(RowIndex row,
413 const SparseMatrix& matrix_transpose);
414
415 // A singleton row can always be removed by changing the corresponding
416 // variable bounds to take into account the bounds on this singleton row.
417 void DeleteSingletonRow(MatrixEntry e, LinearProgram* lp);
418
419 // Internal operation when removing a zero-cost singleton column corresponding
420 // to the given entry. This modifies the constraint bounds to take into acount
421 // the bounds of the corresponding variable.
422 void UpdateConstraintBoundsWithVariableBounds(MatrixEntry e,
423 LinearProgram* lp);
424
425 // Checks if all other variables in the constraint are integer and the
426 // coefficients are divisible by the coefficient of the singleton variable.
427 bool IntegerSingletonColumnIsRemovable(const MatrixEntry& matrix_entry,
428 const LinearProgram& lp) const;
429
430 // A singleton column with a cost of zero can always be removed by changing
431 // the corresponding constraint bounds to take into acount the bound of this
432 // singleton column.
433 void DeleteZeroCostSingletonColumn(const SparseMatrix& matrix_transpose,
434 MatrixEntry e, LinearProgram* lp);
435
436 // Returns true if the constraint associated to the given singleton column was
437 // an equality or could be made one:
438 // If a singleton variable is free in a direction that improves the cost, then
439 // we can always move it as much as possible in this direction. Only the
440 // constraint will stop us, making it an equality. If the constraint doesn't
441 // stop us, then the program is unbounded (provided that there is a feasible
442 // solution).
443 //
444 // Note that this operation does not need any "undo" during the post-solve. At
445 // optimality, the dual value on the constraint row will be of the correct
446 // sign, and relaxing the constraint bound will not impact the dual
447 // feasibility of the solution.
448 //
449 // TODO(user): this operation can be generalized to columns with just one
450 // blocking constraint. Investigate how to use this. The 'reverse' can
451 // probably also be done, relaxing a constraint that is blocking a
452 // unconstrained variable.
453 bool MakeConstraintAnEqualityIfPossible(const SparseMatrix& matrix_transpose,
454 MatrixEntry e, LinearProgram* lp);
455
456 // If a singleton column appears in an equality, we can remove its cost by
457 // changing the other variables cost using the constraint. We can then delete
458 // the column like in DeleteZeroCostSingletonColumn().
459 void DeleteSingletonColumnInEquality(const SparseMatrix& matrix_transpose,
460 MatrixEntry e, LinearProgram* lp);
461
462 ColumnDeletionHelper column_deletion_helper_;
463 RowDeletionHelper row_deletion_helper_;
464 std::vector<SingletonUndo> undo_stack_;
465
466 // This is used as a "cache" by MakeConstraintAnEqualityIfPossible() to avoid
467 // scanning more than once each row. See the code to see how this is used.
468 absl::StrongVector<RowIndex, bool> row_sum_is_cached_;
470 row_lb_sum_;
472 row_ub_sum_;
473
474 // The columns that are deleted by this preprocessor.
475 SparseMatrix deleted_columns_;
476 // The transpose of the rows that are deleted by this preprocessor.
477 // TODO(user): implement a RowMajorSparseMatrix class to simplify the code.
478 SparseMatrix deleted_rows_;
479};
480
481// --------------------------------------------------------
482// FixedVariablePreprocessor
483// --------------------------------------------------------
484// Removes the fixed variables from the problem.
486 public:
487 explicit FixedVariablePreprocessor(const GlopParameters* parameters)
491 delete;
493 bool Run(LinearProgram* lp) final;
494 void RecoverSolution(ProblemSolution* solution) const final;
495
496 private:
497 ColumnDeletionHelper column_deletion_helper_;
498};
499
500// --------------------------------------------------------
501// ForcingAndImpliedFreeConstraintPreprocessor
502// --------------------------------------------------------
503// This preprocessor computes for each constraint row the bounds that are
504// implied by the variable bounds and applies one of the following reductions:
505//
506// * If the intersection of the implied bounds and the current constraint bounds
507// is empty (modulo some tolerance), the problem is INFEASIBLE.
508//
509// * If the intersection of the implied bounds and the current constraint bounds
510// is a singleton (modulo some tolerance), then the constraint is said to be
511// forcing and all the variables that appear in it can be fixed to one of their
512// bounds. All these columns and the constraint row is removed.
513//
514// * If the implied bounds are included inside the current constraint bounds
515// (modulo some tolerance) then the constraint is said to be redundant or
516// implied free. Its bounds are relaxed and the constraint will be removed
517// later by the FreeConstraintPreprocessor.
518//
519// * Otherwise, wo do nothing.
521 public:
523 const GlopParameters* parameters)
530 bool Run(LinearProgram* lp) final;
531 void RecoverSolution(ProblemSolution* solution) const final;
532
533 private:
534 bool lp_is_maximization_problem_;
535 SparseMatrix deleted_columns_;
536 DenseRow costs_;
537 DenseBooleanColumn is_forcing_up_;
538 ColumnDeletionHelper column_deletion_helper_;
539 RowDeletionHelper row_deletion_helper_;
540};
541
542// --------------------------------------------------------
543// ImpliedFreePreprocessor
544// --------------------------------------------------------
545// It is possible to compute "implied" bounds on a variable from the bounds of
546// all the other variables and the constraints in which this variable take
547// place. If such "implied" bounds are inside the variable bounds, then the
548// variable bounds can be relaxed and the variable is said to be "implied free".
549//
550// This preprocessor detects the implied free variables and make as many as
551// possible free with a priority towards low-degree columns. This transformation
552// will make the simplex algorithm more efficient later, but will also make it
553// possible to reduce the problem by applying subsequent transformations:
554//
555// * The SingletonPreprocessor already deals with implied free singleton
556// variables and removes the columns and the rows in which they appear.
557//
558// * Any multiple of the column of a free variable can be added to any other
559// column without changing the linear program solution. This is the dual
560// counterpart of the fact that any multiple of an equality row can be added to
561// any row.
562//
563// TODO(user): Only process doubleton columns so we have more chance in the
564// later passes to create more doubleton columns? Such columns lead to a smaller
565// problem thanks to the DoubletonFreeColumnPreprocessor.
567 public:
568 explicit ImpliedFreePreprocessor(const GlopParameters* parameters)
573 bool Run(LinearProgram* lp) final;
574 void RecoverSolution(ProblemSolution* solution) const final;
575
576 private:
577 // This preprocessor adds fixed offsets to some variables. We remember those
578 // here to un-offset them in RecoverSolution().
579 DenseRow variable_offsets_;
580
581 // This preprocessor causes some variables who would normally be
582 // AT_{LOWER,UPPER}_BOUND to be VariableStatus::FREE. We store the restore
583 // value of these variables; which will only be used (eg. restored) if the
584 // variable actually turns out to be VariableStatus::FREE.
585 VariableStatusRow postsolve_status_of_free_variables_;
586};
587
588// --------------------------------------------------------
589// DoubletonFreeColumnPreprocessor
590// --------------------------------------------------------
591// This preprocessor removes one of the two rows in which a doubleton column of
592// a free variable appears. Since we can add any multiple of such a column to
593// any other column, the way this works is that we can always remove all the
594// entries on one row.
595//
596// Actually, we can remove all the entries except the one of the free column.
597// But we will be left with a singleton row that we can delete in the same way
598// as what is done in SingletonPreprocessor. That is by reporting the constraint
599// bounds into the one of the originally free variable. After this operation,
600// the doubleton free column will become a singleton and may or may not be
601// removed later by the SingletonPreprocessor.
602//
603// Note that this preprocessor can be seen as the dual of the
604// DoubletonEqualityRowPreprocessor since when taking the dual, an equality row
605// becomes a free variable and vice versa.
606//
607// Note(user): As far as I know, this doubleton free column procedure is more
608// general than what can be found in the research papers or in any of the linear
609// solver open source codes as of July 2013. All of them only process such
610// columns if one of the two rows is also an equality which is not actually
611// required. Most probably, commercial solvers do use it though.
613 public:
614 explicit DoubletonFreeColumnPreprocessor(const GlopParameters* parameters)
617 delete;
619 const DoubletonFreeColumnPreprocessor&) = delete;
621 bool Run(LinearProgram* lp) final;
622 void RecoverSolution(ProblemSolution* solution) const final;
623
624 private:
625 enum RowChoice {
626 DELETED = 0,
627 MODIFIED = 1,
628 // This is just a constant for the number of rows in a doubleton column.
629 // That is 2, one will be DELETED, the other MODIFIED.
630 NUM_ROWS = 2,
631 };
632 struct RestoreInfo {
633 // The index of the original free doubleton column and its objective.
634 ColIndex col;
635 Fractional objective_coefficient;
636
637 // The row indices of the two involved rows and their coefficients on
638 // column col.
639 RowIndex row[NUM_ROWS];
640 Fractional coeff[NUM_ROWS];
641
642 // The deleted row as a column.
643 SparseColumn deleted_row_as_column;
644 };
645
646 std::vector<RestoreInfo> restore_stack_;
647 RowDeletionHelper row_deletion_helper_;
648};
649
650// --------------------------------------------------------
651// UnconstrainedVariablePreprocessor
652// --------------------------------------------------------
653// If for a given variable, none of the constraints block it in one direction
654// and this direction improves the objective, then this variable can be fixed to
655// its bound in this direction. If this bound is infinite and the variable cost
656// is non-zero, then the problem is unbounded.
657//
658// More generally, by using the constraints and the variables that are unbounded
659// on one side, one can derive bounds on the dual values. These can be
660// translated into bounds on the reduced costs or the columns, which may force
661// variables to their bounds. This is called forcing and dominated columns in
662// the Andersen & Andersen paper.
664 public:
665 explicit UnconstrainedVariablePreprocessor(const GlopParameters* parameters)
668 delete;
670 const UnconstrainedVariablePreprocessor&) = delete;
672 bool Run(LinearProgram* lp) final;
673 void RecoverSolution(ProblemSolution* solution) const final;
674
675 // Removes the given variable and all the rows in which it appears: If a
676 // variable is unconstrained with a zero cost, then all the constraints in
677 // which it appears can be made free! More precisely, during postsolve, if
678 // such a variable is unconstrained towards +kInfinity, for any activity value
679 // of the involved constraints, an M exists such that for each value of the
680 // variable >= M the problem will be feasible.
681 //
682 // The algorithm during postsolve is to find a feasible value for all such
683 // variables while trying to keep their magnitudes small (for better numerical
684 // behavior). target_bound should take only two possible values: +/-kInfinity.
687 LinearProgram* lp);
688
689 private:
690 // Lower/upper bounds on the feasible dual value. We use constraints and
691 // variables unbounded in one direction to derive these bounds. We use these
692 // bounds to compute bounds on the reduced costs of the problem variables.
693 // Note that any finite bounds on a reduced cost means that the variable
694 // (ignoring its domain) can move freely in one direction.
695 DenseColumn dual_lb_;
696 DenseColumn dual_ub_;
697
698 // Indicates if a given column may have participated in the current lb/ub
699 // on the reduced cost of the same column.
700 DenseBooleanRow may_have_participated_ub_;
701 DenseBooleanRow may_have_participated_lb_;
702
703 ColumnDeletionHelper column_deletion_helper_;
704 RowDeletionHelper row_deletion_helper_;
705 DenseColumn rhs_;
706 DenseColumn activity_sign_correction_;
707 DenseBooleanRow is_unbounded_;
708
709 SparseMatrix deleted_columns_;
710 SparseMatrix deleted_rows_as_column_;
711};
712
713// --------------------------------------------------------
714// FreeConstraintPreprocessor
715// --------------------------------------------------------
716// Removes the constraints with no bounds from the problem.
718 public:
719 explicit FreeConstraintPreprocessor(const GlopParameters* parameters)
723 delete;
725 bool Run(LinearProgram* lp) final;
726 void RecoverSolution(ProblemSolution* solution) const final;
727
728 private:
729 RowDeletionHelper row_deletion_helper_;
730};
731
732// --------------------------------------------------------
733// EmptyConstraintPreprocessor
734// --------------------------------------------------------
735// Removes the constraints with no coefficients from the problem.
737 public:
738 explicit EmptyConstraintPreprocessor(const GlopParameters* parameters)
742 delete;
744 bool Run(LinearProgram* lp) final;
745 void RecoverSolution(ProblemSolution* solution) const final;
746
747 private:
748 RowDeletionHelper row_deletion_helper_;
749};
750
751// --------------------------------------------------------
752// RemoveNearZeroEntriesPreprocessor
753// --------------------------------------------------------
754// Removes matrix entries that have only a negligible impact on the solution.
755// Using the variable bounds, we derive a maximum possible impact, and remove
756// the entries whose impact is under a given tolerance.
757//
758// TODO(user): This preprocessor doesn't work well on badly scaled problems. In
759// particular, it will set the objective to zero if all the objective
760// coefficients are small! Run it after ScalingPreprocessor or fix the code.
762 public:
763 explicit RemoveNearZeroEntriesPreprocessor(const GlopParameters* parameters)
766 delete;
768 const RemoveNearZeroEntriesPreprocessor&) = delete;
770 bool Run(LinearProgram* lp) final;
771 void RecoverSolution(ProblemSolution* solution) const final;
772
773 private:
774};
775
776// --------------------------------------------------------
777// SingletonColumnSignPreprocessor
778// --------------------------------------------------------
779// Make sure that the only coefficient of all singleton columns (i.e. column
780// with only one entry) is positive. This is because this way the column will
781// be transformed in an identity column by the scaling. This will lead to more
782// efficient solve when this column is involved.
784 public:
785 explicit SingletonColumnSignPreprocessor(const GlopParameters* parameters)
788 delete;
790 const SingletonColumnSignPreprocessor&) = delete;
792 bool Run(LinearProgram* lp) final;
793 void RecoverSolution(ProblemSolution* solution) const final;
794
795 private:
796 std::vector<ColIndex> changed_columns_;
797};
798
799// --------------------------------------------------------
800// DoubletonEqualityRowPreprocessor
801// --------------------------------------------------------
802// Reduce equality constraints involving two variables (i.e. aX + bY = c),
803// by substitution (and thus removal) of one of the variables by the other
804// in all the constraints that it is involved in.
806 public:
807 explicit DoubletonEqualityRowPreprocessor(const GlopParameters* parameters)
810 delete;
812 const DoubletonEqualityRowPreprocessor&) = delete;
814 bool Run(LinearProgram* lp) final;
815 void RecoverSolution(ProblemSolution* solution) const final;
816
817 private:
818 enum ColChoice {
819 DELETED = 0,
820 MODIFIED = 1,
821 // For for() loops iterating over the ColChoice values, and/or arrays.
822 NUM_DOUBLETON_COLS = 2,
823 };
824 static ColChoice OtherColChoice(ColChoice x) {
825 return x == DELETED ? MODIFIED : DELETED;
826 }
827
828 ColumnDeletionHelper column_deletion_helper_;
829 RowDeletionHelper row_deletion_helper_;
830
831 struct RestoreInfo {
832 // The row index of the doubleton equality constraint, and its constant.
833 RowIndex row;
834 Fractional rhs; // The constant c in the equality aX + bY = c.
835
836 // The indices and the data of the two columns that we touched, exactly
837 // as they were beforehand.
838 ColIndex col[NUM_DOUBLETON_COLS];
839 Fractional coeff[NUM_DOUBLETON_COLS];
840 Fractional lb[NUM_DOUBLETON_COLS];
841 Fractional ub[NUM_DOUBLETON_COLS];
842 SparseColumn column[NUM_DOUBLETON_COLS];
843 Fractional objective_coefficient[NUM_DOUBLETON_COLS];
844
845 // If the modified variable has status AT_[LOWER,UPPER]_BOUND, then we'll
846 // set one of the two original variables to one of its bounds, and set the
847 // other to VariableStatus::BASIC. We store this information (which variable
848 // will be set to one of its bounds, and which bound) for each possible
849 // outcome.
851 ColChoice col_choice;
856 : col_choice(c), status(s), value(v) {}
857 };
858 ColChoiceAndStatus bound_backtracking_at_lower_bound;
859 ColChoiceAndStatus bound_backtracking_at_upper_bound;
860 };
861 void SwapDeletedAndModifiedVariableRestoreInfo(RestoreInfo* r);
862
863 std::vector<RestoreInfo> restore_stack_;
864 DenseColumn saved_row_lower_bounds_;
865 DenseColumn saved_row_upper_bounds_;
866};
867
868// Because of numerical imprecision, a preprocessor like
869// DoubletonEqualityRowPreprocessor can transform a constraint/variable domain
870// like [1, 1+1e-7] to a fixed domain (for ex by multiplying the above domain by
871// 1e9). This causes an issue because at postsolve, a FIXED_VALUE status now
872// needs to be transformed to a AT_LOWER_BOUND/AT_UPPER_BOUND status. This is
873// what this function is doing for the constraint statuses only.
874//
875// TODO(user): A better solution would simply be to get rid of the FIXED status
876// altogether, it is better to simply use AT_LOWER_BOUND/AT_UPPER_BOUND
877// depending on the constraining bound in the optimal solution. Note that we can
878// always at the end transform any variable/constraint with a fixed domain to
879// FIXED_VALUE if needed to keep the same external API.
880void FixConstraintWithFixedStatuses(const DenseColumn& row_lower_bounds,
881 const DenseColumn& row_upper_bounds,
882 ProblemSolution* solution);
883
884// --------------------------------------------------------
885// DualizerPreprocessor
886// --------------------------------------------------------
887// DualizerPreprocessor may change the given program to its dual depending
888// on the value of the parameter solve_dual_problem.
889//
890// IMPORTANT: FreeConstraintPreprocessor() must be called first since this
891// preprocessor does not deal correctly with free constraints.
893 public:
894 explicit DualizerPreprocessor(const GlopParameters* parameters)
899 bool Run(LinearProgram* lp) final;
900 void RecoverSolution(ProblemSolution* solution) const final;
901 void UseInMipContext() final {
902 LOG(FATAL) << "In the presence of integer variables, "
903 << "there is no notion of a dual problem.";
904 }
905
906 // Convert the given problem status to the one of its dual.
908
909 private:
910 DenseRow variable_lower_bounds_;
911 DenseRow variable_upper_bounds_;
912
913 RowIndex primal_num_rows_;
914 ColIndex primal_num_cols_;
915 bool primal_is_maximization_problem_;
916 RowToColMapping duplicated_rows_;
917
918 // For postsolving the variable/constraint statuses.
919 VariableStatusRow dual_status_correspondence_;
920 ColMapping slack_or_surplus_mapping_;
921};
922
923// --------------------------------------------------------
924// ShiftVariableBoundsPreprocessor
925// --------------------------------------------------------
926// For each variable, inspects its bounds and "shift" them if necessary, so that
927// its domain contains zero. A variable that was shifted will always have at
928// least one of its bounds to zero. Doing it all at once allows to have a better
929// precision when modifying the constraint bounds by using an accurate summation
930// algorithm.
931//
932// Example:
933// - A variable with bound [1e10, infinity] will be shifted to [0, infinity].
934// - A variable with domain [-1e10, 1e10] will not be shifted. Note that
935// compared to the first case, doing so here may introduce unecessary
936// numerical errors if the variable value in the final solution is close to
937// zero.
938//
939// The expected impact of this is:
940// - Better behavior of the scaling.
941// - Better precision and numerical accuracy of the simplex method.
942// - Slightly improved speed (because adding a column with a variable value of
943// zero takes no work later).
944//
945// TODO(user): Having for each variable one of their bounds at zero is a
946// requirement for the DualizerPreprocessor and for the implied free column in
947// the ImpliedFreePreprocessor. However, shifting a variable with a domain like
948// [-1e10, 1e10] may introduce numerical issues. Relax the definition of
949// a free variable so that only having a domain containing 0.0 is enough?
951 public:
952 explicit ShiftVariableBoundsPreprocessor(const GlopParameters* parameters)
955 delete;
957 const ShiftVariableBoundsPreprocessor&) = delete;
959 bool Run(LinearProgram* lp) final;
960 void RecoverSolution(ProblemSolution* solution) const final;
961
962 const DenseRow& offsets() const { return offsets_; }
963
964 private:
965 // Contains for each variable by how much its bounds where shifted during
966 // presolve. Note that the shift was negative (new bound = initial bound -
967 // offset).
968 DenseRow offsets_;
969 // Contains the initial problem bounds. They are needed to get the perfect
970 // numerical accuracy for variables at their bound after postsolve.
971 DenseRow variable_initial_lbs_;
972 DenseRow variable_initial_ubs_;
973};
974
975// --------------------------------------------------------
976// ScalingPreprocessor
977// --------------------------------------------------------
978// Scales the SparseMatrix of the linear program using a SparseMatrixScaler.
979// This is only applied if the parameter use_scaling is true.
981 public:
982 explicit ScalingPreprocessor(const GlopParameters* parameters)
987 bool Run(LinearProgram* lp) final;
988 void RecoverSolution(ProblemSolution* solution) const final;
989 void UseInMipContext() final { LOG(FATAL) << "Not implemented."; }
990
991 private:
992 DenseRow variable_lower_bounds_;
993 DenseRow variable_upper_bounds_;
994 Fractional cost_scaling_factor_;
995 Fractional bound_scaling_factor_;
996 SparseMatrixScaler scaler_;
997};
998
999// --------------------------------------------------------
1000// ToMinimizationPreprocessor
1001// --------------------------------------------------------
1002// Changes the problem from maximization to minimization (if applicable).
1004 public:
1005 explicit ToMinimizationPreprocessor(const GlopParameters* parameters)
1009 delete;
1011 bool Run(LinearProgram* lp) final;
1012 void RecoverSolution(ProblemSolution* solution) const final;
1013};
1014
1015// --------------------------------------------------------
1016// AddSlackVariablesPreprocessor
1017// --------------------------------------------------------
1018// Transforms the linear program to the equation form
1019// min c.x, s.t. A.x = 0. This is done by:
1020// 1. Introducing slack variables for all constraints; all these variables are
1021// introduced with coefficient 1.0, and their bounds are set to be negative
1022// bounds of the corresponding constraint.
1023// 2. Changing the bounds of all constraints to (0, 0) to make them an equality.
1024//
1025// As a consequence, the matrix of the linear program always has full row rank
1026// after this preprocessor. Note that the slack variables are always added last,
1027// so that the rightmost square sub-matrix is always the identity matrix.
1029 public:
1030 explicit AddSlackVariablesPreprocessor(const GlopParameters* parameters)
1034 const AddSlackVariablesPreprocessor&) = delete;
1036 bool Run(LinearProgram* lp) final;
1037 void RecoverSolution(ProblemSolution* solution) const final;
1038
1039 private:
1040 ColIndex first_slack_col_;
1041};
1042
1043} // namespace glop
1044} // namespace operations_research
1045
1046#endif // OR_TOOLS_GLOP_PREPROCESSOR_H_
#define LOG(severity)
Definition: base/logging.h:420
bool empty() const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
AddSlackVariablesPreprocessor(const AddSlackVariablesPreprocessor &)=delete
AddSlackVariablesPreprocessor(const GlopParameters *parameters)
void RecoverSolution(ProblemSolution *solution) const final
AddSlackVariablesPreprocessor & operator=(const AddSlackVariablesPreprocessor &)=delete
ColumnDeletionHelper(const ColumnDeletionHelper &)=delete
void MarkColumnForDeletionWithState(ColIndex col, Fractional value, VariableStatus status)
const DenseBooleanRow & GetMarkedColumns() const
Definition: preprocessor.h:166
ColumnDeletionHelper & operator=(const ColumnDeletionHelper &)=delete
void RestoreDeletedColumns(ProblemSolution *solution) const
DoubletonEqualityRowPreprocessor(const DoubletonEqualityRowPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
DoubletonEqualityRowPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:807
DoubletonEqualityRowPreprocessor & operator=(const DoubletonEqualityRowPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
DoubletonFreeColumnPreprocessor & operator=(const DoubletonFreeColumnPreprocessor &)=delete
DoubletonFreeColumnPreprocessor(const DoubletonFreeColumnPreprocessor &)=delete
DoubletonFreeColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:614
DualizerPreprocessor(const DualizerPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ProblemStatus ChangeStatusToDualStatus(ProblemStatus status) const
DualizerPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:894
DualizerPreprocessor & operator=(const DualizerPreprocessor &)=delete
EmptyColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:235
void RecoverSolution(ProblemSolution *solution) const final
EmptyColumnPreprocessor(const EmptyColumnPreprocessor &)=delete
EmptyColumnPreprocessor & operator=(const EmptyColumnPreprocessor &)=delete
EmptyConstraintPreprocessor & operator=(const EmptyConstraintPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
EmptyConstraintPreprocessor(const EmptyConstraintPreprocessor &)=delete
EmptyConstraintPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:738
FixedVariablePreprocessor(const FixedVariablePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
FixedVariablePreprocessor & operator=(const FixedVariablePreprocessor &)=delete
FixedVariablePreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:487
ForcingAndImpliedFreeConstraintPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:522
ForcingAndImpliedFreeConstraintPreprocessor(const ForcingAndImpliedFreeConstraintPreprocessor &)=delete
ForcingAndImpliedFreeConstraintPreprocessor & operator=(const ForcingAndImpliedFreeConstraintPreprocessor &)=delete
FreeConstraintPreprocessor(const FreeConstraintPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
FreeConstraintPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:719
FreeConstraintPreprocessor & operator=(const FreeConstraintPreprocessor &)=delete
ImpliedFreePreprocessor(const ImpliedFreePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ImpliedFreePreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:568
ImpliedFreePreprocessor & operator=(const ImpliedFreePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const override
MainLpPreprocessor(const MainLpPreprocessor &)=delete
MainLpPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:105
MainLpPreprocessor & operator=(const MainLpPreprocessor &)=delete
virtual void RecoverSolution(ProblemSolution *solution) const =0
bool IsSmallerWithinPreprocessorZeroTolerance(Fractional a, Fractional b) const
Definition: preprocessor.h:84
Preprocessor(const GlopParameters *parameters)
Definition: preprocessor.cc:46
const GlopParameters & parameters_
Definition: preprocessor.h:92
Preprocessor & operator=(const Preprocessor &)=delete
Preprocessor(const Preprocessor &)=delete
std::unique_ptr< TimeLimit > infinite_time_limit_
Definition: preprocessor.h:94
virtual bool Run(LinearProgram *lp)=0
void SetTimeLimit(TimeLimit *time_limit)
Definition: preprocessor.h:75
bool IsSmallerWithinFeasibilityTolerance(Fractional a, Fractional b) const
Definition: preprocessor.h:80
ProportionalColumnPreprocessor & operator=(const ProportionalColumnPreprocessor &)=delete
ProportionalColumnPreprocessor(const ProportionalColumnPreprocessor &)=delete
ProportionalColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:259
void RecoverSolution(ProblemSolution *solution) const final
ProportionalRowPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:300
void RecoverSolution(ProblemSolution *solution) const final
ProportionalRowPreprocessor & operator=(const ProportionalRowPreprocessor &)=delete
ProportionalRowPreprocessor(const ProportionalRowPreprocessor &)=delete
RemoveNearZeroEntriesPreprocessor & operator=(const RemoveNearZeroEntriesPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
RemoveNearZeroEntriesPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:763
RemoveNearZeroEntriesPreprocessor(const RemoveNearZeroEntriesPreprocessor &)=delete
void RestoreDeletedRows(ProblemSolution *solution) const
const DenseBooleanColumn & GetMarkedRows() const
RowDeletionHelper & operator=(const RowDeletionHelper &)=delete
RowDeletionHelper(const RowDeletionHelper &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ScalingPreprocessor & operator=(const ScalingPreprocessor &)=delete
ScalingPreprocessor(const ScalingPreprocessor &)=delete
ScalingPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:982
ShiftVariableBoundsPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:952
void RecoverSolution(ProblemSolution *solution) const final
ShiftVariableBoundsPreprocessor(const ShiftVariableBoundsPreprocessor &)=delete
ShiftVariableBoundsPreprocessor & operator=(const ShiftVariableBoundsPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
SingletonColumnSignPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:785
SingletonColumnSignPreprocessor & operator=(const SingletonColumnSignPreprocessor &)=delete
SingletonColumnSignPreprocessor(const SingletonColumnSignPreprocessor &)=delete
SingletonPreprocessor(const SingletonPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
SingletonPreprocessor & operator=(const SingletonPreprocessor &)=delete
SingletonPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:399
SingletonUndo(OperationType type, const LinearProgram &lp, MatrixEntry e, ConstraintStatus status)
void Undo(const GlopParameters &parameters, const SparseMatrix &deleted_columns, const SparseMatrix &deleted_rows, ProblemSolution *solution) const
ToMinimizationPreprocessor & operator=(const ToMinimizationPreprocessor &)=delete
ToMinimizationPreprocessor(const ToMinimizationPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ToMinimizationPreprocessor(const GlopParameters *parameters)
void RemoveZeroCostUnconstrainedVariable(ColIndex col, Fractional target_bound, LinearProgram *lp)
UnconstrainedVariablePreprocessor & operator=(const UnconstrainedVariablePreprocessor &)=delete
UnconstrainedVariablePreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:665
void RecoverSolution(ProblemSolution *solution) const final
UnconstrainedVariablePreprocessor(const UnconstrainedVariablePreprocessor &)=delete
SatParameters parameters
SharedTimeLimit * time_limit
const std::string name
int64 value
const int FATAL
Definition: log_severity.h:32
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
void FixConstraintWithFixedStatuses(const DenseColumn &row_lower_bounds, const DenseColumn &row_upper_bounds, ProblemSolution *solution)
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
Definition: fp_utils.h:153
Fractional target_bound
Fractional coeff
Definition: preprocessor.h:336
MatrixEntry(RowIndex _row, ColIndex _col, Fractional _coeff)
Definition: preprocessor.h:332
ColIndex col
Definition: preprocessor.h:335
RowIndex row
Definition: preprocessor.h:334