![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <set_cover_cft.h>
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={}) |
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.
|
default |
operations_research::scp::FullToCoreModel::FullToCoreModel | ( | const Model * | full_model | ) |
Definition at line 1101 of file set_cover_cft.cc.
|
inline |
Definition at line 401 of file set_cover_cft.h.
|
protected |
Definition at line 1201 of file set_cover_cft.cc.
|
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.
|
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.
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.
|
inlineprotected |
Definition at line 408 of file set_cover_cft.h.
|
inlineprotected |
Definition at line 411 of file set_cover_cft.h.
|
protected |
Definition at line 1190 of file set_cover_cft.cc.
|
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.
Reimplemented from operations_research::scp::CoreModel.
Definition at line 1153 of file set_cover_cft.cc.
void operations_research::scp::FullToCoreModel::ResetPricingPeriod | ( | ) |
Definition at line 1114 of file set_cover_cft.cc.
|
protected |
|
protected |
Definition at line 1186 of file set_cover_cft.cc.
|
inlineprotected |
Access the full model with the strongly typed view.
Definition at line 430 of file set_cover_cft.h.
|
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.
|
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.
|
protected |
Definition at line 1227 of file set_cover_cft.cc.