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 条
  • [31] Penalized semidefinite programming for quadratically-constrained quadratic optimization
    Ramtin Madani
    Mohsen Kheirandishfard
    Javad Lavaei
    Alper Atamtürk
    Journal of Global Optimization, 2020, 78 : 423 - 451
  • [32] A Coordinate Ascent Method for Solving Semidefinite Relaxations of Non-convex Quadratic Integer Programs
    Buchheim, Christoph
    Montenegro, Maribel
    Wiegele, Angelika
    COMBINATORIAL OPTIMIZATION, ISCO 2016, 2016, 9849 : 110 - 122
  • [33] On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
    Engau, Alexander
    Anjos, Miguel F.
    Vannelli, Anthony
    OPTIMIZATION METHODS & SOFTWARE, 2012, 27 (03) : 539 - 559
  • [34] BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems
    Krislock, Nathan
    Malick, Jerome
    Roupin, Frederic
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2017, 43 (04):
  • [35] Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
    Lee, Timothy
    Mitchell, John E.
    DISCRETE OPTIMIZATION, 2017, 24 : 152 - 169
  • [36] A dynamical systems analysis of semidefinite programming with application to quadratic optimization with pure quadratic equality constraints
    Orsi, RJ
    Mahony, RE
    Moore, JB
    APPLIED MATHEMATICS AND OPTIMIZATION, 1999, 40 (02) : 191 - 210
  • [37] A global continuation algorithm for solving binary quadratic programming problems
    Pan, Shaohua
    Tan, Tao
    Jiang, Yuxi
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2008, 41 (03) : 349 - 362
  • [38] A global continuation algorithm for solving binary quadratic programming problems
    Shaohua Pan
    Tao Tan
    Yuxi Jiang
    Computational Optimization and Applications, 2008, 41 : 349 - 362
  • [39] Some advances on Lovasz-Schrijver semidefinite programming relaxations of the fractional stable set polytope
    Bianchi, S.
    Escalante, M.
    Nasini, G.
    Tuncel, L.
    DISCRETE APPLIED MATHEMATICS, 2014, 164 : 460 - 469
  • [40] Solving unconstrained binary quadratic programming problem by global equilibrium search
    Shylo V.P.
    Shylo O.V.
    Cybernetics and Systems Analysis, 2011, 47 (6) : 889 - 897
12345