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

#include <set_cover_cft.h>

Inheritance diagram for operations_research::scp::FullToCoreModel:
operations_research::scp::CoreModel operations_research::SetCoverModel

Public Member Functions

 FullToCoreModel ()=default
 FullToCoreModel (const Model *full_model)
Cost FixMoreColumns (const std::vector< SubsetIndex > &columns_to_fix) override
void ResetColumnFixing (const std::vector< FullSubsetIndex > &columns_to_fix, const DualState &state) override
bool UpdateCore (Cost best_lower_bound, const ElementCostVector &best_multipliers, const Solution &best_solution, bool force) override
void ResetPricingPeriod ()
const DualStatebest_dual_state () const
bool FullToSubModelInvariantCheck ()
Public Member Functions inherited from operations_research::scp::CoreModel
 CoreModel ()=default
 Empty initialization to facilitate delayed construction.
 CoreModel (const Model *model)
 Identity sub-model: all items are considered.
 CoreModel (const Model *model, const std::vector< FullSubsetIndex > &columns_focus)
 Focus construction: create a sub-model with only the required items.
virtual ~CoreModel ()=default
BaseInt num_subsets () const
BaseInt num_elements () const
BaseInt num_focus_subsets () const
BaseInt num_focus_elements () const
BaseInt column_size (SubsetIndex j) const
BaseInt row_size (ElementIndex i) const
FullElementIndex MapCoreToFullElementIndex (ElementIndex core_i) const
ElementIndex MapFullToCoreElementIndex (FullElementIndex full_i) const
FullSubsetIndex MapCoreToFullSubsetIndex (SubsetIndex core_j) const
Cost fixed_cost () const
 Current fixed cost: sum of the cost of the fixed columns.
const std::vector< FullSubsetIndex > & fixed_columns () const
 List of fixed columns.
void SetFocus (const std::vector< FullSubsetIndex > &columns_focus)
StrongModelView StrongTypedFullModelView () const
const SparseColumnViewcolumns () const
 Member function relevant for the CFT inherited from Model.
util_intops::StrongIntRange< ElementIndex > ElementRange () const
const SparseRowViewrows () const
 Row view of the set covering problem.
const SubsetCostVectorsubset_costs () const
 Vector of costs for each subset.
util_intops::StrongIntRange< SubsetIndex > SubsetRange () const
 Access to the ranges of subsets and elements.

Protected Member Functions

void SizeUpdate ()
bool IsTimeToUpdate (Cost best_lower_bound, bool force)
decltype(auto) IsFocusCol (FullSubsetIndex j)
decltype(auto) IsFocusRow (FullElementIndex i)
void UpdatePricingPeriod (const DualState &full_dual_state, Cost core_lower_bound, Cost core_upper_bound)
Cost UpdateMultipliers (const ElementCostVector &core_multipliers)
void ComputeAndSetFocus (Cost best_lower_bound, const Solution &best_solution)
FilterModelView FixingFullModelView () const
 Access the full model filtered by the current columns fixed.
StrongModelView StrongTypedFullModelView () const
 Access the full model with the strongly typed view.
std::vector< FullSubsetIndex > SelectNewCoreColumns (const std::vector< FullSubsetIndex > &forced_columns={})

Detailed Description

CoreModel extractor. Stores a pointer to the full model and specilized UpdateCore in such a way to updated the SubModel (stored as base class) and focus the search on a small windows of the full model.

Definition at line 343 of file set_cover_cft.h.

Constructor & Destructor Documentation

◆ FullToCoreModel() [1/2]

operations_research::scp::FullToCoreModel::FullToCoreModel ( )
default

◆ FullToCoreModel() [2/2]

operations_research::scp::FullToCoreModel::FullToCoreModel ( const Model * full_model)

Definition at line 1101 of file set_cover_cft.cc.

Member Function Documentation

◆ best_dual_state()

const DualState & operations_research::scp::FullToCoreModel::best_dual_state ( ) const
inline

Definition at line 401 of file set_cover_cft.h.

◆ ComputeAndSetFocus()

void operations_research::scp::FullToCoreModel::ComputeAndSetFocus ( Cost best_lower_bound,
const Solution & best_solution )
protected

Definition at line 1201 of file set_cover_cft.cc.

◆ FixingFullModelView()

FilterModelView operations_research::scp::FullToCoreModel::FixingFullModelView ( ) const
inlineprotected

Access the full model filtered by the current columns fixed.

Views are not composable (for now), so we can either access the full_model with the strongly typed view or with the filtered view.

Definition at line 423 of file set_cover_cft.h.

◆ FixMoreColumns()

Cost operations_research::scp::FullToCoreModel::FixMoreColumns ( const std::vector< SubsetIndex > & columns_to_fix)
overridevirtual

Fix the provided columns, removing them for the submodel. Rows now covered by fixed columns are also removed from the submodel along with non-fixed columns that only cover those rows.

Mark columns to be fixed and rows that will be covered by them

Compute new core->full(returned) and full->core(modified original) row maps

Create new model object applying the computed mappings

Reimplemented from operations_research::scp::CoreModel.

Definition at line 1120 of file set_cover_cft.cc.

◆ FullToSubModelInvariantCheck()

bool operations_research::scp::FullToCoreModel::FullToSubModelInvariantCheck ( )

Assumes corresponding elements have the same order in both models

Definition at line 1275 of file set_cover_cft.cc.

◆ IsFocusCol()

decltype(auto) operations_research::scp::FullToCoreModel::IsFocusCol ( FullSubsetIndex j)
inlineprotected

Definition at line 408 of file set_cover_cft.h.

◆ IsFocusRow()

decltype(auto) operations_research::scp::FullToCoreModel::IsFocusRow ( FullElementIndex i)
inlineprotected

Definition at line 411 of file set_cover_cft.h.

◆ IsTimeToUpdate()

bool operations_research::scp::FullToCoreModel::IsTimeToUpdate ( Cost best_lower_bound,
bool force )
protected

Definition at line 1190 of file set_cover_cft.cc.

◆ ResetColumnFixing()

void operations_research::scp::FullToCoreModel::ResetColumnFixing ( const std::vector< FullSubsetIndex > & columns_to_fix,
const DualState & state )
overridevirtual

We could implement and in-place core-model update that removes old fixings, set the new one while also updating the column focus. This solution is much simpler. It just create a new core-model object from scratch and then uses the existing interface.

Todo
(anyone): Improve this. It's Inefficient but hardly a botleneck and it also avoid storing a full->core column map.

Reimplemented from operations_research::scp::CoreModel.

Definition at line 1153 of file set_cover_cft.cc.

◆ ResetPricingPeriod()

void operations_research::scp::FullToCoreModel::ResetPricingPeriod ( )

Definition at line 1114 of file set_cover_cft.cc.

◆ SelectNewCoreColumns()

std::vector< FullSubsetIndex > operations_research::scp::FullToCoreModel::SelectNewCoreColumns ( const std::vector< FullSubsetIndex > & forced_columns = {})
protected

◆ SizeUpdate()

void operations_research::scp::FullToCoreModel::SizeUpdate ( )
protected

Definition at line 1186 of file set_cover_cft.cc.

◆ StrongTypedFullModelView()

StrongModelView operations_research::scp::FullToCoreModel::StrongTypedFullModelView ( ) const
inlineprotected

Access the full model with the strongly typed view.

Definition at line 430 of file set_cover_cft.h.

◆ UpdateCore()

bool operations_research::scp::FullToCoreModel::UpdateCore ( Cost best_lower_bound,
const ElementCostVector & best_multipliers,
const Solution & best_solution,
bool force )
overridevirtual

Hook function for specializations. This function can be used to define a "small" core model considering a subset of the full model through the use of column-generation or by only selecting columns with good reduced cost in the full model.

Reimplemented from operations_research::scp::CoreModel.

Definition at line 1215 of file set_cover_cft.cc.

◆ UpdateMultipliers()

Cost operations_research::scp::FullToCoreModel::UpdateMultipliers ( const ElementCostVector & core_multipliers)
protected

Here, we simply check if any columns have been fixed, and only update the best dual state when no fixing is in place.

Mapping a "local" dual state to a global one is possible. This would involve keeping the multipliers for non-focused elements fixed, updating the multipliers for focused elements, and then computing the dual state for the entire model. However, this approach is not implemented here. Such a strategy is unlikely to improve the best dual state unless the focus is always limited to a small subset of elements (and therefore the LB sucks and it is easy to improve) and the CFT is applied exclusively within that narrow scope, but this falls outside the current scope of this project.

Definition at line 1247 of file set_cover_cft.cc.

◆ UpdatePricingPeriod()

void operations_research::scp::FullToCoreModel::UpdatePricingPeriod ( const DualState & full_dual_state,
Cost core_lower_bound,
Cost core_upper_bound )
protected

Definition at line 1227 of file set_cover_cft.cc.


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