Capitalizing on <Emphasis Type="Italic">live</Emphasis> variables: new algorithms for efficient Hessian computation via automatic differentiation

We revisit an algorithm [called Edge Pushing (EP)] for computing Hessians using Automatic Differentiation (AD) recently proposed by Gower and Mello (Optim Methods Softw 27(2): 233–249, 2012). Here we give a new, simpler derivation for the EP algorithm based on the notion of live variables from data-flow analysis in compiler theory and redesign the algorithm with close attention to general applicability and performance. We call this algorithm Livarh and develop an extension of Livarh that incorporates preaccumulation to further reduce execution time—the resulting algorithm is called Livarhacc. We engineer robust implementations for both algorithms Livarh and Livarhacc within ADOL-C, a widely-used operator overloading based AD software tool. Rigorous complexity analyses for the algorithms are provided, and the performance of the algorithms is evaluated using a mesh optimization application and several kinds of synthetic functions as testbeds. The results show that the new algorithms outperform state-of-the-art sparse methods (based on sparsity pattern detection, coloring, compressed matrix evaluation, and recovery) in some cases by orders of magnitude. We have made our implementation available online as open-source software and it will be included in a future release of ADOL-C.     

A fast circuit module for digital systems

This paper describes anAnd-or-Invert module developed for theOldap computer designed and being built at the Tata Institute of Fundamental Research. To obtain the maximum speed out of available transistors, the circuit makes use of antisaturation and anti-cut-off techniques. The effect of different components on the transient response of the circuit is described. Detailed results of DC tolerance analysis and noise margins are included. The module which uses only indigenous components should be useful in any general digital system where speed is an important requirement.     

Solving linear optimization over arithmetic constraint formula

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.     

Generating feasible strategies in nuclear emergencies—a constraint satisfaction problem

RODOS is a Real-time On-line DecisiOn Support system intended for use throughout a nuclear emergency, extending into the longer term. In this paper we concentrate on the early phases in which decisions on sheltering and evacuation have to be taken quickly and under many pressures. RODOS is designed to assist off-site emergency management by formulating and structuring the evaluation of possible combinations of countermeasures. Because there can be very many such combinations to be evaluated, an expert system has been developed to eliminate those that do not satisfy certain constraints depending on factors such as the wind direction and evacuation practicalities. The system uses the ILOG solver constraint satisfaction package and its high-level programming library to reduce the number of strategies to a manageable fraction. This allows a later careful evaluation of the remaining alternatives.     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.     

On the comparison of initialisation strategies in differential evolution for large scale optimisation

Differential Evolution (de) has shown to be a promising global optimisation solver for continuous problems, even for those with a large dimensionality. Different previous works have studied the effects that a population initialisation strategy has on the performance of de when solving large scale continuous problems, and several contradictions have appeared with respect to the benefits that a particular initialisation scheme might provide. Some works have claimed that by applying a particular approach to a given problem, the performance of de is going to be better than using others. In other cases however, researchers have stated that the overall performance of de is not going to be affected by the use of a particular initialisation method. In this work, we study a wide range of well-known initialisation techniques for de. Taking into account the best and worst results, statistically significant differences among considered initialisation strategies appeared. Thus, with the aim of increasing the probability of appearance of high-quality results and/or reducing the probability of appearance of low-quality ones, a suitable initialisation strategy, which depends on the large scale problem being solved, should be selected.     

Extending quick hypervolume

We extend the functionality of the quick hypervolume (QHV) algorithm. Given a set of d-dimensional points this algorithm determines the hypervolume of the dominated space, a useful measure for multiobjective evolutionary algorithms (MOEAs). We extend QHV in two ways: adapt it to compute the exclusive hypervolume of each point, and speed it up with parallel computation, that adjusts nicely to the divide and conquer methodology of QHV. The resulting algorithms are faster and more informative sub-routines, which can be used for MOEAs with a large number of objectives.     

Impartial poker nim

The combinatorial game of nim is well-studied, along with many impartial and partizan modifications. We develop a new impartial modification using the idea of bogus nim heaps and preventing loops. We completely characterize the \(\mathcal {P}\)-positions for the two-heap version, and solve the problem for a larger number of heaps dependent on counting integer partitions of a fixed size.     

Degree sequences and edge connectivity

For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\), this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too.     

Robust optimization for routing problems on trees

The prize-collecting travelling salesman problem (pc-tsp) is a known variant of the classical travelling salesman problem. In the pc-tsp, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow {\mathbb {R}}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow {\mathbb {R}}_+\) and the goal is to find a closed tour K such that \(r\in V(K)\) and such that the cost \(\ell (K)+\pi (V{\setminus } V(K))\), which is the sum of the weights of the edges in the tour and the cost of the vertices not spanned by K, is minimized. In this paper, we study the pc-tsp from a viewpoint of robust optimization. In our setting, an operator must find a closed tour in a (known) edge-weighted tree \(T=(V,E)\) starting and ending in the depot r while some of the edges may be blocked by “avalanches” defining the scenario \(\xi \). The cost \(f(K,\xi )\) of a tour K in scenario \(\xi \) is the cost resulting from “shortcutting” K, i.e. from restricting K to the nodes which are reachable from r in scenario \(\xi \), i.e. in the graph \(T {\setminus } \xi =(V,E{\setminus }\xi )\). In the absolute robust version of the problem one searches for a tour which minimizes the worst-case cost over all scenarios, while in the deviation robust counterpart, the regret, that is, the deviation from an optimum solution for a particular scenario, is sought to be minimized. We show that both versions of the problem can be solved in polynomial time on trees.     

Sterling stirling play

In this paper we analyze a recently proposed impartial combinatorial ruleset that is played on a permutation of the set \(\left[ n\right] \). We call this ruleset Stirling Shave. A procedure utilizing the ordinal sum operation is given to determine the nim value of a given normal play position. Additionally, we enumerate the number of permutations of \(\left[ n\right] \) which are \(\mathcal {P}\)-positions. The formula given involves the Stirling numbers of the first-kind. We also give a complete analysis of the Misère version of Stirling Shave using Conway’s genus theory. An interesting by-product of this analysis is insight into how the ordinal sum operation behaves in Misère Play.     

Some Enumeration Problems on Central Configurations at the Bifurcation Points

In “Counting central configurations at the bifurcation points,” we proposed an algorithm to rigorously count central configurations in some cases that involve one parameter. Here, we improve our algorithm to consider three harder cases: the planar \((3+1)\)-body problem with two equal masses; the planar 4-body problem with two pairs of equal masses which have an axis of symmetry containing one pair of them; the spatial 5-body problem with three equal masses at the vertices of an equilateral triangle and two equal masses on the line passing through the center of the triangle and being perpendicular to the plane containing it.While all three problems have been studied in two parameter cases, numerical observations suggest new results at some points on the bifurcation curves. Applying the improved version of our algorithm, we count at those bifurcation points. As a result, for the \((3+1)\)-body problem, we identify three points on the bifurcation curve where there are 8 central configurations, which adds to the known results of \(8,9,10\) ones. For our 4-body case, at the bifurcation points, there are 3 concave central configurations, which adds to the known results of \(2,4\) ones. For our 5-body case, at the bifurcation point, there is 1 concave central configuration, which adds to the known results of \(0,2\) ones.     

Toric Initial Ideals of Δ-Normal Configurations: Cohen-Macaulayness and Degree Bounds

A normal (respectively, graded normal) vector configuration\({\cal A}\) defines the toric ideal \({I}_{\cal A}\) of a normal (respectively, projectively normal) toric variety. These ideals are Cohen-Macaulay, and when \({\cal A}\) is normal and graded, \({I}_{\cal A}\) is generated in degree at most the dimension of \({I}_{\cal A}\). Based on this, Sturmfels asked if these properties extend to initial ideals—when \({\cal A}\) is normal, is there an initial ideal of \({I}_{\cal A}\) that is Cohen-Macaulay, and when \({\cal A}\) is normal and graded, does \({I}_{\cal A}\) have a Gröbner basis generated in degree at most dim(\({I}_{\cal A}\)) ? In this paper, we answer both questions positively for Δ-normal configurations. These are normal configurations that admit a regular triangulation Δ with the property that the subconfiguration in each cell of the triangulation is again normal. Such configurations properly contain among them all vector configurations that admit a regular unimodular triangulation. We construct non-trivial families of both Δ-normal and non-Δ-normal configurations.     

On the Chromatic Number of \mathbb {R}^4

The lower bound for the chromatic number of \(\mathbb {R}^4\) is improved from \(7\) to \(9\) . Three graphs with unit distance embeddings in \(\mathbb {R}^4\) are described. The first is a \(7\) -chromatic graph of order \(14\) whose chromatic number can be verified by inspection. The second is an \(8\) -chromatic graph of order \(26\) . In this case the chromatic number can be verified quickly by a simple computer program. The third graph is a \(9\) -chromatic graph of order \(65\) for which computer verification takes about one minute.     

Global Fibonacci nim

Fibonacci nim is a popular impartial combinatorial game, usually played with a single pile of stones: two players alternate in removing no more than twice the previous player’s removal. The game is appealing due to its surprising connections with the Fibonacci numbers and the Zeckendorf representation. In this article, we investigate some properties of a variant played with multiple piles of stones, and solve the 2-pile case. A player chooses one of the piles and plays as in Fibonacci nim, but here the move-size restriction is a global parameter, valid for any pile.     

Asynchronously parallel optimization solver for finding multiple minima

We propose and analyze an asynchronously parallel optimization algorithm for finding multiple, high-quality minima of nonlinear optimization problems. Our multistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that when there are finitely many minima, the algorithm almost surely starts a finite number of local optimization runs and identifies every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a Python implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability is shown to scale well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to perform the function evaluation is highly variable. An implementation of the algorithm is available in the libEnsemble library at https://github.com/Libensemble/libensemble.     

Extension sets,affine designs,and Hamada’s conjecture

We introduce the notion of an extension set for an affine plane of order q to study affine designs \({\mathcal {D}}'\) with the same parameters as, but not isomorphic to, the classical affine design \({\mathcal {D}} = \mathrm {AG}_2(3,q)\) formed by the points and planes of the affine space \(\mathrm {AG}(3,q)\) which are very close to this geometric example in the following sense: there are blocks \(B'\) and B of \({\mathcal {D}'}\) and \({\mathcal {D}}\), respectively, such that the residual structures \({\mathcal {D}}'_{B'}\) and \({\mathcal {D}}_B\) induced on the points not in \(B'\) and B, respectively, agree. Moreover, the structure \({\mathcal {D}}'(B')\) induced on \(B'\) is the q-fold multiple of an affine plane \({\mathcal {A}}'\) which is determined by an extension set for the affine plane \(B \cong AG(2,q)\). In particular, this new approach will result in a purely theoretical construction of the two known counterexamples to Hamada’s conjecture for the case \(\mathrm {AG}_2(3,4)\), which were discovered by Harada et al. [7] as the result of a computer search; a recent alternative construction, again via a computer search, is in [23]. On the other hand, we also prove that extension sets cannot possibly give any further counterexamples to Hamada’s conjecture for the case of affine designs with the parameters of some \(\mathrm {AG}_2(3,q)\); thus the two counterexamples for \(q=4\) might be truly sporadic. This seems to be the first result which establishes the validity of Hamada’s conjecture for some infinite class of affine designs of a special type. Nevertheless, affine designs which are that close to the classical geometric examples are of interest in themselves, and we provide both theoretical and computational results for some particular types of extension sets. Specifically, we obtain a theoretical construction for one of the two affine designs with the parameters of \(\mathrm {AG}_2(3,3)\) and 3-rank 11 and for an affine design with the parameters of \(\mathrm {AG}_2(3,4)\) and 2-rank 17 (in both cases, just one more than the rank of the classical example).     

Linear Transformations and Reduction Formulas for the Gelfand Hypergeometric Functions Associated with the Grassmannians $$G_{2,4} $$ and $$G_{3,6} $$

We show that the Gelfand hypergeometric functions associated with the Grassmannians $G_{2,4} $ and $G_{3,6} $ with some special relations imposed on the parameters can be represented in terms of hypergeometric series of a simpler form. In particular, a function associated with the Grassmannian $G_{2,4} $ (the case of three variables) can be represented (depending on the form of the additional conditions on the parameters of the series) in terms of the Horn series $H_2 ,G_2 $ , of the Appell functions $F_1 ,F_2 ,F_3 $ and of the Gauss functions $F_1^2 $ , while the functions associated with the Grassmannian $G_{3,6} $ (the case of four variables) can be represented in terms of the series $G_2 ,F_1 ,F_2 ,F_3 $ and $F_1^2 $ . The relation between certain formulas and the Gelfand--Graev--Retakh reduction formula is discussed. Combined linear transformations and universal elementary reduction rules underlying the method were implemented by a computer program developed by the authors on the basis of the computer algebra system Maple V-4.     

A Functional Central Limit Theorem for a Markov-Modulated Infinite-Server Queue

We consider a model in which the production of new molecules in a chemical reaction network occurs in a seemingly stochastic fashion, and can be modeled as a Poisson process with a varying arrival rate: the rate is λ _i when an external Markov process J(?) is in state i. It is assumed that molecules decay after an exponential time with mean μ ^?1. The goal of this work is to analyze the distributional properties of the number of molecules in the system, under a specific time-scaling. In this scaling, the background process is sped up by a factor N ^α , for some α>0, whereas the arrival rates become N λ _i , for N large. The main result of this paper is a functional central limit theorem (F-CLT) for the number of molecules, in that, after centering and scaling, it converges to an Ornstein-Uhlenbeck process. An interesting dichotomy is observed: (i) if α > 1 the background process jumps faster than the arrival process, and consequently the arrival process behaves essentially as a (homogeneous) Poisson process, so that the scaling in the F-CLT is the usual \(\sqrt {N}\), whereas (ii) for α≤1 the background process is relatively slow, and the scaling in the F-CLT is N ^1?α/2. In the latter regime, the parameters of the limiting Ornstein-Uhlenbeck process contain the deviation matrix associated with the background process J(?).     

Simulation-Based Optimal Design Using a Response Variance Criterion

Classical optimal design criteria suffer from two major flaws when applied to nonlinear problems. First, they are based on linearizing the model around a point estimate of the unknown parameter and therefore depend on the uncertain value of that parameter. Second, classical design methods are unavailable in ill-posed estimation situations, where previous data lack the information needed to properly construct the design criteria. Bayesian optimal design can, in principle, solve these problems. However, Bayesian design methods are not widely applied, mainly due to the fact that standard implementations for efficient and robust routine use are not available. In this article, we point out a concrete recipe for implementing Bayesian optimal design, based on the concept of simulation-based design introduced by Muller, Sanso, and De Iorio (2004 Muller, P., Sanso, B. and De Iorio, M. 2004. Optimal Bayesian Design by Inhomogeneous Markov Chain Simulation. Journal of the American Statistical Association, 99(467): 788–798. [Taylor & Francis Online] , [Google Scholar]). We develop further a predictive variance criterion and introduce an importance weighting mechanism for efficient computation of the variances. The simulation-based approach allows one to start the model-based optimization of experiments at an early stage of the parameter estimation process, in situations where the classical design criteria are not available. We demonstrate that the approach can significantly reduce the number of experiments needed to obtain a desired level of accuracy in the parameter estimates. A computer code package that implements the approach in a simple case is provided as supplemental material (available online).