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:

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.

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:

ortools/set_cover/set_cover_lagrangian.h
ortools/set_cover/set_cover_lagrangian.cc

Detailed Description

Public Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ SetCoverLagrangian() [1/2]

◆ SetCoverLagrangian() [2/2]

Member Function Documentation

◆ ComputeGap()

◆ ComputeLagrangianValue()

◆ ComputeLowerBound()

◆ ComputeReducedCosts()

◆ ComputeSubgradient()

◆ InitializeLagrangeMultipliers()

◆ NextSolution() [1/3]

◆ NextSolution() [2/3]

◆ NextSolution() [3/3]

◆ ParallelComputeLagrangianValue()

◆ ParallelComputeReducedCosts()

◆ ParallelComputeSubgradient()

◆ ParallelUpdateMultipliers()

◆ ThreePhase()

◆ UpdateMultipliers()

◆ UseNumThreads()