Search

We present exact mixed-integer programming linear formulations for verifying the performance of first-order methods for parametric quadratic optimization. We formulate the verification problem as a mixed-integer linear program where the objective is to maximize the infinity norm of the fixed-point residual after a given number of iterations. Our approach captures a wide range of gradient, projection, proximal iterations through affine or piecewise affine constraints. We derive tight polyhedral convex hull formulations of the constraints representing the algorithm iterations. To improve the scalability, we develop a custom bound tightening technique combining interval propagation, operator theory, and optimization-based bound tightening. Numerical examples, including linear and quadratic programs from network optimization and sparse coding using Lasso, show that our method provides several orders of magnitude reductions in the worst-case fixed-point residuals, closely matching the true worst-case performance.

This work presents a hybrid quantum-classical algorithm to perform clustering aggregation, designed for neutral-atoms quantum computers and quantum annealers. Clustering aggregation is a technique that mitigates the weaknesses of clustering algorithms, an important class of data science methods for partitioning datasets, and is widely employed in many real-world applications. By expressing the clustering aggregation problem instances as a Maximum Independent Set (MIS) problem and as a Quadratic Unconstrained Binary Optimization (QUBO) problem, it was possible to solve them by leveraging the potential of Pasqal's Fresnel (neutral-atoms processor) and D-Wave's Advantage QPU (quantum annealer). Additionally, the designed clustering aggregation algorithm was first validated on a Fresnel emulator based on QuTiP and later on an emulator of the same machine based on tensor networks, provided by Pasqal. The results revealed technical limitations, such as the difficulty of adding additional constraints on the employed neutral-atoms platform and the need for better metrics to measure the quality of the produced clusterings. However, this work represents a step towards a benchmark to compare two different machines: a quantum annealer and a neutral-atom quantum computer. Moreover, findings suggest promising potential for future advancements in hybrid quantum-classical pipelines, although further improvements are needed in both quantum and classical components., Comment: Submitted to ISC25

The neutral sodium resonance doublet (Na i D) has been detected in the upper atmosphere of several close-in gas giants, through high-resolution transmission spectroscopy. We aim to investigate whether its variability is linked to the planets' properties, the data quality, or the accuracy of the system parameters used. Using the public code SLOPpy, we extracted the transmission spectrum in the Na i D region of ten gas giants for which a large number of HARPS-N observations are available. We modelled the absorption signals found, performing an MCMC analysis, and converted the measured absorption depth to the corresponding atmospheric height over which most sodium absorption occurs. While two targets (GJ 436 b and KELT-7 b) show no Na i D feature, we found variability in the transmission spectrum of the other targets. Three of them (HD 209458 b, WASP-80 b, and WASP-127 b) present absorption on only some nights, while in the other five targets (HD 189733 b, KELT-9 b, KELT-20 b, WASP-69 b, and WASP-76 b), a significant absorption signal is present on most of the nights analysed. Except for WASP-69 b, the measured absorption depths lead to a ratio of the two Na I D depths that is compatible with or slightly larger than one. As was expected from literature, the relative atmospheric height follows an empirical exponential trend as a function of a scaled product of the planet's equilibrium temperature and surface gravity. We confirm the sodium detection on HD 189733 b, KELT-9 b, KELT-20 b, WASP-69 b, and WASP-76 b. The signal detected in WASP-127 b requires further observations for definitive confirmation. We exclude a planetary origin for the signals found on HD 209458 b and WASP-80 b. The sodium absorption variability does not appear to be related to planetary properties, but rather to data quality, sub-optimal data treatment, or stellar activity., Comment: Accepted for publication in Astronomy & Astrophysics on 26 November 2024. Additional material (Figures B.1-B.3 and Tables B.1-B.9) are available on Zenodo

Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution.

We investigated the impact of female politicians on waste collection in Italian municipalities in different territories observed over the years 2010-2019. We used a staggered difference-in-differences design to obtain a causal interpretation of the estimated effects. We find that the majority of women in the municipal council positively influence pro-environmental individual behaviour. The impact of a female-majority council is heterogeneous by region and more pronounced in areas with lower social capital. Female politicians as catalysts for positive change fade after 5-6 years, likely due to persistent social norms locally, thus stressing the need for additional cultural actions with long-lasting effects.

This paper explores multi-entry strategies for betting pools related to single-elimination tournaments. In such betting pools, participants select winners of games, and their respective score is a weighted sum of the number of correct selections. Most betting pools have a top-heavy payoff structure, so the paper focuses on strategies that maximize the expected score of the best-performing entry. There is no known closed-formula expression for the estimation of this metric, so the paper investigates the challenges associated with the estimation and the optimization of multi-entry solutions. We present an exact dynamic programming approach for calculating the maximum expected score of any given fixed solution, which is exponential in the number of entries. We explore the structural properties of the problem to develop several solution techniques. In particular, by extracting insights from the solutions produced by one of our algorithms, we design a simple yet effective problem-specific heuristic that was the best-performing technique in our experiments, which were based on real-world data extracted from recent March Madness tournaments. In particular, our results show that the best 100-entry solution identified by our heuristic had a 2.2% likelihood of winning a $1 million prize in a real-world betting pool.

Congestion pricing is used to raise revenues and reduce traffic and pollution. However, people have heterogeneous spatial demand patterns and willingness (or ability) to pay tolls, and so pricing may have substantial equity implications. We develop a data-driven approach to design congestion pricing given policymakers' equity and efficiency objectives. First, algorithmically, we extend the Markovian traffic equilibrium setting introduced by Baillon & Cominetti (2008) to model heterogeneous populations and incorporate prices and outside options such as public transit. Second, we empirically evaluate various pricing schemes using data collected by an industry partner in the city of Bogota, one of the most congested cities in the world. We find that pricing personalized to each economic stratum can be substantially more efficient and equitable than uniform pricing; however, non-personalized but area-based pricing can recover much of the gap.

This paper introduces the Minimum Price Markov Game (MPMG), a theoretical model that reasonably approximates real-world first-price markets following the minimum price rule, such as public auctions. The goal is to provide researchers and practitioners with a framework to study market fairness and regulation in both digitized and non-digitized public procurement processes, amid growing concerns about algorithmic collusion in online markets. Using multi-agent reinforcement learning-driven artificial agents, we demonstrate that (i) the MPMG is a reliable model for first-price market dynamics, (ii) the minimum price rule is generally resilient to non-engineered tacit coordination among rational actors, and (iii) when tacit coordination occurs, it relies heavily on self-reinforcing trends. These findings contribute to the ongoing debate about algorithmic pricing and its implications.

Bike-sharing systems play a crucial role in easing traffic congestion and promoting healthier lifestyles. However, ensuring their reliability and user acceptance requires effective strategies for rebalancing bikes. This study introduces a novel approach to address the real-time rebalancing problem with a fleet of vehicles. It employs a dual policy reinforcement learning algorithm that decouples inventory and routing decisions, enhancing realism and efficiency compared to previous methods where both decisions were made simultaneously. We first formulate the inventory and routing subproblems as a multi-agent Markov Decision Process within a continuous time framework. Subsequently, we propose a DQN-based dual policy framework to jointly estimate the value functions, minimizing the lost demand. To facilitate learning, a comprehensive simulator is applied to operate under a first-arrive-first-serve rule, which enables the computation of immediate rewards across diverse demand scenarios. We conduct extensive experiments on various datasets generated from historical real-world data, affected by both temporal and weather factors. Our proposed algorithm demonstrates significant performance improvements over previous baseline methods. It offers valuable practical insights for operators and further explores the incorporation of reinforcement learning into real-world dynamic programming problems, paving the way for more intelligent and robust urban mobility solutions.

We consider solving a combinatorial optimization problem with an unknown linear constraint using a membership oracle that, given a solution, determines whether it is feasible or infeasible with absolute certainty. The goal of the decision maker is to find the best possible solution subject to a budget on the number of oracle calls. Inspired by active learning based on Support Vector Machines (SVMs), we adapt a classical framework in order to solve the problem by learning and exploiting a surrogate linear constraint. The resulting new framework includes training a linear separator on the labeled points and selecting new points to be labeled, which is achieved by applying a sampling strategy and solving a 0-1 integer linear program. Following the active learning literature, one can consider using SVM as a linear classifier and the information-based sampling strategy known as simple margin. We improve on both sides: we propose an alternative sampling strategy based on mixed-integer quadratic programming and a linear separation method inspired by an algorithm for convex optimization in the oracle model. We conduct experiments on the pure knapsack problem and on a college study plan problem from the literature to show how different linear separation methods and sampling strategies influence the quality of the results in terms of objective value.

We present the simulation of nuclear magnetic resonance (NMR) spectroscopy of small organic molecules with two promising quantum computing platforms, namely IBM's quantum processors based on superconducting qubits and IonQ's Aria trapped ion quantum computer addressed via Amazon Braket. We analyze the impact of noise on the obtained NMR spectra, and we formulate an effective decoherence rate that quantifies the threshold noise that our proposed algorithm can tolerate. Furthermore we showcase how our noise analysis allows us to improve the spectra. Our investigations pave the way to better employ such application-driven quantum tasks on current noisy quantum devices., Comment: 10 pages, 13 figures

Algorithmic cooling can be used to find correlated states of many-body quantum systems. It is based on quantum circuits that perform non-unitary operations, whose implementation can be challenging on near-term quantum computers. In this work we develop a method that uses inherent qubit noise to implement non-unitary operations and algorithmic cooling. In our approach, qubit decay during quantum computation is used to simulate dissipation of auxiliary-spin bath, which cools down a simulated system towards its ground state. We test the algorithm on IBM-Q devices and demonstrate the relaxation of system spins to ferromagnetic and antiferromagnetic ordering, controlled by the definition of the system Hamiltonian. The ordering is stable as long as the algorithm is run. We are able to perform cooling and state stabilization for global systems of up to three system spins and four auxiliary spins. Our work paves the way for useful quantum simulations of many-body quantum systems on near-term quantum computers., Comment: 19 pages, 12 figures in total: 11 pages main text with 6 figures

Synchronization of coupled oscillators is a fundamental process in both natural and artificial networks. While much work has investigated the asymptotic stability of the synchronous solution, the fundamental question of the transient behavior toward synchronization has received far less attention. In this work, we present the transverse reactivity as a metric to quantify the instantaneous rate of growth or decay of desynchronizing perturbations. We first use the transverse reactivity to design a coupling-efficient and energy-efficient synchronization strategy that involves varying the coupling strength dynamically according to the current state of the system. We find that our synchronization strategy is able to synchronize networks in both simulation and experiment over a significantly larger (often by orders of magnitude) range of coupling strengths than is possible when the coupling strength is constant. Then, we characterize the effects of network topology on the transient dynamics towards synchronization by introducing the concept of network syncreactivity: A network with a larger syncreactivity has a larger transverse reactivity at every point on the synchronization manifold, independent of the oscillator dynamics. We classify real-world examples of complex networks in terms of their syncreactivity., Comment: Accepted for publication in Nature Communications

In this paper, we consider the problem of generating a set of counterfactual explanations for a group of instances, with the one-for-many allocation rule, where one explanation is allocated to a subgroup of the instances. For the first time, we solve the problem of minimizing the number of explanations needed to explain all the instances, while considering sparsity by limiting the number of features allowed to be changed collectively in each explanation. A novel column generation framework is developed to efficiently search for the explanations. Our framework can be applied to any black-box classifier, like neural networks. Compared with a simple adaptation of a mixed-integer programming formulation from the literature, the column generation framework dominates in terms of scalability, computational performance and quality of the solutions.

Mixed Integer Linear Programming (MILP) is a pillar of mathematical optimization that offers a powerful modeling language for a wide range of applications. During the past decades, enormous algorithmic progress has been made in solving MILPs, and many commercial and academic software packages exist. Nevertheless, the availability of data, both from problem instances and from solvers, and the desire to solve new problems and larger (real-life) instances, trigger the need for continuing algorithmic development. MILP solvers use branch and bound as their main component. In recent years, there has been an explosive development in the use of machine learning algorithms for enhancing all main tasks involved in the branch-and-bound algorithm, such as primal heuristics, branching, cutting planes, node selection and solver configuration decisions. This paper presents a survey of such approaches, addressing the vision of integration of machine learning and mathematical optimization as complementary technologies, and how this integration can benefit MILP solving. In particular, we give detailed attention to machine learning algorithms that automatically optimize some metric of branch-and-bound efficiency. We also address how to represent MILPs in the context of applying learning algorithms, MILP benchmarks and software.

Bike-Sharing Systems provide eco-friendly urban mobility, contributing to the alleviation of traffic congestion and to healthier lifestyles. Efficiently operating such systems and maintaining high customer satisfaction is challenging due to the stochastic nature of trip demand, leading to full or empty stations. Devising effective rebalancing strategies using vehicles to redistribute bikes among stations is therefore of uttermost importance for operators. As a promising alternative to classical mathematical optimization, reinforcement learning is gaining ground to solve sequential decision-making problems. This paper introduces a spatio-temporal reinforcement learning algorithm for the dynamic rebalancing problem with multiple vehicles. We first formulate the problem as a Multi-agent Markov Decision Process in a continuous time framework. This allows for independent and cooperative vehicle rebalancing, eliminating the impractical restriction of time-discretized models where vehicle departures are synchronized. A comprehensive simulator under the first-arrive-first-serve rule is then developed to facilitate the learning process by computing immediate rewards under diverse demand scenarios. To estimate the value function and learn the rebalancing policy, various Deep Q-Network configurations are tested, minimizing the lost demand. Experiments are carried out on various datasets generated from historical data, affected by both temporal and weather factors. The proposed algorithms outperform benchmarks, including a multi-period Mixed-Integer Programming model, in terms of lost demand. Once trained, it yields immediate decisions, making it suitable for real-time applications. Our work offers practical insights for operators and enriches the integration of reinforcement learning into dynamic rebalancing problems, paving the way for more intelligent and robust urban mobility solutions.

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problem-specific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.

We present an analysis of Sun-as-a-star observations from four different high-resolution, stabilized spectrographs -- HARPS, HARPS-N, EXPRES, and NEID. With simultaneous observations of the Sun from four different instruments, we are able to gain insight into the radial velocity precision and accuracy delivered by each of these instruments and isolate instrumental systematics that differ from true astrophysical signals. With solar observations, we can completely characterize the expected Doppler shift contributed by orbiting Solar System bodies and remove them. This results in a data set with measured velocity variations that purely trace flows on the solar surface. Direct comparisons of the radial velocities measured by each instrument show remarkable agreement with residual intra-day scatter of only 15-30 cm/s. This shows that current ultra-stabilized instruments have broken through to a new level of measurement precision that reveals stellar variability with high fidelity and detail. We end by discussing how radial velocities from different instruments can be combined to provide powerful leverage for testing techniques to mitigate stellar signals., Comment: 17 pages, 9 figures, accepted for publication