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.

Given an ensemble of classifiers, dynamic classifier selection (DCS) selects one classifier depending on the particular input vector that we get to classify. DCS is a special case of algorithm selection (AS) where we can choose from multiple different algorithms to process a given input. We investigate if cost-sensitive hierarchical clustering (CSHC), a method originally developed for AS, is suited for DCS. We tailor CSHC for the special case of choosing a classification algorithm and compare with state-of-the-art DCS methods. We then show how the new methodology can be used for stacking. Experimental results show that CSHC-based DCS outperforms the best methods to date.

Motivated by the need to reduce power consumption in the receiver analog-to-digital converter (ADC) in multi-Gbps communication systems, in this paper, we study subcarrier power allocation based on channel side information (CSI) at the transmitter. We derive a fixed point equation for subcarrier power allocation that minimizes uncoded symbol error rate (SER) when a finite precision ADC is used at the receiver. We study the sensitivity of the optimal power allocation with respect to a parameter that depends on the ADC precision. Based on this, we propose a simple analytical approximation for the optimal power allocation, which performs within 0.5 dB of the exact case over a wide range of signal-to-noise ratio (SNR). The proposed power allocation leads to only a small increase in the peak-to-average power ratio (PAPR) (< 0.3 dB) for channel models suggested in IEEE 802.15.3c. Further, for a 16-QAM input, 7/8 rate low density parity check (LDPC) code and 3-bit precision ADC, it attains a coded bit error rate (BER) of 10^{-5} at a SNR of 23.5 dB, which compares favorably with the 25 dB required by a traditional system with equal power allocation across the subcarriers and infinite sampling precision. We also show the robustness of the performance gain to channel estimation errors.

Orthogonal frequency division multiplexing (OFDM) has been incorporated in standards/draft standards such as IEEE 80.15.3c, IEEE 802.11ad for building multi-Gigabit systems operating in a few GHz of bandwidth. The digital implementation of the receivers for such a system is challenging because high precision (6+ bits/sample) analog-to-digital conversion (ADC) at such high speeds is power hungry and expensive. In this paper, we show that by suitable subcarrier power allocation we can get good performance even with low precision ADC (1-4 bits/sample without oversampling). We derive an analytical expression for the uncoded SER of an M-QAM OFDM system with finite precision ADC. By accounting for automatic gain control (AGC), we show that equal received subcarrier power (ERSP) leads to less quantization noise power than equal transmit subcarrier power (ETSP). Furthermore, for high SNR, ERSP has a lower symbol error rate (SER) than ETSP. But for lower SNR, ETSP is better, and hence we also use convex combinations of ETSP and ERSP power allocations. We illustrate the accuracy of our analytical results with simulations for the Saleh-Valenzuela channel model with log-normal fading. Our results show that for 16-QAM, at SER of 0.01, with a 3-bit ADC and a combination of ERSP and ETSP, we can come within 1 dB of ETSP of the full precision case (while ETSP with 3-bit ADC has a SER floor above 0.04).