Algorithm for approximately solving quadratic assignment problems.
Project description
Fast Approximate Quadratic Assignment Problem Solver
This is a Python implementation of an algorithm for approximately solving quadratic assignment problems described in
Joshua T. Vogelstein and John M. Conroy and Vince Lyzinski and Louis J. Podrazik and Steven G. Kratzer and Eric T. Harley and Donniell E. Fishkind and R. Jacob Vogelstein and Carey E. Priebe (2012) Fast Approximate Quadratic Programming for Large (Brain) Graph Matching. arXiv:1112.5507.
It solves
min𝑃∈𝒫<𝐹, 𝑃𝐷𝑃𝖳>
where 𝐷, 𝐹 ∈ ℝ𝑛×𝑛, 𝒫 is the set of 𝑛×𝑛 permutation matrices and <., .> denotes the Frobenius inner product.
The implementation employs the Frank–Wolfe algorithm.
Example
import numpy as np
from faqap import minimize
# Make runs deterministic, descent origins are chosen randomly by default.
np.random.seed(123456789)
D = np.array(
[
[0, 0, 0, -4],
[0, 0, -3, 0],
[0, -2, 0, 0],
[-1, 0, 0, 0]
],
dtype=np.float64
)
F = np.array(
[
[0, 0, 0, +1],
[0, 0, +2, 0],
[0, +3, 0, 0],
[+4, 0, 0, 0]
],
dtype=np.float64
)
solution_permutation = minimize(D=D, F=F, descents_count=1).x
# Expected is the permutation reversing elements.
print("solution permutation =", solution_permutation)
Output
solution permutation = [3 2 1 0]
Install
pip install faqap
Dependencies
- Python (>=3.5)
- NumPy (>=1.10)
- SciPy (>=1.4)
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distribution
Hashes for faqap-0.2.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 12a8e954be2f99cefdff28b3d854b3e5dc6535d81b388a128d5f510f30ab817f |
|
MD5 | 7e15cd18af4532fa63dc4305a21135c8 |
|
BLAKE2b-256 | d1f340c2f91ee3142734f3346f7a0363ad8bb0f94f48880330e86f6ffbc80716 |