Description: Biogeochemical models, capturing the major feedbacks of the pelagic ecosystem of the world ocean, are today often embedded into Earth system models which are increasingly used for decision making regarding climate policies. These models contain poorly constrained parameters (e.g., maximum phytoplankton growth rate), which are typically adjusted until the model shows reasonable behavior. Systematic approaches determine these parameters by minimizing the misfit between the model and observational data. In most common model approaches, however, the underlying functions mimicking the biogeochemical processes are nonlinear and non-convex. Thus, systematic optimization algorithms are likely to get trapped in local minima and might lead to non-optimal results. To judge the quality of an obtained parameter estimate, we propose determining a preferably large lower bound for the global optimum that is relatively easy to obtain and that will help to assess the quality of an optimum, generated by an optimization algorithm. Due to the unavoidable noise component in all observations, such a lower bound is typically larger than zero. We suggest deriving such lower bounds based on typical properties of biogeochemical models (e.g., a limited number of extremes and a bounded time derivative). We illustrate the applicability of the method with two real-world examples. The first example uses real-world observations of the Baltic Sea in a box model setup. The second example considers a three-dimensional coupled ocean circulation model in combination with satellite chlorophyll a.

Description: Global biogeochemical ocean models contain a variety of different biogeochemical components and often much simplified representations of complex dynamical interactions, which are described by many (≈10–≈100) parameters. The values of many of these parameters are empirically difficult to constrain, due to the fact that in the models they represent processes for a range of different groups of organisms at the same time, while even for single species parameter values are often difficult to determine in situ. Therefore, these models are subject to a high level of parametric uncertainty. This may be of consequence for their skill with respect to accurately describing the relevant features of the present ocean, as well as their sensitivity to possible environmental changes. We here present a framework for the calibration of global biogeochemical ocean models on short and long time scales. The framework combines an offline approach for transport of biogeochemical tracers with an Estimation of Distribution Algorithm (Covariance Matrix Adaption Evolution Strategy, CMAES). We explore the performance and capability of this framework by five different optimizations of six biogeochemical parameters of a global biogeochemical model. First, a twin experiment explores the feasibility of this approach. Four optimizations against a climatology of observations of annual mean dissolved nutrients and oxygen determine the extent, to which different setups of the optimization influence model's fit and parameter estimates. Because the misfit function applied focuses on the large-scale distribution of inorganic biogeochemical tracers, parameters that act on large spatial and temporal scales are determined earliest, and with the least spread. Parameters more closely tied to surface biology, which act on shorter time scales, are more difficult to determine. In particular the search for optimum zooplankton parameters can benefit from a sound knowledge of maximum and minimum parameter values, leading to a more efficient optimization. It is encouraging that, although the misfit function does not contain any direct information about biogeochemical turnover, the optimized models nevertheless provide a better fit to observed global biogeochemical fluxes.

Description: We present a new quantum-inspired evolutionary algorithm, the attractor population QEA (apQEA). Our benchmark problem is a classical and difficult problem from Combinatorics, namely finding low-discrepancy colorings in the hypergraph of arithmetic progressions on the first n integers, which is a massive hypergraph (e.g., with approx. 3.88 ×1011 hyperedges for n = 250 000). Its optimal low-discrepancy coloring bound is known and it has been a long-standing open problem to give practically and/or theoretically efficient algorithms. We show that apQEA outperforms known QEA approaches and the classical combinatorial algorithm (Sárközy 1974) by a large margin. Regarding practicability, it is also far superior to the SDP-based polynomial-time algorithm of Bansal (2010), the latter being a breakthrough work from a theoretical point of view. Thus we give the first practical algorithm to construct optimal colorings in this hypergraph, up to a constant factor. We hope that our work will spur further applications of Algorithm Engineering to Combinatorics.

Description: In the past three decades, deductive games have become interesting from the algorithmic point of view. Deductive games are two players zero sum games of imperfect information. The first player, called "codemaker", chooses a secret code and the second player, called "codebreaker", tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. A well known deductive game is the famous Mastermind game. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and k 〉= n colors where no repetition of colors is allowed. We present a strategy that identifies the secret code in O(n log n) queries. Our algorithm improves the previous result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2 for the case k = n. To our knowledge there is no previous work dealing with the case k 〉 n. Keywords: Mastermind; combinatorial problems; permutations; algorithms

Description: We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MlLP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.

Description: Mastermind is famous two-player game. The first player (codemaker) chooses a secret code which the second player (codebreaker) is supposed to crack within a minimum number of code guesses (queries). Therefore, the codemaker’s duty is to help the codebreaker by providing a well-defined error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and 𝑘≥𝑛 colors and ℓ:=𝑘+1−𝑛, we prove a lower bound of ∑𝑘𝑗=ℓlog2𝑗 and an upper bound of 𝑛log2𝑛+𝑘 on the number of queries necessary to break the secret code. For the important case 𝑘=𝑛, where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of Θ(𝑛log𝑛) queries.

Description: Mastermind is a two players zero sum game of imperfect information. Starting with Erdős and Rényi (1963), its combinatorics have been studied to date by several authors, e.g., Knuth (1977), Chvátal (1983), Goodrich (2009). The first player, called “codemaker”, chooses a secret code and the second player, called “codebreaker”, tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. For variants that allow color repetition, Doerr et al. (2016) showed optimal results. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and 𝑘≥𝑛 colors where no repetition of colors is allowed. We present upper and lower bounds on the number of guesses necessary to break the secret code. For the case 𝑘=𝑛, the secret code can be algorithmically identified within less than (𝑛−3)⌈log2𝑛⌉+52𝑛−1 queries. This result improves the result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2. For the case 𝑘〉𝑛, we prove an upper bound of (𝑛−2)⌈log2𝑛⌉+𝑘+1. Furthermore, we prove a new lower bound of n for the case 𝑘=𝑛, which improves the recent 𝑛−loglog(𝑛) bound of Berger et al. (2016). We then generalize this lower bound to k queries for the case 𝑘≥𝑛.