Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::SetCoverLagrangian Class Reference

Detailed Description

Definition at line 50 of file set_cover_lagrangian.h.

#include <set_cover_lagrangian.h>

Inheritance diagram for operations_research::SetCoverLagrangian:
operations_research::SubsetListBasedSolutionGenerator operations_research::SetCoverSolutionGenerator

Public Member Functions

 SetCoverLagrangian (SetCoverInvariant *inv)
 SetCoverLagrangian (SetCoverInvariant *inv, const absl::string_view name)
SetCoverLagrangian & UseNumThreads (int num_threads)
bool NextSolution (absl::Span< const SubsetIndex > _) final
ElementCostVector InitializeLagrangeMultipliers () const
SubsetCostVector ComputeReducedCosts (const SubsetCostVector &costs, const ElementCostVector &multipliers) const
SubsetCostVector ParallelComputeReducedCosts (const SubsetCostVector &costs, const ElementCostVector &multipliers) const
ElementCostVector ComputeSubgradient (const SubsetCostVector &reduced_costs) const
ElementCostVector ParallelComputeSubgradient (const SubsetCostVector &reduced_costs) const
Cost ComputeLagrangianValue (const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const
Cost ParallelComputeLagrangianValue (const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const
void UpdateMultipliers (double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const
void ParallelUpdateMultipliers (double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const
Cost ComputeGap (const SubsetCostVector &reduced_costs, const SubsetBoolVector &solution, const ElementCostVector &multipliers) const
void ThreePhase (Cost upper_bound)
std::tuple< Cost, SubsetCostVector, ElementCostVector > ComputeLowerBound (const SubsetCostVector &costs, Cost upper_bound)
bool NextSolution () final
bool NextSolution (const SubsetBoolVector &in_focus) final
Public Member Functions inherited from operations_research::SubsetListBasedSolutionGenerator
 SubsetListBasedSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name)
bool NextSolution (absl::Span< const SubsetIndex > _) override
bool NextSolution () final
bool NextSolution (const SubsetBoolVector &in_focus) final
Public Member Functions inherited from operations_research::SetCoverSolutionGenerator
 SetCoverSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name)
virtual ~SetCoverSolutionGenerator ()=default
void SetName (const absl::string_view name)
SetCoverInvariant * inv () const
virtual SetCoverSolutionGenerator & ResetLimits ()
SetCoverSolutionGenerator & SetMaxIterations (int64_t max_iterations)
int64_t max_iterations () const
SetCoverSolutionGenerator & SetTimeLimitInSeconds (double seconds)
absl::Duration run_time () const
double run_time_in_seconds () const
double run_time_in_microseconds () const
std::string name () const
std::string class_name () const
Cost cost () const
bool CheckInvariantConsistency () const

Additional Inherited Members

Protected Member Functions inherited from operations_research::SetCoverSolutionGenerator
SetCoverModel * model () const
BaseInt num_subsets () const
double time_limit_in_seconds () const
Protected Attributes inherited from operations_research::SetCoverSolutionGenerator
absl::Duration run_time_
SetCoverInvariant::ConsistencyLevel consistency_level_

Constructor & Destructor Documentation

◆ SetCoverLagrangian() [1/2]

operations_research::SetCoverLagrangian::SetCoverLagrangian ( SetCoverInvariant * inv)
inlineexplicit

Definition at line 52 of file set_cover_lagrangian.h.

◆ SetCoverLagrangian() [2/2]

operations_research::SetCoverLagrangian::SetCoverLagrangian ( SetCoverInvariant * inv,
const absl::string_view name )
inline

Definition at line 55 of file set_cover_lagrangian.h.

Member Function Documentation

◆ ComputeGap()

Cost operations_research::SetCoverLagrangian::ComputeGap ( const SubsetCostVector & reduced_costs,
const SubsetBoolVector & solution,
const ElementCostVector & multipliers ) const

Definition at line 353 of file set_cover_lagrangian.cc.

◆ ComputeLagrangianValue()

Cost operations_research::SetCoverLagrangian::ComputeLagrangianValue ( const SubsetCostVector & reduced_costs,
const ElementCostVector & multipliers ) const

Definition at line 245 of file set_cover_lagrangian.cc.

◆ ComputeLowerBound()

std::tuple< Cost, SubsetCostVector, ElementCostVector > operations_research::SetCoverLagrangian::ComputeLowerBound ( const SubsetCostVector & costs,
Cost upper_bound )

Definition at line 492 of file set_cover_lagrangian.cc.

◆ ComputeReducedCosts()

SubsetCostVector operations_research::SetCoverLagrangian::ComputeReducedCosts ( const SubsetCostVector & costs,
const ElementCostVector & multipliers ) const

Definition at line 139 of file set_cover_lagrangian.cc.

◆ ComputeSubgradient()

ElementCostVector operations_research::SetCoverLagrangian::ComputeSubgradient ( const SubsetCostVector & reduced_costs) const

Definition at line 172 of file set_cover_lagrangian.cc.

◆ InitializeLagrangeMultipliers()

ElementCostVector operations_research::SetCoverLagrangian::InitializeLagrangeMultipliers ( ) const

Definition at line 48 of file set_cover_lagrangian.cc.

◆ NextSolution() [1/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( )
inlinefinalvirtual

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 181 of file set_cover_heuristics.h.

◆ NextSolution() [2/3]

bool operations_research::SetCoverLagrangian::NextSolution ( absl::Span< const SubsetIndex > _)
inlinefinalvirtual

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 71 of file set_cover_lagrangian.h.

◆ NextSolution() [3/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus)
inlinefinalvirtual

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 183 of file set_cover_heuristics.h.

◆ ParallelComputeLagrangianValue()

Cost operations_research::SetCoverLagrangian::ParallelComputeLagrangianValue ( const SubsetCostVector & reduced_costs,
const ElementCostVector & multipliers ) const

Definition at line 258 of file set_cover_lagrangian.cc.

◆ ParallelComputeReducedCosts()

SubsetCostVector operations_research::SetCoverLagrangian::ParallelComputeReducedCosts ( const SubsetCostVector & costs,
const ElementCostVector & multipliers ) const

Definition at line 109 of file set_cover_lagrangian.cc.

◆ ParallelComputeSubgradient()

ElementCostVector operations_research::SetCoverLagrangian::ParallelComputeSubgradient ( const SubsetCostVector & reduced_costs) const

Definition at line 181 of file set_cover_lagrangian.cc.

◆ ParallelUpdateMultipliers()

void operations_research::SetCoverLagrangian::ParallelUpdateMultipliers ( double step_size,
Cost lagrangian_value,
Cost upper_bound,
const SubsetCostVector & reduced_costs,
ElementCostVector * multipliers ) const

Definition at line 329 of file set_cover_lagrangian.cc.

◆ ThreePhase()

void operations_research::SetCoverLagrangian::ThreePhase ( Cost upper_bound)

◆ UpdateMultipliers()

void operations_research::SetCoverLagrangian::UpdateMultipliers ( double step_size,
Cost lagrangian_value,
Cost upper_bound,
const SubsetCostVector & reduced_costs,
ElementCostVector * multipliers ) const

Definition at line 306 of file set_cover_lagrangian.cc.

◆ UseNumThreads()

SetCoverLagrangian & operations_research::SetCoverLagrangian::UseNumThreads ( int num_threads)
inline

Definition at line 62 of file set_cover_lagrangian.h.

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