Core concepts

This page explains the key concepts and components of PyCNP’s data model and algorithms.

Model

The Model class is the main entry point for defining and solving Critical Node Problems. It provides methods to:

  • Add nodes to the graph

  • Add edges between nodes (undirected)

  • Configure and solve the problem

from pycnp import Model

model = Model()
model.add_node(0)
model.add_node(1)
model.add_edge(0, 1)

Reading problem instances

PyCNP provides the read() function to load graph instances from files. The function automatically detects the file format (adjacency list or edge list) and creates a ProblemData object.

from pycnp import Model, read

# Load from file (auto-detects format)
problem_data = read("graph.txt")
model = Model.from_data(problem_data)

File formats

PyCNP supports two graph file formats:

Adjacency List Format

Each line contains a node ID followed by its neighbors, separated by spaces. The first line specifies the total number of nodes.

235
0: 215
1: 22 25 42 67 117 149 192 226
2: 24 95 220
3: 26 58
4: 50 53 66 72 169
...

Edge List Format

The first line contains the header p edge num_nodes num_edges. Each subsequent line defines an edge with e node1 node2.

p edge 36 91
e 0 5
e 1 3
e 1 9
e 1 12
e 1 13
e 1 14
e 1 27
e 1 28
...

Problem types

PyCNP supports two problem types:

CNP (Critical Node Problem)

The standard Critical Node Problem on undirected graphs. Given a graph \(G = (V, E)\) and a budget \(k\), the objective is to find a subset \(S \subseteq V\) with \(|S| \leq k\) that minimizes the number of connected pairs of nodes in \(G \setminus S\).

DCNP (Distance-based Critical Node Problem)

An extension that introduces a hop distance constraint. Two nodes are only considered connected if they are within the specified hop_distance of each other. This variant is useful for modeling network disruption scenarios where only local connectivity matters.

Search strategies

PyCNP implements four local search strategies:

CBNS (Component-Based Neighborhood Search)

A component-based neighborhood search that explores connected components of the solution space. It identifies connected components in the current solution and performs neighborhood operations to improve the objective value.

CHNS (Component-Based Hybrid Neighborhood Search)

A hybrid approach combining component-based search with additional neighborhood structures. It provides a balance between intensification and diversification during the search process.

DLAS (Diversified Late Acceptance Search)

A late acceptance search strategy that balances exploration and exploitation by accepting non-improving moves based on recent solution quality history.

BCLS (Betweenness Centrality-based Late Acceptance Search)

A strategy using betweenness centrality for guiding the search, specifically designed for DCNP problems where node importance is distance-dependent.

Crossover operators

Three crossover operators are available for the memetic algorithm’s population evolution:

DBX (Double Backbone Based Crossover)

Identifies common nodes between parent solutions (the “backbone”) and preserves them in the offspring. Uses the backbone structure to guide the creation of new solutions.

  • Usage: CNP problems with 2 parents

  • Strategy: Preserves common structure, inherits remaining nodes from one parent

IRR (Inherit-Repair-Recombination)

A three-parent crossover designed specifically for DCNP. The operator follows a three-phase process:

  1. Inherit: Select nodes from parents based on inheritance probabilities

  2. Repair: Fix any constraint violations in the inherited solution

  3. Recombine: Combine repaired solutions to form the final offspring

  • Usage: DCNP problems with exactly 3 parents

  • Requirement: Variable population must be disabled (is_pop_variable=False)

RSC (Reduce-Solve-Combine)

The primary crossover operator for CNP that uses problem reduction:

  1. Reduce: Identify common nodes between parents and reduce the problem

  2. Solve: Apply local search to the reduced subproblem

  3. Combine: Merge the solution with non-common nodes from parents

  • Usage: CNP problems with problem reduction enabled

  • Parameter: beta controls the fraction of common nodes to preserve

Stopping criteria

The solver requires a stopping criterion to terminate the search:

MaxIterations

Stops after a fixed number of algorithm iterations.

param max_iterations:

Maximum number of iterations to run

MaxRuntime

Stops after a specified amount of time (in seconds).

param max_runtime:

Maximum runtime in seconds

NoImprovement

Stops if no improving solution is found for a specified number of consecutive iterations.

param max_no_improvement:

Maximum iterations without improvement before stopping

Memetic algorithm

PyCNP uses a Memetic Algorithm (MA), which combines global search with local refinement:

  1. Population-based evolution - Maintains a population of solutions that evolve over generations

  2. Local search - Applies problem-specific neighborhood search to improve each offspring

  3. Crossover operators - Combines parent solutions to create diverse offspring

The MemeticSearch class handles the population and evolution process. Key configuration parameters include:

  • search - The local search strategy (CBNS, CHNS, DLAS, or BCLS)

  • crossover - The crossover operator (DBX, IRR, or RSC)

  • is_problem_reduction - Whether to use problem reduction with RSC crossover

  • is_pop_variable - Whether the population size can adapt during search

  • initial_pop_size - The initial population size (default: 5)

Variable population sizing

PyCNP supports adaptive population sizing through the VariablePopulationParams class. When enabled, the population can expand or contract based on search progress:

  • max_pop_size - Maximum population size (default: 20)

  • increase_pop_size - Number of individuals to add when expanding (default: 3)

  • max_idle_gens - Number of idle generations before triggering population update (default: 20)

The population expands when no improvement is observed for max_idle_gens consecutive iterations, injecting diversity into the search process.

C++ ProblemData

The C++ ProblemData class is the underlying data structure used by PyCNP to store graph information. It is created automatically when loading instances via read().