![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
The SetCoverLagrangian class implements the Lagrangian relaxation of the set cover problem. In the following, we refer to the following articles: [1] Caprara, Alberto, Matteo Fischetti, and Paolo Toth. 1999. “A Heuristic Method for the Set Covering Problem.” Operations Research 47 (5): 730–43. https://www.jstor.org/stable/223097 [2] Fisher, Marshall L. 1981. “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science 27 (1): 1–18. https://www.jstor.org/stable/2631139 [3] Held, M., Karp, R.M. The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming 1, 6–25 (1971). https://link.springer.com/article/10.1007/BF01584070 [4] Williamson, David P. 2002. “The Primal-Dual Method for Approximation Algorithms.” Mathematical Programming, 91 (3): 447–78. https://link.springer.com/article/10.1007/s101070100262 The implementation benefits from the features of SetCoverSolutionGenerator. Notice however that NextSolution() is not implemented, and the class is intended to be used only for ComputeLowerBound(). FOR THE TIME BEING.
Definition at line 50 of file set_cover_lagrangian.h.
#include <set_cover_lagrangian.h>
Public Member Functions | |
SetCoverLagrangian (SetCoverInvariant *inv) | |
SetCoverLagrangian (SetCoverInvariant *inv, const absl::string_view name) | |
SetCoverLagrangian & | UseNumThreads (int num_threads) |
bool | NextSolution (absl::Span< const SubsetIndex > _) final |
This is a dummy implementation of NextSolution() that is not used. | |
ElementCostVector | InitializeLagrangeMultipliers () const |
Initializes the multipliers vector (u) based on the cost per subset. | |
SubsetCostVector | ComputeReducedCosts (const SubsetCostVector &costs, const ElementCostVector &multipliers) const |
SubsetCostVector | ParallelComputeReducedCosts (const SubsetCostVector &costs, const ElementCostVector &multipliers) const |
Computes the reduced costs for all subsets in parallel using ThreadPool. | |
ElementCostVector | ComputeSubgradient (const SubsetCostVector &reduced_costs) const |
ElementCostVector | ParallelComputeSubgradient (const SubsetCostVector &reduced_costs) const |
Cost | ComputeLagrangianValue (const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const |
Cost | ParallelComputeLagrangianValue (const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const |
void | UpdateMultipliers (double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const |
void | ParallelUpdateMultipliers (double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const |
Cost | ComputeGap (const SubsetCostVector &reduced_costs, const SubsetBoolVector &solution, const ElementCostVector &multipliers) const |
void | ThreePhase (Cost upper_bound) |
Performs the three-phase algorithm. | |
std::tuple< Cost, SubsetCostVector, ElementCostVector > | ComputeLowerBound (const SubsetCostVector &costs, Cost upper_bound) |
Computes a lower bound on the optimal cost. | |
bool | NextSolution () final |
Virtual methods that must be implemented by derived classes. | |
bool | NextSolution (const SubsetBoolVector &in_focus) final |
Same as above, but with a vector of Booleans as focus. | |
Public Member Functions inherited from operations_research::SubsetListBasedSolutionGenerator | |
SubsetListBasedSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name) | |
bool | NextSolution (absl::Span< const SubsetIndex > _) override |
bool | NextSolution () final |
Virtual methods that must be implemented by derived classes. | |
bool | NextSolution (const SubsetBoolVector &in_focus) final |
Same as above, but with a vector of Booleans as focus. | |
Public Member Functions inherited from operations_research::SetCoverSolutionGenerator | |
SetCoverSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name) | |
virtual | ~SetCoverSolutionGenerator ()=default |
void | SetName (const absl::string_view name) |
SetCoverInvariant * | inv () const |
virtual SetCoverSolutionGenerator & | ResetLimits () |
Resets the limits to their default values. | |
SetCoverSolutionGenerator & | SetMaxIterations (int64_t max_iterations) |
Sets the maximum number of iterations. | |
int64_t | max_iterations () const |
Returns the maximum number of iterations. | |
SetCoverSolutionGenerator & | SetTimeLimitInSeconds (double seconds) |
Sets the time limit in seconds. | |
absl::Duration | run_time () const |
double | run_time_in_seconds () const |
Returns the total elapsed runtime in seconds. | |
double | run_time_in_microseconds () const |
Returns the total elapsed runtime in microseconds. | |
std::string | name () const |
Returns the name of the heuristic. | |
std::string | class_name () const |
Returns the name of the class. | |
Cost | cost () const |
Returns the current cost of the solution in the invariant. | |
bool | CheckInvariantConsistency () const |
Additional Inherited Members | |
Protected Member Functions inherited from operations_research::SetCoverSolutionGenerator | |
SetCoverModel * | model () const |
Accessors. | |
BaseInt | num_subsets () const |
double | time_limit_in_seconds () const |
The time limit in seconds. | |
Protected Attributes inherited from operations_research::SetCoverSolutionGenerator | |
absl::Duration | run_time_ |
run_time_ is an abstract duration for the time spent in NextSolution(). | |
SetCoverInvariant::ConsistencyLevel | consistency_level_ |
The consistency needed by the solution generator. |
|
inlineexplicit |
Definition at line 52 of file set_cover_lagrangian.h.
|
inline |
Definition at line 55 of file set_cover_lagrangian.h.
Cost operations_research::SetCoverLagrangian::ComputeGap | ( | const SubsetCostVector & | reduced_costs, |
const SubsetBoolVector & | solution, | ||
const ElementCostVector & | multipliers ) const |
Computes the gap between the current solution and the optimal solution. This is the sum of the multipliers for the elements that are not covered by the current solution.
gap += std::abs(reduced_costs[subset]); We know the sign of rhs.
Definition at line 353 of file set_cover_lagrangian.cc.
Cost operations_research::SetCoverLagrangian::ComputeLagrangianValue | ( | const SubsetCostVector & | reduced_costs, |
const ElementCostVector & | multipliers ) const |
Computes the value of the Lagrangian L(u). L(u) = min \sum_{j \in N} c_j(u) x_j + \sum{i \in M} u_i. If c_j(u) < 0: x_j(u) = 1, if c_j(u) > 0: x_j(u) = 0, otherwise x_j(u) is unbound, it can take any value in {0, 1}.
Compute the (scalar) value of the Lagrangian vector by fixing the value of x_j based on the sign of c_j(u). In [1] equation (4), it is: L(u) = min \sum_{j \in N} c_j(u) x_j + \sum{i \in M} u_i . This is obtained
This is \sum{i \in M} u_i.
Definition at line 245 of file set_cover_lagrangian.cc.
std::tuple< Cost, SubsetCostVector, ElementCostVector > operations_research::SetCoverLagrangian::ComputeLowerBound | ( | const SubsetCostVector & | costs, |
Cost | upper_bound ) |
Computes a lower bound on the optimal cost.
Computes a lower bound on the optimal cost. The returned value is the lower bound, the reduced costs, and the multipliers.
For the time being, 4 threads seems to be the fastest. Running linux perf of the process shows that up to 60% of the cycles are lost as idle cycles in the CPU backend, probably because the algorithm is memory bound.
step_size should be updated like this. For the time besing, we keep the step size, because the implementation of the rest is not adequate yet step_size = step_sizer.UpdateStepSize(iter, lagrangian_value); if (stopper.DecideWhetherToStop(iter, lower_bound)) { break; }
Definition at line 492 of file set_cover_lagrangian.cc.
SubsetCostVector operations_research::SetCoverLagrangian::ComputeReducedCosts | ( | const SubsetCostVector & | costs, |
const ElementCostVector & | multipliers ) const |
Computes the Lagrangian (row-)cost vector. For a subset j, c_j(u) = c_j - sum_{i \in I_j} u_i. I_j denotes the indices of elements present in subset j.
Reduced cost (row vector). Denoted as c_j(u) in [1], right after equation (5). For a subset j, c_j(u) = c_j - sum_{i \in I_j}.u_i. I_j is the set of indices for elements in subset j. For a general Integer Program A.x <= b, this would be: c_j(u) = c_j - sum_{i \in I_j} a_{ij}.u_i
Definition at line 139 of file set_cover_lagrangian.cc.
ElementCostVector operations_research::SetCoverLagrangian::ComputeSubgradient | ( | const SubsetCostVector & | reduced_costs | ) | const |
Computes the subgradient (column-)cost vector. For all element indices i, s_i(u) = 1 - sum_{j \in J_i} x_j(u), where J_i denotes the set of indices of subsets j covering element i.
Vector of primal slack variable. Denoted as s_i(u) in [1], equation (6). For all element indices i, s_i(u) = 1 - sum_{j \in J_i} x_j(u), where J_i denotes the set of indices of subsets j covering element i. For a general Integer Program A x <= b, the subgradient cost vector is defined as A x - b. See [2].
NOTE(user): Should the initialization be done with coverage[element]?
Definition at line 172 of file set_cover_lagrangian.cc.
ElementCostVector operations_research::SetCoverLagrangian::InitializeLagrangeMultipliers | ( | ) | const |
Initializes the multipliers vector (u) based on the cost per subset.
Notes from a discussion with Luca Accorsi (accorsi@) and Francesco Cavaliere regarding [1]:
Concerning the fundamental ideas behind this approach, one may refer to [2].
Minimum marginal cost to cover this element.
Definition at line 48 of file set_cover_lagrangian.cc.
|
inlinefinalvirtual |
Virtual methods that must be implemented by derived classes.
Computes the next full solution taking into account all the subsets.
Implements operations_research::SetCoverSolutionGenerator.
Definition at line 181 of file set_cover_heuristics.h.
|
inlinefinalvirtual |
This is a dummy implementation of NextSolution() that is not used.
Implements operations_research::SetCoverSolutionGenerator.
Definition at line 71 of file set_cover_lagrangian.h.
|
inlinefinalvirtual |
Same as above, but with a vector of Booleans as focus.
Implements operations_research::SetCoverSolutionGenerator.
Definition at line 183 of file set_cover_heuristics.h.
Cost operations_research::SetCoverLagrangian::ParallelComputeLagrangianValue | ( | const SubsetCostVector & | reduced_costs, |
const ElementCostVector & | multipliers ) const |
Same as above, but parallelized, using the number of threads specified in the constructor.
This is \sum{i \in M} u_i.
Definition at line 258 of file set_cover_lagrangian.cc.
SubsetCostVector operations_research::SetCoverLagrangian::ParallelComputeReducedCosts | ( | const SubsetCostVector & | costs, |
const ElementCostVector & | multipliers ) const |
Computes the reduced costs for all subsets in parallel using ThreadPool.
Same as above, but parallelized, using the number of threads specified in the constructor.
Definition at line 109 of file set_cover_lagrangian.cc.
ElementCostVector operations_research::SetCoverLagrangian::ParallelComputeSubgradient | ( | const SubsetCostVector & | reduced_costs | ) | const |
Same as above, but parallelized, using the number of threads specified in the constructor.
The subgradient has one component per element, each thread processes several subsets. Hence, have one vector per thread to avoid data races.
Definition at line 181 of file set_cover_lagrangian.cc.
void operations_research::SetCoverLagrangian::ParallelUpdateMultipliers | ( | double | step_size, |
Cost | lagrangian_value, | ||
Cost | upper_bound, | ||
const SubsetCostVector & | reduced_costs, | ||
ElementCostVector * | multipliers ) const |
Same as above, but parallelized, using the number of threads specified in the constructor.
step_size is \lambda_k in [1].
Compute the square of the Euclidean norm of the subgradient vector.
First compute lambda_k * (UB - L(u^k)).
Avoid multipliers to go negative and to go through the roof. 1e6 chosen
Definition at line 329 of file set_cover_lagrangian.cc.
void operations_research::SetCoverLagrangian::ThreePhase | ( | Cost | upper_bound | ) |
Performs the three-phase algorithm.
void operations_research::SetCoverLagrangian::UpdateMultipliers | ( | double | step_size, |
Cost | lagrangian_value, | ||
Cost | upper_bound, | ||
const SubsetCostVector & | reduced_costs, | ||
ElementCostVector * | multipliers ) const |
Updates the multipliers vector (u) with the given step size. Following [3], each of the coordinates is defined as: u^{k+1}_i = max(u^k_i + lambda_k * (UB - L(u^k)) / |s^k(u)|^2 * s^k_i(u), 0). lambda_k is step_size in the function signature below. UB is upper_bound.
Perform a subgradient step. In the general case, for an Integer Program A.x <=b, the Lagragian multipliers vector at step k+1 is defined as: u^{k+1} = u^k + t_k (A x^k - b) with term t_k = lambda_k * (UB - L(u^k)) / |A x^k - b|^2. |.| is the 2-norm (i.e. Euclidean) In our case, the problem A x <= b is in the form A x >= 1. We need to replace A x - b by s_i(u) = 1 - sum_{j \in J_i} x_j(u). |A x^k - b|^2 = |s(u)|^2, and t_k is of the form: t_k = lambda_k * (UB - L(u^k)) / |s^k(u)|^2. Now, the coordinates of the multipliers vectors u^k, u^k_i are nonnegative, i.e. u^k_i >= 0. Negative values are simply cut off. Following [3], each of the coordinates is defined as: u^{k+1}_i = max(u^k_i + lambda_k * (UB - L(u^k)) / |s^k(u)|^2 * s^k_i(u), 0). This is eq. (7) in [1].
step_size is \lambda_k in [1].
Compute the square of the Euclidean norm of the subgradient vector.
First compute lambda_k * (UB - L(u^k)).
Avoid multipliers to go negative and to go over the roof. 1e6 chosen arbitrarily. [***]
Definition at line 306 of file set_cover_lagrangian.cc.
|
inline |
Definition at line 62 of file set_cover_lagrangian.h.