Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class ZeroHalfCutHelper
Note: 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.
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.
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.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe \u003ccode\u003eZeroHalfCutHelper\u003c/code\u003e class implements heuristics to find violated zero-half cuts based on the parity of LP coefficients and the right-hand side.\u003c/p\u003e\n"],["\u003cp\u003eIt maintains a simplified LP matrix modulo 2 to search for cut candidates, as described in the paper "Algorithms to Separate {0, 1/2}-Chvátal-Gomory Cuts".\u003c/p\u003e\n"],["\u003cp\u003eThe class offers methods to add constraints, process variables, and retrieve promising zero-half cut candidates.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eProcessVariables\u003c/code\u003e must be called first, followed by adding constraints before using \u003ccode\u003eGetZeroHalfInterestingCuts\u003c/code\u003e to obtain potential cuts.\u003c/p\u003e\n"],["\u003cp\u003eThe current implementation focuses on initial functionality, with potential for future improvements in both heuristics and code performance.\u003c/p\u003e\n"]]],["The `ZeroHalfCutHelper` class aims to find violated zero-half cuts in linear programming. It maintains a copy of the LP matrix modulo 2, focusing on the parity of coefficients and the right-hand side. Key actions include: adding constraints via `AddOneConstraint`, processing variables with `ProcessVariables`, and adding binary rows via `AddBinaryRow`. Other methods include `EliminateVarUsingRow`, `Reset`, `MatrixCol`, `MatrixRow`, `SymmetricDifference`, and `InterestingCandidates`. These methods are designed to simplify and analyze the matrix to discover good cut candidates, according to the heuristic explained in the paper by Arie et al.\n"],null,["# ZeroHalfCutHelper\n\nC++ Reference: class ZeroHalfCutHelper\n======================================\n\n\nNote: This documentation is automatically generated.\nHeuristic 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). \n\nFor 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). \n\nMost 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.\n\n| Method ||\n|----------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddBinaryRow`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L79) | Return type: `void ` Arguments: `const CombinationOfRows& binary_row` \u003cbr /\u003e |\n| [`AddOneConstraint`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L51) | Return type: `void ` Arguments: ` glop::RowIndex, const std::vector\u003cstd::pair\u003cglop::ColIndex, IntegerValue\u003e\u003e& terms, IntegerValue lb, IntegerValue ub` \u003cbr /\u003e |\n| [`EliminateVarUsingRow`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L88) | 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. |\n| [`InterestingCandidates`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L56) | \u003cbr /\u003e Arguments: `ModelRandomGenerator* random` \u003cbr /\u003e |\n| [`MatrixCol`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L81) | Return type: `const std::vector\u003cint\u003e& ` Arguments: `int col` \u003cbr /\u003e |\n| [`MatrixRow`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L80) | Return type: `const CombinationOfRows& ` Arguments: `int row` \u003cbr /\u003e |\n| [`ProcessVariables`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L48) | Return type: `void ` Arguments: `const std::vector\u003cdouble\u003e& lp_values, const std::vector\u003cIntegerValue\u003e& lower_bounds, const std::vector\u003cIntegerValue\u003e& 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. |\n| [`Reset`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L59) | Return type: `void ` Arguments: `int size` Visible for testing. |\n| [`SymmetricDifference`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/zero_half_cuts.h#L96) | Return type: `void ` Arguments: `std::function\u003cbool(int)\u003e extra_condition, const std::vector\u003cint\u003e& a, std::vector\u003cint\u003e* 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. |"]]
