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