operations_research::sat::RoundingOptions Struct Reference

#include <cuts.h>

Public Attributes
IntegerValue	max_scaling = IntegerValue(60)
bool	use_ib_before_heuristic = true
bool	prefer_positive_ib = true

Detailed Description

Given an upper bounded linear constraint, this function tries to transform it to a valid cut that violate the given LP solution using integer rounding.

Note

the returned cut might not always violate the LP solution, in which case it can be discarded.

What this does is basically take the integer division of the constraint by an integer. If the coefficients where doubles, this would be the same as scaling the constraint and then rounding. We choose the coefficient of the most fractional variable (rescaled by its coefficient) as the divisor, but there are other possible alternatives.

Note

if the constraint is tight under the given lp solution, and if there is a unique variable not at one of its bounds and fractional, then we are guaranteed to generate a cut that violate the current LP solution. This should be the case for Chvatal-Gomory base constraints modulo our loss of precision while doing exact integer computations.

Precondition:

• We assumes that the given initial constraint is tight using the given lp values. This could be relaxed, but for now it should always be the case, so we log a message and abort if not, to ease debugging.

• The IntegerVariable of the cuts are not used here. We assumes that the first three vectors are in one to one correspondence with the initial order of the variable in the cut.

  Todo

  (user): There is a bunch of heuristic involved here, and we could spend more effort tuning them. In particular, one can try many heuristics and keep the best looking cut (or more than one). This is not on the critical code path, so we can spend more effort in finding good cuts.

Definition at line 401 of file cuts.h.

Member Data Documentation

max_scaling

IntegerValue operations_research::sat::RoundingOptions::max_scaling = IntegerValue(60)

Definition at line 402 of file cuts.h.

prefer_positive_ib

bool operations_research::sat::RoundingOptions::prefer_positive_ib = true

Definition at line 404 of file cuts.h.

use_ib_before_heuristic

bool operations_research::sat::RoundingOptions::use_ib_before_heuristic = true

Definition at line 403 of file cuts.h.

---

The documentation for this struct was generated from the following file:

• ortools/sat/cuts.h