An evolutionary Stackelberg framework for a two-population routing game is proposed, in which a boundedly rational central controller manages a fleet of vehicles sharing the network with selfish drivers. The controller assigns routes to minimize social cost by managing her fleet via the E-Aloof strategy, a low-information, adaptive rule that requires only the observation of the instantaneous traffic distribution and no memory of past states; E-Aloof is an evolutionary extension of the greedy, static Aloof strategy. The drivers of the remaining vehicles behave selfishly and myopically, adapting routes according to the Stackelberg Replicator Dynamic by comparing their travel costs with those of randomly sampled vehicles. The work formulates the problem as a nonatomic routing game on a two-parallel-link network. It establishes the existence of asymptotically stable equilibria under standard assumptions of continuously differentiable, nondecreasing, convex cost functions. The conditions under which centralization improves performance are derived, showing that while Aloof is beneficial when at least half of the vehicles are centralized, E-Aloof requires fewer centralized vehicles depending on the cost functions. For linear costs, conditions are found under which the equilibria coincide with those of a full-information Stackelberg game.

Recent advances in the combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the characterization of the mathematical properties that a symmetric integer matrix of order n≥3 must satisfy to encode the Path-Length Matrix of an Unrooted Binary Tree. This result, together with the identification of fundamental facet-defining inequalities for the convex hull of BMEP solutions, has led to an integer linear programming formulation that currently serves as the reference exact solution algorithm. Here, we show how to exploit these advances to improve the approximation algorithms for the problem. We first leverage the tight linear programming relaxation of this formulation to develop an enhanced Neighbor Joining-like heuristic. Next, we embed this heuristic into a Beam Search framework to further improve the quality of the solutions. Computational experiments show that the proposed algorithms outperform existing heuristics, making their use highly desirable in practice. AVAILABILITY AND IMPLEMENTATION: Codes and data are available at https://github.com/HenriDeh/BME_BeamSearch.git and archived at https://zenodo.org/records/15631441 (DOI: 10.5281/zenodo.15631440).

The real-time railway traffic management problem consists of selecting appropriate train routes and schedules for minimizing the propagation of delay in case of traffic perturbation. In this paper, we tackle this problem by introducing RECIFE-MILP, a heuristic algorithm based on a mixed-integer linear programming model. RECIFE-MILP uses a model that extends one we previously proposed by including additional elements characterizing railway reality. In addition, it implements performance boosting methods selected among several ones through an algorithm configuration tool. We present a thorough experimental analysis that shows that the performances of RECIFE-MILP are better than the ones of the currently implemented traffic management strategy. RECIFE-MILP often finds the optimal solution to instances within the short computation time available in real-time applications. Moreover, RECIFE-MILP is robust to its configuration if an appropriate selection of the combination of boosting methods is performed.

Aphylogeny is an unrooted binary tree that represents the evolutionary relationships of a set of n species. Phylogenies find applications in several scientific areas ranging from medical research, to drug discovery, to epidemiology, to systematics, and to population dynamics. In such applications, the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the analyzed species, such as DNA, RNA, amino acid, or codon fragments. On the contrary, the information about the phylogeny itself is generally missing and is determined by solving an optimization problem, called the phylogeny estimation problem (PEP), whose versions depend on the criterion used to select a phylogeny from among plausible alternatives. In this paper, we investigate a recent version of the PEP, called the balanced minimum evolution problem (BMEP). We present a mixed-integer linear programming model to exactly solve instances of the BMEP and develop branching rules and families of valid inequalities to further strengthen the model. Our results give perspective on the mathematics of the BMEP and suggest new directions on the development of future efficient exact approaches to solutions of the problem.

Abstract A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA or protein sequences. Among different criteria used for this purpose, the minimum evolution criterion is an optimality based criterion aiming to rebuild PT characterized by a minimal length. This problem is known to be 𝒩𝒫‐hard. We introduce in this article some mixed integer programming models, and we also study possible cuts and lower bounds for the optimal value. So far, the number of sequences that can be involved in optimal phylogenetic reconstruction is still limited to 10. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

MOTIVATION: The general-time-reversible (GTR) model is one of the most popular models of nucleotide substitution because it constitutes a good trade-off between mathematical tractability and biological reality. However, when it is applied for inferring evolutionary distances and/or instantaneous rate matrices, the GTR model seems more prone to inapplicability than more restrictive time-reversible models. Although it has been previously noted that the causes for intractability are caused by the impossibility of computing the logarithm of a matrix characterised by negative eigenvalues, the issue has not been investigated further. RESULTS: Here, we formally characterize the mathematical conditions, and discuss their biological interpretation, which lead to the inapplicability of the GTR model. We investigate the relations between, on one hand, the occurrence of negative eigenvalues and, on the other hand, both sequence length and sequence divergence. We then propose a possible re-formulation of previous procedures in terms of a non-linear optimization problem. We analytically investigate the effect of our approach on the estimated evolutionary distances and transition probability matrix. Finally, we provide an analysis on the goodness of the solution we propose. A numerical example is discussed.

Abstract A network design problem which arises in the distribution of a public utility provided by several competitive suppliers is studied. The problem addressed is that of determining minimum‐cost (generalized) arc capacities in order to accommodate any demand between given source–sink pairs of nodes, where demands are assumed to fall within predetermined ranges. Feasible flows are initially considered as simply bounded by the usual arc capacity constraints. Then, more general linear constraints are introduced which may limit the weighted sum of the flows on some subsets of arcs. An exact cutting plane algorithm is presented for solving both of the above cases and some computational results are reported. © 2004 Wiley Periodicals, Inc.

In this paper, we consider different aspects of the problem of controlling a multi-inventory system in the presence of uncertain demand and setups. The demand is unknown but bounded in an assigned compact set. The control input is assumed to be constant in its operating regime and to incur setup whenever a variation of this regime is required. Both setup times and setup configurations are unknown. We provide necessary and sufficient stabilizability conditions which turn out to be the same in the case in which there are no setups. Stabilization can be achieved, provided that the planning horizon is large enough and a computable lower bound is given. We also face the problem of ultimately confining the state in an assigned constraint set and provide conditions on this set for the problem to be feasible. Furthermore, we consider the case in which the controls are quantized, as in the case of systems which work in a switching mode. Finally, we deal with the case in which multiple setups may happen during the planning horizon.

A class of production-distribution problems with unknown-but-bounded uncertain demand is considered. At each time, the demand is unknown, but each of its components is assumed to belong to an assigned interval. Furthermore, the system has production, transportation, and storage capacity constraints. The paper extends previous results to the case in which transportation delays are present. We show that the problem of finding a strategy which keeps bounded the storage levels reduces to that of finding a strategy for the associated instantaneous network, which is the network obtained by setting all the delays to zero in the original system. The state variables of the associated instantaneous network are the "inventory positions," given by the goods actually present in the warehouses plus the goods already ordered and leading to them.

The authors deal with optimal control problems of deterministic queuing networks. The class of networks considered is characterized by a single-class population of customers, each of which has to undergo the same sequence of operations. The network is composed of a number of identically structured islands, where a decisional node has to route incoming customers to one between two different servers. With reference to the minimization of the mean flow time in the overall network, the optimality of an informationally decentralized, threshold-type, and quasi-stationary policy is proved.>