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.

#include <set_cover_cft.h>

Inheritance diagram for operations_research::scp::FullToCoreModel:

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 DualState &	best_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 SparseColumnView &	columns () const
	Member function relevant for the CFT inherited from Model.
util_intops::StrongIntRange< ElementIndex >	ElementRange () const
const SparseRowView &	rows () const
	Row view of the set covering problem.
const SubsetCostVector &	subset_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={})

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:

ortools/set_cover/set_cover_cft.h
ortools/set_cover/set_cover_cft.cc

Detailed Description

Public Member Functions

Protected Member Functions

Constructor & Destructor Documentation

◆ FullToCoreModel() [1/2]

◆ FullToCoreModel() [2/2]

Member Function Documentation

◆ best_dual_state()

◆ ComputeAndSetFocus()

◆ FixingFullModelView()

◆ FixMoreColumns()

◆ FullToSubModelInvariantCheck()

◆ IsFocusCol()

◆ IsFocusRow()

◆ IsTimeToUpdate()

◆ ResetColumnFixing()

◆ ResetPricingPeriod()

◆ SelectNewCoreColumns()

◆ SizeUpdate()

◆ StrongTypedFullModelView()

◆ UpdateCore()

◆ UpdateMultipliers()

◆ UpdatePricingPeriod()