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
23namespace operations_research {
24namespace 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);
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)
const CombinationOfRows & MatrixRow(int row) const
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)
void AddOneConstraint(glop::RowIndex, const std::vector< std::pair< glop::ColIndex, IntegerValue > > &terms, IntegerValue lb, IntegerValue ub)
const std::vector< int > & MatrixCol(int col) const
std::vector< std::vector< std::pair< glop::RowIndex, IntegerValue > > > InterestingCandidates(ModelRandomGenerator *random)
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