Editing Protein design (section)

====Message-passing based approximations to the linear programming dual====
ILP solvers depend on linear programming (LP) algorithms, such as the [[Simplex algorithm|Simplex]] or [[barrier function|barrier]]-based methods to perform the LP relaxation at each branch. These LP algorithms were developed as general-purpose optimization methods and are not optimized for the protein design problem (Equation ({{EquationNote|1}})). In consequence, the LP relaxation becomes the bottleneck of ILP solvers when the problem size is large.<ref name=yanover06>{{cite journal|last=Yanover|first=Chen|author2=Talya Meltzer |author3=Yair Weiss |title=Linear Programming Relaxations and Belief Propagation – An Empirical Study|journal=Journal of Machine Learning Research|year=2006|volume=7|pages=1887–1907}}</ref> Recently, several alternatives based on [[belief propagation|message-passing algorithms]] have been designed specifically for the optimization of the LP relaxation of the protein design problem. These algorithms can approximate both the [[Duality (optimization)|dual]] or the [[Duality (optimization)|primal]] instances of the integer programming, but in order to maintain guarantees on optimality, they are most useful when used to approximate the dual of the protein design problem, because approximating the dual guarantees that no solutions are missed.  Message-passing based approximations include the ''tree reweighted max-product message passing'' algorithm,<ref>{{cite journal|last=Wainwright|first=Martin J |author2=Tommi S. Jaakkola |author3=Alan S. Willsky|title=MAP estimation via agreement on trees: message-passing and linear programming.|journal=IEEE Transactions on Information Theory|year=2005|pages=3697–3717|doi=10.1109/tit.2005.856938|volume=51|issue=11 |citeseerx=10.1.1.71.9565 |s2cid=10007532 }}</ref><ref>{{cite journal|last=Kolmogorov|first=Vladimir|title=Convergent tree-reweighted message passing for energy minimization.|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=October 28, 2006|volume=28|issue=10|pages=1568–1583|doi=10.1109/TPAMI.2006.200|pmid=16986540|s2cid=8616813}}</ref> and the ''message passing linear programming'' algorithm.<ref>{{cite journal|last=Globerson|first=Amir|author2=Tommi S. Jaakkola |title=Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations.|journal=Advances in Neural Information Processing Systems|year=2007}}</ref>