In this paper, we formulate a new problem related to the well-known influence maximization in the context of computational advertising. Our new problem considers allocating marketing channels (e.g., TV, newspaper, and websites) to advertisers from the view point of a match maker, which was not taken into account in previous studies on the influence maximization. The objective of the problem is to find an allocation such that each advertiser can influence some given number of customers while the slots of marketing channels are limited. We propose an algorithm based on the Lagrangian decomposition. We empirically show that our algorithm computes better quality solutions than existing algorithms, scales up to graphs of 10M vertices, and performs well particularly in a parallel environment.

Model selection and hyperparameter optimization is crucial in applying machine learning to a novel dataset. Recently, a subcommunity of machine learning has focused on solving this problem with Sequential Model-based Bayesian Optimization (SMBO), demonstrating substantial successes in many applications. However, for computationally expensive algorithms the overhead of hyperparameter optimization can still be prohibitive. In this paper we mimic a strategy human domain experts use: speed up optimization by starting from promising configurations that performed well on similar datasets. The resulting initialization technique integrates naturally into the generic SMBO framework and can be trivially applied to any SMBO method. To validate our approach, we perform extensive experiments with two established SMBO frameworks (Spearmint and SMAC) with complementary strengths; optimizing two machine learning frameworks on 57 datasets. Our initialization procedure yields mild improvements for low-dimensional hyperparameter optimization and substantially improves the state of the art for the more complex combined algorithm selection and hyperparameter optimization problem.

Hyperparameter optimization is crucial for achieving peak performance with many machine learning algorithms; however, the evaluation of new optimization techniques on real-world hyperparameter optimization problems can be very expensive. Therefore, experiments are often performed using cheap synthetic test functions with characteristics rather different from those of real benchmarks of interest. In this work, we introduce another option: cheap-to-evaluate surrogates of real hyperparameter optimization benchmarks that share the same hyperparameter spaces and feature similar response surfaces. Specifically, we train regression models on data describing a machine learning algorithm’s performance depending on its hyperparameter setting, and then cheaply evaluate hyperparameter optimization methods using the model’s performance predictions in lieu of running the real algorithm. We evaluated a wide range of regression techniques, both in terms of how well they predict the performance of new hyperparameter settings and in terms of the quality of surrogate benchmarks obtained. We found that tree-based models capture the performance of several machine learning algorithms well and yield surrogate benchmarks that closely resemble real-world benchmarks, while being much easier to use and orders of magnitude cheaper to evaluate.

This paper proposes incremental preference elicitation methods for multiobjective state space search. Our approach consists in integrating weight elicitation and search to determine, in a vector-valued state-space graph, a solution path that best fits the Decision Maker's preferences. We first assume that the objective weights are imprecisely known and propose a state space search procedure to determine the set of possibly optimal solutions. Then, we introduce incremental elicitation strategies during the search that use queries to progressively reduce the set of admissible weights until a nearly-optimal path can be identified. The validity of our algorithms is established and numerical tests are provided to test their efficiency both in terms of number of queries and solution times.

Modern organizations (e.g., hospitals, social networks, government agencies) rely heavily on audit to detect and punish insiders who inappropriately access and disclose confidential information. Recent work on audit games models the strategic interaction between an auditor with a single audit resource and auditees as a Stackelberg game, augmenting associated well-studied security games with a configurable punishment parameter. We significantly generalize this audit game model to account for multiple audit resources where each resource is restricted to audit a subset of all potential violations, thus enabling application to practical auditing scenarios. We provide an FPTAS that computes an approximately optimal solution to the resulting non-convex optimization problem. The main technical novelty is in the design and correctness proof of an optimization transformation that enables the construction of this FPTAS. In addition, we experimentally demonstrate that this transformation significantly speeds up computation of solutions for a class of audit games and security games.

With increasing numbers of electric and hybrid vehicles on the road, transportation presents a unique opportunity to leverage data-driven intelligence to realize large scale impact in energy use and emissions. Energy management in these vehicles is highly sensitive to upcoming power load on the vehicle, which is not considered in conventional reactive policies calculated at design time. Advancements in cheap sensing and computation have enabled on-board upcoming load predictions which can be used to optimize energy management. In this work, we propose and evaluate a novel, real-time optimization strategy that leverages predictions from prior data in a simulated hybrid battery-supercapacitor energy management task. We demonstrate a complete adaptive system that improves over the lifetime of the vehicle as more data is collected and prediction accuracy improves. Using thousands of miles of real-world data collected from both petrol and electric vehicles, we evaluate the performance of our optimization strategy with respect to our cost function. The system achieves performance within 10% of the optimal upper bound calculated using a priori knowledge of the upcoming loads. This performance implies improved battery thermal stability, efficiency, and longevity. Our strategy can be applied to optimize energy use in gas-electric hybrids, battery cooling in electric vehicles, and many other load-sensitive tasks in transportation.

We develop a new approach for a pre-disaster planning problem which consists in computing an optimal investment plan to strengthen a transportation network, given that a future disaster probabilistically destroys links in the network. We show how the problem can be formulated as a non-linear integer program and devise an AI algorithm to solve it. In particular, we introduce a new type of extreme resource constraint and develop a practically efficient propagation algorithm for it. Experiments show several orders of magnitude improvements over existing approaches, allowing us to close an existing real-world benchmark and to solve to optimality other, more challenging benchmarks.

The power output of photovoltaic systems (PVS) increases with the use of effective and efficient solar tracking techniques. However, current techniques suffer from several drawbacks in their tracking policy: (i) they usually do not consider the forecasted or prevailing weather conditions; even when they do, they (ii) rely on complex closed-loop controllers and sophisticated instruments; and (iii) typically, they do not take the energy consumption of the trackers into account. In this paper, we propose a policy iteration method (along with specialized variants), which is able to calculate near-optimal trajectories for effective and efficient day-ahead solar tracking, based on weather forecasts coming from on-line providers. To account for the energy needs of the tracking system, the technique employs a novel and generic consumption model. Our simulations show that the proposed methods can increase the power output of a PVS considerably, when compared to standard solar tracking techniques.

Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a low-cost, environmentally-friendly transportation alternative for cities. The management of these systems gives rise to many optimization problems. Chief among these problems is the issue of bicycle rebalancing. Users imbalance the system by creating demand in an asymmetric pattern. This necessitates action to put the system back in balance with the requisite levels of bicycles at each station to facilitate future use. In this paper, we tackle the problem of maintaing system balance during peak rush-hour usageas well as rebalancing overnight to prepare the systemfor rush-hour usage. We provide novel problem formulationsthat have been motivated by both a close collaborationwith the New York City bike share (Citibike) and a careful analysisof system usage data. We analyze system data to discover the best placement of bikes tofacilitate usage. We solve routing problems forovernight shifts as well as clustering problems for handlingmid rush-hour usage. The tools developed from this research are currently in daily use at NYC Bike Share LLC, operators of Citibike.

We address the problem of power system restoration after a significant blackout. Prior work focus on optimization methods for finding high-quality restoration plans. Optimal solutions consist in a sequence of grid repairs and corresponding steady states. However, such approaches lack formal guarantees on the transient stability of restoration actions, a key property to avoid additional grid damage and cascading failures. In this paper, we show how to integrate transient stability in the optimization procedure by capturing the rotor dynamics of power generators. Our approach reasons about the differential equations describing the dynamics and their underlying transient states. The key contribution lies in modeling and solving optimization problems that return stable generators dispatch minimizing the difference with respect to steady states solutions. Computational efficiency is increased using preprocessing procedures along with traditional reduction techniques. Experimental results on existing benchmarks confirm the feasibility of the new approach.