Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
set_cover_lagrangian.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_SET_COVER_SET_COVER_LAGRANGIAN_H_
15#define OR_TOOLS_SET_COVER_SET_COVER_LAGRANGIAN_H_
16
17#include <memory>
18#include <tuple>
19
20#include "absl/strings/string_view.h"
21#include "absl/types/span.h"
26
27namespace operations_research {
28
29// The SetCoverLagrangian class implements the Lagrangian relaxation of the set
30// cover problem.
31
32// In the following, we refer to the following articles:
33// [1] Caprara, Alberto, Matteo Fischetti, and Paolo Toth. 1999. “A Heuristic
34// Method for the Set Covering Problem.” Operations Research 47 (5): 730–43.
35// https://www.jstor.org/stable/223097
36// [2] Fisher, Marshall L. 1981. “The Lagrangian Relaxation Method for Solving
37// Integer Programming Problems.” Management Science 27 (1): 1–18.
38// https://www.jstor.org/stable/2631139
39// [3] Held, M., Karp, R.M. The traveling-salesman problem and minimum spanning
40// trees: Part II. Mathematical Programming 1, 6–25 (1971).
41// https://link.springer.com/article/10.1007/BF01584070
42// [4] Williamson, David P. 2002. “The Primal-Dual Method for Approximation
43// Algorithms.” Mathematical Programming, 91 (3): 447–78.
44// https://link.springer.com/article/10.1007/s101070100262
45
46// The implementation benefits from the features of SetCoverSolutionGenerator.
47// Notice however that NextSolution() is not implemented, and the class is
48// intended to be used only for ComputeLowerBound(). FOR THE TIME BEING.
49
51 public:
54
55 SetCoverLagrangian(SetCoverInvariant* inv, const absl::string_view name)
57 inv, SetCoverInvariant::ConsistencyLevel::kInconsistent,
58 "Lagrangian", name),
59 num_threads_(1),
60 thread_pool_(nullptr) {}
61
63 num_threads_ = num_threads;
64 thread_pool_ = std::make_unique<ThreadPool>(num_threads);
65 return *this;
66 }
67
69
70 // This is a dummy implementation of NextSolution() that is not used.
71 bool NextSolution(absl::Span<const SubsetIndex> _) final { return false; }
72
73 // Initializes the multipliers vector (u) based on the cost per subset.
75
76 // Computes the Lagrangian (row-)cost vector.
77 // For a subset j, c_j(u) = c_j - sum_{i \in I_j} u_i.
78 // I_j denotes the indices of elements present in subset j.
80 const SubsetCostVector& costs,
81 const ElementCostVector& multipliers) const;
82
83 // Same as above, but parallelized, using the number of threads specified in
84 // the constructor.
86 const SubsetCostVector& costs,
87 const ElementCostVector& multipliers) const;
88
89 // Computes the subgradient (column-)cost vector.
90 // For all element indices i, s_i(u) = 1 - sum_{j \in J_i} x_j(u),
91 // where J_i denotes the set of indices of subsets j covering element i.
93 const SubsetCostVector& reduced_costs) const;
94
95 // Same as above, but parallelized, using the number of threads specified in
96 // the constructor.
98 const SubsetCostVector& reduced_costs) const;
99
100 // Computes the value of the Lagrangian L(u).
101 // L(u) = min \sum_{j \in N} c_j(u) x_j + \sum{i \in M} u_i.
102 // If c_j(u) < 0: x_j(u) = 1, if c_j(u) > 0: x_j(u) = 0,
103 // otherwise x_j(u) is unbound, it can take any value in {0, 1}.
104 Cost ComputeLagrangianValue(const SubsetCostVector& reduced_costs,
105 const ElementCostVector& multipliers) const;
106
107 // Same as above, but parallelized, using the number of threads specified in
108 // the constructor.
110 const SubsetCostVector& reduced_costs,
111 const ElementCostVector& multipliers) const;
112
113 // Updates the multipliers vector (u) with the given step size.
114 // Following [3], each of the coordinates is defined as: u^{k+1}_i =
115 // max(u^k_i + lambda_k * (UB - L(u^k)) / |s^k(u)|^2 * s^k_i(u), 0).
116 // lambda_k is step_size in the function signature below. UB is upper_bound.
117 void UpdateMultipliers(double step_size, Cost lagrangian_value,
118 Cost upper_bound,
119 const SubsetCostVector& reduced_costs,
120 ElementCostVector* multipliers) const;
121
122 // Same as above, but parallelized, using the number of threads specified in
123 // the constructor.
124 void ParallelUpdateMultipliers(double step_size, Cost lagrangian_value,
125 Cost upper_bound,
126 const SubsetCostVector& reduced_costs,
127 ElementCostVector* multipliers) const;
128
129 // Computes the gap between the current solution and the optimal solution.
130 // This is the sum of the multipliers for the elements that are not covered
131 // by the current solution.
132 Cost ComputeGap(const SubsetCostVector& reduced_costs,
134 const ElementCostVector& multipliers) const;
135
136 // Performs the three-phase algorithm.
137 void ThreePhase(Cost upper_bound);
138
139 // Computes a lower bound on the optimal cost.
140 // The returned value is the lower bound, the reduced costs, and the
141 // multipliers.
142 std::tuple<Cost, SubsetCostVector, ElementCostVector> ComputeLowerBound(
143 const SubsetCostVector& costs, Cost upper_bound);
144
145 private:
146 // The number of threads to use for parallelization.
147 int num_threads_;
148
149 // The thread pool used for parallelization.
150 std::unique_ptr<ThreadPool> thread_pool_;
151
152 // Total (scalar) Lagrangian cost.
153 Cost lagrangian_;
154
155 // Lagrangian cost vector, per subset.
156 SubsetCostVector lagrangians_;
157
158 // Computes the delta vector.
159 // This is definition (9) in [1].
160 SubsetCostVector ComputeDelta(const SubsetCostVector& reduced_costs,
161 const ElementCostVector& multipliers) const;
162};
163
164} // namespace operations_research
165
166#endif // OR_TOOLS_SET_COVER_SET_COVER_LAGRANGIAN_H_
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.
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
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
Definition base_types.h:58
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
Definition base_types.h:59
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
Definition base_types.h:71
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
Definition base_types.h:32