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) {
177 const double violation =
179 if (violation <= 0.0)
return 0.0;
182 return violation / l2_norm;
190 const int shifted_size = size - 3;
195 const double* view = values.
data();
196 for (;
i < shifted_size;
i += 4) {
197 a0 +=
static_cast<double>(constraint.
coeffs[
i].value()) *
198 view[constraint.
vars[
i].value()];
199 a1 +=
static_cast<double>(constraint.
coeffs[
i + 1].value()) *
200 view[constraint.
vars[
i + 1].value()];
201 a2 +=
static_cast<double>(constraint.
coeffs[
i + 2].value()) *
202 view[constraint.
vars[
i + 2].value()];
203 a3 +=
static_cast<double>(constraint.
coeffs[
i + 3].value()) *
204 view[constraint.
vars[
i + 3].value()];
206 double activity = a0 + a1 + a2 + a3;
208 activity +=
static_cast<double>(constraint.
coeffs[
i].value()) *
209 view[constraint.
vars[
i].value()];
211 activity +=
static_cast<double>(constraint.
coeffs[
i + 1].value()) *
212 view[constraint.
vars[
i + 1].value()];
214 activity +=
static_cast<double>(constraint.
coeffs[
i + 2].value()) *
215 view[constraint.
vars[
i + 2].value()];
227 return std::sqrt(sum);
231 IntegerValue result(0);
242 double scalar_product = 0.0;
245 IntegerVariable var1 = ct1.
vars[index_1];
246 IntegerVariable var2 = ct2.
vars[index_2];
249 scalar_product +=
static_cast<double>(ct1.
coeffs[index_1].value()) *
250 static_cast<double>(ct2.
coeffs[index_2].value());
253 var1 = ct1.
vars[index_1];
254 var2 = ct2.
vars[index_2];
255 }
else if (var1 > var2) {
257 var2 = ct2.
vars[index_2];
260 var1 = ct1.
vars[index_1];
263 return scalar_product;
269IntegerValue ComputeGcd(absl::Span<const IntegerValue> values) {
270 if (values.empty())
return IntegerValue(1);
272 for (
const IntegerValue value : values) {
276 if (gcd < 0)
return IntegerValue(1);
277 return IntegerValue(gcd);
284 const IntegerValue gcd = ComputeGcd(
285 {constraint->
coeffs.get(),
static_cast<size_t>(constraint->
num_terms)});
286 if (gcd == 1)
return;
302 for (
int i = 0;
i < size; ++
i) {
303 if (constraint->
coeffs[
i] == 0)
continue;
304 constraint->
vars[new_size] = constraint->
vars[
i];
308 constraint->
resize(new_size);
313 for (
int i = 0;
i < size; ++
i) {
314 const IntegerValue coeff = constraint->
coeffs[
i];
316 constraint->
coeffs[
i] = -coeff;
324 for (
int i = 0;
i < size; ++
i) {
325 const IntegerVariable var = constraint->
vars[
i];
336 for (
int i = 0;
i <
vars.size(); ++
i) {
343 IntegerValue result =
offset;
344 for (
int i = 0;
i <
vars.size(); ++
i) {
352 IntegerValue result =
offset;
353 for (
int i = 0;
i <
vars.size(); ++
i) {
364 IntegerValue result =
offset;
365 for (
int i = 0;
i <
vars.size(); ++
i) {
376 if (
vars.empty())
return absl::StrCat(
offset.value());
378 for (
int i = 0;
i <
vars.size(); ++
i) {
379 absl::StrAppend(&result,
i > 0 ?
" " :
"",
383 absl::StrAppend(&result,
" + ",
offset.value());
389 absl::flat_hash_set<IntegerVariable> seen_variables;
391 for (
int i = 0;
i < size; ++
i) {
393 if (!seen_variables.insert(ct.
vars[
i]).second)
return false;
395 if (!seen_variables.insert(
NegationOf(ct.
vars[
i])).second)
return false;
404 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
409 canonical_expr.
vars.push_back(expr.
vars[
i]);
413 return canonical_expr;
420 int64_t positive_sum(0);
421 int64_t negative_sum(0);
423 const IntegerVariable var = constraint.
vars[
i];
424 const IntegerValue coeff = constraint.
coeffs[
i];
428 int64_t min_prod =
CapProd(coeff.value(), lb.value());
429 int64_t max_prod =
CapProd(coeff.value(), ub.value());
430 if (min_prod > max_prod) std::swap(min_prod, max_prod);
432 positive_sum =
CapAdd(positive_sum, std::max(int64_t{0}, max_prod));
433 negative_sum =
CapAdd(negative_sum, std::min(int64_t{0}, min_prod));
436 const int64_t limit = std::numeric_limits<int64_t>::max();
437 if (positive_sum >= limit)
return false;
438 if (negative_sum <= -limit)
return false;
439 if (
CapSub(positive_sum, negative_sum) >= limit)
return false;
455 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
469 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
470 if (expr.
vars[
i] == var) {
476 return IntegerValue(0);
482 for (
int i = 0;
i < expr.
vars.size(); ++
i) {
483 if (expr.
vars[
i] == var) {
487 return IntegerValue(0);
492 IntegerValue min_activity(0);
493 IntegerValue max_activity(0);
495 for (
int i = 0;
i < size; ++
i) {
496 const IntegerVariable var = constraint.
vars[
i];
497 const IntegerValue coeff = constraint.
coeffs[
i];
502 if (!
AddProductTo(lb, coeff, &min_activity))
return true;
503 if (!
AddProductTo(ub, coeff, &max_activity))
return true;
505 if (!
AddProductTo(ub, coeff, &min_activity))
return true;
506 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
double NormalizedViolation(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const
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