Google OR-Tools v9.11
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)
 
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 191 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 198 of file linear_constraint.h.

◆ LinearConstraintBuilder() [2/6]

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

Definition at line 200 of file linear_constraint.h.

◆ LinearConstraintBuilder() [3/6]

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

Definition at line 202 of file linear_constraint.h.

◆ LinearConstraintBuilder() [4/6]

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

Definition at line 204 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 213 of file linear_constraint.h.

◆ LinearConstraintBuilder() [6/6]

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

Definition at line 214 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 123 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 84 of file linear_constraint.cc.

◆ AddLinearExpression() [1/2]

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

Definition at line 66 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 71 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 127 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 105 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 51 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 40 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 145 of file linear_constraint.cc.

◆ BuildConstraint()

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

Definition at line 149 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 158 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 254 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 260 of file linear_constraint.h.

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