Detailed Description

Copyright 2025 Francesco Cavaliere Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

MULTIPLIERS BASED GREEDY ///////////////////////

THREE PHASE ALGORITHM ////////////////////////

OUTER REFINEMENT PROCEDURE //////////////////////

FULL TO CORE PRICING /////////////////////////

Classes
class	BoundCBs
class	CoreModel
class	DualState
class	FullToCoreModel
class	HeuristicCBs
struct	PrimalDualState
	Utility aggregate to store and pass around both primal and dual states. More...
class	Solution
class	SubgradientCBs
struct	SubgradientContext
class	SubModelView

Typedefs
using	Model = SetCoverModel
using	SubModel = CoreModel

Functions
void	SubgradientOptimization (SubModel &model, SubgradientCBs &cbs, PrimalDualState &best_state)
Solution	RunMultiplierBasedGreedy (const SubModel &model, const DualState &dual_state, Cost cost_cutoff)
Cost	CoverGreedly (const SubModel &model, const DualState &dual_state, Cost cost_cutoff, BaseInt stop_size, std::vector< SubsetIndex > &sol_subsets)
PrimalDualState	RunThreePhase (SubModel &model, const Solution &init_solution)
PrimalDualState	RunCftHeuristic (SubModel &model, const Solution &init_solution)
Cost	DivideIfGE0 (Cost numerator, Cost denominator)
template<typename SubModelT>
bool	ValidateSubModel (const SubModelT &model)

Variables
static constexpr BaseInt	kMinCov = 5
	Coverage counter to decide the number of columns to keep in the core model.

Typedef Documentation

◆ Model

using operations_research::scp::Model = SetCoverModel

Todo: (anyone): since we are working within the scp namespace, the "SetCover*" prefix became redundant and can be removed. For now, only redefine it locally.

Definition at line 24 of file set_cover_submodel.h.

◆ SubModel

using operations_research::scp::SubModel = CoreModel

Definition at line 69 of file set_cover_submodel.h.

Function Documentation

◆ CoverGreedly()

Cost operations_research::scp::CoverGreedly	(	const SubModel &	model,
		const DualState &	dual_state,
		Cost	cost_cutoff,
		BaseInt	size_cutoff,
		std::vector< SubsetIndex > &	sol_subsets )

Lower level greedy function which creates or completes a "solution" (seen as set of subsets of the current SubModel) until a cutoff size or cost is reached.

Note: since the cutoff might be reached, the returned solution might not be feasible.

Solution already has required size -> early exit

Process input solution (if not empty)

Initialize column scores taking into account rows already covered

Fill up partial solution

Either remove redundant columns or discard solution

Definition at line 623 of file set_cover_cft.cc.

◆ DivideIfGE0()

Cost operations_research::scp::DivideIfGE0	(	Cost	numerator,
		Cost	denominator )

inline

In the narrow scope of the CFT subgradient, there are often divisions between non-negative quantities (e.g., to compute a relative gap). In these specific cases, the denominator should always be greater than the numerator. This function checks that.

Definition at line 113 of file set_cover_cft.h.

◆ RunCftHeuristic()

PrimalDualState operations_research::scp::RunCftHeuristic	(	SubModel &	model,
		const Solution &	init_solution = {} )

OUTER REFINEMENT PROCEDURE //////////////////////

Definition at line 911 of file set_cover_cft.cc.

◆ RunMultiplierBasedGreedy()

Solution operations_research::scp::RunMultiplierBasedGreedy	(	const SubModel &	model,
		const DualState &	dual_state,
		Cost	cost_cutoff = std::numeric_limits< BaseInt >::max() )

MULTIPLIERS BASED GREEDY /////////////////////// Higher level function that return a function obtained by the dual multiplier based greedy.

Definition at line 614 of file set_cover_cft.cc.

◆ RunThreePhase()

PrimalDualState operations_research::scp::RunThreePhase	(	SubModel &	model,
		const Solution &	init_solution )

Phase 1: refine the current dual_state and model

Phase 2: search for good solutions

Phase 3: Fix the best columns (diving)

Definition at line 785 of file set_cover_cft.cc.

◆ SubgradientOptimization()

void operations_research::scp::SubgradientOptimization	(	SubModel &	core_model,
		SubgradientCBs &	cbs,
		PrimalDualState &	best_state )

Subgradient optimization procedure. Optimizes the Lagrangian relaxation of the Set-Covering problem until a termination criterion si met.

Poor multipliers can lead to wasted iterations or stagnation in the subgradient method. To address this, we adjust the multipliers to get closer the trivial lower bound (= 0).

Compute subgradient (O(nnz))

Definition at line 284 of file set_cover_cft.cc.

◆ ValidateSubModel()

template<typename SubModelT>

bool operations_research::scp::ValidateSubModel ( const SubModelT & model )

Definition at line 273 of file set_cover_submodel.h.

Variable Documentation

◆ kMinCov

BaseInt operations_research::scp::kMinCov = 5

staticconstexpr

Coverage counter to decide the number of columns to keep in the core model.