operations_research::sat::ZeroHalfCutHelper Class Reference

#include <zero_half_cuts.h>

Classes
struct	CombinationOfRows

Public Member Functions
void	ProcessVariables (const std::vector< double > &lp_values, absl::Span< const IntegerValue > lower_bounds, absl::Span< const IntegerValue > upper_bounds)
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	Reset (int size)
	Visible for testing.
void	AddBinaryRow (const CombinationOfRows &binary_row)
const CombinationOfRows &	MatrixRow (int row) const
const std::vector< int > &	MatrixCol (int col) const
void	EliminateVarUsingRow (int col, int row)
	This is basically one step of a Gaussian elimination with the given pivot.
void	SymmetricDifference (absl::Span< const int > a, std::vector< int > *b)

Detailed Description

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.

Definition at line 41 of file zero_half_cuts.h.

Member Function Documentation

AddBinaryRow()

void operations_research::sat::ZeroHalfCutHelper::AddBinaryRow

(

const CombinationOfRows &

binary_row

)

No point pushing an all zero row with a zero rhs.

Definition at line 61 of file zero_half_cuts.cc.

AddOneConstraint()

void operations_research::sat::ZeroHalfCutHelper::AddOneConstraint	(	glop::RowIndex	row,
		absl::Span< const glop::ColIndex >	cols,
		absl::Span< const IntegerValue >	coeffs,
		IntegerValue	lb,
		IntegerValue	ub )

Only consider odd coefficient.

Ignore column in the binary matrix if its lp value is almost zero.

Because we work on the shifted variable, the rhs needs to be updated.

We ignore constraint with large coefficient, since there is little chance to cancel them and because of that the efficacity of a generated cut will be limited.

Todo

(user): experiment with the best value. probably only tight rows are best? and we could use the basis status rather than recomputing the activity for that.

Todo

(user): Avoid adding duplicates and just randomly pick one. Note that we should also remove duplicate in a generic way.

Definition at line 70 of file zero_half_cuts.cc.

EliminateVarUsingRow()

void operations_research::sat::ZeroHalfCutHelper::EliminateVarUsingRow	(	int	col,
		int	row )

This is basically one step of a Gaussian elimination with the given pivot.

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.

First update the row representation of the matrix.

Update slack & parity.

Update the multipliers the same way.

Cancel both.

Then update the col representation of the matrix.

Eliminate new singleton column right away.

Clear col since it is now singleton.

Definition at line 151 of file zero_half_cuts.cc.

InterestingCandidates()

std::vector< std::vector< std::pair< glop::RowIndex, IntegerValue > > > operations_research::sat::ZeroHalfCutHelper::InterestingCandidates

(

ModelRandomGenerator *

random

)

Remove singleton column from the picture.

Process rows by increasing size, but randomize if same size.

Heuristic: eliminate the variable with highest shifted lp value.

As an heuristic, we just try to add zero rows with an odd rhs and a low enough slack.

Definition at line 218 of file zero_half_cuts.cc.

MatrixCol()

const std::vector< int > & operations_research::sat::ZeroHalfCutHelper::MatrixCol ( int col ) const

inline

Definition at line 81 of file zero_half_cuts.h.

MatrixRow()

const CombinationOfRows & operations_research::sat::ZeroHalfCutHelper::MatrixRow ( int row ) const

inline

Definition at line 80 of file zero_half_cuts.h.

ProcessVariables()

void operations_research::sat::ZeroHalfCutHelper::ProcessVariables	(	const std::vector< double > &	lp_values,
		absl::Span< const IntegerValue >	lower_bounds,
		absl::Span< const 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.

Shift all variables to their closest bound.

Definition at line 40 of file zero_half_cuts.cc.

Reset()

void operations_research::sat::ZeroHalfCutHelper::Reset

(

int

size

)

Visible for testing.

Definition at line 31 of file zero_half_cuts.cc.

SymmetricDifference()

void operations_research::sat::ZeroHalfCutHelper::SymmetricDifference	(	absl::Span< const int >	a,
		std::vector< int > *	b )

Visible for testing.

Like std::set_symmetric_difference, but use a vector<bool> 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.

Todo

(user): optim by doing that at the end?

Remove position that are not marked, and clear tmp_marked_.

Definition at line 125 of file zero_half_cuts.cc.

---

The documentation for this class was generated from the following files:

• ortools/sat/zero_half_cuts.h
• ortools/sat/zero_half_cuts.cc