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 454 of file bop_ls.h.
- 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
Fill the by_constraint_matrix_.
IMPORTANT: The order of the constraint needs to exactly match the one of the constraint in the AssignmentAndConstraintFeasibilityMaintainer.
Add the objective constraint as the first constraint.
Add the non-binary problem constraints.
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.
Definition at line 474 of file bop_ls.cc.
| 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.
1.14.0