Camargue
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Public Member Functions | Static Public Member Functions | Private Attributes | List of all members
CMR::Data::KarpPartition Class Reference

Class for computing and storing Karp partitions. More...

#include <karp.hpp>

Public Member Functions

 KarpPartition ()=default
 Default construct an empty partition.
 
 KarpPartition (const Data::Instance &inst, bool make_dummy, bool save_part)
 Construct a KarpPartition, with the option to force a dummy partition and/or write the partition to file. More...
 
 KarpPartition (const Data::Instance &inst)
 Construct a partition from an Instance inst.
 
int num_parts () const
 The number of sub-regions into which the data has been partitioned.
 
const std::vector< int > & operator[] (int i) const
 The nodes of the i th partition.
 

Static Public Member Functions

static int bucket_size (const int ncount)
 Maximum partition size as function of number of nodes ncount.
 

Private Attributes

std::vector< std::vector< int > > part_list
 A ragged matrix storing the partitions.
 

Detailed Description

Class for computing and storing Karp partitions.

Computes a geometric partition of a TSP instance, a la Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in The Plane (Karp, 1977). Given geometric TSP data, it partitions the set of nodes into rectangles containing at most some fixed number of nodes.

Remarks
This class is used exclusively in the separation of simple domino parity inequalities, but also it only needs to be computed once for a given instance, because it is invariant under changes to the active edge set/support graph. Hence it should be owned by a Solver or similar.
This is a highly limited interface to the Concorde function CCutil_karp_partition and the Concorde structure CCsubdiv.

Constructor & Destructor Documentation

CMR::Data::KarpPartition::KarpPartition ( const Data::Instance inst,
bool  make_dummy,
bool  save_part 
)

Construct a KarpPartition, with the option to force a dummy partition and/or write the partition to file.

A dummy partition consists of the whole vertex set. Dummy partitions are used by default if inst has under 300 nodes, or if its norm is incompatible with the Concorde KD tree code.

Parameters
instthe Instance to generate the partition from.
make_dummyif true, force a dummy partition to be used.
save_partif true, save the partition to a file called inst.problem_name().kpart.

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