C++ Reference: class ZeroHalfCutHelper

This documentation is automatically generated.

Heuristic to find a good sums of rows from the LP (with coeff -1, +1) that can lead to a violated zero-half cut (i.e. after integer rounding with a divisor 2).

For this, all that matter is the parity of the coefficients and the rhs in the linear combination of the original problem constraint. So this class maintain a copy of the LP matrix modulo 2 on which simplification and heuristic are performed to find good cut candidates(s).

Most of what is done here is described in the paper "Algorithms to Separate {0, 1/2}-Chvátal-Gomory Cuts", Arie M. C. A. Koster, Adrian Zymolka, Manuel Kutschka.
Method
AddBinaryRow

Return type: void

Arguments: const CombinationOfRows& binary_row

AddOneConstraint

Return type: void

Arguments: glop::RowIndex, const std::vector<std::pair<glop::ColIndex, IntegerValue>>& terms, IntegerValue lb, IntegerValue ub

EliminateVarUsingRow

Return type: void

Arguments: int col, int row

Visible for testing. Adds the given row to all other rows having an odd cofficient on the given column. This then eliminate the entry (col, row) that is now a singleton by incresing the slack of the given row.

InterestingCandidates

Arguments: ModelRandomGenerator* random

MatrixCol

Return type: const std::vector<int>&

Arguments: int col

MatrixRow

Return type: const CombinationOfRows&

Arguments: int row

ProcessVariables

Return type: void

Arguments: const std::vector<double>& lp_values, const std::vector<IntegerValue>& lower_bounds, const std::vector<IntegerValue>& upper_bounds

Public API: ProcessVariables() must be called first and then constraints can be added one by one. Finally GetZeroHalfInterestingCuts() will return a set of good candidates. TODO(user): This is a first implementation, both the heuristic and the code performance can probably be improved uppon.

Reset

Return type: void

Arguments: int size

Visible for testing.

SymmetricDifference

Return type: void

Arguments: std::function<bool(int)> extra_condition, const std::vector<int>& a, std::vector<int>* b

Visible for testing. Like std::set_symmetric_difference, but use a vector instead of sort. This assumes tmp_marked_ to be all false. We don't DCHECK it here for speed, but it DCHECKed on each EliminateVarUsingRow() call. In addition, the result is filtered using the extra_condition function.