Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::SetCoverLagrangian Class Reference

Detailed Description

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>

Inheritance diagram for operations_research::SetCoverLagrangian:
operations_research::SubsetListBasedSolutionGenerator operations_research::SetCoverSolutionGenerator

Public Member Functions

 SetCoverLagrangian (SetCoverInvariant *inv)
 SetCoverLagrangian (SetCoverInvariant *inv, const absl::string_view name)
SetCoverLagrangianUseNumThreads (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, ElementCostVectorComputeLowerBound (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)
SetCoverInvariantinv () const
virtual SetCoverSolutionGeneratorResetLimits ()
 Resets the limits to their default values.
SetCoverSolutionGeneratorSetMaxIterations (int64_t max_iterations)
 Sets the maximum number of iterations.
int64_t max_iterations () const
 Returns the maximum number of iterations.
SetCoverSolutionGeneratorSetTimeLimitInSeconds (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
SetCoverModelmodel () 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.

Constructor & Destructor Documentation

◆ SetCoverLagrangian() [1/2]

operations_research::SetCoverLagrangian::SetCoverLagrangian ( SetCoverInvariant * inv)
inlineexplicit

Definition at line 52 of file set_cover_lagrangian.h.

◆ SetCoverLagrangian() [2/2]

operations_research::SetCoverLagrangian::SetCoverLagrangian ( SetCoverInvariant * inv,
const absl::string_view name )
inline

Definition at line 55 of file set_cover_lagrangian.h.

Member Function Documentation

◆ ComputeGap()

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.

Todo
(user): Parallelize this, if need be.

gap += std::abs(reduced_costs[subset]); We know the sign of rhs.

Definition at line 353 of file set_cover_lagrangian.cc.

◆ ComputeLagrangianValue()

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

  • if c_j(u) < 0: x_j(u) = 1,
  • if c_j(u) > 0: x_j(u) = 0, (**)
  • if c_j(u) = 0: x_j(u) is unbound, in {0, 1}, we use 0. For a general Integer Program A x <= b, the Lagrangian vector L(u) [2] is L(u) = min \sum_{j \in N} c_j(u) x_j + \sum{i \in M} b_i.u_i.

This is \sum{i \in M} u_i.

Definition at line 245 of file set_cover_lagrangian.cc.

◆ ComputeLowerBound()

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.

◆ ComputeReducedCosts()

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.

◆ ComputeSubgradient()

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.

◆ InitializeLagrangeMultipliers()

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]:

  • the 3-phase algorithm in the paper actually uses pricing (which would better be called "partial" pricing),
  • the columns that were used in the preceding solutions should be fixed, because otherwise it diversifies too much and degrades the best solution (under "queue" in the paper).
  • the median algorithm is already in the STL (nth_element). Denoted as u in [1], it is a dual vector: a column vector of nonnegative (zero is included) multipliers for the different constraints. A deterministic way to compute a feasible (non-optimal) u: For all element indices i, u_i = min {j \in J_i} c_j / I_j, where I_j denotes the number of elements covered by subset j.

Concerning the fundamental ideas behind this approach, one may refer to [2].

Todo
(user): Parallelize this.
Todo
(user): Parallelize this.

Minimum marginal cost to cover this element.

Todo
(user): use std::min_element on rows[element] with a custom comparator that gets marginal_costs[subset]. Check performance.

Definition at line 48 of file set_cover_lagrangian.cc.

◆ NextSolution() [1/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( )
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.

◆ NextSolution() [2/3]

bool operations_research::SetCoverLagrangian::NextSolution ( absl::Span< const SubsetIndex > _)
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.

◆ NextSolution() [3/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus)
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.

◆ ParallelComputeLagrangianValue()

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.

◆ ParallelComputeReducedCosts()

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.

Todo
(user): compute a close-to-optimal k-subset partitioning of the columns based on their sizes. [***]

Definition at line 109 of file set_cover_lagrangian.cc.

◆ ParallelComputeSubgradient()

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.

Todo
(user): it may be better to split the elements among the threads, although this might be less well-balanced.

Definition at line 181 of file set_cover_lagrangian.cc.

◆ ParallelUpdateMultipliers()

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.

◆ ThreePhase()

void operations_research::SetCoverLagrangian::ThreePhase ( Cost upper_bound)

Performs the three-phase algorithm.

◆ UpdateMultipliers()

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.

◆ UseNumThreads()

SetCoverLagrangian & operations_research::SetCoverLagrangian::UseNumThreads ( int num_threads)
inline

Definition at line 62 of file set_cover_lagrangian.h.


The documentation for this class was generated from the following files: