procrustes.kopt

K-opt (Greedy) Heuristic Module.

procrustes.kopt.kopt_heuristic_single(fun: Callable, p0: ndarray, k: int = 3, tol: float = 1e-08) → Tuple[ndarray, float]

Find a locally-optimal permutation matrix using the k-opt (greedy) heuristic.

$$\underbrace{\text{min}}_{\left\{\mathbf{P} \left| {[\mathbf{P}]_{ij} \in \{0, 1\} \atop \sum_{i=1}^n [\mathbf{P}]_{ij} = \sum_{j=1}^n [\mathbf{P}]_{ij} = 1} \right. \right\}} f(\mathbf{P})$$

All possible 2-, ..., k-fold column-permutations of the initial permutation matrix are tried to identify one which gives a lower value of objective function $f$. Starting from this updated permutation matrix, the process is repeated until no further k-fold column-reordering of a given permutation matrix lower the objective function.

Parameters:

• fun (callable) -- The objective function $f$ to be minimized.

• p0 (ndarray) -- The 2D-array permutation matrix representing the initial guess for $\mathbf{P}$.

• k (int, optional) -- The order of the permutation. For example, k=3 swaps all possible 3-permutations.

• tol (float, optional) -- When value of the objective function is less than given tolerance, the algorithm stops.

Returns:

• p_opt (ndarray) -- The locally-optimal permutation matrix $\mathbf{P}$ (i.e., solution).

• f_opt (float) -- The locally-optimal value of objective function given by $\text{fun(p_opt)}$.

procrustes.kopt.kopt_heuristic_double(fun: Callable, p1: ndarray, p2: ndarray, k: int = 3, tol: float = 1e-08) → Tuple[ndarray, ndarray, float]

Find locally-optimal permutation matrices using the k-opt (greedy) heuristic.

$$\underbrace{\text{arg min}}_{ \left\{ {\mathbf{P}_1, \mathbf{P}_2} \left| {{[\mathbf{P}_1]_{ij} \in \{0, 1\} \atop [\mathbf{P}_2]_{ij} \in \{0, 1\}} \atop {\sum_{i=1}^m [\mathbf{P}_1]_{ij} = \sum_{j=1}^m [\mathbf{P}_1]_{ij} = 1 \atop \sum_{i=1}^n [\mathbf{P}_2]_{ij} = \sum_{j=1}^n [\mathbf{P}_2]_{ij} = 1}} \right. \right\}} f(\mathbf{P}_1, \mathbf{P}_2)$$

All possible 2-, ..., k-fold permutations of the initial permutation matrices are tried to identify ones which give a lower value of objective function $f$. This corresponds to row-swaps for $\mathbf{ P}_1$ and column-swaps for $\mathbf{ P}_2$. Starting from these updated permutation matrices, the process is repeated until no further k-fold reordering of either permutation matrix lower the objective function.

Parameters:

• fun (callable) -- The objective function $f$ to be minimized.

• p1 (ndarray) -- The 2D-array permutation matrix representing the initial guess for $\mathbf{P}_1$.

• p2 (ndarray) -- The 2D-array permutation matrix representing the initial guess for $\mathbf{P}_2$.

• k (int, optional) -- The order of the permutation. For example, k=3 swaps all possible 3-permutations.

• tol (float, optional) -- When value of the objective function is less than given tolerance, the algorithm stops.

Returns:

• p1_opt (ndarray) -- The locally-optimal permutation matrix $\mathbf{P}_1$.

• p2_opt (ndarray) -- The locally-optimal permutation matrix $\mathbf{P}_2$.

• f_opt (float) -- The locally-optimal value of objective function given by $\text{fun(p1_opt, p2_opt)}$.