Zörnig Peter
Department of Statistics, Institute of Exact Sciences, University of Brasília , Brasília, Brazil .
J Comput Biol. 2015 Aug;22(8):729-42. doi: 10.1089/cmb.2014.0265. Epub 2014 Dec 19.
We present integer programming models for some variants of the farthest string problem. The number of variables and constraints is substantially less than that of the integer linear programming models known in the literature. Moreover, the solution of the linear programming-relaxation contains only a small proportion of noninteger values, which considerably simplifies the rounding process. Numerical tests have shown excellent results, especially when a small set of long sequences is given.
我们针对最远字符串问题的一些变体提出了整数规划模型。变量和约束的数量大大少于文献中已知的整数线性规划模型。此外，线性规划松弛的解中只有一小部分非整数值，这极大地简化了舍入过程。数值测试显示了出色的结果，特别是当给出一小组长序列时。
