Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology

Management Science

Associated organisational units

Text available via DOI:

https://doi.org/10.1142/S0217595914500225
Final published version

Keywords

Combinatorial optimization, integer programming, binary quadratic programming, semidefinite programming, doubly non-negative relaxation, computational biology, protein folding, protein similarity, rotamer assignment , contact map overlap

View graph of relations

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology. / Engau, Alexander.
In: Asia-Pacific Journal of Operational Research, Vol. 31, No. 4, 1450022, 27.03.2014.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Bibtex

@article{c8d9944f4e9c42b29d3b642bbb9cc1e0,

title = "Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology",

abstract = "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.",

keywords = "Combinatorial optimization, integer programming, binary quadratic programming, semidefinite programming, doubly non-negative relaxation, computational biology, protein folding, protein similarity, rotamer assignment , contact map overlap ",

author = "Alexander Engau",

year = "2014",

month = mar,

day = "27",

doi = "10.1142/S0217595914500225",

language = "English",

volume = "31",

journal = "Asia-Pacific Journal of Operational Research",

issn = "0217-5959",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "4",

}

RIS

TY - JOUR

T1 - Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology

AU - Engau, Alexander

PY - 2014/3/27

Y1 - 2014/3/27

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - integer programming

KW - binary quadratic programming

KW - semidefinite programming

KW - doubly non-negative relaxation

KW - computational biology

KW - protein folding

KW - protein similarity

KW - rotamer assignment

KW - contact map overlap

U2 - 10.1142/S0217595914500225

DO - 10.1142/S0217595914500225

M3 - Journal article

VL - 31

JO - Asia-Pacific Journal of Operational Research

JF - Asia-Pacific Journal of Operational Research

SN - 0217-5959

IS - 4

M1 - 1450022

ER -

Research

Associated organisational units

Links

Text available via DOI:

Keywords