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 
33 namespace operations_research {
34 namespace 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.
43 class Preprocessor {
44  public:
45  explicit Preprocessor(const GlopParameters* parameters);
46  Preprocessor(const Preprocessor&) = delete;
47  Preprocessor& operator=(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)
109  ~MainLpPreprocessor() override {}
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).
331 struct 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 {
348  } OperationType;
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.
880 void 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)
1006  : Preprocessor(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)
1031  : Preprocessor(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
void RestoreDeletedColumns(ProblemSolution *solution) const
ColumnDeletionHelper & operator=(const ColumnDeletionHelper &)=delete
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(const DoubletonFreeColumnPreprocessor &)=delete
DoubletonFreeColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:614
DoubletonFreeColumnPreprocessor & operator=(const DoubletonFreeColumnPreprocessor &)=delete
DualizerPreprocessor(const DualizerPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
DualizerPreprocessor & operator=(const DualizerPreprocessor &)=delete
ProblemStatus ChangeStatusToDualStatus(ProblemStatus status) const
DualizerPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:894
EmptyColumnPreprocessor & operator=(const EmptyColumnPreprocessor &)=delete
EmptyColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:235
void RecoverSolution(ProblemSolution *solution) const final
EmptyColumnPreprocessor(const EmptyColumnPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
EmptyConstraintPreprocessor(const EmptyConstraintPreprocessor &)=delete
EmptyConstraintPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:738
EmptyConstraintPreprocessor & operator=(const EmptyConstraintPreprocessor &)=delete
FixedVariablePreprocessor(const FixedVariablePreprocessor &)=delete
FixedVariablePreprocessor & operator=(const FixedVariablePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
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 & operator=(const FreeConstraintPreprocessor &)=delete
FreeConstraintPreprocessor(const FreeConstraintPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
FreeConstraintPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:719
ImpliedFreePreprocessor & operator=(const ImpliedFreePreprocessor &)=delete
ImpliedFreePreprocessor(const ImpliedFreePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ImpliedFreePreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:568
void RecoverSolution(ProblemSolution *solution) const override
MainLpPreprocessor(const MainLpPreprocessor &)=delete
MainLpPreprocessor & operator=(const MainLpPreprocessor &)=delete
MainLpPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:105
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(const Preprocessor &)=delete
std::unique_ptr< TimeLimit > infinite_time_limit_
Definition: preprocessor.h:94
Preprocessor & operator=(const Preprocessor &)=delete
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(const ProportionalColumnPreprocessor &)=delete
ProportionalColumnPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:259
void RecoverSolution(ProblemSolution *solution) const final
ProportionalColumnPreprocessor & operator=(const ProportionalColumnPreprocessor &)=delete
ProportionalRowPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:300
void RecoverSolution(ProblemSolution *solution) const final
ProportionalRowPreprocessor(const ProportionalRowPreprocessor &)=delete
ProportionalRowPreprocessor & operator=(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
ScalingPreprocessor & operator=(const ScalingPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ScalingPreprocessor(const ScalingPreprocessor &)=delete
ScalingPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:982
ShiftVariableBoundsPreprocessor & operator=(const ShiftVariableBoundsPreprocessor &)=delete
ShiftVariableBoundsPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:952
void RecoverSolution(ProblemSolution *solution) const final
ShiftVariableBoundsPreprocessor(const ShiftVariableBoundsPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
SingletonColumnSignPreprocessor & operator=(const SingletonColumnSignPreprocessor &)=delete
SingletonColumnSignPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:785
SingletonColumnSignPreprocessor(const SingletonColumnSignPreprocessor &)=delete
SingletonPreprocessor(const SingletonPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
SingletonPreprocessor(const GlopParameters *parameters)
Definition: preprocessor.h:399
SingletonPreprocessor & operator=(const SingletonPreprocessor &)=delete
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