Posed over a century ago as a model of electronic structure within atoms, the so-called Thomson problem of determining the minimum-energy configuration of identical point charges in the unit sphere remains a well-known open problem in statistical physics. In the related Tammes problem, we seek an arrangement of points on a sphere which maximizes the smallest distance between any pair of points. Global optima are only known for very small instances of the Thomson and Tammes problems. In this paper, we present a branch-and-bound algorithm for these problems which exploits their geometry and dynamically eliminates symmetric subproblems. Our algorithm shows the global optimality within numerical tolerance of the putative solution to the 7-electron instance of the Thomson problem for the first time. For the Tammes problem, we recover the established results for instances with up to 13 points.

Abstract When computing bounds, spatial branch-and-bound algorithms often linearly outer approximate convex relaxations for non-convex expressions in order to capitalize on the efficiency and robustness of linear programming solvers. Considering that linear outer approximations sacrifice accuracy when approximating highly nonlinear functions and recognizing the recent advancements in the efficiency and robustness of available methods to solve optimization problems with quadratic objectives and constraints, we contemplate here the construction of quadratic outer approximations of twice-differentiable convex functions for use in deterministic global optimization. To this end, we present a novel cutting-plane algorithm that determines the tightest scaling parameter, $$\alpha $$ α , in the second-order Taylor series approximation quadratic underestimator proposed by Su et al. [25]. We use a representative set of convex functions extracted from optimization benchmark libraries to showcase–qualitatively and quantitatively–the tightness of the constructed quadratic underestimators and to demonstrate the overall computational efficiency of our algorithm. Furthermore, we extend our construction procedure to generate even tighter quadratic underestimators by allowing overestimation in infeasible polyhedral regions of optimization problems, as informed by the latter’s linear constraints.

Abstract Recent advances in the efficiency and robustness of algorithms solving convex quadratically constrained quadratic programming (QCQP) problems motivate developing techniques for creating convex quadratic relaxations that, although more expensive to compute, provide tighter bounds than their classical linear counterparts. In the first part of this two-paper series (Strahl et al. Constructing tight quadratic relaxations for global optimization: I. Outer-approximating twice-differentiable convex functions. Forthcoming, (2024)), we developed a cutting-plane algorithm to construct convex quadratic underestimators for twice-differentiable convex functions, which we extend here to address the case of non-convex difference-of-convex (d.c.) functions as well. Furthermore, we generalize our approach to consider a hierarchy of quadratic forms, thereby allowing the construction of even tighter underestimators. Utilizing a benchmark library of d.c. functions, we demonstrate noteworthy reduction in the hypervolume between our quadratic underestimators and linear ones constructed at the same points. Additionally, we construct convex QCQP relaxations at the root node of a spatial branch-and-bound tree for a set of systematically created d.c. optimization problems in up to four dimensions, and we show that our relaxations reduce the gap between the lower bound computed by the state-of-the-art global optimization solver BARON and the optimal solution by an excess of 90%, on average.

Abstract This paper reviews the literature on algorithms for solving bound-constrained mixed-integer derivative-free optimization problems and presents a systematic comparison of available implementations of these algorithms on a large collection of test problems. Thirteen derivative-free optimization solvers are compared using a test set of 267 problems. The testbed includes: (i) pure-integer and mixed-integer problems, and (ii) small, medium, and large problems covering a wide range of characteristics found in applications. We evaluate the solvers according to their ability to find a near-optimal solution, find the best solution among currently available solvers, and improve a given starting point. Computational results show that the ability of all these solvers to obtain good solutions diminishes with increasing problem size, but the solvers evaluated collectively found optimal solutions for 93% of the problems in our test set. The open-source solvers MISO and NOMAD were the best performers among all solvers tested. MISO outperformed all other solvers on large and binary problems, while NOMAD was the best performer on mixed-integer, non-binary discrete, small, and medium-sized problems.

This paper investigates the effectiveness of transfer learning based on information criteria. We propose a procedure that combines transfer learning with Mallows' Cp (TLCp) and prove that it outperforms the conventional Mallows' Cp criterion in terms of accuracy and stability. Our theoretical results indicate that, for any sample size in the target domain, the proposed TLCp estimator performs better than the Cp estimator by the mean squared error (MSE) metric {in the case of orthogonal predictors}, provided that i) the dissimilarity between the tasks from source domain and target domain is small, and ii) the procedure parameters (complexity penalties) are tuned according to certain explicit rules. Moreover, we show that our transfer learning framework can be extended to other feature selection criteria, such as the Bayesian information criterion. By analyzing the solution of the orthogonalized Cp, we identify an estimator that asymptotically approximates the solution of the Cp criterion in the case of non-orthogonal predictors. Similar results are obtained for the non-orthogonal TLCp. Finally, simulation studies and applications with real data demonstrate the usefulness of the TLCp scheme.

Whereas much research in the area of optimization is directed toward developing algorithms for optimization of feasible models, the diagnosis of infeasible models has not received as much attention. Identification of irreducible infeasible sets (IISs) can facilitate the process of correcting infeasible models. Several filtering algorithms have been proposed for IIS identification but efficient implementations are available only for linear programs. We propose a novel approach for IIS identification that is applicable to linear programs (LPs), nonlinear programs (NLPs), mixed-integer linear programs (MIPs), and mixed-integer nonlinear programs (MINLPs). The approach makes use of a deletion presolve procedure that exploits bounds tightening techniques to reduce the model to an infeasible set (IS) in a computationally efficient manner. The IS is subsequently reduced to an IIS by applying one of the currently available exact filtering algorithms for IIS identification. We implement the proposed deletion presolve along with four filtering algorithms for IIS identification within the global solver BARON. The effectiveness and usefulness of the proposed approach is demonstrated through computational experiments on a test set of 790 infeasible LPs, NLPs, MIPs, and MINLPs. Deletion presolve rapidly eliminates a large fraction of the problem constraints and speeds up the filtering algorithms by over forty times on average. Speedups of as high as 1,000 times are observed for some problems, while, for 40% of the test problems, the deletion presolve itself reduces the original model to an IIS.

Abstract This paper addresses the solution of bound-constrained optimization problems using algorithms that require only the availability of objective function values but no derivative information. We refer to these algorithms as derivative-free algorithms. Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied, and it has found renewed interest in recent time. Along with many derivative-free algorithms, many software implementations have also appeared. The paper presents a review of derivative-free algorithms, followed by a systematic comparison of 22 related implementations using a test set of 502 problems. The test bed includes convex and nonconvex problems, smooth as well as nonsmooth problems. The algorithms were tested under the same conditions and ranked under several criteria, including their ability to find near-global solutions for nonconvex problems, improve a given starting point, and refine a near-optimal solution. A total of 112,448 problem instances were solved. We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size. For the problems used in this study, , , and are better, on average, than other derivative-free solvers in terms of solution quality within 2,500 function evaluations. These global solvers outperform local solvers even for convex problems. Finally, , , and show superior performance in terms of refining a near-optimal solution.

MOTIVATION: The Basic Local Alignment Search Tool (BLAST) is one of the most widely used bioinformatics tools. The widespread impact of BLAST is reflected in over 53,000 citations that this software has received in the past two decades, and the use of the word 'blast' as a verb referring to biological sequence comparison. Any improvement in the execution speed of BLAST would be of great importance in the practice of bioinformatics, and facilitate coping with ever increasing sizes of biomolecular databases. RESULTS: Using a general-purpose graphics processing unit (GPU), we have developed GPU-BLAST, an accelerated version of the popular NCBI-BLAST. The implementation is based on the source code of NCBI-BLAST, thus maintaining the same input and output interface while producing identical results. In comparison to the sequential NCBI-BLAST, the speedups achieved by GPU-BLAST range mostly between 3 and 4. AVAILABILITY: The source code of GPU-BLAST is freely available at http://archimedes.cheme.cmu.edu/biosoftware.html.

The functional properties of a protein are strongly dependent on its structural conformation. The primary question addressed in this work is how to determine structural and therefore functional similarity from 3D protein structures. The approach we take relies on protein structure alignment, which elucidates functional protein relationships that are not depicted by the sequence.

MOTIVATION: The protein side-chain conformation problem is a central problem in proteomics with wide applications in protein structure prediction and design. Computational complexity results show that the problem is hard to solve. Yet, instances from realistic applications are large and demand fast and reliable algorithms. RESULTS: We propose a new global optimization algorithm, which for the first time integrates residue reduction and rotamer reduction techniques previously developed for the protein side-chain conformation problem. We show that the proposed approach simplifies dramatically the topology of the underlining residue graph. Computations show that our algorithm solves problems using only 1-10% of the time required by the mixed-integer linear programming approach available in the literature. In addition, on a set of hard side-chain conformation problems, our algorithm runs 2-78 times faster than SCWRL 3.0, which is widely used for solving these problems. AVAILABILITY: The implementation is available as an online server at http://eudoxus.scs.uiuc.edu/r3.html

The classical assignment problem matches n jobs to n machines in a way that minimizes total assignment costs. To allow for the possibility of diverting internal jobs outside the machine shop and accepting external jobs into the machine shop, we define the assignment problem with external interactions (APEX) as a linear assignment problem with a single unrestricted arc. A feasible solution of APEX may involve up to twice as many assignments as an assignment problem of the same size. An efficient sequential shortest path algorithm is developed for APEX. The algorithm uses initialization heuristics to obtain a dual feasible solution that satisfies the complementary slackness conditions with a partial set of assignments. Primal feasibility is then obtained through a shortest augmenting path algorithm that makes the remaining assignments. As APEX can be formulated as a minimum-cost network flow problem and as a standard assignment problem of larger size, we compare the proposed algorithm with state-of-the-art network flow and assignment approaches. The algorithm developed here has much smaller storage requirements than have alternative approaches. In addition, extensive computational results demonstrate that it is from 2 to 52 times faster. © 1997 John Wiley & Sons, Inc. Networks 30:171–185, 1997