#include <set_cover_heuristics.h>

Public Member Functions
	Preprocessor (absl::Nonnull< SetCoverInvariant * > inv)

bool	NextSolution ()
	Preprocessor.

bool	NextSolution (absl::Span< const SubsetIndex > focus)

int	num_columns_fixed_by_singleton_row () const
	Returns the number of columns that are the only one for a given row.

Detailed Description

Solver classes for the weighted set covering problem.

The solution procedure is based on the general scheme known as local search. Once a solution exists, it is improved by modifying it slightly, for example by flipping a binary variable, so as to minimize the cost. But first, we have to generate a first solution that is as good as possible.

The first solution is then improved by using local search descent, which eliminates the S_j's that have no interest in the solution.

A mix of the guided local search (GLS) and Tabu Search (TS) metaheuristic is also provided.

The term 'focus' hereafter means a subset of the S_j's designated by their indices. Focus make it possible to run the algorithms on the corresponding subproblems.

Todo: (user): make the different algorithms concurrent, solving independent subproblems in different threads.

The preprocessor finds the elements that can only be covered by one subset. Obviously, such subsets which are the only ones that can cover a given element are chosen.

Definition at line 74 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ Preprocessor()

operations_research::Preprocessor::Preprocessor ( absl::Nonnull< SetCoverInvariant * > inv )

inlineexplicit

Definition at line 76 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/2]

bool operations_research::Preprocessor::NextSolution ( )

Preprocessor.

Returns true if a solution was found.

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

Definition at line 50 of file set_cover_heuristics.cc.

◆ NextSolution() [2/2]

bool operations_research::Preprocessor::NextSolution ( absl::Span< const SubsetIndex > focus )

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

Definition at line 54 of file set_cover_heuristics.cc.

◆ num_columns_fixed_by_singleton_row()

int operations_research::Preprocessor::num_columns_fixed_by_singleton_row ( ) const

inline

Returns the number of columns that are the only one for a given row.

Definition at line 89 of file set_cover_heuristics.h.

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

ortools/algorithms/set_cover_heuristics.h
ortools/algorithms/set_cover_heuristics.cc