operations_research::bop::OneFlipConstraintRepairer Class Reference

#include <bop_ls.h>

Classes
struct	ConstraintTerm

Public Member Functions
	OneFlipConstraintRepairer (const sat::LinearBooleanProblem &problem, const AssignmentAndConstraintFeasibilityMaintainer &maintainer, const sat::VariablesAssignment &sat_assignment)
	OneFlipConstraintRepairer (const OneFlipConstraintRepairer &)=delete
	This type is neither copyable nor movable.
OneFlipConstraintRepairer &	operator= (const OneFlipConstraintRepairer &)=delete
ConstraintIndex	ConstraintToRepair () const
TermIndex	NextRepairingTerm (ConstraintIndex ct_index, TermIndex init_term_index, TermIndex start_term_index) const
bool	RepairIsValid (ConstraintIndex ct_index, TermIndex term_index) const
sat::Literal	GetFlip (ConstraintIndex ct_index, TermIndex term_index) const

Static Public Attributes
static const ConstraintIndex	kInvalidConstraint
static const TermIndex	kInitTerm
static const TermIndex	kInvalidTerm

Detailed Description

This class is an utility class used to select which infeasible constraint to repair and identify one variable to flip to actually repair the constraint. A constraint 'lb <= sum_i(w_i * x_i) <= ub', with 'lb' the lower bound, 'ub' the upper bound, 'w_i' the weight of the i-th term and 'x_i' the boolean variable appearing in the i-th term, is infeasible for a given assignment iff its value 'sum_i(w_i * x_i)' is outside of the bounds. Repairing-a-constraint-in-one-flip means making the constraint feasible by just flipping the value of one unassigned variable of the current assignment from the AssignmentAndConstraintFeasibilityMaintainer. For performance reasons, the pairs weight / variable (w_i, x_i) are stored in a sparse manner as a vector of terms (w_i, x_i). In the following the TermIndex term_index refers to the position of the term in the vector.

Definition at line 455 of file bop_ls.h.

Constructor & Destructor Documentation

OneFlipConstraintRepairer() [1/2]

operations_research::bop::OneFlipConstraintRepairer::OneFlipConstraintRepairer	(	const sat::LinearBooleanProblem &	problem,
		const AssignmentAndConstraintFeasibilityMaintainer &	maintainer,
		const sat::VariablesAssignment &	sat_assignment )

Note

the constraint indices used in this class follow the same convention as the one used in the AssignmentAndConstraintFeasibilityMaintainer.

Todo

(user): maybe merge the two classes? maintaining this implicit indices convention between the two classes sounds like a bad idea.

OneFlipConstraintRepairer() [2/2]

operations_research::bop::OneFlipConstraintRepairer::OneFlipConstraintRepairer ( const OneFlipConstraintRepairer & )

delete

This type is neither copyable nor movable.

Member Function Documentation

ConstraintToRepair()

ConstraintIndex operations_research::bop::OneFlipConstraintRepairer::ConstraintToRepair

(

)

const

Returns the index of a constraint to repair. This will always return the index of a constraint that can be repaired in one flip if there is one. Note however that if there is only one possible candidate, it will be returned without checking that it can indeed be repaired in one flip. This is because the later check can be expensive, and is not needed in our context.

Optimization: We inspect the constraints in reverse order because the objective one will always be first (in our current code) and with some luck, we will break early instead of fully exploring it.

Optimization: We return the only candidate without inspecting it. This is critical at the beginning of the search or later if the only candidate is the objective constraint which can be really long.

The constraint can't be repaired in one decision.

Definition at line 526 of file bop_ls.cc.

GetFlip()

sat::Literal operations_research::bop::OneFlipConstraintRepairer::GetFlip	(	ConstraintIndex	ct_index,
		TermIndex	term_index ) const

Returns the literal formed by the variable at the given constraint term and assigned to the opposite value of this variable in the current assignment.

Definition at line 626 of file bop_ls.cc.

NextRepairingTerm()

TermIndex operations_research::bop::OneFlipConstraintRepairer::NextRepairingTerm	(	ConstraintIndex	ct_index,
		TermIndex	init_term_index,
		TermIndex	start_term_index ) const

Returns the index of the next term which repairs the constraint when the value of its variable is flipped. This method explores terms with an index strictly greater than start_term_index and then terms with an index smaller than or equal to init_term_index if any. Returns kInvalidTerm when no reparing terms are found.

Note

if init_term_index == start_term_index, then all the terms will be explored. Both TermIndex arguments can take values in [-1, constraint size).

Definition at line 579 of file bop_ls.cc.

operator=()

OneFlipConstraintRepairer & operations_research::bop::OneFlipConstraintRepairer::operator= ( const OneFlipConstraintRepairer & )

delete

RepairIsValid()

bool operations_research::bop::OneFlipConstraintRepairer::RepairIsValid	(	ConstraintIndex	ct_index,
		TermIndex	term_index ) const

Returns true if the constraint is infeasible and if flipping the variable at the given index will repair it.

Definition at line 609 of file bop_ls.cc.

Member Data Documentation

kInitTerm

const TermIndex operations_research::bop::OneFlipConstraintRepairer::kInitTerm

static

Definition at line 474 of file bop_ls.h.

kInvalidConstraint

const ConstraintIndex operations_research::bop::OneFlipConstraintRepairer::kInvalidConstraint

static

Definition at line 473 of file bop_ls.h.

kInvalidTerm

const TermIndex operations_research::bop::OneFlipConstraintRepairer::kInvalidTerm

static

Definition at line 475 of file bop_ls.h.

---

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

• ortools/bop/bop_ls.h
• ortools/bop/bop_ls.cc