14#ifndef OR_TOOLS_SET_COVER_SET_COVER_LAGRANGIAN_H_
15#define OR_TOOLS_SET_COVER_SET_COVER_LAGRANGIAN_H_
20#include "absl/strings/string_view.h"
21#include "absl/types/span.h"
60 thread_pool_(nullptr) {}
63 num_threads_ = num_threads;
64 thread_pool_ = std::make_unique<ThreadPool>(num_threads);
71 bool NextSolution(absl::Span<const SubsetIndex> _)
final {
return false; }
150 std::unique_ptr<ThreadPool> thread_pool_;
void UpdateMultipliers(double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const
Cost ComputeLagrangianValue(const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const
ElementCostVector ComputeSubgradient(const SubsetCostVector &reduced_costs) const
void ThreePhase(Cost upper_bound)
Performs the three-phase algorithm.
void ParallelUpdateMultipliers(double step_size, Cost lagrangian_value, Cost upper_bound, const SubsetCostVector &reduced_costs, ElementCostVector *multipliers) const
ElementCostVector ParallelComputeSubgradient(const SubsetCostVector &reduced_costs) const
SetCoverLagrangian & UseNumThreads(int num_threads)
SubsetCostVector ParallelComputeReducedCosts(const SubsetCostVector &costs, const ElementCostVector &multipliers) const
Computes the reduced costs for all subsets in parallel using ThreadPool.
SetCoverLagrangian(SetCoverInvariant *inv)
Cost ParallelComputeLagrangianValue(const SubsetCostVector &reduced_costs, const ElementCostVector &multipliers) const
bool NextSolution(absl::Span< const SubsetIndex > _) final
This is a dummy implementation of NextSolution() that is not used.
SetCoverLagrangian(SetCoverInvariant *inv, const absl::string_view name)
ElementCostVector InitializeLagrangeMultipliers() const
Initializes the multipliers vector (u) based on the cost per subset.
std::tuple< Cost, SubsetCostVector, ElementCostVector > ComputeLowerBound(const SubsetCostVector &costs, Cost upper_bound)
Computes a lower bound on the optimal cost.
SubsetCostVector ComputeReducedCosts(const SubsetCostVector &costs, const ElementCostVector &multipliers) const
Cost ComputeGap(const SubsetCostVector &reduced_costs, const SubsetBoolVector &solution, const ElementCostVector &multipliers) const
SetCoverInvariant * inv() const
std::string name() const
Returns the name of the heuristic.
SubsetListBasedSolutionGenerator(SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name)
bool NextSolution(absl::Span< const SubsetIndex > _) override
In SWIG mode, we don't want anything besides these top-level includes.
util_intops::StrongVector< SubsetIndex, Cost > SubsetCostVector
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
util_intops::StrongVector< ElementIndex, Cost > ElementCostVector
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.