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

#include <set_cover_submodel.h>

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

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

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.

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: