OR-Tools  8.2
zero_half_cuts.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 #ifndef OR_TOOLS_SAT_ZERO_HALF_CUTS_H_
15 #define OR_TOOLS_SAT_ZERO_HALF_CUTS_H_
16 
17 #include <vector>
18 
20 #include "ortools/sat/integer.h"
21 #include "ortools/sat/util.h"
22 
23 namespace operations_research {
24 namespace sat {
25 
26 // Heuristic to find a good sums of rows from the LP (with coeff -1, +1) that
27 // can lead to a violated zero-half cut (i.e. after integer rounding with a
28 // divisor 2).
29 //
30 // For this, all that matter is the parity of the coefficients and the rhs in
31 // the linear combination of the original problem constraint. So this class
32 // maintain a copy of the LP matrix modulo 2 on which simplification and
33 // heuristic are performed to find good cut candidates(s).
34 //
35 // Most of what is done here is described in the paper "Algorithms to Separate
36 // {0, 1/2}-Chvátal-Gomory Cuts", Arie M. C. A. Koster, Adrian Zymolka, Manuel
37 // Kutschka.
39  public:
40  // Public API: ProcessVariables() must be called first and then constraints
41  // can be added one by one. Finally GetZeroHalfInterestingCuts() will return a
42  // set of good candidates.
43  //
44  // TODO(user): This is a first implementation, both the heuristic and the
45  // code performance can probably be improved uppon.
46  void ProcessVariables(const std::vector<double>& lp_values,
47  const std::vector<IntegerValue>& lower_bounds,
48  const std::vector<IntegerValue>& upper_bounds);
49  void AddOneConstraint(
50  glop::RowIndex,
51  const std::vector<std::pair<glop::ColIndex, IntegerValue>>& terms,
52  IntegerValue lb, IntegerValue ub);
53  std::vector<std::vector<std::pair<glop::RowIndex, IntegerValue>>>
55 
56  // Visible for testing.
57  void Reset(int size);
58 
59  // Visible for testing.
60  //
61  // Boolean matrix. Each column correspond to one variable (col indices).
62  // Each row to a sum of the initial problem constraints. We store the
63  // coefficient modulo 2, so only the positions of the ones.
65  // How this row was formed from the initial problem constraints.
66  std::vector<std::pair<glop::RowIndex, IntegerValue>> multipliers;
67 
68  // The index of the odd coefficient of this combination.
69  std::vector<int> cols;
70 
71  // The parity of the rhs (1 for odd).
73 
74  // How tight this constraints is under the current LP solution.
75  double slack;
76  };
77  void AddBinaryRow(const CombinationOfRows& binary_row);
78  const CombinationOfRows& MatrixRow(int row) const { return rows_[row]; }
79  const std::vector<int>& MatrixCol(int col) const { return col_to_rows_[col]; }
80 
81  // Visible for testing.
82  //
83  // Adds the given row to all other rows having an odd cofficient on the given
84  // column. This then eliminate the entry (col, row) that is now a singleton by
85  // incresing the slack of the given row.
86  void EliminateVarUsingRow(int col, int row);
87 
88  // Visible for testing.
89  //
90  // Like std::set_symmetric_difference, but use a vector<bool> instead of sort.
91  // This assumes tmp_marked_ to be all false. We don't DCHECK it here for
92  // speed, but it DCHECKed on each EliminateVarUsingRow() call. In addition,
93  // the result is filtered using the extra_condition function.
94  void SymmetricDifference(std::function<bool(int)> extra_condition,
95  const std::vector<int>& a, std::vector<int>* b);
96 
97  private:
98  void ProcessSingletonColumns();
99 
100  // As we combine rows, when the activity of a combination get too far away
101  // from its bound, we just discard it. Note that the row will still be there
102  // but its index will not appear in the col-wise representation of the matrix.
103  const double kSlackThreshold = 0.5;
104  const int kMaxAggregationSize = 100;
105 
106  // We don't consider long constraint or constraint with high magnitude, since
107  // the highest violation we can hope for is 1, and if the magnitude is large
108  // then the cut efficacity will not be great.
109  const int kMaxInputConstraintSize = 100;
110  const double kMaxInputConstraintMagnitude = 1e6;
111 
112  // Variable information.
113  std::vector<double> lp_values_;
114  std::vector<double> shifted_lp_values_;
115  std::vector<int> bound_parity_;
116 
117  // Binary matrix.
118  //
119  // Note that as we combine rows, we never move their indices. So after initial
120  // creation rows_ will always have the same size.
121  std::vector<CombinationOfRows> rows_;
122  std::vector<std::vector<int>> col_to_rows_;
123  std::vector<int> singleton_cols_;
124 
125  // Temporary vector used by SymmetricDifference().
126  std::vector<bool> tmp_marked_;
127 };
128 
129 } // namespace sat
130 } // namespace operations_research
131 
132 #endif // OR_TOOLS_SAT_ZERO_HALF_CUTS_H_
void AddBinaryRow(const CombinationOfRows &binary_row)
void SymmetricDifference(std::function< bool(int)> extra_condition, const std::vector< int > &a, std::vector< int > *b)
void ProcessVariables(const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds)
const CombinationOfRows & MatrixRow(int row) const
const std::vector< int > & MatrixCol(int col) const
std::vector< std::vector< std::pair< glop::RowIndex, IntegerValue > > > InterestingCandidates(ModelRandomGenerator *random)
void AddOneConstraint(glop::RowIndex, const std::vector< std::pair< glop::ColIndex, IntegerValue >> &terms, IntegerValue lb, IntegerValue ub)
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > lower_bounds
std::vector< double > upper_bounds
std::vector< std::pair< glop::RowIndex, IntegerValue > > multipliers