Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::scp Namespace Reference

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.

Detailed Description

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

http://www.apache.org/licenses/LICENSE-2.0

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 /////////////////////////

Typedef Documentation

◆ Model

Todo
(anyone): since we are working within the scp namespace, the "SetCover*" prefix became redundant and can be removed. For now, only redefine it locally.

Definition at line 24 of file set_cover_submodel.h.

◆ SubModel

Function Documentation

◆ CoverGreedly()

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.

Note
since the cutoff might be reached, the returned solution might not be feasible.

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.

◆ DivideIfGE0()

Cost operations_research::scp::DivideIfGE0 ( Cost numerator,
Cost denominator )
inline

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.

◆ RunCftHeuristic()

PrimalDualState operations_research::scp::RunCftHeuristic ( SubModel & model,
const Solution & init_solution = {} )

OUTER REFINEMENT PROCEDURE //////////////////////

Definition at line 911 of file set_cover_cft.cc.

◆ RunMultiplierBasedGreedy()

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.

◆ RunThreePhase()

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.

◆ SubgradientOptimization()

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.

◆ ValidateSubModel()

template<typename SubModelT>
bool operations_research::scp::ValidateSubModel ( const SubModelT & model)

Definition at line 273 of file set_cover_submodel.h.

Variable Documentation

◆ kMinCov

BaseInt operations_research::scp::kMinCov = 5
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.