The Problem Verifier

The verifier enforces a few methods that need to be implemented. We give a short overview over the expected behavior of an implementation.

verify_semantics_of_instance(self, instance: any, instance_size: int) -> bool

The verifier.verify_semantics_of_instance is the first method of the verifier that will be called by the match. It is meant to check if there are any semantic issues in the instance that make it infeasible for passing to a solver - it should then return False. Otherwise, return True.

In the default implementation, it simply checks whether instance is empty and returns False in this case and True otherwise. This method can be optionally implemented, as many problems just need the default implementation.

A usage example would be a problem in which a group has to find a structure inside a planar graph. The verifier.verify_semantics_of_instance method would then check if the instance actually encodes a planar graph.

---

verify_semantics_of_solution(self, solution: any, instance_size: int, solution_type: bool)-> bool

This method is only called if the verifier.verify_semantics_of_instance method returned True.

In the verifier.verify_semantics_of_solution method, a solution is checked if it is semantically valid on its own and returns True in this case, False otherwise.

In the default implementation, it simply checks whether solution is empty and returns False in this case and True otherwise. This method can be optionally implemented, as many problems just need the default implementation.

The solution_type encodes whether the given solution is a certificate solution (True) or a solver solution (False). This information can be used if the problem design treats the solutions of the generator and the solver differently, e.g. by giving the solver solution a higher error tolerance.

A usage example for this method is the biclique problem, in which a solver is to determine two node sets set1 and set2 which form a bipartite clique. Here, we need to check whether these two node sets are disjoint and if one of them is empty. This check has to be done independent of any concrete instance.

---

verify_solution_against_instance(self, instance: any, solution: any, instance_size: int, solution_type: bool) -> bool

This method is only called if the verifier.verify_semantics_of_solution method returned True.

The verifier.verify_solution_against_instance method is the heart of the verifier. It checks whether a given solution is valid for a given instance, be it the certificate solution or the solver solution against the instance. This method should return True only if the solution is meeting all requirements on the given instance.

The solution_type encodes whether the given solution is a certificate solution (True) or a solver solution (False). This information can be used if the problem design treats the solutions of the generator and the solver differently, e.g. by giving the solver solution a higher error tolerance.

---

calculate_approximation_ratio(self, instance: any, instance_size: int, generator_solution: any, solver_solution: any) -> float

This method is only called if the verifier.verify_solution_against_instance method returned True.

As the final step of a fight, one still has to check how good the solution of a solver is compared to that of a generator. The verifier.calculate_approximation_ratio method should calculate and return an approximation ratio of the solver solution compared to the generator solution.

If a problem is not approximable, this method should simply return 1.0.