The consistency level is maintained up to kFreeAndUncovered. More...

#include <set_cover_heuristics.h>

Public Member Functions
	TrivialSolutionGenerator (SetCoverInvariant *inv)

bool	NextSolution ()
	TrivialSolutionGenerator.

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

Detailed Description

The consistency level is maintained up to kFreeAndUncovered.

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.

An obvious idea is to take all the S_j's (or equivalently to set all the x_j's to 1). It's very silly but fast, and we can improve on it later using local search.

Definition at line 52 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ TrivialSolutionGenerator()

operations_research::TrivialSolutionGenerator::TrivialSolutionGenerator ( SetCoverInvariant * inv )

inlineexplicit

Definition at line 54 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/2]

bool operations_research::TrivialSolutionGenerator::NextSolution ( )

TrivialSolutionGenerator.

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 56 of file set_cover_heuristics.cc.

◆ NextSolution() [2/2]

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

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

Definition at line 60 of file set_cover_heuristics.cc.

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