21 shifted_lp_values_.clear();
22 bound_parity_.clear();
24 col_to_rows_.resize(size);
25 tmp_marked_.resize(size);
29 const std::vector<double>& lp_values,
32 Reset(lp_values.size());
35 lp_values_ = lp_values;
36 for (
int i = 0; i < lp_values.size(); ++i) {
39 if (lb_dist < ub_dist) {
40 shifted_lp_values_.push_back(lb_dist);
43 shifted_lp_values_.push_back(ub_dist);
52 for (
const int col : binary_row.
cols) {
53 col_to_rows_[
col].push_back(rows_.size());
55 rows_.push_back(binary_row);
59 const glop::RowIndex
row,
60 const std::vector<std::pair<glop::ColIndex, IntegerValue>>& terms,
61 IntegerValue lb, IntegerValue ub) {
62 if (terms.size() > kMaxInputConstraintSize)
return;
64 double activity = 0.0;
65 IntegerValue magnitude(0);
68 for (
const auto& term : terms) {
69 const int col = term.first.value();
70 activity +=
ToDouble(term.second) * lp_values_[
col];
74 if ((term.second.value() & 1) == 0)
continue;
77 if (shifted_lp_values_[
col] > 1e-2) {
82 rhs_adjust ^= bound_parity_[
col];
88 if (magnitude > kMaxInputConstraintMagnitude)
return;
96 const double tighteness_threshold = 1e-2;
97 if (
ToDouble(ub) - activity < tighteness_threshold) {
100 binary_row.
rhs_parity = (ub.value() & 1) ^ rhs_adjust;
103 if (activity -
ToDouble(lb) < tighteness_threshold) {
106 binary_row.
rhs_parity = (lb.value() & 1) ^ rhs_adjust;
112 std::function<
bool(
int)> extra_condition,
const std::vector<int>&
a,
113 std::vector<int>*
b) {
114 for (
const int v : *
b) tmp_marked_[v] =
true;
115 for (
const int v :
a) {
116 if (tmp_marked_[v]) {
117 tmp_marked_[v] =
false;
119 tmp_marked_[v] =
true;
128 for (
const int v : *
b) {
129 if (tmp_marked_[v]) {
130 if (extra_condition(v)) {
131 (*b)[new_size++] = v;
133 tmp_marked_[v] =
false;
139void ZeroHalfCutHelper::ProcessSingletonColumns() {
140 for (
const int singleton_col : singleton_cols_) {
141 if (col_to_rows_[singleton_col].empty())
continue;
142 CHECK_EQ(col_to_rows_[singleton_col].size(), 1);
143 const int row = col_to_rows_[singleton_col][0];
145 auto& mutable_cols = rows_[
row].cols;
146 for (
const int col : mutable_cols) {
147 if (
col == singleton_col)
continue;
148 mutable_cols[new_size++] =
col;
150 CHECK_LT(new_size, mutable_cols.size());
151 mutable_cols.resize(new_size);
152 col_to_rows_[singleton_col].clear();
153 rows_[
row].slack += shifted_lp_values_[singleton_col];
155 singleton_cols_.clear();
160 int eliminated_row) {
161 CHECK_LE(rows_[eliminated_row].slack, 1e-6);
162 CHECK(!rows_[eliminated_row].cols.empty());
165 tmp_marked_.resize(
std::max(col_to_rows_.size(), rows_.size()));
166 DCHECK(std::all_of(tmp_marked_.begin(), tmp_marked_.end(),
167 [](
bool b) { return !b; }));
169 for (
const int other_row : col_to_rows_[eliminated_col]) {
170 if (other_row == eliminated_row)
continue;
171 col_to_rows_[eliminated_col][new_size++] = other_row;
174 &rows_[other_row].cols);
177 rows_[other_row].rhs_parity ^= rows_[eliminated_row].rhs_parity;
178 rows_[other_row].slack += rows_[eliminated_row].slack;
182 auto& mutable_multipliers = rows_[other_row].multipliers;
183 mutable_multipliers.insert(mutable_multipliers.end(),
184 rows_[eliminated_row].multipliers.begin(),
185 rows_[eliminated_row].multipliers.end());
186 std::sort(mutable_multipliers.begin(), mutable_multipliers.end());
188 for (
const auto& entry : mutable_multipliers) {
189 if (new_size > 0 && entry == mutable_multipliers[new_size - 1]) {
193 mutable_multipliers[new_size++] = entry;
196 mutable_multipliers.resize(new_size);
199 col_to_rows_[eliminated_col].resize(new_size);
207 for (
const int other_col : rows_[eliminated_row].cols) {
208 if (other_col == eliminated_col)
continue;
209 const int old_size = col_to_rows_[other_col].size();
210 rows_[eliminated_row].cols[new_size++] = other_col;
212 [
this](
int i) {
return rows_[i].slack < kSlackThreshold; },
213 col_to_rows_[eliminated_col], &col_to_rows_[other_col]);
214 if (old_size != 1 && col_to_rows_[other_col].size() == 1) {
215 singleton_cols_.push_back(other_col);
218 rows_[eliminated_row].cols.resize(new_size);
222 col_to_rows_[eliminated_col].clear();
223 rows_[eliminated_row].slack += shifted_lp_values_[eliminated_col];
226std::vector<std::vector<std::pair<glop::RowIndex, IntegerValue>>>
228 std::vector<std::vector<std::pair<glop::RowIndex, IntegerValue>>> result;
231 singleton_cols_.clear();
232 for (
int col = 0;
col < col_to_rows_.size(); ++
col) {
233 if (col_to_rows_[
col].size() == 1) singleton_cols_.push_back(
col);
237 std::vector<int> to_process;
238 for (
int row = 0;
row < rows_.size(); ++
row) to_process.push_back(
row);
239 std::shuffle(to_process.begin(), to_process.end(), *random);
240 std::stable_sort(to_process.begin(), to_process.end(), [
this](
int a,
int b) {
241 return rows_[a].cols.size() < rows_[b].cols.size();
244 for (
const int row : to_process) {
245 ProcessSingletonColumns();
247 if (rows_[
row].cols.empty())
continue;
248 if (rows_[
row].slack > 1e-6)
continue;
249 if (rows_[
row].multipliers.size() > kMaxAggregationSize)
continue;
252 int eliminated_col = -1;
253 double max_lp_value = 0.0;
254 for (
const int col : rows_[
row].cols) {
255 if (shifted_lp_values_[
col] > max_lp_value) {
256 max_lp_value = shifted_lp_values_[
col];
257 eliminated_col =
col;
260 if (eliminated_col == -1)
continue;
267 for (
const auto&
row : rows_) {
268 if (
row.cols.empty() &&
row.rhs_parity &&
row.slack < kSlackThreshold) {
269 result.push_back(
row.multipliers);
272 VLOG(1) <<
"#candidates: " << result.size() <<
" / " << rows_.size();
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define VLOG(verboselevel)
void EliminateVarUsingRow(int col, int row)
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)
void AddOneConstraint(glop::RowIndex, const std::vector< std::pair< glop::ColIndex, IntegerValue > > &terms, IntegerValue lb, IntegerValue ub)
std::vector< std::vector< std::pair< glop::RowIndex, IntegerValue > > > InterestingCandidates(ModelRandomGenerator *random)
IntType IntTypeAbs(IntType t)
double ToDouble(IntegerValue value)
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