An improved integer linear programming formulation for the closest 0-1 string problem. (April 2017)

• Record Type: Journal Article
• Authors: Arbib, Claudio; Servilio, Mara; Ventura, Paolo
• Is Part Of: Computers & operations research. Volume 80(2017)
• Page Start: 94
• Page End: 100
• Publication Date: 2017-04
• Subjects: Closest string problem -- Branch-and-cut -- Continuous relaxation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.11.019
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: An integer linear programming formulation of the Closest String Problem (CSP) is proposed. An enforcement of the polyhedron of the CSP continuous relaxation via the rst closure of { 0, 1 2 } -Chvátal-Gomory cuts is given. A linear-time algorithm for separating a fractional optimum in the polyhedron via a { 0, 1 2 } -Chvátal-Gomory cut is implemented within a branchand-cut scheme. The algorithm is tested on a large set of signi cant 0-1 CSP instances, including problems from the literature. Experiments in the binary case show an outstanding improvement of performance, with mean CPU time reduced by various orders of magnitude. Abstract: The Closest String Problem (CSP) calls for finding an n -string that minimizes its maximum Hamming distance from m given n -strings. Recently, integer linear programs (ILP) have been successfully applied within heuristics to improve efficiency and effectiveness. We consider an ILP for the binary case (0-1 CSP) that updates the previous formulations and solve it by branch-and-cut. The method separates in polynomial time the first closure of { 0, 1 2 } -Chvátal-Gomory cuts and can either be used stand-alone to find optimal solutions, or as a plug-in to improve heuristics based on the exact solution of reduced problems. Due to the parity structure of the right-hand side, the impressive performances obtained with this method in the binary case cannot be directly replicated in the general case.