procrustes.kopt

K-opt (Greedy) Heuristic Module.

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

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: numpy.ndarray, p2: numpy.ndarray, k: int = 3, tol: float = 1e-08) Tuple[numpy.ndarray, numpy.ndarray, float][source]

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)}$$.