Search

In this paper, we consider both first- and second-order techniques to address continuous optimization problems arising in machine learning. In the first-order case, we propose a framework of transition from deterministic or semi-deterministic to stochastic quadratic regularization methods. We leverage the two-phase nature of stochastic optimization to propose a novel first-order algorithm with adaptive sampling and adaptive step size. In the second-order case, we propose a novel stochastic damped L-BFGS method that improves on previous algorithms in the highly nonconvex context of deep learning. Both algorithms are evaluated on well-known deep learning datasets and exhibit promising performance., Comment: 29 pages, 8 figures. arXiv admin note: text overlap with arXiv:2012.05783

We present ZERO, a modular and extensible C++ library interfacing Mathematical Programming and Game Theory. ZERO provides a comprehensive toolkit of modeling interfaces and algorithms for Reciprocally Bilinear Games (RBGs), i.e., simultaneous non-cooperative games where each player solves a mathematical program with a linear objective in the player's variable and bilinear in its opponents' variables. This class of games generalizes the classical problems of Operations Research to a multi-agent setting. ZERO modular structure gives users all the elementary ingredients to design new game-theoretic models and algorithms for RBGs, and find their Nash equilibria. The library provides additional extended support for integer non-convexities, linear bilevel problems, and linear equilibrium problems with equilibrium constraints. We provide an overview of the software's key components and showcase a Knapsack Game, i.e., a game where each player solves a binary knapsack problem. Aiming to boost practical methodological contributions at the interplay of Mathematical Programming and Game Theory, we release ZERO as open-source software. Source code, documentation and examples are available at www.getzero.one.

We introduce Cut-and-Play, a practically-efficient algorithm for computing Nash equilibria in simultaneous non-cooperative games where players decide via nonconvex and possibly unbounded optimization problems with separable payoff functions. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the game and iteratively refines them with cutting planes and branching operations. Our algorithm does not require convexity or continuity of the player's optimization problems and can be integrated with existing optimization software. We test Cut-and-Play on two families of challenging nonconvex games involving discrete decisions and bilevel problems, and we empirically demonstrate that it efficiently computes equilibria while outperforming existing game-specific algorithms.

Motivated by the shortage of seats that the Chilean school choice system is facing, we introduce the problem of jointly increasing school capacities and finding a student-optimal assignment in the expanded market. Due to the theoretical and practical complexity of the problem, we provide a comprehensive set of tools to solve the problem, including different mathematical programming formulations, a cutting plane algorithm, and two heuristics that allow obtaining near-optimal solutions quickly. On the theoretical side, we show the correctness of our formulations, different properties of the objective and feasible region that facilitate computation, and also several properties of the underlying mechanism to find a student-optimal matching under capacity expansions. On the computational side, we use data from the Chilean school choice system to demonstrate the impact of our framework and derive insights that could help alleviate the problem. Our results show that each additional seat can benefit multiple students and that we can effectively target the assignment of previously unassigned students or improve the assignment of several students through improvement chains. Nevertheless, our results show that the marginal effect of each additional seat is decreasing and that simply adding seats is insufficient to ensure every student gets assigned to some school. Finally, we discuss several extensions of our framework, showcasing its flexibility to accommodate different needs.

Despite the extensive research efforts and the remarkable results obtained on Vehicle Routing Problems (VRP) by using algorithms proposed by the Machine Learning community that are partially or entirely based on data-driven analysis, most of these approaches are still seldom employed by the Operations Research (OR) community. Among the possible causes, we believe, the different approach to the computational evaluation of the proposed methods may play a major role. With the current work, we want to highlight a number of challenges (and possible ways to handle them) arising during the computational studies of heuristic approaches to VRPs that, if appropriately addressed, may produce a computational study having the characteristics of those presented in OR papers, thus hopefully promoting the collaboration between the two communities.

The Random Utility Maximization model is by far the most adopted framework to estimate consumer choice behavior. However, behavioral economics has provided strong empirical evidence of irrational choice behavior, such as halo effects, that are incompatible with this framework. Models belonging to the Random Utility Maximization family may therefore not accurately capture such irrational behavior. Hence, more general choice models, overcoming such limitations, have been proposed. However, the flexibility of such models comes at the price of increased risk of overfitting. As such, estimating such models remains a challenge. In this work, we propose an estimation method for the recently proposed Generalized Stochastic Preference choice model, which subsumes the family of Random Utility Maximization models and is capable of capturing halo effects. Specifically, we show how to use partially-ranked preferences to efficiently model rational and irrational customer types from transaction data. Our estimation procedure is based on column generation, where relevant customer types are efficiently extracted by expanding a tree-like data structure containing the customer behaviors. Further, we propose a new dominance rule among customer types whose effect is to prioritize low orders of interactions among products. An extensive set of experiments assesses the predictive accuracy of the proposed approach. Our results show that accounting for irrational preferences can boost predictive accuracy by 12.5% on average, when tested on a real-world dataset from a large chain of grocery and drug stores.

We study the problem of optimizing assortment decisions in the presence of product-specific costs when customers choose according to a multinomial logit model. This problem is NP-hard and approximate solutions methods have been proposed in the literature to obtain both lower and upper bounds in a tractable manner. We propose the first exact solution method for this problem and show that provably optimal assortments of instances with up to one thousand products can be found, on average, in about two tenths of a second. In particular, we propose a bounding procedure based on the approximation method of Feldman and Topaloglu (2015a) to provide tight lower and upper bounds at a fraction of their computing times. We show how these bounds can be used to effectively identify an optimal assortment. We also describe how to adapt our approach to handle cardinality or space/resource capacity constraints on the assortment as well as assortment optimization under a mixed-multinomial logit model. In both cases, our solution method provides significant computational boosts compared to exact methods from the literature.

Transfer learning through large pre-trained models has changed the landscape of current applications in natural language processing (NLP). Recently Optimus, a variational autoencoder (VAE) which combines two pre-trained models, BERT and GPT-2, has been released, and its combination with generative adversial networks (GANs) has been shown to produce novel, yet very human-looking text. The Optimus and GANs combination avoids the troublesome application of GANs to the discrete domain of text, and prevents the exposure bias of standard maximum likelihood methods. We combine the training of GANs in the latent space, with the finetuning of the decoder of Optimus for single word generation. This approach lets us model both the high-level features of the sentences, and the low-level word-by-word generation. We finetune using reinforcement learning (RL) by exploiting the structure of GPT-2 and by adding entropy-based intrinsically motivated rewards to balance between quality and diversity. We benchmark the results of the VAE-GAN model, and show the improvements brought by our RL finetuning on three widely used datasets for text generation, with results that greatly surpass the current state-of-the-art for the quality of the generated texts., Comment: 11 pages, 5 figures, 8 tables

The understanding of depletion layers is of major importance to control the optical and electronic properties of metal oxide (MO) nanocrystals (NCs). Here, we show that depletion layer engineering is the main mechanism of photodoping of MO NCs. We show that the introduction of different electronic interfaces induces a double-bending of the electronic bands and a distinct carrier density profile. We found that the light-induced depletion layer modulation and bending of the bands close to the surface of the nanocrystal is the main mechanism responsible for the storage of extra electrons after photodoping in MO NCs. We support our results by a combined experimental and theoretical approach in the case of Sn:In2O3/In2O3 core-shell NCs, in which we compare numerical simulations with empirical modeling and experiments. This allows not only to extract the main mechanism of photodoping in MO NCs but also to engineer the charge storage capability of MO NCs after photodoping. Our results are transferable to other core-multishell systems, opening up a novel direction to control the optoelectronic properties of nanoscale MOs by designing their energetic band profiles through depletion layer engineering.

We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and broadly applicable as well as problem-specific exact and heuristic solution approaches. While our perspective is that of mathematical optimization, a main goal of this work is to reach out to and build bridges between the different communities in which cardinality optimization problems are frequently encountered. In particular, we highlight that modern mixed-integer programming, which is often regarded as impractical due to commonly unsatisfactory behavior of black-box solvers applied to generic problem formulations, can in fact produce provably high-quality or even optimal solutions for cardinality optimization problems, even in large-scale real-world settings. Achieving such performance typically draws on the merits of problem-specific knowledge that may stem from different fields of application and, e.g., shed light on structural properties of a model or its solutions, or lead to the development of efficient heuristics; we also provide some illustrative examples.

Cluster synchronization in networks of coupled oscillators is the subject of broad interest from the scientific community, with applications ranging from neural to social and animal networks and technological systems. Most of these networks are directed, with flows of information or energy that propagate unidirectionally from given nodes to other nodes. Nevertheless, most of the work on cluster synchronization has focused on undirected networks. Here we characterize cluster synchronization in general directed networks. Our first observation is that, in directed networks, a cluster A of nodes might be one-way dependent on another cluster B: in this case, A may remain synchronized provided that B is stable, but the opposite does not hold. The main contribution of this paper is a method to transform the cluster stability problem in an irreducible form. In this way, we decompose the original problem into subproblems of the lowest dimension, which allows us to immediately detect inter-dependencies among clusters. We apply our analysis to two examples of interest, a human network of violin players executing a musical piece for which directed interactions may be either activated or deactivated by the musicians, and a multilayer neural network with directed layer-to-layer connections., Comment: This is a preprint of an article published in Nature Communications. The final authenticated version is available online at: https://doi.org/10.1038/s41467-021-24363-7 or https://rdcu.be/cnyaD

State of the art radial velocity (RV) exoplanet searches are limited by the effects of stellar magnetic activity. Magnetically active spots, plage, and network regions each have different impacts on the observed spectral lines, and therefore on the apparent stellar RV. Differentiating the relative coverage, or filling factors, of these active regions is thus necessary to differentiate between activity-driven RV signatures and Doppler shifts due to planetary orbits. In this work, we develop a technique to estimate feature-specific magnetic filling factors on stellar targets using only spectroscopic and photometric observations. We demonstrate linear and neural network implementations of our technique using observations from the solar telescope at HARPS-N, the HK Project at the Mt. Wilson Observatory, and the Total Irradiance Monitor onboard SORCE. We then compare the results of each technique to direct observations by the Solar Dynamics Observatory (SDO). Both implementations yield filling factor estimates that are highly correlated with the observed values. Modeling the solar RVs using these filling factors reproduces the expected contributions of the suppression of convective blueshift and rotational imbalance due to brightness inhomogeneities. Both implementations of this technique reduce the overall activity-driven RMS RVs from 1.64 m/s to 1.02 m/s, corresponding to a 1.28 m/s reduction in the RMS variation. The technique provides an additional 0.41 m/s reduction in the RMS variation compared to traditional activity indicators., Comment: 16 pages, 6 figures, accepted by The Astrophysical Journal

The atmospheres of gaseous giant exoplanets orbiting close to their parent stars (hot Jupiters) have been probed for nearly two decades. They allow us to investigate the chemical and physical properties of planetary atmospheres under extreme irradiation conditions. Previous observations of hot Jupiters as they transit in front of their host stars have revealed the frequent presence of water vapour and carbon monoxide in their atmospheres; this has been studied in terms of scaled solar composition under the usual assumption of chemical equilibrium. Both molecules as well as hydrogen cyanide were found in the atmosphere of HD 209458b, a well studied hot Jupiter (with equilibrium temperature around 1,500 kelvin), whereas ammonia was tentatively detected there and subsequently refuted. Here we report observations of HD 209458b that indicate the presence of water (H2O), carbon monoxide (CO), hydrogen cyanide (HCN), methane (CH4), ammonia (NH3) and acetylene (C2H2), with statistical significance of 5.3 to 9.9 standard deviations per molecule. Atmospheric models in radiative and chemical equilibrium that account for the detected species indicate a carbon-rich chemistry with a carbon-to-oxygen ratio close to or greater than 1, higher than the solar value (0.55). According to existing models relating the atmospheric chemistry to planet formation and migration scenarios, this would suggest that HD 209458b formed far from its present location and subsequently migrated inwards. Other hot Jupiters may also show a richer chemistry than has been previously found, which would bring into question the frequently made assumption that they have solar-like and oxygen-rich compositions., Comment: As part of the Springer Nature Content Sharing Initiative, it is possible to access a view-only version of this paper by using the following SharedIt link: https://rdcu.be/cifrz

In this paper we describe Ecole (Extensible Combinatorial Optimization Learning Environments), a library to facilitate integration of machine learning in combinatorial optimization solvers. It exposes sequential decision making that must be performed in the process of solving as Markov decision processes. This means that, rather than trying to predict solutions to combinatorial optimization problems directly, Ecole allows machine learning to work in cooperation with a state-of-the-art a mixed-integer linear programming solver that acts as a controllable algorithm. Ecole provides a collection of computationally efficient, ready to use learning environments, which are also easy to extend to define novel training tasks. Documentation and code can be found at https://www.ecole.ai.

Transiting ultra-hot Jupiters are ideal candidates to study the exoplanet atmospheres and their dynamics, particularly by means of high-resolution, high signal-to-noise ratio spectra. One such object is KELT-20b, orbiting the fast rotating A2-type star KELT-20. Many atomic species have already been found in its atmosphere, with blueshifted signals that hints at the presence of a day-to-night side wind. We aimed to observe the atmospheric Rossiter-McLaughlin effect in the ultra-hot Jupiter KELT-20b, and to study any variation of the atmospheric signal during the transit. For this purpose, we analysed five nights of HARPS-N spectra covering five transits of KELT-20b. We computed the mean line profiles of the spectra with a least-squares deconvolution, and then we extracted the stellar radial velocities by fitting them with a rotational broadening profile in order to obtain the radial velocity time-series. We used the mean line profile residuals tomography to analyse the planetary atmospheric signal and its variations. We also used the cross-correlation method to study an already known double-peak feature in the FeI planetary signal. We observed both the classical and the atmospheric Rossiter-McLaughlin effect in the radial velocity time-series. The latter gave us an estimate of the radius of the planetary atmosphere that correlates with the stellar mask used in our work: R(p+atmo)/Rp = 1.13 +/- 0.02). We isolated the planetary atmospheric trace in the tomography, and we found radial velocity variations of the planetary atmospheric signal during transit with an overall blueshift of approximatively 10 km/s, along with small variations in the signal's depth and, less significant, in the full width at half maximum (FWHM). We also find a possible variation in the structure and position of FeI signal in different transits., Comment: 13 pages, 20 figures. Accepted for publication in A&A

Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.