title: Improving the efficiency of branch-and-bound complete-search NMR assignment using the symmetry of molecules and spectra.
abstract: Nuclear magnetic resonance (NMR) assignment of small molecules is presented as a typical example of a combinatorial optimization problem in chemical physics. Three strategies that help improve the efficiency of solution search by the branch and bound method are presented: 1. reduction of the size of the solution space by resort to a condensed structure formula, wherein symmetric nuclei are grouped together; 2. partitioning of the solution space based on symmetry, that becomes the basis for an efficient branching procedure; and 3. a criterion of selection of input restrictions that leads to increased gaps between branches and thus faster pruning of non-viable solutions. Although the examples chosen to illustrate this work focus on small-molecule NMR assignment, the results are generic and might help solving other combinatorial optimization problems.
authors.affiliation: Ecole Polytechnique Féderale de Lausanne (EPFL), CH1-1015 Lausanne, Switzerland.
authors.forename: Andrés
authors.initials: A
authors.lastname: Bernal
authors.affiliation: Chemistry Department, Universidad del Valle, AA 25360 Cali, Valle, Colombia.
authors.forename: Andrés M
authors.initials: AM
authors.lastname: Castillo
authors.affiliation: MindLab Research Group, Universidad Nacional de Colombia, Bogotá D.C., Colombia.
authors.forename: Fabio
authors.initials: F
authors.lastname: González
authors.affiliation: Ecole Polytechnique Féderale de Lausanne (EPFL), CH1-1015 Lausanne, Switzerland.
authors.forename: Luc
authors.initials: L
authors.lastname: Patiny
authors.affiliation: DARMN Research Group, Universidad del Valle, Cali, Valle, Colombia.
authors.forename: Julien
authors.initials: J
authors.lastname: Wist