Computational performance evaluation of two integer linear programming models for the minimum common string partition problem

DOI10.1007/S11590-015-0921-4zbMATH Open1339.90236arXiv1501.02388OpenAlexW1567328788MaRDI QIDQ5963700FDOQ5963700

Günther R. Raidl, Christian Blum

Publication date: 23 February 2016

Published in: Optimization Letters (Search for Journal in Brave)

Abstract: In the minimum common string partition (MCSP) problem two related input strings are given. "Related" refers to the property that both strings consist of the same set of letters appearing the same number of times in each of the two strings. The MCSP seeks a minimum cardinality partitioning of one string into non-overlapping substrings that is also a valid partitioning for the second string. This problem has applications in bioinformatics e.g. in analyzing related DNA or protein sequences. For strings with lengths less than about 1000 letters, a previously published integer linear programming (ILP) formulation yields, when solved with a state-of-the-art solver such as CPLEX, satisfactory results. In this work, we propose a new, alternative ILP model that is compared to the former one. While a polyhedral study shows the linear programming relaxations of the two models to be equally strong, a comprehensive experimental comparison using real-world as well as artificially created benchmark instances indicates substantial computational advantages of the new formulation.

Full work available at URL: https://arxiv.org/abs/1501.02388

zbMATH Keywords

integer linear programmingbioinformaticsminimum common string partitioncomputational comparison

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• Algorithms and Computation
• The string edit distance matching problem with moves
• Minimum common string partition revisited
• Mathematical programming strategies for solving the minimum common string partition problem
• Quick Greedy Computation for Minimum Common String Partitions
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Computing a longest common subsequence for a set of strings
• The greedy algorithm for edit distance with moves
• Title not available (Why is that?)
• Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Mathematical Foundations of Computer Science 2005
• Solving the minimum common string partition problem with the help of ants

Cited In (3)

• Minimum common string partition: on solving large‐scale problem instances
• On the role of metaheuristic optimization in bioinformatics
• ILP-based reduced variable neighborhood search for large-scale minimum common string partition

Uses Software

• CPLEX

   Recommendations

• Mathematical programming strategies for solving the minimum common string partition problem 👍 👎
• Minimum common string partition: on solving large‐scale problem instances 👍 👎
• Minimum common string partition problem: hardness and approximations 👍 👎
• Algorithms and Computation 👍 👎
• ILP-based reduced variable neighborhood search for large-scale minimum common string partition 👍 👎
• Exponential and polynomial time algorithms for the minimum common string partition problem 👍 👎
• Computational comparison on the partitioning strategies in multiple choice integer programming 👍 👎
• An improved approximation algorithm for the minimum common integer partition problem 👍 👎
• An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem 👍 👎

This page was built for publication: Computational performance evaluation of two integer linear programming models for the minimum common string partition problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963700)