25#include "absl/base/attributes.h"
26#include "absl/container/flat_hash_set.h"
27#include "absl/log/check.h"
28#include "absl/strings/str_cat.h"
29#include "absl/types/span.h"
42 if (coeff == 0)
return;
46 terms_.push_back({var, coeff});
54 if (coeff == 0)
return;
59 terms_.push_back({expr.
var, coeff * expr.
coeff});
75 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
78 terms_.push_back({expr.
vars[
i], expr.
coeffs[
i] * coeff});
83 offset_ += expr.
offset * coeff;
87 absl::Span<const LiteralValueValue> product) {
88 if (product.empty())
return true;
93 product_min = std::min(product_min, term.left_value * term.right_value);
97 IntegerValue coeff = term.left_value * term.right_value - product_min;
98 if (coeff == 0)
continue;
109 bool* is_quadratic) {
110 if (integer_trail->
IsFixed(left)) {
112 }
else if (integer_trail->
IsFixed(right)) {
115 const IntegerValue left_min = integer_trail->
LowerBound(left);
116 const IntegerValue right_min = integer_trail->
LowerBound(right);
121 if (is_quadratic !=
nullptr) *is_quadratic =
true;
130 Literal lit, IntegerValue coeff) {
131 DCHECK(encoder_ !=
nullptr);
133 bool view_is_direct =
true;
134 if (!encoder_->LiteralOrNegationHasView(lit, &var, &view_is_direct)) {
138 if (view_is_direct) {
179 const int shifted_size = size - 3;
184 const double* view = values.
data();
185 for (;
i < shifted_size;
i += 4) {
186 a0 +=
static_cast<double>(constraint.
coeffs[
i].value()) *
187 view[constraint.
vars[
i].value()];
188 a1 +=
static_cast<double>(constraint.
coeffs[
i + 1].value()) *
189 view[constraint.
vars[
i + 1].value()];
190 a2 +=
static_cast<double>(constraint.
coeffs[
i + 2].value()) *
191 view[constraint.
vars[
i + 2].value()];
192 a3 +=
static_cast<double>(constraint.
coeffs[
i + 3].value()) *
193 view[constraint.
vars[
i + 3].value()];
195 double activity = a0 + a1 + a2 + a3;
197 activity +=
static_cast<double>(constraint.
coeffs[
i].value()) *
198 view[constraint.
vars[
i].value()];
200 activity +=
static_cast<double>(constraint.
coeffs[
i + 1].value()) *
201 view[constraint.
vars[
i + 1].value()];
203 activity +=
static_cast<double>(constraint.
coeffs[
i + 2].value()) *
204 view[constraint.
vars[
i + 2].value()];
216 return std::sqrt(sum);
220 IntegerValue result(0);
231 double scalar_product = 0.0;
234 IntegerVariable var1 = ct1.
vars[index_1];
235 IntegerVariable var2 = ct2.
vars[index_2];
238 scalar_product +=
static_cast<double>(ct1.
coeffs[index_1].value()) *
239 static_cast<double>(ct2.
coeffs[index_2].value());
242 var1 = ct1.
vars[index_1];
243 var2 = ct2.
vars[index_2];
244 }
else if (var1 > var2) {
246 var2 = ct2.
vars[index_2];
249 var1 = ct1.
vars[index_1];
252 return scalar_product;
258IntegerValue ComputeGcd(absl::Span<const IntegerValue> values) {
259 if (values.empty())
return IntegerValue(1);
261 for (
const IntegerValue value : values) {
265 if (gcd < 0)
return IntegerValue(1);
266 return IntegerValue(gcd);
273 const IntegerValue gcd = ComputeGcd(
274 {constraint->
coeffs.get(),
static_cast<size_t>(constraint->
num_terms)});
275 if (gcd == 1)
return;
291 for (
int i = 0;
i < size; ++
i) {
292 if (constraint->
coeffs[
i] == 0)
continue;
293 constraint->
vars[new_size] = constraint->
vars[
i];
297 constraint->
resize(new_size);
302 for (
int i = 0;
i < size; ++
i) {
303 const IntegerValue coeff = constraint->
coeffs[
i];
305 constraint->
coeffs[
i] = -coeff;
313 for (
int i = 0;
i < size; ++
i) {
314 const IntegerVariable var = constraint->
vars[
i];
325 for (
int i = 0;
i <
vars.size(); ++
i) {
332 IntegerValue result =
offset;
333 for (
int i = 0;
i <
vars.size(); ++
i) {
341 IntegerValue result =
offset;
342 for (
int i = 0;
i <
vars.size(); ++
i) {
353 IntegerValue result =
offset;
354 for (
int i = 0;
i <
vars.size(); ++
i) {
365 if (
vars.empty())
return absl::StrCat(
offset.value());
367 for (
int i = 0;
i <
vars.size(); ++
i) {
368 absl::StrAppend(&result,
i > 0 ?
" " :
"",
372 absl::StrAppend(&result,
" + ",
offset.value());
378 absl::flat_hash_set<IntegerVariable> seen_variables;
380 for (
int i = 0;
i < size; ++
i) {
382 if (!seen_variables.insert(ct.
vars[
i]).second)
return false;
384 if (!seen_variables.insert(
NegationOf(ct.
vars[
i])).second)
return false;
393 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
398 canonical_expr.
vars.push_back(expr.
vars[
i]);
402 return canonical_expr;
409 int64_t positive_sum(0);
410 int64_t negative_sum(0);
412 const IntegerVariable var = constraint.
vars[
i];
413 const IntegerValue coeff = constraint.
coeffs[
i];
417 int64_t min_prod =
CapProd(coeff.value(), lb.value());
418 int64_t max_prod =
CapProd(coeff.value(), ub.value());
419 if (min_prod > max_prod) std::swap(min_prod, max_prod);
421 positive_sum =
CapAdd(positive_sum, std::max(int64_t{0}, max_prod));
422 negative_sum =
CapAdd(negative_sum, std::min(int64_t{0}, min_prod));
425 const int64_t limit = std::numeric_limits<int64_t>::max();
426 if (positive_sum >= limit)
return false;
427 if (negative_sum <= -limit)
return false;
428 if (
CapSub(positive_sum, negative_sum) >= limit)
return false;
444 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
458 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
459 if (expr.
vars[
i] == var) {
465 return IntegerValue(0);
471 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
472 if (expr.
vars[
i] == var) {
476 return IntegerValue(0);
481 IntegerValue min_activity(0);
482 IntegerValue max_activity(0);
484 for (
int i = 0;
i < size; ++
i) {
485 const IntegerVariable var = constraint.
vars[
i];
486 const IntegerValue coeff = constraint.
coeffs[
i];
491 if (!
AddProductTo(lb, coeff, &min_activity))
return true;
492 if (!
AddProductTo(ub, coeff, &max_activity))
return true;
494 if (!
AddProductTo(ub, coeff, &min_activity))
return true;
495 if (!
AddProductTo(lb, coeff, &max_activity))
return true;
static int64_t GCD64(int64_t x, int64_t y)
IntegerValue LowerBound(IntegerVariable i) const
Returns the current lower/upper bound of the given integer variable.
IntegerValue UpperBound(IntegerVariable i) const
IntegerValue FixedValue(IntegerVariable i) const
Checks that the variable is fixed and returns its value.
bool IsFixed(IntegerVariable i) const
Checks if the variable is fixed.
IntegerValue LevelZeroUpperBound(IntegerVariable var) const
IntegerValue LevelZeroLowerBound(IntegerVariable var) const
Returns globally valid lower/upper bound on the given integer variable.
void AddQuadraticLowerBound(AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
LinearExpression BuildExpression()
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff=IntegerValue(1))
void AddTerm(IntegerVariable var, IntegerValue coeff)
void AddLinearExpression(const LinearExpression &expr)
void AddConstant(IntegerValue value)
Adds the corresponding term to the current linear expression.
LinearConstraint BuildConstraint(IntegerValue lb, IntegerValue ub)
bool BuildIntoConstraintAndCheckOverflow(IntegerValue lb, IntegerValue ub, LinearConstraint *ct)
ABSL_MUST_USE_RESULT bool AddDecomposedProduct(absl::Span< const LiteralValueValue > product)
value_type * data()
– Pass-through methods to STL vector ----------------------------------—
double ComputeActivity(const LinearConstraint &constraint, const util_intops::StrongVector< IntegerVariable, double > &values)
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
bool AddProductTo(IntegerValue a, IntegerValue b, IntegerValue *result)
Computes result += a * b, and return false iff there is an overflow.
void DivideByGCD(LinearConstraint *constraint)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
IntType IntTypeAbs(IntType t)
double ComputeL2Norm(const LinearConstraint &ct)
Returns sqrt(sum square(coeff)).
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
bool ProdOverflow(IntegerValue t, IntegerValue value)
void RemoveZeroTerms(LinearConstraint *constraint)
Removes the entries with a coefficient of zero.
IntegerValue ComputeInfinityNorm(const LinearConstraint &ct)
Returns the maximum absolute value of the coefficients.
std::string IntegerTermDebugString(IntegerVariable var, IntegerValue coeff)
std::vector< IntegerVariable > NegationOf(absl::Span< const IntegerVariable > vars)
Returns the vector of the negated variables.
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
const IntegerVariable kNoIntegerVariable(-1)
bool PossibleOverflow(const IntegerTrail &integer_trail, const LinearConstraint &constraint)
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearExpression *output)
void MakeAllCoefficientsPositive(LinearConstraint *constraint)
Makes all coefficients positive by transforming a variable to its negation.
LinearExpression CanonicalizeExpr(const LinearExpression &expr)
bool MergePositiveVariableTermsAndCheckForOverflow(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearConstraint *output)
LinearExpression PositiveVarExpr(const LinearExpression &expr)
Returns the same expression with positive variables.
IntegerValue GetCoefficient(const IntegerVariable var, const LinearExpression &expr)
void MakeAllVariablesPositive(LinearConstraint *constraint)
Makes all variables "positive" by transforming a variable to its negation.
IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var, const LinearExpression &expr)
bool ValidateLinearConstraintForOverflow(const LinearConstraint &constraint, const IntegerTrail &integer_trail)
bool NoDuplicateVariable(const LinearConstraint &ct)
Returns false if duplicate variables are found in ct.
bool VariableIsPositive(IntegerVariable i)
double ToDouble(IntegerValue value)
double ScalarProduct(const LinearConstraint &ct1, const LinearConstraint &ct2)
In SWIG mode, we don't want anything besides these top-level includes.
bool AtMinOrMaxInt64(int64_t x)
Checks if x is equal to the min or the max value of an int64_t.
int64_t CapAdd(int64_t x, int64_t y)
int64_t CapSub(int64_t x, int64_t y)
int64_t CapProd(int64_t x, int64_t y)
std::unique_ptr< IntegerValue[]> coeffs
std::unique_ptr< IntegerVariable[]> vars
IntegerValue LevelZeroMin(IntegerTrail *integer_trail) const
IntegerValue Min(const IntegerTrail &integer_trail) const
double LpValue(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const
Return[s] the evaluation of the linear expression.
std::string DebugString() const
std::vector< IntegerVariable > vars
std::vector< IntegerValue > coeffs
IntegerValue Max(const IntegerTrail &integer_trail) const