Search

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

We demonstrate algorithmic cooling on IBM-Q devices. We utilize inherent qubit noise to simulate the equilibration of an interacting spin system towards its ground state, when coupled to a dissipative auxiliary-spin bath. The steady-state correlations in the system are defined by the system Hamiltonian and are stable as long as the algorithm can be executed. In particular, we demonstrate the relaxation of system spins to ferromagnetic and antiferromagnetic ordering, controlled by the definition of the Hamiltonian. We are able to perform simulated cooling for global systems of up to three system spins and four auxiliary spins., Comment: 17 pages, 12 figures in total: 9 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

Purpose: A prior randomized trial found a school social intervention yielded significantly better outcomes (social and autism features) immediately following intervention compared to typical school programming (services-as-usual [SAU]) for children on the autism spectrum. In that study, children in the SAU condition subsequently completed a summer social intervention. This study tested longer-term maintenance of effects for children who completed both interventions. Methods: A total of 103 children (ages 6-12 years) on the autism spectrum enrolled and 102 completed the initial RCT. Following the summer social intervention, 90 children from the original RCT completed the longer-term follow-up study. In addition to baseline and posttest in the initial RCT, children from both groups were tested at three follow-up points (five total testing points). At the time of first longitudinal follow-up testing, the children were 1.25-4.25 years post-intervention (ages 8-15 years). Results: Longitudinal multilevel model analyses (and follow-up contrasts) revealed significant improvements for both groups post-intervention on measures of emotion recognition, autism features, and social skills, indicating maintenance of post-intervention improvements over the three follow-up testing points. No between-group differences were found for autism features or social skills over time; however, the school social intervention may have yielded somewhat better emotion recognition skills. Exploratory tests found that child IQ, language level, and length of time since completing the intervention did not moderate outcomes. Conclusion: Both social interventions yielded positive and durable longer-term improvements for children on the autism spectrum. [This paper will be published in "Journal of Autism and Development Disorders."]

Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal trees in terms of accuracy. Other discrete optimization models in the literature address the optimality problem but only work well on relatively small datasets. \cite{firat2020column} proposed a column-generation-based heuristic approach for learning decision trees. This approach improves scalability and can work with large datasets. In this paper, we describe improvements to this column generation approach. First, we modify the subproblem model to significantly reduce the number of subproblems in multiclass classification instances. Next, we show that the data-dependent constraints in the master problem are implied, and use them as cutting planes. Furthermore, we describe a separation model to generate data points for which the linear programming relaxation solution violates their corresponding constraints. We conclude by presenting computational results that show that these modifications result in better scalability., Comment: Submitted to Computers and Operations Research journal

Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints, that we refer to as APV. We are given a universe of substitutable products and a stream of T customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to the constraint that each product is required to be shown to a minimum number of customers. The minimum display requirement for each product is given exogenously and we refer to these constraints as visibility constraints. We assume that customer choices follow a Multinomial Logit model (MNL). We provide a characterization of the structure of the optimal assortments and present an efficient polynomial time algorithm for solving APV. To accomplish this, we introduce a novel function called the ``expanded revenue" of an assortment and establish its supermodularity. Our algorithm takes advantage of this structural property. Additionally, we demonstrate that APV can be formulated as a compact linear program. Next, we consider APV with cardinality constraints, which we prove to be strongly NP-hard and not admitting a Fully Polynomial Time Approximation Scheme (FPTAS), even in the special case where all the products have identical prices. Subsequently, we devise a Polynomial Time Approximation Scheme (PTAS) for APV under cardinality constraints with identical prices. Our algorithm starts by linearizing the objective function through a carefully crafted guessing procedure, then solves the linearized program, and finally randomly rounds the obtained solution to derive a near optimal solution. We also examine the revenue loss resulting from the enforcement of visibility constraints, comparing it to the unconstrained version of the problem and propose a novel strategy to offset the loss.

In recent years, the integration of Machine Learning (ML) models with Operation Research (OR) tools has gained popularity across diverse applications, including cancer treatment, algorithmic configuration, and chemical process optimization. In this domain, the combination of ML and OR often relies on representing the ML model output using Mixed Integer Programming (MIP) formulations. Numerous studies in the literature have developed such formulations for many ML predictors, with a particular emphasis on Artificial Neural Networks (ANNs) due to their significant interest in many applications. However, ANNs frequently contain a large number of parameters, resulting in MIP formulations that are impractical to solve, thereby impeding scalability. In fact, the ML community has already introduced several techniques to reduce the parameter count of ANNs without compromising their performance, since the substantial size of modern ANNs presents challenges for ML applications as it significantly impacts computational efforts during training and necessitates significant memory resources for storage. In this paper, we showcase the effectiveness of pruning, one of these techniques, when applied to ANNs prior to their integration into MIPs. By pruning the ANN, we achieve significant improvements in the speed of the solution process. We discuss why pruning is more suitable in this context compared to other ML compression techniques, and we identify the most appropriate pruning strategies. To highlight the potential of this approach, we conduct experiments using feed-forward neural networks with multiple layers to construct adversarial examples. Our results demonstrate that pruning offers remarkable reductions in solution times without hindering the quality of the final decision, enabling the resolution of previously unsolvable instances.

This work concerns a many-body deterministic model that displays life-like properties as emergence, complexity, self-organization, spontaneous compartmentalization, and self-regulation. The model portraits the dynamics of an ensemble of locally coupled polar phase oscillators, moving in a two-dimensional space, that in certain conditions exhibit emergent superstructures. Those superstructures are self-organized dynamic networks, resulting from a synchronization process of many units, over length scales much greater than the interaction length. Such networks compartmentalize the two-dimensional space with no a priori constraints, due to the formation of porous transport walls, and represent a highly complex and novel non-linear behavior. The analysis is numerically carried out as a function of a control parameter showing distinct regimes: static, stable dynamic networks, intermittency, and chaos. A statistical analysis is drawn to determine the control parameter ranges for the various behaviors to appear., Comment: 14 pages, 8 figures and 4 movies

In this tutorial, we present a computational overview on computing Nash equilibria in Integer Programming Games ($IPG$s), $i.e.$, how to compute solutions for a class of non-cooperative and nonconvex games where each player solves a mixed-integer optimization problem. $IPG$s are a broad class of games extending the modeling power of mixed-integer optimization to multi-agent settings. This class of games includes, for instance, any finite game and any multi-agent extension of traditional combinatorial optimization problems. After providing some background motivation and context of applications, we systematically review and classify the state-of-the-art algorithms to compute Nash equilibria. We propose an essential taxonomy of the algorithmic ingredients needed to compute equilibria, and we describe the theoretical and practical challenges associated with equilibria computation. Finally, we quantitatively and qualitatively compare a sequential Stackelberg game with a simultaneous $IPG$ to highlight the different properties of their solutions., Comment: To appear in INFORMS TutORials in Operations Research 2023