operations_research::scp::Solution Class Reference

Detailed Description

Implementation of: 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

Hereafter referred to as CFT.

SUMMARY The CFT algorithm is a heuristic approach to the set-covering problem. At its core, it combines a primal greedy heuristic with dual information obtained from the optimization of the Lagrangian relaxation of the problem. (Note: columns/subsets and rows/elements will be used interchangeably.)

STRUCTURE The core of the algorithm is the 3Phase:

1. Subgradient optimization of the Lagrangian relaxation.
2. A primal greedy heuristic guided by the dual information.
3. Fixing some of the "best" columns (in terms of reduced costs) into the solution (diving).

• Repeat until an exit criterion is met.

The paper also considers an optional outer loop, which invokes the 3Phase process and then fixes some columns from the current best solution. This introduces two levels of diving: the outer loop fixes "primal-good" columns (based on the best solution), while the inner loop fixes "dual-good" columns (based on reduced costs).

Note

The outer loop is not implemented in this version (yet - April 2025).

Key characteristics of the algorithm:

• The CFT algorithm is tailored for instances where the number of columns is significantly larger than the number of rows.
• To improve efficiency, a core model approach is used. This involves selecting a small subset of columns based on their reduced costs, thereby substantially reducing the problem size handled in the internal steps.
• Due to the use of the core model and column fixing, the algorithm rarely considers the entire problem. Instead, it operates on a small "window" of the problem. Efficiently managing this small window is a central aspect of any CFT implementation.
• The core model scheme also enables an alternative implementation where the algorithm starts with a small model and progressively adds columns through a column-generation procedure. While this column generation procedure is problem-dependent and cannot be implemented here, the architecture of this implementation is designed to be extensible, allowing for such a procedure to be added in the future. COMMON DEFINITIONS ////////////////////////// Small class to store the solution of a sub-model. It contains the cost and the subset list.

Definition at line 87 of file set_cover_cft.h.

#include <set_cover_cft.h>

Public Member Functions
	Solution ()=default
	Solution (const SubModel &model, const std::vector< SubsetIndex > &core_subsets)
double	cost () const
const std::vector< FullSubsetIndex > &	subsets () const
void	AddSubset (FullSubsetIndex subset, Cost cost)
bool	Empty () const
void	Clear ()

Constructor & Destructor Documentation

Solution() [1/2]

operations_research::scp::Solution::Solution ( )

default

Solution() [2/2]

operations_research::scp::Solution::Solution	(	const SubModel &	model,
		const std::vector< SubsetIndex > &	core_subsets )

Definition at line 124 of file set_cover_cft.cc.

Member Function Documentation

AddSubset()

void operations_research::scp::Solution::AddSubset ( FullSubsetIndex subset, Cost cost )

inline

Definition at line 94 of file set_cover_cft.h.

Clear()

void operations_research::scp::Solution::Clear ( )

inline

Definition at line 99 of file set_cover_cft.h.

cost()

double operations_research::scp::Solution::cost ( ) const

inline

Definition at line 92 of file set_cover_cft.h.

Empty()

bool operations_research::scp::Solution::Empty ( ) const

inline

Definition at line 98 of file set_cover_cft.h.

subsets()

const std::vector< FullSubsetIndex > & operations_research::scp::Solution::subsets ( ) const

inline

Definition at line 93 of file set_cover_cft.h.

---

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

• ortools/set_cover/set_cover_cft.h
• ortools/set_cover/set_cover_cft.cc