#include <set_cover_lagrangian.h>

Public Member Functions
	SetCoverLagrangian (SetCoverInvariant *inv, int num_threads=1)

bool	NextSolution ()

bool	NextSolution (const std::vector< SubsetIndex > &focus)

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.

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

Definition at line 44 of file set_cover_lagrangian.h.

Constructor & Destructor Documentation

◆ SetCoverLagrangian()

operations_research::SetCoverLagrangian::SetCoverLagrangian	(	SetCoverInvariant *	inv,
		int	num_threads = 1 )

inlineexplicit

Definition at line 46 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 352 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 491 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 46 of file set_cover_lagrangian.cc.

◆ NextSolution() [1/2]

bool operations_research::SetCoverLagrangian::NextSolution ( )

Returns true if a solution was found.

Todo: (user): Add time-outs and exit with a partial solution. This seems unlikely, though.

◆ NextSolution() [2/2]

bool operations_research::SetCoverLagrangian::NextSolution ( const std::vector< SubsetIndex > & focus )

Computes the next partial solution considering only the subsets whose indices are in focus.

◆ 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.

Todo: (user): check how costly it is to create a new ThreadPool.

Todo

Todo: (user): use a queue of subsets to process? instead of a fixed range.

This parallelization is not very efficient, because all the threads use the same costs vector. Maybe it should be local to the thread. It's unclear whether sharing columns and costs is better than having each thread use its own partial copy. Finally, it might be better to use a queue of subsets to process, instead of a fixed range.

Definition at line 102 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 arbitrarily. [***]

Definition at line 328 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 305 of file set_cover_lagrangian.cc.

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

ortools/algorithms/set_cover_lagrangian.h
ortools/algorithms/set_cover_lagrangian.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SetCoverLagrangian()

Member Function Documentation

◆ ComputeGap()

◆ ComputeLagrangianValue()

◆ ComputeLowerBound()

◆ ComputeReducedCosts()

◆ ComputeSubgradient()

◆ InitializeLagrangeMultipliers()

◆ NextSolution() [1/2]

◆ NextSolution() [2/2]

◆ ParallelComputeLagrangianValue()

◆ ParallelComputeReducedCosts()

◆ ParallelComputeSubgradient()

◆ ParallelUpdateMultipliers()

◆ ThreePhase()

◆ UpdateMultipliers()