#include <set_cover_heuristics.h>

Public Member Functions
	SteepestSearch (SetCoverInvariant *inv)

bool	NextSolution (int num_iterations)

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

bool	NextSolution (absl::Span< const SubsetIndex > focus, const SubsetCostVector &costs, int num_iterations)
	Same as above, with a different set of costs.

Detailed Description

Once we have a first solution to the problem, there may be (most often, there are) elements in E that are covered several times. To decrease the total cost, SteepestSearch tries to eliminate some redundant S_j's from the solution or equivalently, to flip some x_j's from 1 to 0. the algorithm gets its name because it goes in the steepest immediate direction, taking the S_j with the largest total cost.

Definition at line 222 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ SteepestSearch()

operations_research::SteepestSearch::SteepestSearch ( SetCoverInvariant * inv )

inlineexplicit

Definition at line 224 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/3]

bool operations_research::SteepestSearch::NextSolution	(	absl::Span< const SubsetIndex >	focus,
		const SubsetCostVector &	costs,
		int	num_iterations )

Same as above, with a different set of costs.

Definition at line 259 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

bool operations_research::SteepestSearch::NextSolution	(	absl::Span< const SubsetIndex >	focus,
		int	num_iterations )

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

Definition at line 252 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

bool operations_research::SteepestSearch::NextSolution ( int num_iterations )

Returns true if a solution was found within num_iterations.

Todo: (user): Add time-outs and exit with a partial solution.

Definition at line 246 of file set_cover_heuristics.cc.

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

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