{'fraction_non_alphanumeric': 0.038348082595870206, 'fraction_numerical': 0.0022123893805309734, 'mean_word_length': 4.471774193548387, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Branch-and-Bound Algorithm for the Closest String Problem

We are concerned with the Closest String Problem (CSP), which can be defined as follows: given a finite set S = {s, s, . . . , s} of strings, each string with length m, find a center string t of length m minimizing d, such that for every string s ∈ S, dH(t, s ) ≤ d. By dH(t, s ) we mean the Hamming distance between t and s. This problem has applications in Molecular Biology and Coding Theory. The CSP is known to be NP-hard [2]. Even though there are good approximation algorithms for this problem (including a PTAS [3]), and exact algorithms for instances with constant difference [1], there are no studies reporting on the quality of integer programming formulations for the general case, when the maximum distance d between a solution and the strings in S is variable. We propose three integer programming formulations and prove some containment relations among them A heuristic algorithm is also provided, which allows us to find good upper bounds on the value of an optimal solution. We report computational results of a branch-and-bound algorithm based on the IP formulations, and of the heuristic, on a set of instances representative of real applications. These results show that it is possible to solve CSP instances of moderate size to near optimality using optimization techniques.