Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | Static Public Attributes | List of all members
operations_research::bop::AssignmentAndConstraintFeasibilityMaintainer Class Reference

#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
 

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 283 of file bop_ls.h.

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() [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 360 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 383 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 366 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 371 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 378 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 338 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 354 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 343 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 348 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 363 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 298 of file bop_ls.h.

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