Detailed Description

CoreModel stores a subset of the filtered columns and rows in an explicit Model object. The indices are compacted and mapped to the range [0, <sub-model-size>], effectively creating a smaller set-covering model. Similar to SubModelView, the core model supports column fixing and focusing on a subset of the original model. Mappings are maintained to translate indices back to the original model space.

Definition at line 162 of file set_cover_submodel.h.

#include <set_cover_submodel.h>

Inheritance diagram for operations_research::scp::CoreModel:

Public Member Functions
	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)
virtual Cost	FixMoreColumns (const std::vector< SubsetIndex > &columns_to_fix)
virtual void	ResetColumnFixing (const std::vector< FullSubsetIndex > &columns_to_fix, const DualState &state)
virtual bool	UpdateCore (Cost best_lower_bound, const ElementCostVector &best_multipliers, const Solution &best_solution, bool force)
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.

Constructor & Destructor Documentation

◆ CoreModel() [1/3]

operations_research::scp::CoreModel::CoreModel ( )

default

Empty initialization to facilitate delayed construction.

◆ CoreModel() [2/3]

operations_research::scp::CoreModel::CoreModel ( const Model * model )

Identity sub-model: all items are considered.

Definition at line 136 of file set_cover_submodel.cc.

◆ CoreModel() [3/3]

operations_research::scp::CoreModel::CoreModel	(	const Model *	model,
		const std::vector< FullSubsetIndex > &	columns_focus )

Focus construction: create a sub-model with only the required items.

Definition at line 144 of file set_cover_submodel.cc.

◆ ~CoreModel()

virtual operations_research::scp::CoreModel::~CoreModel ( )

virtualdefault

Member Function Documentation

◆ column_size()

BaseInt operations_research::scp::CoreModel::column_size ( SubsetIndex j ) const

inline

Definition at line 181 of file set_cover_submodel.h.

◆ columns()

const SparseColumnView & operations_research::SetCoverModel::columns ( ) const

inline

Member function relevant for the CFT inherited from Model.

Definition at line 171 of file set_cover_model.h.

◆ ElementRange()

util_intops::StrongIntRange< ElementIndex > operations_research::SetCoverModel::ElementRange ( ) const

inline

Definition at line 187 of file set_cover_model.h.

◆ fixed_columns()

const std::vector< FullSubsetIndex > & operations_research::scp::CoreModel::fixed_columns ( ) const

inline

List of fixed columns.

Definition at line 215 of file set_cover_submodel.h.

◆ fixed_cost()

Cost operations_research::scp::CoreModel::fixed_cost ( ) const

inline

Current fixed cost: sum of the cost of the fixed columns.

Definition at line 213 of file set_cover_submodel.h.

◆ FixMoreColumns()

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

virtual

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 in operations_research::scp::FullToCoreModel.

Definition at line 286 of file set_cover_submodel.cc.

◆ MapCoreToFullElementIndex()

FullElementIndex operations_research::scp::CoreModel::MapCoreToFullElementIndex ( ElementIndex core_i ) const

inline

Definition at line 190 of file set_cover_submodel.h.

◆ MapCoreToFullSubsetIndex()

FullSubsetIndex operations_research::scp::CoreModel::MapCoreToFullSubsetIndex ( SubsetIndex core_j ) const

inline

Definition at line 199 of file set_cover_submodel.h.

◆ MapFullToCoreElementIndex()

ElementIndex operations_research::scp::CoreModel::MapFullToCoreElementIndex ( FullElementIndex full_i ) const

inline

Definition at line 194 of file set_cover_submodel.h.

◆ num_elements()

BaseInt operations_research::scp::CoreModel::num_elements ( ) const

inline

Definition at line 178 of file set_cover_submodel.h.

◆ num_focus_elements()

BaseInt operations_research::scp::CoreModel::num_focus_elements ( ) const

inline

Definition at line 180 of file set_cover_submodel.h.

◆ num_focus_subsets()

BaseInt operations_research::scp::CoreModel::num_focus_subsets ( ) const

inline

Definition at line 179 of file set_cover_submodel.h.

◆ num_subsets()

BaseInt operations_research::scp::CoreModel::num_subsets ( ) const

inline

Definition at line 177 of file set_cover_submodel.h.

◆ ResetColumnFixing()

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

virtual

Reimplemented in operations_research::scp::FullToCoreModel.

Definition at line 308 of file set_cover_submodel.cc.

◆ row_size()

BaseInt operations_research::scp::CoreModel::row_size ( ElementIndex i ) const

inline

Definition at line 185 of file set_cover_submodel.h.

◆ rows()

const SparseRowView & operations_research::SetCoverModel::rows ( ) const

inline

Row view of the set covering problem.

Definition at line 174 of file set_cover_model.h.

◆ SetFocus()

void operations_research::scp::CoreModel::SetFocus ( const std::vector< FullSubsetIndex > & columns_focus )

Redefine the active items. The new sub-model will ignore all columns not in focus and (optionally) the rows for which row_flags is not true. It does not overwrite the current fixing.

Note: Assumes that columns_focus covers all rows for which rows_flags is true (i.e.: non-covered rows should be set to false to rows_flags). This property get exploited to keep the rows in the same ordering of the original model using "cleanish" code.

Todo: (c4v4): change model in-place to avoid reallocations.

Now we can fill the new core model

SetCoverModel lacks a way to remove columns

Handle empty columns

Definition at line 176 of file set_cover_submodel.cc.

◆ StrongTypedFullModelView()

StrongModelView operations_research::scp::CoreModel::StrongTypedFullModelView ( ) const

inline

Definition at line 243 of file set_cover_submodel.h.

◆ subset_costs()

const SubsetCostVector & operations_research::SetCoverModel::subset_costs ( ) const

inline

Vector of costs for each subset.

Definition at line 151 of file set_cover_model.h.

◆ SubsetRange()

util_intops::StrongIntRange< SubsetIndex > operations_research::SetCoverModel::SubsetRange ( ) const

inline

Access to the ranges of subsets and elements.

Definition at line 183 of file set_cover_model.h.

◆ UpdateCore()

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

inlinevirtual

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 in operations_research::scp::FullToCoreModel.

Definition at line 237 of file set_cover_submodel.h.

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

ortools/set_cover/set_cover_submodel.h
ortools/set_cover/set_cover_submodel.cc

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

◆ CoreModel() [1/3]

◆ CoreModel() [2/3]

◆ CoreModel() [3/3]

◆ ~CoreModel()

Member Function Documentation

◆ column_size()

◆ columns()

◆ ElementRange()

◆ fixed_columns()

◆ fixed_cost()

◆ FixMoreColumns()

◆ MapCoreToFullElementIndex()

◆ MapCoreToFullSubsetIndex()

◆ MapFullToCoreElementIndex()

◆ num_elements()

◆ num_focus_elements()

◆ num_focus_subsets()

◆ num_subsets()

◆ ResetColumnFixing()

◆ row_size()

◆ rows()

◆ SetFocus()

◆ StrongTypedFullModelView()

◆ subset_costs()

◆ SubsetRange()

◆ UpdateCore()