Quadratic Assignment Problem (QAP) Optimization

This repository contains tools for solving and analyzing the Quadratic Assignment Problem (QAP) using various optimization algorithms.

Project Structure

• qap_optimizer/: Rust-based optimization engine.
• analysis/: Python-based analysis and visualization module.
• config.toml: Centralized configuration for both components.
• instances/: (User-provided) Benchmark instances and solutions.
• data/: (Generated) CSV results and discovery data.
• figures/: (Generated) Analysis plots.

Setup & Configuration

1. Requirements

• Rust (latest stable)
• Python 3.11+ (with pip)

2. Instance Data Setup

Before running the optimizer, you must provide the QAP instances. By default, the project expects an instances/ folder in the root directory.

1. Create the directory: mkdir instances
2. Add .dat files (instances) and optionally .sln files (optimal solutions).

Data Format (.dat)

The instance files follow the standard QAPLIB format:

• The first line contains the problem size n.
• This is followed by two n x n matrices:
  • Flow Matrix: The weights between all pairs of facilities.
  • Distance Matrix: The distances between all pairs of locations.

Solution Format (.sln)

• The first line contains the problem size n and the optimal cost.
• The second line contains the optimal permutation of facilities to locations.

3. Centralized Configuration (config.toml)

The project is controlled via config.toml. Key settings include:

• [paths]: Define where instances are loaded from and where data/figures are saved.
• [instances]: Specify which instances to solve (the filenames without .dat). If the list is empty, the optimizer will process all .dat files in the instances_dir.
• [benchmarks]: Set num_runs for statistical significance and greedy_top_n for randomized heuristics.
• [discovery]: Configure high-repetition runs (ls_runs) for specific enabled_instances to analyze search space properties.
• [analysis]: Control plot aesthetics (style, resolution) and limits (e.g., discovery_max_restarts).

Usage

1. Running the Optimizer

The optimizer processes the instances and saves detailed statistics to the data/ directory.

cd qap_optimizer
cargo run --release

2. Generating Analysis & Visualizations

The analysis module processes the generated CSV files to produce summary tables in the console and analysis plots in the figures/ directory.

cd analysis
python -m venv .venv
# Activate venv: .\.venv\Scripts\activate (Win) or source .venv/bin/activate (Unix)
pip install -r requirements.txt
python main.py

Implemented Features

• Adaptive Timing: Random Search and Random Walk are automatically timed to match Local Search algorithms.
• Simulated Annealing: Includes adaptive initial temperature (95% acceptance) and step-wise cooling.
• Lam-like Annealing: Implementation of the adaptive Lam schedule for optimized acceptance rates.
• Tabu Search: Efficient implementation with tenure management ($N/4$), candidate lists, and aspiration criteria.
• Search Space Discovery: High-frequency data collection to analyze correlation between initial and final solution quality.
• Similarity Analysis: Hamming distance calculations between local and global optima.
• Expected Minima Prediction: Statistical estimation of the best expected quality after multiple restarts.