This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods. The instances and code for the competition are available at https://github.com/paulorocosta/ai-for-tsp-competition.

Real Time Bidding is the process of selling and buying online advertisements in real time auctions. Real time auctions are performed in header bidding partners or ad exchanges to sell publishers' ad placements. Ad exchanges run second price auctions and a reserve price should be set for each ad placement or impression. This reserve price is normally determined by the bids of header bidding partners. However, ad exchange may outbid higher reserve prices and optimizing this value largely affects the revenue. In this paper, we propose a deep reinforcement learning approach for adjusting the reserve price of individual impressions using contextual information. Normally, ad exchanges do not return any information about the auction except the sold-unsold status. This binary feedback is not suitable for maximizing the revenue because it contains no explicit information about the revenue. In order to enrich the reward function, we develop a novel reward shaping approach to provide informative reward signal for the reinforcement learning agent. Based on this approach, different intervals of reserve price get different weights and the reward value of each interval is learned through a search procedure. Using a simulator, we test our method on a set of impressions. Results show superior performance of our proposed method in terms of revenue compared with the baselines.

This paper proposes a Deep Reinforcement Learning (DRL) approach for solving knapsack problem. The proposed method consists of a state aggregation step based on tabular reinforcement learning to extract features and construct states. The state aggregation policy is applied to each problem instance of the knapsack problem, which is used with Advantage Actor Critic (A2C) algorithm to train a policy through which the items are sequentially selected at each time step. The method is a constructive solution approach and the process of selecting items is repeated until the final solution is obtained. The experiments show that our approach provides close to optimal solutions for all tested instances, outperforms the greedy algorithm, and is able to handle larger instances and more flexible than an existing DRL approach. In addition, the results demonstrate that the proposed model with the state aggregation strategy not only gives better solutions but also learns in less timesteps, than the one without state aggregation.

The extremely high turnover of online advertising makes it one of the most important sources of income for many online ad publishers. Advertising through world wide web is mainly performed by Real Time Bidding in which the advertisers and the publishers participate to online auctions for trading the ad slots. Publishers usually set the reserve prices for their ad slots and any winning buyer in the auctions performed by ad exchanges has to pay at least the value of reserve price. Header bidding is a way of real time bidding and it becomes very popular, but how to use it together with advertising Exchanges (AdX) to achieve good revenue for online publishers is not well studied. In this paper, we propose a method that makes use of the historical auction data from header bidding and AdX to learn and optimize the reserve price for AdX. We propose a method based on supervised learning and survival analysis to increase the reserve price. The method assumes no information about current auctions and the bids of header bidding and AdX response are predicted and used to determine the highest possible reserve price. The experiments with real-world auction data show the promising results of our method in increasing the expected revenue of online publishers.

Water distribution networks have shown an increased rate of failure due to material deterioration. In this paper, we apply a Recurrent Neural Hawkes Process model to learn the failure intensity function of water pipes. The failure intensity function is learned based on two components: the base failure rate that is determined by the unique pipe profile attributes, and the effect of past failures. Compared to the existing solutions, our model is able to predict the time to next failure on an individual water pipe level. The learned failure intensity function is used to identify value points in the deterioration process of water pipes that represent their economical end-of-life. We use data from a Dutch water distribution network that consists of 49,600 km of pipelines to test the performance of the proposed model. We have made this dataset available online.

Online advertising is one of the most important sources of income for many online publishers. The process is as easy as placing slots in the website and selling those slots in real time bidding auctions. Since websites load in few milliseconds, the bidding and selling process should not take too much time. Sellers or publishers of advertisements aim to maximize the revenue obtained through online advertising. In this paper, we propose a method to select the most profitable ad network for each ad request that is built upon our previous work [1]. The proposed method consists of two parts: a prediction model and a reinforcement learning modeling. We test two strategies of selecting ad network orderings. The first strategy uses the developed prediction model to greedily choose the network with the highest expected revenue. The second strategy is a two-step approach, where a reinforcement learning method is used to improve the revenue estimation of the prediction model. Using real AD auction data, we show that the ad network ordering obtained from the second strategy returns much higher revenue than the first strategy.

A high percentage of online advertising is currently performed through real time bidding. Impressions are generated once a user visits the websites containing empty ad slots, which are subsequently sold in an online ad exchange market. Nowadays, one of the most important sources of income for publishers who own websites is through online advertising. From a publisher’s point of view it is critical to send its impressions to most profitable ad networks and to fill its ad slots quickly in order to increase their revenue. In this paper we present a method for helping publishers to decide which ad networks to use for each available impression. Our proposed method uses reinforcement learning with initial state-action values obtained from a prediction model to find the best ordering of ad networks in the waterfall fashion. We show that this method increases the expected revenue of the publisher.