14#ifndef OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
15#define OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
26#include "absl/base/attributes.h"
27#include "absl/log/check.h"
28#include "absl/strings/str_cat.h"
29#include "absl/types/span.h"
63 std::unique_ptr<IntegerVariable[]>
vars;
64 std::unique_ptr<IntegerValue[]>
coeffs;
79 IntegerVariable* tmp_vars =
new IntegerVariable[size];
80 IntegerValue* tmp_coeffs =
new IntegerValue[size];
81 const int to_copy = std::min(size,
num_terms);
83 memcpy(tmp_vars,
vars.get(),
sizeof(IntegerVariable) * to_copy);
84 memcpy(tmp_coeffs,
coeffs.get(),
sizeof(IntegerValue) * to_copy);
94 absl::StrAppend(&result,
lb.value(),
" <= ");
97 absl::StrAppend(&result,
i > 0 ?
" " :
"",
101 absl::StrAppend(&result,
" <= ",
ub.value());
107 if (this->num_terms != other.
num_terms)
return false;
108 if (this->num_terms == 0)
return true;
109 if (memcmp(this->vars.get(), other.
vars.get(),
110 sizeof(IntegerVariable) * this->num_terms)) {
113 if (memcmp(this->coeffs.get(), other.
coeffs.get(),
114 sizeof(IntegerValue) * this->num_terms)) {
121 if (this->lb != other.
lb)
return false;
122 if (this->ub != other.
ub)
return false;
143 std::vector<IntegerVariable>
vars;
212 : encoder_(encoder), lb_(0), ub_(0) {}
217 : encoder_(encoder), lb_(lb), ub_(ub) {}
226 : encoder_(nullptr), lb_(lb), ub_(ub) {}
230 void AddTerm(IntegerVariable var, IntegerValue coeff);
241 absl::Span<const LiteralValueValue> product);
246 Literal lit, IntegerValue coeff = IntegerValue(1));
262 bool* is_quadratic =
nullptr);
266 offset_ = IntegerValue(0);
304 IntegerValue offset_ = IntegerValue(0);
308 std::vector<std::pair<IntegerVariable, IntegerValue>> terms_;
314 const LinearConstraint& constraint,
324 const LinearConstraint& constraint);
335 const LinearConstraint& constraint2);
356 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
358 output->
vars.clear();
363 std::sort(terms->begin(), terms->end());
365 IntegerValue current_coeff(0);
366 for (
const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
367 if (previous_var == entry.first) {
368 current_coeff += entry.second;
369 }
else if (previous_var ==
NegationOf(entry.first)) {
370 current_coeff -= entry.second;
372 if (current_coeff != 0) {
373 output->
vars.push_back(previous_var);
374 output->
coeffs.push_back(current_coeff);
376 previous_var = entry.first;
377 current_coeff = entry.second;
380 if (current_coeff != 0) {
381 output->
vars.push_back(previous_var);
382 output->
coeffs.push_back(current_coeff);
387 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
392 output->
resize(terms->size());
393 std::sort(terms->begin(), terms->end());
395 IntegerValue current_coeff(0);
396 for (
const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
397 if (previous_var == entry.first) {
398 current_coeff += entry.second;
399 }
else if (previous_var ==
NegationOf(entry.first)) {
400 current_coeff -= entry.second;
402 if (current_coeff != 0) {
403 output->
vars[new_size] = previous_var;
404 output->
coeffs[new_size] = current_coeff;
407 previous_var = entry.first;
408 current_coeff = entry.second;
411 if (current_coeff != 0) {
412 output->
vars[new_size] = previous_var;
413 output->
coeffs[new_size] = current_coeff;
420 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
425 output->
resize(terms->size());
426 std::sort(terms->begin(), terms->end());
428 int64_t current_coeff = 0;
429 for (
const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
431 if (previous_var == entry.first) {
436 if (current_coeff != 0) {
437 output->
vars[new_size] = previous_var;
438 output->
coeffs[new_size] = current_coeff;
441 previous_var = entry.first;
442 current_coeff = entry.second.value();
445 if (current_coeff != 0) {
446 output->
vars[new_size] = previous_var;
447 output->
coeffs[new_size] = current_coeff;
void AddQuadraticLowerBound(AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
LinearConstraintBuilder()
LinearExpression BuildExpression()
LinearConstraintBuilder(IntegerEncoder *encoder)
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff=IntegerValue(1))
void ResetBounds(IntegerValue lb, IntegerValue ub)
Reset the bounds passed at construction time.
LinearConstraintBuilder(IntegerEncoder *encoder, IntegerValue lb, IntegerValue ub)
void AddTerm(IntegerVariable var, IntegerValue coeff)
void AddLinearExpression(const LinearExpression &expr)
void AddConstant(IntegerValue value)
Adds the corresponding term to the current linear expression.
LinearConstraintBuilder(const Model *model)
void Clear()
Clears all added terms and constants. Keeps the original bounds.
LinearConstraintBuilder(const Model *model, IntegerValue lb, IntegerValue ub)
LinearConstraint BuildConstraint(IntegerValue lb, IntegerValue ub)
LinearConstraintBuilder(IntegerValue lb, IntegerValue ub)
bool BuildIntoConstraintAndCheckOverflow(IntegerValue lb, IntegerValue ub, LinearConstraint *ct)
ABSL_MUST_USE_RESULT bool AddDecomposedProduct(absl::Span< const LiteralValueValue > product)
double ComputeActivity(const LinearConstraint &constraint, const util_intops::StrongVector< IntegerVariable, double > &values)
void DivideByGCD(LinearConstraint *constraint)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
double ComputeL2Norm(const LinearConstraint &ct)
Returns sqrt(sum square(coeff)).
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.
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
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 ScalarProduct(const LinearConstraint &ct1, const LinearConstraint &ct2)
In SWIG mode, we don't want anything besides these top-level includes.
bool AddIntoOverflow(int64_t x, int64_t *y)
LinearConstraint()=default
std::unique_ptr< IntegerValue[]> coeffs
std::unique_ptr< IntegerVariable[]> vars
absl::Span< const IntegerValue > CoeffsAsSpan() const
std::string DebugString() const
absl::Span< const IntegerVariable > VarsAsSpan() const
bool IsEqualIgnoringBounds(const LinearConstraint &other) const
bool operator==(const LinearConstraint &other) const
LinearConstraint(IntegerValue _lb, IntegerValue _ub)
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