Optimization and Control
Branch & Price & Cut for the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW)
Florian Rascoussier, Romain Billot, Lina Fahed et al. (+1 more)
In urban contexts, travel times vary strongly with the time of day and traffic conditions. The Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) extends the classical VRPTW by making travel times depend on departure time, with the objective of minimizing the total travel time of at most $k$ vehicle routes serving customers within strict time windows. Exact resolution of this realistic yet understudied problem currently relies on the Branch & Price approach of Dabia et al. (2013), in which a Column Generation scheme decomposes the problem into a set-partitioning master problem and a resource-constrained shortest-path pricing problem solved by dynamic programming. This work, conducted within the MAMUT project (Machine Learning and Matheuristics for Urban Transport), aims to advance the state of the art for the exact and explainable resolution of the TDVRPTW. We propose to reimplement and revisit the pioneering Branch & Price
algorithm by transferring recent advances made on the single-vehicle variant (TDTSPTW) to the multi-vehicle setting, notably an exact anytime extension of A* and a Large Neighborhood Search guided by dynamic programming for the pricing sub-problem. We further explore the integration of data mining and machine learning to guide column generation by exploiting knowledge from previously computed routes. The goal is a high-performance and interpretable solver that meets the requirements of real-world urban transport while preserving guarantees on solution quality.
Read the full abstract ▾
All authors Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon
Optimization and Control
Randomized Constructive Heuristics for the VRPTW: A Focus on Regret-k
Florian Rascoussier, Romain Billot, Lina Fahed et al. (+1 more)
The Vehicle Routing Problem with Time Windows (VRPTW) requires a fleet of capacitated vehicles to serve customers within strict time windows while minimizing total travel time. Constructive heuristics are fundamental for generating solutions and commonly serve as starting points for metaheuristics such as Iterated Local Search (ILS), Genetic
Algorithms, and Ant Colony Optimization (ACO). This work studies three classical constructive heuristics - Nearest Neighbor, Best Insertion, and Regret-k - within a randomized, multi-start framework, a setting that remains largely under-explored despite their well-established deterministic use. We address how to effectively randomize these heuristics and, in particular, propose a novel randomization of Regret-k by separating the ”who” (which customer to insert next) and ”where” (insertion position) decisions, applying a probabilistic selection proportional to the regret value to preserve the heuristic's foresight while injecting the diversity needed for a multi-start approach. We further study the impact of combining these greedy randomized constructions with Local Search and ACO. Experiments follow the DIMACS 2021 conventions (integer, truncated Euclidean distances) on the Solomon and Gehring & Homberger
benchmarks (100–1000 customers), comparing against the Best-Known Solutions and the state-of-the-art Hybrid Genetic Search solver, with all critical components implemented in modern C++ and bound to Python via pybind11. To the best of our knowledge, the randomization of Regret-k has never been examined; our analysis highlights the trade-off between solution quality and computational cost, providing a preliminary step toward hybrid methods (ACO, ILS, Branch-and-Price) for the Time-Dependent VRPTW within the MAMUT project.
Read the full abstract ▾
All authors Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon
Optimization and Control
Optimality of a Threshold Policy for a Queueing System with One Fast Server and Two Identical Slow Servers
Weina Wang, Taha Ameen, Yudong Chen et al. (+3 more)
This paper studies the optimal control problem of a queueing system with three servers: one fast server and two identical slow servers. The two-server version of this problem, with one fast server and one slow server, was introduced by Lin and Kumar (1984), and the optimal policy has been shown to be of threshold type. However, generalizing this result beyond the two-server setting has been considered an open problem. In this paper, we resolve the first nontrivial case by proving that a threshold policy is optimal for the three-server system considered. The core technical ideas in this paper are generated by GPT-5.5 Pro. We have included a short report describing the authors' interactions with GPT-5.5 Pro. The authors verified the proofs and rewrote the paper for better rigor, clarity, and exposition. In addition, three key lemmas have also been verified in Lean 4.
Read the full abstract ▾
All authors Weina Wang, Taha Ameen, Yudong Chen, Yige Hong, Josh Nichols, Matthew Zurek
Numerical Analysis · Cross-listed from cs.LG
Computational Identifiability
Lucius E.J. Bynum, Rajesh Ranganath and Kyunghyun Cho
Identification conditions describe the computability of a target query or parameter of interest as a function of the type and amount of information available. In causal identification, this information is often expressed in the form of a causal graph, and data are observed or collected for some subset of variables in the graph. Target queries may be for a single effect alone or for a class of effects in a given model. The derivation of an identification
algorithm then defines mathematically the process by which the desired causal effect(s) can be uniquely determined, theoretically, in expectation. Identifiability in expectation, or 'theoretical identifiability,' generally assumes asymptotic properties, infinite data, or other mathematically idealized conditions. In this paper, we explore a fundamental distinction between this theoretical, idealized notion of identifiability and a proposed alternative that is computation-bound. The framework we propose - 'computational identifiability' - is to instead define a finite computational search procedure for an empirical
estimator. If this process finds an
estimator empirically, within a desired error tolerance, then identifiability is satisfied, conditional on the specified assumptions of the search (i.e., a prior distribution over the parameters) and conditional on the search procedure itself. Through several experiments, we demonstrate how this framework allows us to answer fine-grained, practical identification questions, such as identification with small finite samples, with ambiguous graphical criteria, with mixed observational-interventional data, and across counterfactual data and estimands. Code is available at https://github.com/lbynum/metadentify.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.RO
Bayesian Optimization for Learning Nonlinear MPC in Autonomous Agent Navigation
Lorenzo Ortolani, Gabriel Voss, Gabriele Beltrami et al. (+2 more)
Real-time autonomous
navigation in dynamic, unknown environments remains a fundamental challenge for mobile robotics. We propose a map-free framework that tightly integrates reactive rolling-horizon planning with nonlinear Model Predictive Control (MPC). At each control cycle, a
LiDAR-based Gaussian occupancy representation is constructed and used to generate collision-free trajectories via A* search, which are then tracked by a CasADi/IPOPT MPC formulation incorporating a smooth sigmoid obstacle barrier. To improve robustness to parameter sensitivity, we adopt an offline
Bayesian optimization scheme based on Tree-structured Parzen
Estimators (TPE), which identifies near-optimal controller parameters with respect to a composite
navigation objective. In addition, a Gaussian Process surrogate is used to analyze parameter sensitivity and provide insight into the optimization landscape. The proposed framework is
robot-agnostic and is evaluated on the Unitree Go2 quadruped in simulation using Gazebo, followed by deployment on the physical
robot. Experimental results show that parameters tuned in simulation transfer effectively to hardware, maintaining comparable performance without additional tuning. The full system achieves up to a 90.0%
navigation success rate when deployed, along with a 38.9% average improvement in the evaluation metrics across simulated environments.
Read the full abstract ▾
All authors Lorenzo Ortolani, Gabriel Voss, Gabriele Beltrami, Francesco Dorati, Tommaso Felice Banfi
Mathematical Physics
Quasi-Product States and Factor Types for the One-Dimensional Hard-Core Model
Farrukh Mukhamedov and Yuri Suhov
We study the von Neumann
algebra generated by a quasi-product state associated with the one-dimensional hard-core
lattice gas. If \(\kappa>0\) denotes the activity (fugacity), the transfer-
matrix construction gives the stationary transition
matrix \[ P=\begin{pmatrix}p&q\\ 1&0\end{pmatrix}, \qquad p+q=1, \qquad \kappa=\frac{q}{p^2}. \] The stationary Markov measure on the hard-core path space induces a faithful diagonal state on the corresponding path \(AF\)-
algebra. We give a state-preserving identification of its GNS von Neumann
algebra with the Feldman–Moore
algebra of the measured tail equivalence relation. The relation is hyperfinite and ergodic, and its nonzero ratio set is \(\kappa^{\mathbb Z}\). Consequently, the generated
algebra is the hyperfinite factor of type \(\mathrm{II}_1\) when \(\kappa=1\), and of type \(\mathrm{III}_{\lambda}\), where \(\lambda=\min\{\kappa,\kappa^{-1}\}\), when \(\kappa\ne1\). The point \(\kappa=1\) is not a thermodynamic phase transition: the pressure and particle density are analytic for all \(\kappa>0\). We also describe the precise support-corner relation with the GNS
algebra of the diagonal Gibbs state on the quasi-local
spin algebra, and we determine the centralizer and the flow of weights.
Read the full abstract ▾
Numerical Analysis · Cross-listed from cond-mat.stat-mech
Numerical simulations of the spread from the mean of the SLE and Multiple SLE dynamics
Phillip Kim and Vlad Margarint
The Schramm-Loewner
Evolution (SLE) describes a family of fractal curves that arise in the study of the scaling limits of many planar Statistical Physics models. These curves are modeled using the Loewner Differential Equation for the conformal maps $g_t(z)$ with a Brownian motion driver. Using Euler's Method, in the current work we performed numerical experiments to study at a fixed time the quantities $|g_t(z) - \overline{g_t(z)}|$ and $Re(g_t(z)) - Re(\overline{g_t(z)})$, where $Re$ denotes the real part and $\overline{g_t(z)}$ refers to the sample average. These random variables measure the 'spread' of the dynamics from the average behavior at fixed time. One of the scopes of this work is to give numerical predictions for future theoretical investigations on these quantities. When investigating these quantities in the SLE case our experiments predict that the distribution is bimodal when the dynamics started close to the origin, and it can become bell-shaped if the dynamics is started further from the origin. In the second part, we performed experiments for a Multiple SLE model whose driver is Dyson Brownian Motion. Due to singularity in the dynamics of the drivers and the many data points needed, this part is challenging from a computational perspective. In the multiple SLE case, our experiments predict that the distribution is bell-shaped in all cases. In addition, we check the changes in the distributions as we vary the parameter $\kappa$ in the SLE case and $\beta$ in the Multiple SLE case.
Read the full abstract ▾
General Mathematics
Binomial Transform of Sequences Counting $N$-ary Convexities
Aidar Dulliev and Daniil Naumikhin
We consider the enumeration of $N$-ary convex structures on finite sets. Our main result shows that the total number of convexities is expressed as the binomial transform of the sequence of numbers of grounded convexities. We present the exact numbers of all $N$-ary and grounded $N$-ary convexities for $|X|\leqslant 5$. The obtained integer sequences have been cross-referenced with the OEIS. As a result, we identified both known sequences (such as A000798) and new ones not previously listed.
Read the full abstract ▾
General Mathematics
Does 2026 AI exhibit intelligence, or can Claude outsmart Pierre or Catherine ?
Robert C. Dalang
Using a sequence of high-school level mathematics questions that were not available on the Internet, we compare the performance of the popular AI software Claude with that of my friends and fellow human beings Pierre and Catherine. Pierre had solid scientific training as a young man, while Catherine studied literature. All three were subjected to a simulated pre-calculus oral exam with main questions and follow-up questions. Their performances are compared and the ones with the best and worst performances are identified. The outcome is that the current version of Claude, even though it is an extremely useful tool that has probably recorded the solution to nearly all calculus questions that are available on the Internet, exhibits only a very limited understanding of the subject and does not exhibit the ability to make intelligent connections between different features of a pre-calculus mathematics problem that it has never seen before.
Read the full abstract ▾
Probability
The inradius law for the cavities of planar Brownian motion, with applications to the Wiener sausage
Tristan Guillaume
“`text Let $K_1=B[0,1]$ be the trace of a planar Brownian motion, and let $N_{\mathrm{in}}(\eta)$ be the number of its cavities, the bounded components of $\mathbb{R}^2\setminus K_1$, whose inradius exceeds $\eta$. We prove that, almost surely and in $L^p$ for every $p\in[1,2]$, $\eta^2(\log(1/\eta))^2 N_{\mathrm{in}}(\eta)\to c_{\mathrm{in}}=\frac{\pi}{2}\int G^2 d\mathcal{L}\in(0,\frac12]$, where $G$ is the ratio of the inradius of a shape to the square root of its area and $\mathcal{L}$ is Werner's limiting shape law. The inradius, and not the area by which the cavities have been counted classically, decides survival under thickening: a cavity contains a hole of the Wiener sausage of radius $r$ if and only if its inradius exceeds $r$. Through Brownian scaling, the number $\beta_1^T(r)$ of holes of the sausage of radius $r$ of $B[0,T]$, the Betti curve of its degree-one persistent homology, is bounded below at the scale $T/(r^2(\log T)^2)$, with the identified constant $4c_{\mathrm{in}}$ in expectation and with any smaller constant with probability tending to one. A matching upper bound cannot follow from any general bound in terms of perimeter, area, diameter or length; we prove that it is equivalent to a first-moment estimate for near-critical pockets, the holes at level $\eta$ on which the distance to the trace is at most $2\eta$. That estimate is proved in a companion paper, so that the expected number of holes is of exact order $T/(r^2(\log T)^2)$. “`
Read the full abstract ▾
Probability
Downward conditional monotonicity gives survival and extinction for contact processes in random environments
Joseph P. Stover
The concept of downward conditional monotonicity for the Markov-modulated Poisson process (MMPP) is introduced and used to derive the optimal
stochastic domination of a standard Poisson point process. The maximum arrival rate for the Poisson process which allows this domination to exist is shown to be related to an
eigenvalue extracted from the generator
matrix of the quasi-birth–death (QBD) formulation of the MMPP. This allows derivation of survival and extinction regimes for a large family of contact processes whose infection and recovery rates vary over time according to an underlying random environment with a finite number of states. Direct comparison with standard contact processes which dominate from above and below accomplishes this.
Read the full abstract ▾
Commutative Algebra
Complexes of finite Gorenstein flat and injective dimensions
Kaito Kimura
In this paper, we consider a Gorenstein-dimensional analogue of Foxby's characterization of Gorenstein rings. We prove that a commutative Noetherian local ring is Gorenstein if it admits a complex whose depth, Gorenstein flat dimension, and Gorenstein injective dimension are all finite. This gives an affirmative answer to the original question of Christensen, Foxby, and Holm, which had remained open in this generality even for modules, and at the same time establishes its natural extension to complexes.
Read the full abstract ▾
Analysis of PDEs
The partial data Calderón problem in dimension three
Gunther Uhlmann and Yiran Wang
We consider an inverse boundary value problem for the time-independent Schrödinger equation in dimension three. We prove that the local Dirichlet-to-Neumann map defined near a boundary point uniquely determines the potential in a neighborhood of the boundary point in the interior. In particular, we show that the uniqueness question can be reduced to the injectivity of a weighted X-ray transform, which links inverse boundary value problems to integral geometry.
Read the full abstract ▾
Number Theory
A Tsang-range high-moment bound for $\operatorname{Im}\log L(\tfrac12+it,\chi)$ under GRH
Scott D. Hughes
Conditional on the Generalized Riemann Hypothesis for $L(s,\chi)$, we prove the Selberg–Tsang high-moment bound for $X_\chi(t) = \operatorname{Im}\log L(\tfrac12+it,\chi)$ at fixed squarefree odd conductor $q \ge 3$ and primitive non-principal character $\chi$. Writing $L_T = \log\log(qT)$: for every $K > 0$ there exist constants $C_K$ and $T_0$ such that $\frac{1}{T}\int_T^{2T} |X_\chi(t)|^{2k}\,dt \le (C_K\,k\,L_T)^k$ for all $T \ge T_0$ and every integer $1 \le k \le K L_T$. The proof ports Selberg's pointwise approximate formula for $S(t)$ to $L(s,\chi)$ at fixed conductor under GRH, splits it into three
prime-power Dirichlet
polynomials, and evaluates their moments via Soundararajan's mean-value lemma. As a corollary, Markov's inequality yields a Gaussian-scale tail $\exp(-c V^2 / L_T)$ for $\sqrt{L_T} \ll V \ll L_T$ – a GRH-conditional, fixed-conductor, imaginary-part analogue of the large-deviation upper bounds known for $\log|\zeta(\tfrac12+it)|$.
Read the full abstract ▾
Algebraic Topology
Smooth manifolds homotopy equivalent to products of spheres
Sagnik Biswas
We classify, up to almost diffeomorphism, the smooth closed oriented
manifolds homotopy equivalent to each of the sphere products $S^{4k-1}\times S^{4k}$, $S^{4k}\times S^{4k}$, and $S^{4k}\times S^{4k+1}$. In each case we realize the image of the normal-invariant map in the smooth surgery exact sequence by explicit families of
manifolds: sphere bundles over $S^{4k}$; pinch maps and Milnor plumbings of disk bundles; and Novikov sphere bundles together with connected sums of homotopy spheres.
Read the full abstract ▾
Numerical Analysis
A Virtual Element Method for elliptic problems on trimmed background meshes
L. Beirão da Veiga, C. Canuto, R. H. Nochetto et al. (+2 more)
We consider a two-dimensional piecewise $C^2$ domain that cuts through a quasi-uniform fixed polygonal background mesh, for instance made of quadrilaterals. A simple procedure based on convex hulls gives rise to a rather small number of polygonal boundary elements of various shapes, including elements with small edges and large aspect ratios; this is the computational mesh for a virtual element method (VEM), a trimmed background mesh. We classify all possible
geometric configurations and study their stability and approximability properties. This entails deriving robust stabilization mechanisms and interpolation estimates for anisotropic elements and elements with small cuts, as well as a weak maximum principle for enhanced virtual elements; these contributions have intrinsic interest for VEM theory on
geometric flexibility. We prove that the resulting VEM is uniformly stable in $H^1$, and also show optimal order-regularity error estimates in $H^1$ and $L^2$. Insightful numerical experiments corroborate and complement our theory. The proposed method is suitable for treating ALE formulations of problems in moving domains.
Read the full abstract ▾
All authors L. Beirão da Veiga, C. Canuto, R. H. Nochetto, G. Vacca, M. Verani