![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
Classes | |
class | BoundCBs |
class | CoreModel |
class | DualState |
class | FullToCoreModel |
class | HeuristicCBs |
struct | PrimalDualState |
Utility aggregate to store and pass around both primal and dual states. More... | |
class | Solution |
class | SubgradientCBs |
struct | SubgradientContext |
class | SubModelView |
Typedefs | |
using | Model = SetCoverModel |
using | SubModel = CoreModel |
Functions | |
void | SubgradientOptimization (SubModel &model, SubgradientCBs &cbs, PrimalDualState &best_state) |
Solution | RunMultiplierBasedGreedy (const SubModel &model, const DualState &dual_state, Cost cost_cutoff) |
Cost | CoverGreedly (const SubModel &model, const DualState &dual_state, Cost cost_cutoff, BaseInt stop_size, std::vector< SubsetIndex > &sol_subsets) |
PrimalDualState | RunThreePhase (SubModel &model, const Solution &init_solution) |
PrimalDualState | RunCftHeuristic (SubModel &model, const Solution &init_solution) |
Cost | DivideIfGE0 (Cost numerator, Cost denominator) |
template<typename SubModelT> | |
bool | ValidateSubModel (const SubModelT &model) |
Variables | |
static constexpr BaseInt | kMinCov = 5 |
Coverage counter to decide the number of columns to keep in the core model. |
Copyright 2025 Francesco Cavaliere Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
MULTIPLIERS BASED GREEDY ///////////////////////
THREE PHASE ALGORITHM ////////////////////////
OUTER REFINEMENT PROCEDURE //////////////////////
FULL TO CORE PRICING /////////////////////////
Definition at line 24 of file set_cover_submodel.h.
Definition at line 69 of file set_cover_submodel.h.
Cost operations_research::scp::CoverGreedly | ( | const SubModel & | model, |
const DualState & | dual_state, | ||
Cost | cost_cutoff, | ||
BaseInt | size_cutoff, | ||
std::vector< SubsetIndex > & | sol_subsets ) |
Lower level greedy function which creates or completes a "solution" (seen as set of subsets of the current SubModel) until a cutoff size or cost is reached.
Solution already has required size -> early exit
Process input solution (if not empty)
Initialize column scores taking into account rows already covered
Fill up partial solution
Either remove redundant columns or discard solution
Definition at line 623 of file set_cover_cft.cc.
In the narrow scope of the CFT subgradient, there are often divisions between non-negative quantities (e.g., to compute a relative gap). In these specific cases, the denominator should always be greater than the numerator. This function checks that.
Definition at line 113 of file set_cover_cft.h.
PrimalDualState operations_research::scp::RunCftHeuristic | ( | SubModel & | model, |
const Solution & | init_solution = {} ) |
OUTER REFINEMENT PROCEDURE //////////////////////
Definition at line 911 of file set_cover_cft.cc.
Solution operations_research::scp::RunMultiplierBasedGreedy | ( | const SubModel & | model, |
const DualState & | dual_state, | ||
Cost | cost_cutoff = std::numeric_limits< BaseInt >::max() ) |
MULTIPLIERS BASED GREEDY /////////////////////// Higher level function that return a function obtained by the dual multiplier based greedy.
Definition at line 614 of file set_cover_cft.cc.
PrimalDualState operations_research::scp::RunThreePhase | ( | SubModel & | model, |
const Solution & | init_solution ) |
Phase 1: refine the current dual_state and model
Phase 2: search for good solutions
Phase 3: Fix the best columns (diving)
Definition at line 785 of file set_cover_cft.cc.
void operations_research::scp::SubgradientOptimization | ( | SubModel & | core_model, |
SubgradientCBs & | cbs, | ||
PrimalDualState & | best_state ) |
Subgradient optimization procedure. Optimizes the Lagrangian relaxation of the Set-Covering problem until a termination criterion si met.
Poor multipliers can lead to wasted iterations or stagnation in the subgradient method. To address this, we adjust the multipliers to get closer the trivial lower bound (= 0).
Compute subgradient (O(nnz))
Definition at line 284 of file set_cover_cft.cc.
bool operations_research::scp::ValidateSubModel | ( | const SubModelT & | model | ) |
Definition at line 273 of file set_cover_submodel.h.
|
staticconstexpr |
Coverage counter to decide the number of columns to keep in the core model.
FULL TO CORE PRICING /////////////////////////
Definition at line 338 of file set_cover_cft.h.