We propose a novel two-level hierarchical auction model for 5G RAN network slicing that enables financially-aware resource allocation among Mobile Network Operators (MNOs), Mobile Virtual Network Operators (MVNOs), and end users. Compared to prior models that primarily emphasize technical resource utilization, our approach integrates a realistic financial cost framework, including electricity consumption and resale bidding fees into the optimization process. Each level solves a Winner Determination Problem (WDP) using Integer Linear Programming (ILP) and scalable heuristic algorithms. Vickrey–Clarke–Groves (VCG)-based pricing is adopted to ensure incentive compatibility and procedural fairness among bidders. The optimization objective is to maximize the social welfare, defined in this work as the total valuation of accepted requests minus the electricity cost incurred by CU–DU placement. Power consumption is therefore internalized as a cost component in the objective function rather than treated as an independent optimization target. Through extensive simulations over different network topologies and dynamic traffic conditions, we show that the proposed approach achieves higher social welfare compared to baseline methods, while maintaining scalability and satisfying the latency and capacity constraints of heterogeneous network slices.

Neural combinatorial optimization (NCO) has gained significant attention due to the potential of deep learning to efficiently solve combinatorial optimization problems. NCO has been widely applied to job shop scheduling problems (JSPs) with the current focus predominantly on deterministic problems. In this paper, we propose a novel attention-based scenario processing module (SPM) to extend NCO methods for solving stochastic JSPs. Our approach explicitly incorporates stochastic information by an attention mechanism that captures the embedding of sampled scenarios (i.e., an approximation of stochasticity). Fed with the embedding, the base neural network is intervened by the attended scenarios, which accordingly learns an effective policy under stochasticity. We also propose a training paradigm that works harmoniously with either the expected makespan or Value-at-Risk objective. Results demonstrate that our approach outperforms existing learning and non-learning methods for the flexible JSP problem with stochastic processing times on a variety of instances. In addition, our approach holds significant generalizability to varied numbers of scenarios and disparate distributions.

Deep reinforcement learning (DRL) has emerged as an effective technique for dynamic algorithm configuration, particularly in evolutionary computation, enabling adaptive parameter updates during algorithmic execution. DRL-based methods have shown broad applicability across different problem domains and are designed to configure algorithms without problem-specific information, making them highly transferable across problem variants and scalable to different problem sizes. This paper proposes a novel graph neural network-based approach that learns representations of Search Trajectory Networks (STNs) to track the convergence behavior of multiple objectives and dynamically reconfigures multi-objective evolutionary algorithms during execution. By capturing how solutions evolve and interact over time, the STN-based state representation enables real-time insight into convergence, diversity, and their trade-offs, facilitating more informed and adaptive configuration decisions. Extensive experiments indicate that our method outperforms the state-of-the-art DRL-based algorithm configuration methods. It also demonstrates good scalability to large problem instances and effectiveness in real-world optimization problems, which are often computationally expensive to tune.

Algorithm selection is a well-known problem where researchers investigate how to construct useful features representing the problem instances and then apply feature-based machine learning models to predict the best algorithm for each instance. However, even for simple optimization problems like Euclidean Traveling Salesman Problem (TSP), there lacks a general and effective feature representation for problem instances. The important features of TSP are relatively well understood in the literature, based on extensive domain knowledge and post-analysis of the solutions. In recent years, Convolutional Neural Network (CNN) has gained popularity for TSP algorithm selection. Compared to traditional feature-based models, CNN has an automatic feature-learning ability and demands less domain expertise. However, it is still required to generate intermediate representations, i.e., multiple images to represent TSP instances first. In this paper, we revisit algorithm selection for TSP and propose GINES, a new Graph Neural Network (GNN) that uses city coordinates and distances as input. GINES introduces a novel message-passing mechanism and local feature extractor to learn TSP’s spatial information. Evaluation of two benchmarks shows GINES outperforms CNN and GINE models and surpasses traditional feature-based methods on one dataset. Our codes and datasets are available at https://github.com/lurenyi233/GINES TSP.

This paper proposes Decomposed Retrieval of Constraints (DRoC), a novel framework aimed at enhancing large language models (LLMs) in exploiting solvers to tackle vehicle routing problems (VRPs) with intricate constraints. While LLMs have shown promise in solving simple VRPs, their potential in addressing complex VRP variants is still suppressed, due to the limited embedded internal knowledge that is required to accurately reflect diverse VRP constraints. Our approach mitigates the issue by integrating external knowledge via a novel retrieval-augmented generation (RAG) approach. More specifically, the DRoC decomposes VRP constraints, externally retrieves information relevant to each constraint, and synergistically combines internal and external knowledge to benefit the program generation for solving VRPs. The DRoC also allows LLMs to dynamically select between RAG and self-debugging mechanisms, thereby optimizing program generation without the need for additional training. Experiments across 48 VRP variants exhibit the superiority of DRoC, with significant improvements in the accuracy rate and runtime error rate delivered by the generated programs. The DRoC framework has the potential to elevate LLM performance in complex optimization tasks, fostering the applicability of LLMs in industries such as transportation and logistics.

Deep reinforcement learning (DRL) has been widely used for dynamic algorithm configuration, particularly in evolutionary computation, which benefits from the adaptive update of parameters during the algorithmic execution. However, applying DRL to algorithm configuration for multi-objective combinatorial optimization (MOCO) problems remains relatively unexplored. This paper presents a novel graph neural network (GNN) based DRL to configure multi-objective evolutionary algorithms. We model the dynamic algorithm configuration as a Markov decision process, representing the convergence of solutions in the objective space by a graph, with their embeddings learned by a GNN to enhance the state representation. Experiments on diverse MOCO challenges indicate that our method outperforms traditional and DRL-based algorithm configuration methods in terms of efficacy and adaptability. It also exhibits advantageous generalizability across objective types and problem sizes, and applicability to different evolutionary computation methods.

Network slicing is a key 5G technology that enables multiple virtual networks to share physical infrastructure, optimizing flexibility and resource allocation. This involves Mobile Network Operators (MNO), Mobile Virtual Network Operators (MVNOs), and end users, where MNO leases network slices to MVNOs, and then provides customized services. This work considers end-to-end network slicing with a focus on fair sharing and financial-related power efficiency, modeled as a twolevel hierarchical combinatorial auction. At the upper level, an MNO auctions slices to competing MVNOs, while at the lower level, MVNOs allocate resources to end users through their own auctions. Dynamic user requests add complexity to the process. Our model optimizes resource allocation and revenue generation using a pair-bid mechanism and Vickrey-Clarke- Groves (VCG) pricing. The pair-bid approach enhances competition and efficiency, while VCG ensures truthful bidding based on marginal system impact. Simulations validate the model’s effectiveness in resource distribution and financial performance, showing a $\mathbf{1 2. 5} \boldsymbol{\%}$ revenue improvement over the baseline.

Combinatorial optimization (CO) problems, central to decision-making scenarios like logistics and manufacturing, are traditionally solved using problem-specific algorithms requiring significant domain expertise. While large language models (LLMs) have shown promise in automating CO problem solving, existing approaches rely on intermediate steps such as code generation or solver invocation, limiting their generality and accessibility. This paper introduces a novel framework that empowers LLMs to serve as end-to-end CO solvers by directly mapping natural language problem descriptions to solutions. We propose a two-stage training strategy: supervised fine-tuning (SFT) imparts LLMs with solution construction patterns from domain-specific solvers, while a feasibility-and-optimality-aware reinforcement learning (FOARL) process explicitly mitigates constraint violations and refines solution quality. Evaluation across seven NP-hard CO problems shows that our method achieves a high feasibility rate and reduces the average optimality gap to 1.03–8.20% by tuning a 7B-parameter LLM, surpassing both general-purpose LLMs (e.g., GPT-4o), reasoning models (e.g., DeepSeek-R1), and domain-specific heuristics. Our method establishes a unified language-based pipeline for CO without extensive code execution or manual architectural adjustments for different problems, offering a general and language-driven alternative to traditional solver design while maintaining relative feasibility guarantees.

The Job Shop Scheduling Problem (JSSP) is a complex combinatorial optimization problem. While online Reinforcement Learning (RL) has shown promise by quickly finding acceptable solutions for JSSP, it faces key limitations: it requires extensive training interactions from scratch leading to sample inefficiency, cannot leverage existing high-quality solutions from traditional methods like Constraint Programming (CP), and require simulated environments to train in, which are impracticable to build for complex scheduling environments. We introduce Offline Learned Dispatching (Offline-LD), an offline reinforcement learning approach for JSSP, which addresses these limitations by learning from historical scheduling data. Our approach is motivated by scenarios where historical scheduling data and expert solutions are available or scenarios where online training of RL approaches with simulated environments is impracticable. Offline-LD introduces maskable variants of two Q-learning methods, namely, Maskable Quantile Regression DQN (mQRDQN) and discrete maskable Soft Actor-Critic (d-mSAC), that are able to learn from historical data, through Conservative Q-Learning (CQL), whereby we present a novel entropy bonus modification for d-mSAC, for maskable action spaces. Moreover, we introduce a novel reward normalization method for JSSP in an offline RL setting. Our experiments demonstrate that Offline-LD outperforms online RL on both generated and benchmark instances when trained on only 100 solutions generated by CP. Notably, introducing noise to the expert dataset yields comparable or superior results to using the expert dataset, with the same amount of instances, a promising finding for real-world applications, where data is inherently noisy and imperfect.

In this paper, we introduce multi-objective deep centralized multi-agent actor-critic (MO-DCMAC), a multi-objective reinforcement learning method for infrastructural maintenance optimization, an area traditionally dominated by single-objective reinforcement learning (RL) approaches. Previous single-objective RL methods combine multiple objectives, such as probability of collapse and cost, into a singular reward signal through reward-shaping. In contrast, MO-DCMAC can optimize a policy for multiple objectives directly, even when the utility function is nonlinear. We evaluated MO-DCMAC using two utility functions, which use probability of collapse and cost as input. The first utility function is the threshold utility, in which MO-DCMAC should minimize cost so that the probability of collapse is never above the threshold. The second is based on the failure mode, effects, and criticality analysis methodology used by asset managers to assess maintenance plans. We evaluated MO-DCMAC, with both utility functions, in multiple maintenance environments, including ones based on a case study of the historical quay walls of Amsterdam. The performance of MO-DCMAC was compared against multiple rule-based policies based on heuristics currently used for constructing maintenance plans. Our results demonstrate that MO-DCMAC outperforms traditional rule-based policies across various environments and utility functions.

The Adaptive Large Neighborhood Search (ALNS) algorithm has shown considerable success in solving combinatorial optimization problems (COPs). Nonetheless, the performance of ALNS relies on the proper configuration of its selection and acceptance parameters, which is known to be a complex and resource-intensive task. To address this, we introduce a Deep Reinforcement Learning (DRL) based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. The proposed method aims to learn, based on the state of the search, to configure ALNS for the next iteration to yield more effective solutions for the given optimization problem. We evaluate the proposed method on an orienteering problem with stochastic weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches that were the winning methods of the competition, achieving this with significantly fewer training observations. Furthermore, we demonstrate several good properties of the proposed DR-ALNS method: it is easily adapted to solve different routing problems, its learned policies perform consistently well across various instance sizes, and these policies can be directly applied to different problem variants.

Nowadays, a large amount of structured and unstructured data is being produced in various fields, creating tremendous opportunities to implement Machine Learning (ML) algorithms for decision-making. Although ML algorithms can outperform human performance in some fields, the black-box inherent characteristics of advanced models can hinder experts from exploiting them in sensitive domains such as medicine. The black-box nature of advanced ML models shadows the transparency of these algorithms, which could hamper their fair and robust performance due to the complexity of the algorithms. Consequently, individuals, organizations, and societies will not be able to achieve the full potential of ML without establishing trust in its development, deployment, and use. The field of eXplainable Artificial Intelligence (XAI) endeavors to solve this problem by providing human-understandable explanations for black-box models as a potential solution to acquire trustworthy AI. However, explainability is one of many requirements to fulfill trustworthy AI, and other prerequisites must also be met. Hence, this survey analyzes the fulfillment of five algorithmic requirements of accuracy, transparency, trust, robustness, and fairness through the lens of the literature in the medical domain. Regarding that medical experts are reluctant to put their judgment aside in favor of a machine, trustworthy AI algorithmic fulfillment could be a way to convince them to use ML. The results show there is still a long way to implement the algorithmic requirements in practice, and scholars need to consider them in future studies.

Network slicing is an important characteristic of 5G/6G networks that increases flexibility and enables different applications over a single infrastructure. The physical resources are partitioned to create virtualized networks, each dedicated to services with specific requirements. Several entities participate in network slicing, including Mobile Network Operators (MNOs), Mobile Virtual Network Operators (MVNOs), and users. An MNO owns the physical network infrastructure and the resources. MVNOs lease resources from the MNO and operate as service providers towards their subscribers. The goal of this work is to optimize the end-to-end network slicing process to provide services to users with a fair sharing of resources. We model this problem as a hierarchical combinatorial auction with a modified Vickrey-Clarke-Groves pricing mechanism. In the upper-level auction, an MNO is the seller supplying Network Slice to several MVNOs, who act as the bidders. In the lower-level auction, each MVNO holds an auction as a seller delivering services to their subscribed end-users, who play the role of bidders. We formulate and solve the Winner Determination Problem using mathematical programming and heuristic algorithms. The simulations show that the model can achieve fair sharing of resources, and it enables improving the MNO and MVNO revenue.

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.

Abstract The airfreight industry of shipping goods with special handling needs, also known as special cargo, often deals with non-transparent data and outdated technology, resulting in significant inefficiency. A special cargo ontology is a means of extracting, structuring, and storing domain knowledge and representing the concepts and relationships that can be processed by computers. This ontology can be used as the base of semantic data retrieval in many artificial intelligence applications, such as planning for special cargo shipments. Domain information extraction is an essential task in implementing and maintaining special cargo ontology. However, the absence of domain information makes instantiating the cargo ontology challenging. We propose a relation representation learning approach based on a hierarchical attention-based multi-task model and leverage it in the special cargo domain. The proposed relation representation learning architecture is applied for identifying and categorizing samples of various relation types in the special cargo ontology. The model is trained with domain-specific documents on a number of semantic tasks that vary from lightweight tasks in the bottom layers to the heavyweight tasks in the top layers of the model in a hierarchical setting. Therefore, it conveys complementary input features and learns a rich representation. We also train a domain-specific relation representation model that relies only on an entity-linked corpus of cargo shipment domain. These two relation representation models are then employed in a supervised multi-class classifier called Special Cargo Relation Extractor (SCRE). The results of the experiments show that the proposed relation representation models can represent the complex semantic information of the special cargo domain efficiently.

Machine Learning (ML) models play an important role in healthcare thanks to their remarkable performance in predicting complex phenomena. During the COVID-19 pandemic, different ML models were implemented to support decisions in the medical settings. However, clinical experts need to ensure that these models are valid, provide clinically useful information, and are implemented and used correctly. In this vein, they need to understand the logic behind the models to be able to trust them. Hence, developing transparent and interpretable models has increasing relevance. In this work, we applied four interpretable ML models including logistic regression, decision tree, pyFUME, and RIPPER to classify suspected COVID-19 patients based on clinical data collected from blood samples. After preprocessing the data set and training the models, we evaluate the models based on their predictive performance. Then, we illustrate that interpretability can be achieved in different ways. First, SHAP explanations are built from logistic regression and decision trees to obtain the features' importance. Then, the potential of pyFUME and RIPPER in providing inherent interpretability are reflected. Finally, potential ways to achieve trust in future studies are briefly discussed.

Contains fulltext : 250749.pdf (Publisher’s version ) (Open Access)

In this work we consider a seller who sells an item via second-price auctions with a reserve price. By controlling the reserve price, the seller can influence the revenue from the auction, and in this paper, we propose a method for learning optimal reserve prices. We study a limited information setting where the probability distribution of the bids from bidders is unknown and the values of the bids are not revealed to the seller. Furthermore, we do not assume that the seller has access to a historical data set with bids. Our main contribution is a method that incorporates knowledge about the rules of second-price auctions into a multiarmed bandit framework for optimizing reserve prices in our limited information setting. The proposed method can be applied in both stationary and nonstationary environments. Experiments show that the proposed method outperforms state-of-the-art bandit algorithms. In stationary environments, our method outperforms these algorithms when the horizon is short and performs as good as they do for longer horizons. Our method is especially useful if there is a high number of potential reserve prices. In addition, our method adapts quickly to changing environments and outperforms state-of-the-art bandit algorithms designed for nonstationary environments. Summary of Contribution: A key challenge in online advertising is the pricing of advertisements in online auctions. The scope of our study is second-price auctions with a focus on the reserve price optimization problem from a seller’s point of view. This problem is motivated by the real-life practice of small and medium-sized web publishers. However, the proposed solution approach is applicable to any seller who sells an item via second-price auctions and wants to optimize its reserve price during these auctions. Our solution approach is based on techniques from machine learning and operations research, and it would be beneficial especially for sellers who start the selling process without any historical data and can collect the data on the outcomes of the auctions while making reserve price decisions over time. History: Accepted by RamRamesh, Area Editor for Data Science & Machine Learning. Supplemental Material: The supplementary material is available at https://doi.org/10.1287/ijoc.2022.1199 .

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.

Deep Reinforcement Learning (RL) has achieved high success in solving routing problems. However, state-of-the-art deep RL approaches require a considerable amount of data before they reach reasonable performance. This may be acceptable for small problems, but as instances grow bigger, this fact severely limits the applicability of these methods to many real-world instances. In this work, we study a setting where the agent can access data from previously handcrafted heuristics for the Traveling Salesman Problem. In our setting, the agent has access to demonstrations from 2-opt improvement policies. Our goal is to learn policies that can surpass the quality of the demonstrations while requiring fewer samples than pure RL. In this study, we propose to first learn policies with Imitation Learning (IL), leveraging a small set of demonstration data to accelerate policy learning. Afterward, we combine on policy and value approximation updates to improve performance over the expert's performance. We show that our method learns good policies in a shorter time and using less data than classical policy gradient, which does not incorporate demonstration data into RL. Moreover, in terms of solution quality, it performs similarly to other state-of-the-art deep RL approaches.

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.

Recent works using deep learning to solve the Traveling Salesman Problem (TSP) have focused on learning construction heuristics. Such approaches find TSP solutions of good quality but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which unlike previous works, can be easily extended to more general $k$-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.

The number of bags mishandled while transferring to a connecting flight is high. Bags at-risk of missing their connections can be processed faster; however, identifying such bags at-risk is still done by simple business rules. This work researches a general model of baggage transfer process and proposes a complex prediction model for identifying the bags at-risk. Our prediction model is compared to the current rule based method and a benchmark using logistic regression. The results show that our model offers an increase in accuracy coupled with a marked increase in precision and recall when identifying bags that are transferred unsuccessfully.

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.

This paper presents a novel method to infer regular expressions from positive examples. The method consists of a candidate’s construction phase and an optimization phase. We first propose multiscaling sample augmentation to capture the cycle patterns from single examples during the candidate’s construction phase. We then use common substrings to build regular expressions that capture patterns across multiple examples, and we show this algorithm is more general than those based on common prefixes or suffixes. Furthermore, we propose a pruning mechanism to improve the efficiency of useful common substring mining, which is an important part of common substring-based expression building algorithm. Finally, in the optimization phase, we model the problem of choosing a set of regular expressions with the lowest cost as an integer linear program, which can be solved to obtain the optimal solution. The experimental results on synthetic and real-life samples demonstrate the effectiveness of our approach in inferring concise and semantically meaningful regular expressions for string datasets.

We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed Mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.

One of the main mechanisms that online publishers use in online advertising in order to sell their advertisement space is the real-time bidding (RTB) mechanism. In RTB the publisher sells advertisement space via a second-price auction. Publishers can set a reserve price for their inventory in the second-price auction. In this paper we consider an online publisher that sells advertisement space and propose a method for learning optimal reserve prices in second-price auctions. We study a limited information setting where the values of the bids are not revealed and no historical information about the values of the bids is available. Our proposed method leverages the dynamics of particles in particle swarm optimization (PSO) to set reserve prices and is suitable for non-stationary environments. We also show that, taking the gap between the winning bid and second highest bid into account leads to better decisions for the reserve prices. Experiments using real-life ad auction data show that the proposed method outperforms popular bandit algorithms.

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.

In this paper we consider an online publisher that sells advertisement space and propose a method for learning optimal reserve prices in second-price auctions. We study a limited information setting where the values of the bids are not revealed and no historical information about the values of the bids is available. Our proposed method is based on the principle of Thompson sampling combined with a particle filter to approximate and sample from the posterior distribution. Our method is suitable for non-stationary environments, and we show that, when the distribution of the winning bid suffers from estimation uncertainty, taking the gap between the winning bid and second highest bid into account leads to better decisions for the reserve prices. Experiments using real-life ad auction data show that the proposed method outperforms popular bandit algorithms.

In this paper we consider an online publisher that sells advertisement space and propose a method for learning optimal reserve prices in second-price auctions. We study a limited information setting where the values of the bids are not revealed and no historical information about the values of the bids is available. Our proposed method combines an adaptive search procedure with a fuzzy logic pricing step to set reserve prices and is suitable for non-stationary environments. In the fuzzy logic pricing step, we take the gap between the winning bid and second highest bid into account and show that this leads to better decisions for the reserve prices. Experiments using real-life ad auction data show that the proposed method outperforms popular bandit algorithms.

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.

Dutch Railways (NS) uses a shunt plan simulator to determine capacities of shunting yards. Central to this simulator is a local search heuristic. Solving this capacity determination problem is very time consuming, as it requires to solve an NP-hard shunting planning problem, and furthermore, the capacity has to determined for a large number of possible scenarios at over 30 shunting yards in The Netherlands. In this paper, we propose to combine machine learning with local search in order to speed up finding shunting plans in the capacity determination problem. The local search heuristic models the activities that take place on the shunting yard as nodes in an activity graph with precedence relations. Consequently, we apply the Deep Graph Convolutional Neural Network, which is a graph classification method, to predict whether local search will find a feasible shunt plan given an initial solution. Our experimental results show our approach can significantly reduce the simulation time in determining the capacity of a given shunting yard. This study demonstrates how machine learning can be used to boost optimization algorithms in an industrial application.

In this work we study a dynamic pricing problem with demand censoring and limited price changes. In our problem there is a seller of a single product that aims to maximize revenue over a finite sales horizon. The seller does not know the form of the mean demand function but does have some limited knowledge. We assume that the seller has a hypothesis set of mean demand functions and that the true mean demand function is an element of this set. Furthermore, the seller faces a business constraint on the number of price changes that is allowed during the sales horizon. More specifically, the number of price changes that the seller is allowed to make is bounded above by a finite integer. We furthermore assume that the seller can only observe the sales (minimum between realized demand and available inventory) and thus that demand is censored. In each period the seller can replenish his inventory to a particular level. The objective of the seller is to set the best price and inventory level in each period of the sales horizon in order to maximize his profit. The profit is determined by the revenue of the sales minus holding costs and costs for lost sales (unsatisfied demand). In determining the best price and inventory level the seller faces and exploration-exploitation trade-off. The seller has to experiment with different prices and inventory levels in order to learn from historical sales data which contains information about market responses to offered prices. On the other hand, the seller also needs to exploit what it has learned and set prices and inventory levels that are optimal given the information collected so far. We propose a heuristic policy for this problem and study its performance using numerical experiments. The results are promising and indicate that the growth rate of regret of the policy is sub-linear with respect to the sales horizon.

In many situations, simulation models are developed to handle complex real-world business optimisation problems. In our case, a discrete-event simulation model is used to simulate trailer management and fleet configuration in a big Fast-Moving Consumer Goods company. To address the problem of finding suitable simulation inputs for optimisation, we propose a simulation optimisation approach. The simulation optimisation model combines metaheuristic search (genetic algorithm), with an approximation model filter (feed-forward neural network) to optimise the input configuration of the simulation model. In this work, we introduce an ensure probability that overrules the rejection of potential solutions by the approximation model and demonstrate its effectiveness. In addition, we evaluate the impact of the genetic algorithm parameters and show how population size, filter threshold, and mutation probability impact overall fleet optimisation performance. Lastly, we compare the proposed method with a single global approximation model and a random-based approach, our results demonstrate the advantage of our method in terms of computational time and solution quality.

A popular method in machine learning for supervised classification is a decision tree. In this work we propose a new framework to learn fuzzy decision trees using mathematical programming. More specifically, we encode the problem of constructing fuzzy decision trees using a Mixed Integer Linear Programming (MIP) model, which can be solved by any optimization solver. We compare the performance of our method with the performance of off-the-shelf decision tree algorithm CART and Fuzzy Inference Systems (FIS) using benchmark data-sets. Our initial results are promising and show the advantages of using non-crisp boundaries for improving classification accuracy on testing data.

The Train Unit Shunting Problem (TUSP) is a difficult sequential decision making problem faced by Dutch Railways (NS). Current heuristic solutions under study at NS fall short in accounting for uncertainty during plan execution and do not efficiently support replanning. Furthermore, the resulting plans lack consistency. We approach the TUSP by formulating it as a Markov Decision Process and develop an image-like state space representation that allows us to develop a Deep Reinforcement Learning (DRL) solution. The Deep Q-Network efficiently reduces the state space and develops an on-line strategy for the TUSP capable of dealing with uncertainty and delivering significantly more consistent solutions compared to approaches currently being developed by NS.

In task allocation problems one usually only considers a single round in which players participate. In practice, many allocation problems are of repeated nature, in which players can decide to keep participating or leave. Players' participation, or behavior, influences the outcome, or social welfare, of these problems. In this paper, we use a fuzzy connective to model agents' behavior in regard to their perception of the game, i.e., optimism level, based on their experiences thus far. We conduct simulations to investigate the interactions between the agents' participation behaviors and the outcomes of the task allocations in multiple rounds. We compare two task allocation algorithms, one merely focusing on costs, and the other focusing on both fairness in the allocation and costs. The results show that the fairer algorithm makes agents more optimistic, and in return, agents keep participating in the allocation game. This leads to a higher social welfare in the long run compared to the cost-minimization algorithm.

In many circumstances where multiple agents need to make a joint decision, voting is used to aggregate the agents' preferences. Each agent's vote carries a weight, and if the sum of the weights of the agents in favor of some outcome is larger than or equal to a given quota, then this outcome is decided upon. The distribution of weights leads to a certain distribution of power. Several `power indices' have been proposed to measure such power. In the so-called inverse problem, we are given a target distribution of power, and are asked to come up with a game in the form of a quota, plus an assignment of weights to the players whose power distribution is as close as possible to the target distribution (according to some specied distance measure). Here we study solution approaches for the larger class of voting game design (VGD) problems, one of which is the inverse problem. In the general VGD problem, the goal is to find a voting game (with a given number of players) that optimizes some function over these games. In the inverse problem, for example, we look for a weighted voting game that minimizes the distance between the distribution of power among the players and a given target distribution of power (according to a given distance measure). Our goal is to find algorithms that solve voting game design problems exactly, and we approach this goal by enumerating all games in the class of games of interest. We first present a doubly exponential algorithm for enumerating the set of simple games. We then improve on this algorithm for the class of weighted voting games and obtain a quadratic exponential (i.e., 2^O(n^2)) algorithm for enumerating them. We show that this improved algorithm runs in output-polynomial time, making it the fastest possible enumeration algorithm up to a polynomial factor. Finally, we propose an exact anytime-algorithm that runs in exponential time for the power index weighted voting game design problem (the `inverse problem'). We implement this algorithm to find a weighted voting game with a normalized Banzhaf power distribution closest to a target power index, and perform experiments to obtain some insights about the set of weighted voting games. We remark that our algorithm is applicable to optimizing any exponential-time computable function, the distance of the normalized Banzhaf index to a target power index is merely taken as an example.

This paper proposes a new variant of the task allocation problem, where the agents are connected in a social network and tasks arrive at the agents distributed over the network. We show that the complexity of this problem remains NP -complete. Moreover, it is not approximable within some factor. In contrast to this, we develop an efficient greedy algorithm for this problem. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a broad set of experiments to evaluate the performance and scalability of the proposed algorithm in terms of solution quality and computation time. Three different types of networks, namely small-world, random and scale-free networks, are used to represent various social relationships among agents in realistic applications. The results demonstrate that our algorithm works well and also that it scales well to large-scale applications. In addition we consider the same problem in a setting where the agents holding the resources are self-interested. For this, we show how the optimal algorithm can be used to incentivize these agents to be truthful. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated.

We consider a multi-agent planning problem as a set of activities that has to be planned by several autonomous agents. In general, due to the possible dependencies between the agents’ activities or interactions during execution of those activities, allowing agents to plan individually may lead to a very inefficient or even infeasible solution to the multi-agent planning problem. This is exactly where plan coordination methods come into play. In this paper, we aim at the development of coordination by design techniques that (i) let each agent construct its plan completely independent of the others while (ii) guaranteeing that the joint combination of their plans always is coordinated. The contribution of this paper is twofold. Firstly, instead of focusing only on the feasibility of the resulting plans, we will investigate the additional costs incurred by the coordination by design method, that means, we propose to take into account the price of autonomy : the ratio of the costs of a solution obtained by coordinating selfish agents versus the costs of an optimal solution. Secondly, we will point out that in general there exist at least two ways to achieve coordination by design: one called concurrent decomposition and the other sequential decomposition . We will briefly discuss the applicability of these two methods, and then illustrate them with two specific coordination problems: coordinating tasks and coordinating resource usage. We also investigate some aspects of the price of autonomy of these two coordination methods.

Multiagent planning methods are concerned with planning by and for a group of agents. If the agents are self-interested, they may be tempted to lie in order to obtain an outcome that is more rewarding for them. We therefore study the multiagent planning problem from a mechanism design perspective, showing how to incentivise agents to be truthful. We prove that the well-known truthful VCG mechanism is not always truthful in the context of optimal planning, and present a modification to fix this. Finally, we present some (domain-dependent) poly-time planning algorithms using this fix that maintain truthfulness in spite of their non-optimality.