27 terms_.push_back({
var, coeff});
39 terms_.push_back({expr.
var, coeff * expr.
coeff});
54 Literal lit, IntegerValue coeff) {
56 bool has_opposite_view =
62 if (has_direct_view && has_opposite_view) {
65 has_opposite_view =
false;
67 has_direct_view =
false;
70 if (has_direct_view) {
74 if (has_opposite_view) {
84 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
86 constraint->
vars.clear();
87 constraint->
coeffs.clear();
91 std::sort(terms->begin(), terms->end());
93 IntegerValue current_coeff(0);
94 for (
const std::pair<IntegerVariable, IntegerValue> entry : *terms) {
95 if (previous_var == entry.first) {
96 current_coeff += entry.second;
97 }
else if (previous_var ==
NegationOf(entry.first)) {
98 current_coeff -= entry.second;
100 if (current_coeff != 0) {
101 constraint->
vars.push_back(previous_var);
102 constraint->
coeffs.push_back(current_coeff);
104 previous_var = entry.first;
105 current_coeff = entry.second;
108 if (current_coeff != 0) {
109 constraint->
vars.push_back(previous_var);
110 constraint->
coeffs.push_back(current_coeff);
126 for (
int i = 0; i < constraint.
vars.size(); ++i) {
127 const IntegerVariable
var = constraint.
vars[i];
128 const IntegerValue coeff = constraint.
coeffs[i];
129 activity += coeff.value() * values[
var];
136 for (
const IntegerValue coeff : constraint.
coeffs) {
139 return std::sqrt(sum);
143 IntegerValue result(0);
144 for (
const IntegerValue coeff : constraint.
coeffs) {
152 DCHECK(std::is_sorted(constraint1.
vars.begin(), constraint1.
vars.end()));
153 DCHECK(std::is_sorted(constraint2.
vars.begin(), constraint2.
vars.end()));
154 double scalar_product = 0.0;
157 while (index_1 < constraint1.
vars.size() &&
158 index_2 < constraint2.
vars.size()) {
159 if (constraint1.
vars[index_1] == constraint2.
vars[index_2]) {
164 }
else if (constraint1.
vars[index_1] > constraint2.
vars[index_2]) {
170 return scalar_product;
176IntegerValue ComputeGcd(
const std::vector<IntegerValue>& values) {
177 if (values.empty())
return IntegerValue(1);
179 for (
const IntegerValue
value : values) {
183 if (gcd < 0)
return IntegerValue(1);
184 return IntegerValue(gcd);
190 if (constraint->
coeffs.empty())
return;
191 const IntegerValue gcd = ComputeGcd(constraint->
coeffs);
192 if (gcd == 1)
return;
200 for (IntegerValue& coeff : constraint->
coeffs) coeff /= gcd;
205 const int size = constraint->
vars.size();
206 for (
int i = 0; i < size; ++i) {
207 if (constraint->
coeffs[i] == 0)
continue;
208 constraint->
vars[new_size] = constraint->
vars[i];
212 constraint->
vars.resize(new_size);
213 constraint->
coeffs.resize(new_size);
217 const int size = constraint->
vars.size();
218 for (
int i = 0; i < size; ++i) {
219 const IntegerValue coeff = constraint->
coeffs[i];
221 constraint->
coeffs[i] = -coeff;
228 const int size = constraint->
vars.size();
229 for (
int i = 0; i < size; ++i) {
230 const IntegerVariable
var = constraint->
vars[i];
245 std::vector<std::pair<IntegerVariable, IntegerValue>> terms;
247 const int size =
ct->vars.size();
248 for (
int i = 0; i < size; ++i) {
250 terms.push_back({
ct->vars[i],
ct->coeffs[i]});
255 std::sort(terms.begin(), terms.end());
259 for (
const auto& term : terms) {
260 ct->vars.push_back(term.first);
261 ct->coeffs.push_back(term.second);
266 absl::flat_hash_set<IntegerVariable> seen_variables;
267 const int size =
ct.vars.size();
268 for (
int i = 0; i < size; ++i) {
270 if (!seen_variables.insert(
ct.vars[i]).second)
return false;
272 if (!seen_variables.insert(
NegationOf(
ct.vars[i])).second)
return false;
281 for (
int i = 0; i < expr.
vars.size(); ++i) {
286 canonical_expr.
vars.push_back(expr.
vars[i]);
290 return canonical_expr;
295 IntegerValue lower_bound = expr.
offset;
296 for (
int i = 0; i < expr.
vars.size(); ++i) {
305 IntegerValue upper_bound = expr.
offset;
306 for (
int i = 0; i < expr.
vars.size(); ++i) {
324 for (
int i = 0; i < expr.
vars.size(); ++i) {
326 result.
vars.push_back(expr.
vars[i]);
338 for (
int i = 0; i < expr.
vars.size(); ++i) {
345 return IntegerValue(0);
351 for (
int i = 0; i < expr.
vars.size(); ++i) {
356 return IntegerValue(0);
#define DCHECK_GE(val1, val2)
#define DCHECK(condition)
static int64 GCD64(int64 x, int64 y)
const IntegerVariable GetLiteralView(Literal lit) const
IntegerValue UpperBound(IntegerVariable i) const
IntegerValue LowerBound(IntegerVariable i) const
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff)
void AddConstant(IntegerValue value)
void AddTerm(IntegerVariable var, IntegerValue coeff)
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearConstraint *constraint)
bool VariableIsPositive(IntegerVariable i)
IntegerValue LinExprLowerBound(const LinearExpression &expr, const IntegerTrail &integer_trail)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
void RemoveZeroTerms(LinearConstraint *constraint)
LinearExpression PositiveVarExpr(const LinearExpression &expr)
double ScalarProduct(const LinearConstraint &constraint1, const LinearConstraint &constraint2)
void MakeAllCoefficientsPositive(LinearConstraint *constraint)
const IntegerVariable kNoIntegerVariable(-1)
LinearExpression CanonicalizeExpr(const LinearExpression &expr)
void CanonicalizeConstraint(LinearConstraint *ct)
bool NoDuplicateVariable(const LinearConstraint &ct)
double ComputeL2Norm(const LinearConstraint &constraint)
IntegerValue GetCoefficient(const IntegerVariable var, const LinearExpression &expr)
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
IntType IntTypeAbs(IntType t)
void MakeAllVariablesPositive(LinearConstraint *constraint)
double ToDouble(IntegerValue value)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var, const LinearExpression &expr)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
IntegerValue ComputeInfinityNorm(const LinearConstraint &constraint)
IntegerValue LinExprUpperBound(const LinearExpression &expr, const IntegerTrail &integer_trail)
void DivideByGCD(LinearConstraint *constraint)
double ComputeActivity(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &values)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< IntegerValue > coeffs
std::vector< IntegerVariable > vars
std::vector< IntegerValue > coeffs
std::vector< IntegerVariable > vars