Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class ImpliedBoundsProcessor
Note: This documentation is automatically generated.
Given an upper-bounded linear relation (sum terms <= ub), this algorithm
inspects the integer variable appearing in the sum and try to replace each of
them by a tight lower bound (>= coeff * binary + lb) using the implied bound
repository. By tight, we mean that it will take the same value under the
current LP solution.
We use a class to reuse memory of the tmp terms.
| Method |
AddLpVariable | Return type: void Arguments: IntegerVariable var Add a new variable that could be used in the new cuts.
Note that the cache must be computed to take this into account.
|
DebugSlack | Return type: bool Arguments: IntegerVariable first_slack,
const LinearConstraint& initial_cut,
const LinearConstraint& cut,
const std::vector<SlackInfo>& info Only used for debugging.
Substituting back the slack created by the function above should give
exactly the same cut as the original one.
|
GetCachedImpliedBoundInfo | Return type: BestImpliedBoundInfo Arguments: IntegerVariable var |
IbCutPool | Return type: TopNCuts& As we compute the best implied bounds for each variable, we add violated
cuts here.
|
ImpliedBoundsProcessor | Arguments: absl::Span<const IntegerVariable> lp_vars_,
IntegerTrail* integer_trail,
ImpliedBounds* implied_bounds We will only replace IntegerVariable appearing in lp_vars_.
|
ProcessUpperBoundedConstraint | Return type: void Arguments:
const absl::StrongVector<IntegerVariable, double>& lp_values,
LinearConstraint* cut Processes and updates the given cut.
|
ProcessUpperBoundedConstraintWithSlackCreation | Return type: void Arguments:
bool substitute_only_inner_variables, IntegerVariable first_slack,
const absl::StrongVector<IntegerVariable, double>& lp_values,
LinearConstraint* cut, std::vector<SlackInfo>* slack_infos |
RecomputeCacheAndSeparateSomeImpliedBoundCuts | Return type: void Arguments:
const absl::StrongVector<IntegerVariable, double>& lp_values See if some of the implied bounds equation are violated and add them to
the IB cut pool if it is the case.
Important: This must be called before we process any constraints with a
different lp_values or level zero bounds.
|
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe ImpliedBoundsProcessor aims to strengthen linear constraints (sum terms <= ub) by substituting integer variables with tighter lower bounds derived from implied bounds.\u003c/p\u003e\n"],["\u003cp\u003eIt leverages an implied bound repository to find the best lower bound for each integer variable, ensuring the substitution maintains the same value in the current LP solution.\u003c/p\u003e\n"],["\u003cp\u003eThe processor utilizes a caching mechanism to store and reuse intermediate computations for efficiency.\u003c/p\u003e\n"],["\u003cp\u003eThe \u003ccode\u003eProcessUpperBoundedConstraint\u003c/code\u003e and \u003ccode\u003eProcessUpperBoundedConstraintWithSlackCreation\u003c/code\u003e methods apply the substitution process to given constraints, potentially generating new cuts added to an IB cut pool.\u003c/p\u003e\n"],["\u003cp\u003eBefore processing constraints with different LP values or level zero bounds, \u003ccode\u003eRecomputeCacheAndSeparateSomeImpliedBoundCuts\u003c/code\u003e should be called to refresh the cache and identify violated implied bound equations.\u003c/p\u003e\n"]]],["The `ImpliedBoundsProcessor` class processes upper-bounded linear relations by replacing integer variables with tighter lower bounds. Key actions include: adding variables (`AddLpVariable`), processing and updating constraints (`ProcessUpperBoundedConstraint`, `ProcessUpperBoundedConstraintWithSlackCreation`), and checking for violations of implied bounds (`RecomputeCacheAndSeparateSomeImpliedBoundCuts`). It uses cached information about implied bounds (`GetCachedImpliedBoundInfo`) and stores violated cuts in a pool (`IbCutPool`). Debugging is supported with `DebugSlack`. The processor is initialized with the `lp_vars`, `integer_trail`, and `implied_bounds` in the constructor.\n"],null,["# ImpliedBoundsProcessor\n\nC++ Reference: class ImpliedBoundsProcessor\n===========================================\n\n\nNote: This documentation is automatically generated.\n\nGiven an upper-bounded linear relation (sum terms \\\u003c= ub), this algorithm inspects the integer variable appearing in the sum and try to replace each of them by a tight lower bound (\\\u003e= coeff \\* binary + lb) using the implied bound repository. By tight, we mean that it will take the same value under the current LP solution. \n\nWe use a class to reuse memory of the tmp terms.\n\n| Method ||\n|--------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddLpVariable`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L119) | Return type: `void ` Arguments: `IntegerVariable var` Add a new variable that could be used in the new cuts. Note that the cache must be computed to take this into account. |\n| [`DebugSlack`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L112) | Return type: `bool ` Arguments: `IntegerVariable first_slack, const LinearConstraint& initial_cut, const LinearConstraint& cut, const std::vector\u003cSlackInfo\u003e& info` Only used for debugging. Substituting back the slack created by the function above should give exactly the same cut as the original one. |\n| [`GetCachedImpliedBoundInfo`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L130) | Return type: `BestImpliedBoundInfo ` Arguments: `IntegerVariable var` \u003cbr /\u003e |\n| [`IbCutPool`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L134) | Return type: `TopNCuts& ` As we compute the best implied bounds for each variable, we add violated cuts here. |\n| [`ImpliedBoundsProcessor`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L66) | \u003cbr /\u003e Arguments: `absl::Span\u003cconst IntegerVariable\u003e lp_vars_, IntegerTrail* integer_trail, ImpliedBounds* implied_bounds` We will only replace IntegerVariable appearing in lp_vars_. |\n| [`ProcessUpperBoundedConstraint`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L82) | Return type: `void ` Arguments: ` const absl::StrongVector\u003cIntegerVariable, double\u003e& lp_values, LinearConstraint* cut` Processes and updates the given cut. |\n| [`ProcessUpperBoundedConstraintWithSlackCreation`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L103) | Return type: `void ` Arguments: ` bool substitute_only_inner_variables, IntegerVariable first_slack, const absl::StrongVector\u003cIntegerVariable, double\u003e& lp_values, LinearConstraint* cut, std::vector\u003cSlackInfo\u003e* slack_infos` \u003cbr /\u003e |\n| [`RecomputeCacheAndSeparateSomeImpliedBoundCuts`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/cuts.h#L78) | Return type: `void ` Arguments: ` const absl::StrongVector\u003cIntegerVariable, double\u003e& lp_values` See if some of the implied bounds equation are violated and add them to the IB cut pool if it is the case. Important: This must be called before we process any constraints with a different lp_values or level zero bounds. |"]]
