Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::sat::LinearConstraintBuilder Class Reference

#include <linear_constraint.h>

Public Member Functions

 LinearConstraintBuilder (const Model *model)
 
 LinearConstraintBuilder (IntegerEncoder *encoder)
 
 LinearConstraintBuilder (const Model *model, IntegerValue lb, IntegerValue ub)
 
 LinearConstraintBuilder (IntegerEncoder *encoder, IntegerValue lb, IntegerValue ub)
 
 LinearConstraintBuilder ()
 
 LinearConstraintBuilder (IntegerValue lb, IntegerValue ub)
 
void AddConstant (IntegerValue value)
 Adds the corresponding term to the current linear expression.
 
void AddTerm (IntegerVariable var, IntegerValue coeff)
 
void AddTerm (AffineExpression expr, IntegerValue coeff)
 
void AddLinearExpression (const LinearExpression &expr)
 
void AddLinearExpression (const LinearExpression &expr, IntegerValue coeff)
 
ABSL_MUST_USE_RESULT bool AddDecomposedProduct (absl::Span< const LiteralValueValue > product)
 
ABSL_MUST_USE_RESULT bool AddLiteralTerm (Literal lit, IntegerValue coeff=IntegerValue(1))
 
void AddQuadraticLowerBound (AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
 
void Clear ()
 Clears all added terms and constants. Keeps the original bounds.
 
void ResetBounds (IntegerValue lb, IntegerValue ub)
 Reset the bounds passed at construction time.
 
LinearConstraint Build ()
 
LinearConstraint BuildConstraint (IntegerValue lb, IntegerValue ub)
 
bool BuildIntoConstraintAndCheckOverflow (IntegerValue lb, IntegerValue ub, LinearConstraint *ct)
 
LinearExpression BuildExpression ()
 

Detailed Description

Allow to build a LinearConstraint while making sure there is no duplicate variables. Note that we do not simplify literal/variable that are currently fixed here.

All the functions manipulate a linear expression with an offset. The final constraint bounds will include this offset.

Todo
(user): Rename to LinearExpressionBuilder?

Definition at line 196 of file linear_constraint.h.

Constructor & Destructor Documentation

◆ LinearConstraintBuilder() [1/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( const Model * model)
inlineexplicit

We support "sticky" kMinIntegerValue for lb and kMaxIntegerValue for ub for one-sided constraints.

Assumes that the 'model' has IntegerEncoder. The bounds can either be specified at construction or during the Build() call.

Definition at line 203 of file linear_constraint.h.

◆ LinearConstraintBuilder() [2/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( IntegerEncoder * encoder)
inlineexplicit

Definition at line 205 of file linear_constraint.h.

◆ LinearConstraintBuilder() [3/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( const Model * model,
IntegerValue lb,
IntegerValue ub )
inline

Definition at line 207 of file linear_constraint.h.

◆ LinearConstraintBuilder() [4/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( IntegerEncoder * encoder,
IntegerValue lb,
IntegerValue ub )
inline

Definition at line 209 of file linear_constraint.h.

◆ LinearConstraintBuilder() [5/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( )
inline
Warning
this version without encoder cannot be used to add literals, so one shouldn't call AddLiteralTerm() on it. All other functions works.
Todo
(user): Have a subclass so we can enforce that a caller using AddLiteralTerm() must construct the Builder with an encoder.

Definition at line 218 of file linear_constraint.h.

◆ LinearConstraintBuilder() [6/6]

operations_research::sat::LinearConstraintBuilder::LinearConstraintBuilder ( IntegerValue lb,
IntegerValue ub )
inline

Definition at line 219 of file linear_constraint.h.

Member Function Documentation

◆ AddConstant()

void operations_research::sat::LinearConstraintBuilder::AddConstant ( IntegerValue value)

Adds the corresponding term to the current linear expression.

Definition at line 125 of file linear_constraint.cc.

◆ AddDecomposedProduct()

ABSL_MUST_USE_RESULT bool operations_research::sat::LinearConstraintBuilder::AddDecomposedProduct ( absl::Span< const LiteralValueValue > product)

Add the corresponding decomposed products (obtained from TryToDecomposeProduct). The code assumes all literals to be in an exactly_one relation. It returns false if one literal does not have an integer view, as it actually calls AddLiteralTerm().

Todo
(user): Checks the value of literals.

Definition at line 86 of file linear_constraint.cc.

◆ AddLinearExpression() [1/2]

void operations_research::sat::LinearConstraintBuilder::AddLinearExpression ( const LinearExpression & expr)

Definition at line 68 of file linear_constraint.cc.

◆ AddLinearExpression() [2/2]

void operations_research::sat::LinearConstraintBuilder::AddLinearExpression ( const LinearExpression & expr,
IntegerValue coeff )

We must use positive variables.

Definition at line 73 of file linear_constraint.cc.

◆ AddLiteralTerm()

ABSL_MUST_USE_RESULT bool operations_research::sat::LinearConstraintBuilder::AddLiteralTerm ( Literal lit,
IntegerValue coeff = IntegerValue(1) )

Add literal * coeff to the constaint. Returns false and do nothing if the given literal didn't have an integer view.

Definition at line 129 of file linear_constraint.cc.

◆ AddQuadraticLowerBound()

void operations_research::sat::LinearConstraintBuilder::AddQuadraticLowerBound ( AffineExpression left,
AffineExpression right,
IntegerTrail * integer_trail,
bool * is_quadratic = nullptr )

Add an under linearization of the product of two affine expressions. If at least one of them is fixed, then we add the exact product (which is linear). Otherwise, we use McCormick relaxation: left * right = (left_min + delta_left) * (right_min + delta_right) = left_min * right_min + delta_left * right_min + delta_right * left_min + delta_left * delta_right which is >= (by ignoring the quatratic term) right_min * left + left_min * right - right_min * left_min

Todo
(user): We could use (max - delta) instead of (min + delta) for each expression instead. This would depend on the LP value of the left and right.

Substract the energy counted twice.

Definition at line 107 of file linear_constraint.cc.

◆ AddTerm() [1/2]

void operations_research::sat::LinearConstraintBuilder::AddTerm ( AffineExpression expr,
IntegerValue coeff )

We can either add var or NegationOf(var), and we always choose the positive one.

Definition at line 52 of file linear_constraint.cc.

◆ AddTerm() [2/2]

void operations_research::sat::LinearConstraintBuilder::AddTerm ( IntegerVariable var,
IntegerValue coeff )

We can either add var or NegationOf(var), and we always choose the positive one.

Definition at line 41 of file linear_constraint.cc.

◆ Build()

LinearConstraint operations_research::sat::LinearConstraintBuilder::Build ( )

Builds and returns the corresponding constraint in a canonical form. All the IntegerVariable will be positive and appear in increasing index order.

The bounds can be changed here or taken at construction.

Todo
(user): this doesn't invalidate the builder object, but if one wants to do a lot of dynamic editing to the constraint, then then underlying algorithm needs to be optimized for that.

Definition at line 147 of file linear_constraint.cc.

◆ BuildConstraint()

LinearConstraint operations_research::sat::LinearConstraintBuilder::BuildConstraint ( IntegerValue lb,
IntegerValue ub )

Definition at line 151 of file linear_constraint.cc.

◆ BuildExpression()

LinearExpression operations_research::sat::LinearConstraintBuilder::BuildExpression ( )

Returns the linear expression part of the constraint only, without the bounds.

Definition at line 167 of file linear_constraint.cc.

◆ BuildIntoConstraintAndCheckOverflow()

bool operations_research::sat::LinearConstraintBuilder::BuildIntoConstraintAndCheckOverflow ( IntegerValue lb,
IntegerValue ub,
LinearConstraint * ct )

Similar to BuildConstraint() but make sure we don't overflow while we merge terms referring to the same variables.

Definition at line 160 of file linear_constraint.cc.

◆ Clear()

void operations_research::sat::LinearConstraintBuilder::Clear ( )
inline

Clears all added terms and constants. Keeps the original bounds.

Definition at line 259 of file linear_constraint.h.

◆ ResetBounds()

void operations_research::sat::LinearConstraintBuilder::ResetBounds ( IntegerValue lb,
IntegerValue ub )
inline

Reset the bounds passed at construction time.

Definition at line 265 of file linear_constraint.h.

The documentation for this class was generated from the following files: