NP-Complete Optimization Toolkit

A comprehensive Python toolkit for solving NP-complete optimization problems, featuring multiple algorithmic approaches from exact methods to metaheuristics.

Originally developed during graduate coursework at the University of Louisville, restructured into a professional, extensible library.

Features

• Multiple Algorithm Classes: Exact methods, heuristics, metaheuristics, and ensemble methods
• Two Problem Domains: Traveling Salesman Problem (TSP) and MAX-CUT
• Clean Modular Architecture: Easy to extend and integrate
• Visualization Tools: Tour plotting and convergence analysis
• Runnable Examples: Ready-to-use scripts demonstrating each algorithm

Installation

git clone https://github.com/Cribmaster2429/np-complete-optimization.git
cd np-complete-optimization
pip install -r requirements.txt

Quick Start

Compare TSP Algorithms

python examples/compare_tsp_algorithms.py

This runs brute-force, branch-and-bound, insertion heuristic, and genetic algorithm on a 10-city instance, showing the trade-off between solution quality and computation time.

Run Genetic Algorithm for TSP

python examples/run_tsp_ga.py --tsp data/tsp/random30.tsp --seeds 5

Run Genetic Algorithm for MAX-CUT

python examples/run_maxcut_ga.py --graph data/graphs/er_n50.json --seeds 10

Run Wisdom of Crowds Ensemble

# First, generate GA solutions
python examples/run_maxcut_ga.py --graph data/graphs/er_n50.json --seeds 10

# Then, run WoC consensus
python examples/run_woc_ensemble.py --graph data/graphs/er_n50.json

Project Structure

np-complete-optimization/
├── tsp/                      # TSP algorithms
│   ├── exact/                # Brute-force, Branch-and-bound
│   ├── search/               # BFS, DFS
│   ├── heuristics/           # Closest-edge insertion
│   ├── genetic/              # Genetic algorithm (PMX/OX crossover)
│   ├── ensemble/             # Wisdom of Crowds
│   └── utils/                # I/O and visualization
│
├── maxcut/                   # MAX-CUT algorithms
│   ├── genetic/              # Genetic algorithm
│   ├── ensemble/             # Wisdom of Crowds
│   └── utils/                # I/O and scoring
│
├── examples/                 # Runnable demo scripts
├── data/                     # Sample datasets
│   ├── tsp/                  # TSPLIB format files
│   └── graphs/               # JSON graph files
│
└── requirements.txt

Algorithm Progression

The toolkit demonstrates a natural progression of algorithmic sophistication:

Algorithm	Type	Optimality	Scalability
Brute Force	Exact	Guaranteed	n ≤ 12
Branch & Bound	Exact	Guaranteed	n ≤ 20
BFS/DFS	Search	Path-finding	Graph dependent
Insertion	Heuristic	Approximate	n ≤ 1000+
Genetic Algorithm	Metaheuristic	Near-optimal	n ≤ 1000+
Wisdom of Crowds	Ensemble	Near-optimal	n ≤ 1000+

Usage as a Library

from tsp.utils.io import read_tsp
from tsp.genetic.ga import run_ga

# Load TSP instance
coords = read_tsp("data/tsp/random30.tsp")

# Run genetic algorithm
tour, length, history, meta = run_ga(
    coords,
    crossover="pmx",
    mut_rate=0.01,
    pop_size=200,
    max_gens=1000,
    seed=42
)

print(f"Best tour length: {length:.2f}")
print(f"Converged in {meta['generations']} generations")

from maxcut.utils.io import read_graph_json
from maxcut.genetic.ga import run_ga

# Load graph
n, u, v, w = read_graph_json("data/graphs/er_n50.json")

# Run genetic algorithm
best_bits, best_cut, history, meta = run_ga(
    n, u, v, w,
    pop_size=200,
    max_gens=1500,
    seed=42
)

print(f"Best cut value: {best_cut:.2f}")

Key Implementation Details

TSP Genetic Algorithm

• Crossover: PMX (Partially Mapped) or OX (Order) for permutation chromosomes
• Selection: Tournament selection (k=3)
• Mutation: Swap mutation
• Seeding: Population initialized with closest-edge insertion heuristic
• Early stopping: Patience-based convergence detection

MAX-CUT Genetic Algorithm

• Representation: Binary bit-string (partition assignment)
• Crossover: Uniform or one-point
• Mutation: Per-bit flip with rate 1/n
• Seeding: Half random, half alternating pattern

Wisdom of Crowds

• Combines multiple GA solutions via weighted voting
• TSP: Edge frequency consensus with greedy 2-regular graph assembly
• MAX-CUT: Bit-majority voting with local refinement

Data Formats

TSPLIB Format (.tsp)

NAME: example
TYPE: TSP
DIMENSION: 10
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 22.5 89.0
2 23.0 81.4
...
EOF

Graph JSON Format

{
  "n": 50,
  "edges": [[0, 1, 1.5], [0, 2, 2.3], ...]
}

Author

Danson Wachira

License

MIT License - see LICENSE for details.