pylibmgm.QAPSolver

class pylibmgm.QAPSolver

Quadratic Assignment Problem solver for graph matching.

Solves pairwise graph matching problems using the Fusion Moves solver [1].

References

Methods

`__init__`(model)	Initialize QAP solver.
`run`([verbose])	Run the QAP solver.

Attributes

Name	Type	Description
default_run_settings	RunSettings	Default run settings. Modify to globally affect new instances and MGM algorithms.
default_stopping_criteria	StoppingCriteria	Default stopping criteria. Modify to globally affect new instances and MGM algorithms.
libmpopt_seed	int	Random seed for the Fusion Moves solver.
run_settings	RunSettings	Run configuration settings.
stopping_criteria	StoppingCriteria	Stopping criteria for the solver.

RunSettings

Configuration for the QAP solver run parameters.

Attribute	Type	Description
`batch_size`	`int`	Number of steps per batch (default: 10).
`greedy_generations`	`int`	Number of greedy generation per step (default: 10).

StoppingCriteria

Stopping criteria for the QAP solver.

Set a hard upper limit with max_batches. Set a relative improvement limit using p and k. Compares upper first, middle and last upperbound (ub) obtained w.r.t. batch iteration. Optimization is stopped, if for k consecutive iterations it holds:

abs(last_ub - middle_ub) <= p * abs(middle_ub - first_ub)).

See Sec 5.3 of [2] for details.

Attribute	Type	Description
`p`	`int`	Convergence threshold parameter (default: 0.6).
`k`	`int`	Number of consecutive iterations the convergence criteria has to be fulfilled.
`max_batches`	`int`	Maximum number of batches to run.

__init__(model: pylibmgm.GmModel) → None

Initialize QAP solver.

Parameters:: model (GmModel) – The pairwise graph matching model to solve.

run(verbose: bool = False) → pylibmgm.GmSolution

Run the QAP solver.

Parameters:: verbose (bool, optional) – Enable verbose output (default: False).
Returns:: Optimized solution.
Return type:: GmSolution