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().