Editing Protein design (section)

====Integer linear programming====
{{Further|Linear programming#Integer unknowns|Integer programming}}

The problem of optimizing <var>E<sub>T</sub></var> (Equation ({{EquationNote|1}})) can be easily formulated as an [[integer linear program]] (ILP).<ref name="kingsford05" /> One of the most powerful formulations uses binary variables to represent the presence of a rotamer and edges in the final solution, and constraints the solution to have exactly one rotamer for each residue and one pairwise interaction for each pair of residues:

: <math>\ \min \sum_{i}\sum_{r_i} E_i(r_i)q_{i}(r_i) + \sum_{j\ne i}\sum_{r_j} E_{ij}(r_i, r_j)q_{ij}(r_i, r_j) \, </math>

s.t.

: <math>\sum_{r_i} q_{i}(r_i) = 1, \ \forall i</math>

: <math>\sum_{r_j} q_{ij}(r_i,r_j) = q_{i}(r_i), \forall i, r_i, j </math>

: <math>q_i, q_{ij} \in \{0,1\}</math>

ILP solvers, such as [[CPLEX]], can compute the exact optimal solution for large instances of protein design problems. These solvers use a [[linear programming relaxation]] of the problem, where <var>q<sub>i</sub></var> and <var>q<sub>ij</sub></var> are allowed to take continuous values, in combination with a [[branch and cut]] algorithm to search only a small portion of the conformation space for the optimal solution. ILP solvers have been shown to solve many instances of the side-chain placement problem.<ref name="kingsford05">{{cite journal|last=Kingsford|first=CL|author2=Chazelle, B |author3=Singh, M |title=Solving and analyzing side-chain positioning problems using linear and integer programming.|journal=Bioinformatics|date=April 1, 2005|volume=21|issue=7|pages=1028–36|pmid=15546935|doi=10.1093/bioinformatics/bti144|doi-access=free}}</ref>