Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer Class Reference

Detailed Description

This class is used to incrementally maintain an assignment and the feasibility of the constraints of a given LinearBooleanProblem.

The current assignment is initialized using a feasible reference solution, i.e. the reference solution satisfies all the constraints of the problem. The current assignment is updated using the Assign() method.

Note
the current assignment is not a solution in the sense that it might not be feasible, ie. violates some constraints.

The assignment can be accessed at any time using Assignment(). The set of infeasible constraints can be accessed at any time using PossiblyInfeasibleConstraints().

Note
this class is reversible, i.e. it is possible to backtrack to previously added backtracking levels. levels. Consider for instance variable a, b, c, and d. Method called Assigned after method call 1- Assign({a, b}) a b 2- AddBacktrackingLevel() a b | 3- Assign({c}) a b | c 4- Assign({d}) a b | c d 5- BacktrackOneLevel() a b 6- Assign({c}) a b c 7- BacktrackOneLevel()

Definition at line 282 of file bop_ls.h.

#include <bop_ls.h>

Public Member Functions

 AssignmentAndConstraintFeasibilityMaintainer (const sat::LinearBooleanProblem &problem, absl::BitGenRef random)
 AssignmentAndConstraintFeasibilityMaintainer (const AssignmentAndConstraintFeasibilityMaintainer &)=delete
 This type is neither copyable nor movable.
AssignmentAndConstraintFeasibilityMaintainer & operator= (const AssignmentAndConstraintFeasibilityMaintainer &)=delete
void SetReferenceSolution (const BopSolution &reference_solution)
void UseCurrentStateAsReference ()
void Assign (absl::Span< const sat::Literal > literals)
void AddBacktrackingLevel ()
void BacktrackOneLevel ()
void BacktrackAll ()
const std::vector< sat::Literal > & PotentialOneFlipRepairs ()
bool IsFeasible () const
 Returns true if there is no infeasible constraint in the current state.
int NumInfeasibleConstraints () const
const std::vector< ConstraintIndex > & PossiblyInfeasibleConstraints () const
 Returns a superset of all the infeasible constraints in the current state.
size_t NumConstraints () const
bool Assignment (VariableIndex var) const
const BopSolution & reference () const
 Returns the current assignment.
int64_t ConstraintLowerBound (ConstraintIndex constraint) const
 Returns the lower bound of the constraint.
int64_t ConstraintUpperBound (ConstraintIndex constraint) const
 Returns the upper bound of the constraint.
int64_t ConstraintValue (ConstraintIndex constraint) const
bool ConstraintIsFeasible (ConstraintIndex constraint) const
 Returns true if the given constraint is currently feasible.
std::string DebugString () const

Static Public Attributes

static const ConstraintIndex kObjectiveConstraint

Constructor & Destructor Documentation

◆ AssignmentAndConstraintFeasibilityMaintainer() [1/2]

operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::AssignmentAndConstraintFeasibilityMaintainer ( const sat::LinearBooleanProblem & problem,
absl::BitGenRef random )
explicit
Note
the constraint indices used in this class are not the same as the one used in the given LinearBooleanProblem here.

AssignmentAndConstraintFeasibilityMaintainer

Add the objective constraint as the first constraint.

Add each constraint.

Infeasible binary constraints are automatically repaired by propagation (when possible). Then there are no needs to consider the binary constraints here, the propagation is delegated to the SAT propagator.

Initialize infeasible_constraint_set_;

Definition at line 211 of file bop_ls.cc.

◆ AssignmentAndConstraintFeasibilityMaintainer() [2/2]

operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::AssignmentAndConstraintFeasibilityMaintainer ( const AssignmentAndConstraintFeasibilityMaintainer & )
delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddBacktrackingLevel()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::AddBacktrackingLevel ( )

Adds a new backtracking level to specify the state that will be restored by BacktrackOneLevel(). See the example in the class comment.

Definition at line 352 of file bop_ls.cc.

◆ Assign()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::Assign ( absl::Span< const sat::Literal > literals)

Assigns all literals. That updates the assignment, the constraint values, and the infeasible constraints.

Note
the assignment of those literals can be reverted thanks to AddBacktrackingLevel() and BacktrackOneLevel().
a variable can't be assigned twice, even for the same literal.

Definition at line 331 of file bop_ls.cc.

◆ Assignment()

bool operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::Assignment ( VariableIndex var) const
inline

Returns the value of the var in the assignment. As the assignment is initialized with the reference solution, if the variable has not been assigned through Assign(), the returned value is the value of the variable in the reference solution.

Definition at line 359 of file bop_ls.h.

◆ BacktrackAll()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::BacktrackAll ( )

Definition at line 375 of file bop_ls.cc.

◆ BacktrackOneLevel()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::BacktrackOneLevel ( )

Backtracks internal structures to the previous level defined by AddBacktrackingLevel(). As a consequence the state will be exactly as before the previous call to AddBacktrackingLevel().

Note
backtracking the initial state has no effect.

Backtrack each literal of the last level.

Definition at line 357 of file bop_ls.cc.

◆ ConstraintIsFeasible()

bool operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::ConstraintIsFeasible ( ConstraintIndex constraint) const
inline

Returns true if the given constraint is currently feasible.

Definition at line 382 of file bop_ls.h.

◆ ConstraintLowerBound()

int64_t operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::ConstraintLowerBound ( ConstraintIndex constraint) const
inline

Returns the lower bound of the constraint.

Definition at line 365 of file bop_ls.h.

◆ ConstraintUpperBound()

int64_t operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::ConstraintUpperBound ( ConstraintIndex constraint) const
inline

Returns the upper bound of the constraint.

Definition at line 370 of file bop_ls.h.

◆ ConstraintValue()

int64_t operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::ConstraintValue ( ConstraintIndex constraint) const
inline

Returns the value of the constraint. The value is computed using the variable values in the assignment. Note that a constraint is feasible iff its value is between its two bounds (inclusive).

Definition at line 377 of file bop_ls.h.

◆ DebugString()

std::string operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::DebugString ( ) const
Todo
(user): show the backtrack levels.

Definition at line 414 of file bop_ls.cc.

◆ IsFeasible()

bool operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::IsFeasible ( ) const
inline

Returns true if there is no infeasible constraint in the current state.

Definition at line 337 of file bop_ls.h.

◆ NumConstraints()

size_t operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::NumConstraints ( ) const
inline

Returns the number of constraints of the problem, objective included, i.e. the number of constraint in the problem + 1.

Definition at line 353 of file bop_ls.h.

◆ NumInfeasibleConstraints()

int operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::NumInfeasibleConstraints ( ) const
inline

Returns the exact number of infeasible constraints.

Note
PossiblyInfeasibleConstraints() will potentially return a larger number of constraints.

Definition at line 342 of file bop_ls.h.

◆ operator=()

AssignmentAndConstraintFeasibilityMaintainer & operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::operator= ( const AssignmentAndConstraintFeasibilityMaintainer & )
delete

◆ PossiblyInfeasibleConstraints()

const std::vector< ConstraintIndex > & operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::PossiblyInfeasibleConstraints ( ) const
inline

Returns a superset of all the infeasible constraints in the current state.

Definition at line 347 of file bop_ls.h.

◆ PotentialOneFlipRepairs()

const std::vector< sat::Literal > & operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::PotentialOneFlipRepairs ( )

This returns the list of literal that appear in exactly all the current infeasible constraints (ignoring the objective) and correspond to a flip in a good direction for all the infeasible constraint. Performing this flip may repair the problem without any propagations.

Important: The returned reference is only valid until the next PotentialOneFlipRepairs() call.

First, we compute the hash that a Literal should have in order to repair all the infeasible constraint (ignoring the objective).

Todo
(user): If this starts to show-up in a performance profile, we can easily maintain this hash incrementally.

We only returns the flips.

Definition at line 380 of file bop_ls.cc.

◆ reference()

const BopSolution & operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::reference ( ) const
inline

Returns the current assignment.

Definition at line 362 of file bop_ls.h.

◆ SetReferenceSolution()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::SetReferenceSolution ( const BopSolution & reference_solution)

Sets a new reference solution and reverts all internal structures to their initial state. Note that the reference solution has to be feasible.

Recompute the value of all constraints.

Definition at line 278 of file bop_ls.cc.

◆ UseCurrentStateAsReference()

void operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::UseCurrentStateAsReference ( )

Behaves exactly like SetReferenceSolution() where the passed reference is the current assignment held by this class. Note that the current assignment must be feasible (i.e. IsFeasible() is true).

Definition at line 302 of file bop_ls.cc.

Member Data Documentation

◆ kObjectiveConstraint

const ConstraintIndex operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer::kObjectiveConstraint
static

When we construct the problem, we treat the objective as one constraint. This is the index of this special "objective" constraint.

Definition at line 297 of file bop_ls.h.

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