This paper considers the NP-hard protein side-chain positioning (SCP) problem, an important final task of protein structure prediction. We formulate the SCP as an integer quadratic program and derive its doubly nonnegative (DNN) (convex) relaxation. Strict feasibility fails for this DNN relaxation. We apply facial reduction to regularize the problem. This gives rise to a natural splitting of the variables. We then use a variation of the Peaceman-Rachford splitting method to solve the DNN relaxation. The resulting relaxation and rounding procedures provide strong approximate solutions. Empirical evidence shows that almost all our instances of this NP-hard SCP problem, taken from the Protein Data Bank, are solved to provable optimality. Our large problems correspond to solving a DNN relaxation with 2,883,601 binary variables to provable optimality. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This research was supported by the Natural Sciences and Engineering Research Council of Canada [Grants 50503-10827 and RGPIN-2016-04660]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0094 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0094 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Splitting methods in optimization arise when one can divide an optimization problem into two or more simpler subproblems. They have proven particularly successful for relaxations of problems involving discrete variables. We revisit and strengthen splitting methods for solving doubly nonnegative relaxations of the particularly difficult, NP-hard quadratic assignment problem. We use a modified restricted contractive splitting method approach. In particular, we show how to exploit redundant constraints in the subproblems. Our strengthened bounds exploit these new subproblems and new dual multiplier estimates to improve on the bounds and convergence results in the literature. Summary of Contribution: In our paper, we consider the quadratic assignment problem (QAP). It is one of the fundamental combinatorial optimization problems in the fields of optimization and operations research and includes many fundamental applications. We revisit and strengthen splitting methods for solving doubly nonnegative (DNN) relaxation of the QAP. We use a modified restricted contractive splitting method. We obtain strengthened bounds from improved lower and upper bounding techniques, and in fact, we solve many of these NP-hard problems to (provable) optimality, thus illustrating both the strength of the DNN relaxation and our new bounding techniques.

We present several solution techniques for the noisy single source localization problem, i.e. the Euclidean distance matrix completion problem with a single missing node to locate under noisy data. For the case that the sensor locations are fixed, we show that this problem is implicitly convex, and we provide a purification algorithm along with the SDP relaxation to solve it efficiently and accurately . For the case that the sensor locations are relaxed, we study a model based on facial reduction. We present several approaches to solve this problem efficiently, and we compare their performance with existing techniques in the literature. Our tools are semidefinite programming , Euclidean distance matrices , facial reduction , and the generalized trust region subproblem . We include extensive numerical tests.

“Elastic network interpolation (ENI)” generates a series of transitional conformations between two protein conformations by interpolating inter-atomic distances. A group of atoms that maintain their inter-atomic distances while moving concurrently in a protein is known as a rigid cluster; “rigid cluster ENI” is the interpolation of the rotations and translations of rigid clusters. Rank 3 positive semidefinite (PSD) matrix manifolds have faces that are defined by these rigid clusters. This facial structure strongly suggests that these matrix manifolds are a natural choice for modelling rigid cluster transitions. In this paper, we show that rigid cluster ENI can be formulated as a facially reduced rank 3 PSD matrix manifold optimization problem.

Determination of a protein's structure can facilitate an understanding of how the structure changes when that protein combines with other proteins or smaller molecules. In this paper we study a semidefinite programming (SDP) relaxation of the (NP-hard) side chain positioning problem presented in Chazelle et al [Chazelle B, Kingsford C, Singh M (2004) A semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Comput. 16:380-392]. We show that the Slater constraint qualification (strict feasibility) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the SDP. In fact, after applying facial reduction, we have a smaller problem that is more stable both in theory and in practice. We include cutting planes to improve the rounded SDP approximate solutions.

Telecommunication companies, such as Internet and cellular service providers, are seeing rapid and uncertain growth of amount of traffic routed through their networks. It has become a challenge for these companies to make optimal decisions for equipment purchase that simultaneously satisfy the uncertain future demand while minimizing investment cost. This paper presents a decision-making framework for installing the required equipment into the networks while in the uncertain environment. The framework is based on new multi-stage stochastic programming mathematical models that capture the complexity of the individual Central Office (CO) decision-making process. The models are solved using the online NEOS server. Two examples are presented to illustrate the procedure. The optimization model also addresses the equipment pricing problem, i.e., what premium is worth paying for shorter installation times.

Semidefinite programming (SDP) is currently one of the most active areas of research in optimization. SDP has attracted researchers from a wide variety of areas because of its theoretical and numerical elegance as well as its wide applicability. In this paper we present a survey of two major areas of application for SDP, namely discrete optimization and matrix completion problems. In the first part of this paper we present a recipe for finding SDP relaxations based on adding redundant constraints and using Lagrangian relaxation. We illustrate this with several examples. We first show that many relaxations for the max-cut problem (MC) are equivalent to both the Lagrangian and the well-known SDP relaxation. We then apply the recipe to obtain new strengthened SDP relaxations for MC as well as known SDP relaxations for several other hard discrete optimization problems. In the second part of this paper we discuss two completion problems, the positive semidefinite matrix completion problem and the Euclidean distance matrix completion problem. We present some theoretical results on the existence of such completions and then proceed to the application of SDP to find approximate completions. We conclude this paper with a new application of SDP to find approximate matrix completions for large and sparse instances of Euclidean distance matrices.