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 条
  • [41] Feasible direction algorithm for solving the SDP relaxations of quadratic {-1,1} programming problems
    Liu, HW
    Wang, XH
    Liu, SY
    OPTIMIZATION METHODS & SOFTWARE, 2004, 19 (02) : 125 - 136
  • [42] Solving the maximum vertex weight clique problem via binary quadratic programming
    Wang, Yang
    Hao, Jin-Kao
    Glover, Fred
    Lu, Zhipeng
    Wu, Qinghua
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (02) : 531 - 549
  • [43] Perturbation Based Search Method for Solving Unconstrained Binary Quadratic Programming Problem
    Solayappan, Muthu
    Ng, Kien Ming
    Poh, Kim Leng
    PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, VOL 27, 2008, 27 : 185 - 191
  • [44] Solving the maximum vertex weight clique problem via binary quadratic programming
    Yang Wang
    Jin-Kao Hao
    Fred Glover
    Zhipeng Lü
    Qinghua Wu
    Journal of Combinatorial Optimization, 2016, 32 : 531 - 549
  • [45] Complexity and nonlinear semidefinite programming reformulation of l1-constrained nonconvex quadratic optimization
    Hsia, Yong
    OPTIMIZATION LETTERS, 2014, 8 (04) : 1433 - 1442
  • [46] Solving Quadratic Unconstrained Binary Optimization with Collaborative Spiking Neural Networks
    Fang, Yan
    Lele, Ashwin Sanjay
    2022 IEEE INTERNATIONAL CONFERENCE ON REBOOTING COMPUTING, ICRC, 2022, : 84 - 88
  • [47] Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology
    Brown, Hannah
    Zuo, Lei
    Gusfield, Dan
    ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2020), 2020, 12099 : 63 - 76
  • [48] Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
    Hayato Waki
    Maho Nakata
    Masakazu Muramatsu
    Computational Optimization and Applications, 2012, 53 : 823 - 844
  • [49] Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
    Waki, Hayato
    Nakata, Maho
    Muramatsu, Masakazu
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2012, 53 (03) : 823 - 844
  • [50] On some features of quadratic unconstrained binary optimization with random coefficients
    Isopi, Marco
    Scoppola, Benedetto
    Troiani, Alessio
    BOLLETTINO DELLA UNIONE MATEMATICA ITALIANA, 2024, : 615 - 635
12345