SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY

被引：0
|
作者：
Engau, Alexander [1 ,2 ]
机构：
[1] Univ Colorado, Dept Math & Stat Sci, Denver, CO 80217 USA
[2] China Agr Univ, Int Coll Beijing, Beijing 100083, Peoples R China
来源：
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2014年 / 31卷 / 04期
关键词：
Combinatorial optimization; integer programming; binary quadratic programming; semidefinite programming; doubly non-negative relaxation; computational biology; protein folding; protein similarity; rotamer assignment; contact map overlap; IMPROVED APPROXIMATION ALGORITHMS; INTERIOR-POINT METHODS; MAX-K-CUT; STABILITY NUMBER; GRAPH; FORMULATIONS; SELECTION; RECIPE;
D O I：
10.1142/S0217595914500225
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We present two recent integer programming models in molecular biology and study practical reformulations to compute solutions to some of these problems. In extension of previously tested linearization techniques, we formulate corresponding semidefinite relaxations and discuss practical rounding strategies to find good feasible approximate solutions. Our computational results highlight the possible advantages and remaining challenges of this approach especially on large-scale problems.
引用
收藏
页数：18
相关论文
共 50 条
12345