Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class CoverCutHelper
Note: This documentation is automatically generated.
Helper to find knapsack cover cuts.
| Method |
alt_cut | Return type: const LinearConstraint& |
cut | Return type: const LinearConstraint& |
GenerateLetchfordSouliLifting | Return type: void Arguments:
IntegerValue base_rhs, const LinearConstraint base_ct,
const std::vector<IntegerValue>& lower_bounds,
const std::vector<IntegerValue>& upper_bounds,
const std::vector<bool>& in_cover Visible for testing.
Applies the lifting procedure described in "On Lifted Cover Inequalities: A
New Lifting Procedure with Unusual Properties", Adam N. Letchford, Georgia
Souli.
The algo is pretty simple, given a cover C for a given rhs. We compute
a rational weight p/q so that sum_C min(w_i, p/q) = rhs. Note that q is
pretty small (lower or equal to the size of C). The generated cut is then
of the form
sum X_i in C for which w_i <= p / q
+ sum gamma_i X_i for the other variable <= |C| - 1.
gamma_i being the smallest k such that w_i <= sum of the k + 1 largest
min(w_i, p/q) for i in C. In particular, it is zero if w_i <= p/q.
Note that this accept a general constraint that has been canonicalized to
sum coeff_i * X_i <= base_rhs. Each coeff_i >= 0 and each X_i >= 0.
|
Info | Return type: const std::string Single line of text that we append to the cut log line.
|
mutable_alt_cut | Return type: LinearConstraint* Provides an alternative cut with a different lifting procedure.
This one use
|
mutable_cut | Return type: LinearConstraint* If successful, info about the last generated cut.
|
TrySimpleKnapsack | Return type: bool Arguments: const LinearConstraint base_ct,
const std::vector<double>& lp_values,
const std::vector<IntegerValue>& lower_bounds,
const std::vector<IntegerValue>& upper_bounds Try to find a cut with a knapsack heuristic.
If this returns true, you can get the cut via cut().
|
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 \u003ccode\u003eCoverCutHelper\u003c/code\u003e class in C++ assists in identifying knapsack cover cuts within optimization problems.\u003c/p\u003e\n"],["\u003cp\u003eIt offers methods to generate and access these cuts, including an alternative cut generation method.\u003c/p\u003e\n"],["\u003cp\u003eA specialized lifting procedure based on Letchford and Souli's work can be applied to enhance the cuts.\u003c/p\u003e\n"],["\u003cp\u003eA simple knapsack heuristic is available to potentially discover cuts more efficiently.\u003c/p\u003e\n"],["\u003cp\u003eInformation about the generated cuts can be retrieved for analysis or logging purposes.\u003c/p\u003e\n"]]],["The `CoverCutHelper` class aids in finding knapsack cover cuts. Key actions include `TrySimpleKnapsack` to find a cut using heuristics, and `cut` or `alt_cut` to retrieve the generated `LinearConstraint`. `GenerateLetchfordSouliLifting` applies a specific lifting procedure to create a cut. The `Info` method provides a text log, while `mutable_cut` and `mutable_alt_cut` return modifiable cut objects. The procedure implemented in `GenerateLetchfordSouliLifting` create a new cut based on the variable weights.\n"],null,[]]
