Stepwise explanations are an important tool for interpreting constraint programs. Existing methods rely heavily on repeated minimal unsatisfiable subsets (MUS) extraction or intensive SAT-based propagation, which are computationally prohibitive for large-scale problems with complex constraints. We propose a novel framework leveraging Multi-Valued Decision Diagrams (MDDs) to overcome these bottlenecks. By decomposing CSPs into smaller, graph-based subproblems compactly represented as MDDs, we enable highly efficient constraint propagation through network-flow reformulation. To further enhance efficiency, we propose a Divide-and-Conquer approach to improve the search for minimal explanation steps. Furthermore, we utilize the MDD’s network-flow structure to generate nested explanations that break down complex derivation steps into granular, arc-level details, revealing specifically how variable-value assignments become infeasible. In this way, our approach equips the explainer agent with a voice that provides more intuitive and granular stepwise explanations. Evaluated on Graph Coloring and Nurse Rostering benchmarks, our framework significantly reduces explanation generation time while maintaining interpretability and conciseness compared to state-of-the-art methods.

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.

Neural combinatorial optimization (NCO) has achieved remarkable performance, yet its learned model representations and decision rationale remain a black box. This impedes both academic research and practical deployment, since researchers and stakeholders require deeper insights into NCO models. In this paper, we take the first critical step towards interpreting NCO models by investigating their representations through various probing tasks. Moreover, we introduce a novel probing tool named Coefficient Significance Probing (CS-Probing) to enable deeper analysis of NCO representations by examining the coefficients and statistical significance during probing. Extensive experiments and analysis reveal that NCO models encode low-level information essential for solution construction, while capturing high-level knowledge to facilitate better decisions. Using CS-Probing, we find that prevalent NCO models impose varying inductive biases on their learned representations, uncover direct evidence related to model generalization, and identify key embedding dimensions associated with specific knowledge. These insights can be potentially translated into practice, for example, with minor code modifications, we improve the generalization of the analyzed model. Our work represents a first systematic attempt to interpret black-box NCO models, showcasing probing as a promising tool for analyzing their internal mechanisms and revealing insights for the NCO community. The source code is publicly available [here](https://github.com/123zhangzq/NeurIPS2025_probing).

Training neural networks (NNs) using combinatorial optimization solvers has gained attention in recent years. In low-data settings, the use of state-of-the-art mixed integer linear programming solvers, for instance, has the potential to exactly train an NN while avoiding computing-intensive training and hyperparameter tuning and simultaneously training and sparsifying the network. We study the case of few-bit discrete-valued neural networks, both binarized neural networks (BNNs) whose values are restricted to ±1 and integer-valued neural networks (INNs) whose values lie in the range [Formula: see text]. Few-bit NNs receive increasing recognition because of their lightweight architecture and ability to run on low-power devices: for example, being implemented using Boolean operations. This paper proposes new methods to improve the training of BNNs and INNs. Our contribution is a multiobjective ensemble approach based on training a single NN for each possible pair of classes and applying a majority voting scheme to predict the final output. Our approach results in the training of robust sparsified networks whose output is not affected by small perturbations on the input and whose number of active weights is as small as possible. We empirically compare this BeMi approach with the current state of the art in solver-based NN training and with traditional gradient-based training, focusing on BNN learning in few-shot contexts. We compare the benefits and drawbacks of INNs versus BNNs, bringing new light to the distribution of weights over the [Formula: see text] interval. Finally, we compare multiobjective versus single-objective training of INNs, showing that robustness and network simplicity can be acquired simultaneously, thus obtaining better test performances. Although the previous state-of-the-art approaches achieve an average accuracy of [Formula: see text] on the Modified National Institute of Standards and Technology data set, the BeMi ensemble approach achieves an average accuracy of 68.4% when trained with 10 images per class and 81.8% when trained with 40 images per class while having up to 75.3% NN links removed. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was partially supported by the European Union Horizon 2020 Research and Innovation Programme [Grant 952215]. The work of A. M. Bernardelli is supported by a PhD scholarship funded under the “Programma Operativo Nazionale Ricerca e Innovazione” 2014–2020. Supplemental Material: The software that supports the findings of this study is available within the paper as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0281 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The rise in instant delivery services necessitates efficient route planning in last-mile delivery scenarios, where new orders arrive dynamically and need to be integrated into existing routes. In such contexts, complete re-optimization of routes are not permitted, and node insertion to existing route sequences is the only viable option. However, many existing heuristics for node insertion, such as the Cheapest Insertion (CI) method, are myopic and often result in suboptimal solutions retrospectively. This paper presents Neuro-Ins, an initial yet novel attempt at harnessing a learning-based framework to handle the insertion of new orders for the Pickup and Delivery Problem (PDP). In contrast to CI, which considers only one node at a time for insertion, Neuro-Ins leverages an Attention-Mechanism (AM) based encoder-decoder structure to collectively consider all nodes to be inserted, thereby enhancing the quality of the eventual solution. To further improve the model's representation of the current route, we introduce a position embedding to enrich the node feature embedding with positional information of the route. Experiments on synthetic and real-world datasets demonstrate that Neuro-Ins, trained by PPO, consistently outperforms CI without compromising computational speed, and it also surpasses the performance of state-of-the-art solution methods implemented in the industry. Our findings emphasize the importance of explicitly considering all nodes to be inserted along with the en-route nodes and their positions in the route, showcasing the efficacy of the proposed AM-based framework in optimizing the instant delivery routes.

This paper addresses the challenge of optimizing large-scale retail expansion in competitive urban environments through a data-driven and automated approach to the Competitive Facility Location (CFL) problem. Traditional CFL methods often face limitations in handling large-scale scenarios, relying on manual pre-selection of candidate sites and imposing restrictions on the number of new locations. Our approach uses Adaptive Large Neighborhood Search (ALNS) enhanced with data enrichment techniques, such as community detection on road networks and population weighting based on mobility data. We developed 2 ALNS variants: Community Geometric Centroid (CGC-ALNS) and Population Weighted Centroid (PWC-ALNS). These methods automate the site selection process, eliminating the need for manual pre-selection and enabling evaluation of a large number of store locations. We benchmarked our approaches against ArcGIS, a widely used commercial software for CFL problems. The results demonstrate notable improvements in performance: CGC-ALNS consistently outperforms ArcGIS with up to a 2% increase in consumer count captured, while PWCALNS achieves even greater gains, with an average increase of 4.6% to 13.1% across various store distribution scenarios. Our key contributions include an automated, data-driven site selection process with no restrictions on the number of new sites, and significant performance improvements over existing commercial solutions.

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.

Conventional methodologies for new retail store catchment area and footfall estimation rely on ground surveys which are costly and time-consuming. This study augments existing research in footfall estimation through the innovative integration of mobility data and road network to create population-weighted centroids and delineate residential neighbourhoods via a community detection algorithm. Our findings are then used to enhance Huff Model which is commonly used in site selection and footfall estimation. Our approach demonstrated the vast potential residing within big data where we harness the power of mobility data and road network information, offering a cost-effective and scalable alternative. It obviates the reliance on often outdated census data and government urban planning records, positioning itself as a formidable driver of informed retail strategy. In doing so, our approach is poised to deliver substantial value to the retail industry.

We address the problem of coordinating multiple agents in a dynamic police patrol scheduling via a Reinforcement Learning (RL) approach. Our approach utilizes Multi-Agent Value Function Approximation (MAVFA) with a rescheduling heuristic to learn dispatching and rescheduling policies jointly. Often, police operations are divided into multiple sectors for more effective and efficient operations. In a dynamic setting, incidents occur throughout the day across different sectors, disrupting initially-planned patrol schedules. To maximize policing effectiveness, police agents from different sectors cooperate by sending reinforcements to support one another in their incident response and even routine patrol. This poses an interesting research challenge on how to make such complex decision of dispatching and rescheduling involving multiple agents in a coordinated fashion within an operationally reasonable time. Unlike existing Multi-Agent RL (MARL) approaches which solve similar problems by either decomposing the problem or action into multiple components, our approach learns the dispatching and rescheduling policies jointly without any decomposition step. In addition, instead of directly searching over the joint action space, we incorporate an iterative best response procedure as a decentralized optimization heuristic and an explicit coordination mechanism for a scalable and coordinated decision-making. We evaluate our approach against the commonly adopted two-stage approach and conduct a series of ablation studies to ascertain the effectiveness of our proposed learning and coordination mechanisms.

We address the problem of maritime traffic management in busy waterways to increase the safety of navigation by reducing congestion. We model maritime traffic as a large multiagent systems with individual vessels as agents, and VTS authority as the regulatory agent. We develop a maritime traffic simulator based on historical traffic data that incorporates realistic domain constraints such as uncertain and asynchronous movement of vessels. We also develop a traffic coordination approach that provides speed recommendation to vessels in different zones. We exploit the nature of collective interactions among agents to develop a scalable policy gradient approach that can scale up to real world problems. Empirical results on synthetic and real world problems show that our approach can significantly reduce congestion while keeping the traffic throughput high.

Maritime navigational safety is of utmost importance to prevent vessel collisions in heavily trafficked ports, and avoid environmental costs. In case of a likely near miss among vessels, port traffic controllers provide assistance for safely navigating the waters, often at very short lead times. A better strategy is to avoid such situations from even happening. To achieve this, we a) formalize the decision model for traffic hotspot mitigation including realistic maritime navigational features and constraints through consultations with domain experts; and b) develop a constraint programming based scheduling approach to mitigate hotspots. We model the problem as a variant of the resource constrained project scheduling problem to adjust vessel movement schedules such that the average delay is minimized and navigational safety constraints are also satisfied. We conduct a thorough evaluation on key performance indicators using real world data, and demonstrate the effectiveness of our approach in mitigating high-risk situations.

Urban law enforcement agencies are under great pressure to respond to emergency incidents effectively while operating within restricted budgets. Minutes saved on emergency response times can save lives and catch criminals, and a responsive police force can deter crime and bring peace of mind to citizens. To efficiently minimize the response times of a law enforcement agency operating in a dense urban environment with limited manpower, we consider in this paper the problem of optimizing the spatial and temporal deployment of law enforcement agents to predefined patrol regions in a real-world scenario informed by machine learning. To this end, we develop a mixed integer linear optimization formulation (MIP) to minimize the risk of failing response time targets. Given the stochasticity of the environment in terms of incident numbers, location, timing, and duration, we use Sample Average Approximation (SAA) to find a robust deployment plan. To overcome the sparsity of real data, samples are provided by an incident generator that learns the spatio-temporal distribution and demand parameters of incidents from a real world historical dataset and generates sets of training incidents accordingly. To improve runtime performance across multiple samples, we implement a heuristic based on Iterated Local Search (ILS), as the solution is intended to create deployment plans quickly on a daily basis. Experimental results demonstrate that ILS performs well against the integer model while offering substantial gains in execution time.

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.

We address the problem of mitigating congestion and preventing hotspots in busy water areas such as Singapore Straits and port waters. Increasing maritime traffic coupled with narrow waterways makes vessel schedule coordination for just-in-time arrival critical for navigational safety. Our contributions are: 1) We formulate the maritime traffic management problem based on the real case study of Singapore waters; 2) We model the problem as a variant of the resource-constrained project scheduling problem (RCPSP), and formulate mixed-integer and constraint programming (MIP/CP) formulations; 3) To improve the scalability, we develop a combinatorial Benders (CB) approach that is significantly more effective than standard MIP and CP formulations. We also develop symmetry breaking constraints and optimality cuts that further enhance the CB approach's effectiveness; 4) We develop a realistic maritime traffic simulator using electronic navigation charts of Singapore Straits. Our scheduling approach on synthetic problems and a real 55-day AIS dataset results in significant reduction of the traffic density while incurring minimal delays.

Scaling decision theoretic planning to large multiagent systems is challenging due to uncertainty and partial observability in the environment. We focus on a multiagent planning model subclass, relevant to urban settings, where agent interactions are dependent on their ``collective influence'' on each other, rather than their identities. Unlike previous work, we address a general setting where system reward is not decomposable among agents. We develop collective actor-critic RL approaches for this setting, and address the problem of multiagent credit assignment, and computing low variance policy gradient estimates that result in faster convergence to high quality solutions. We also develop difference rewards based credit assignment methods for the collective setting. Empirically our new approaches provide significantly better solutions than previous methods in the presence of global rewards on two real world problems modeling taxi fleet optimization and multiagent patrolling, and a synthetic grid navigation domain.

In this article, we investigate effective ways of utilizing crowdworkers in providing various urban services. The task recommendation platform that we design can match tasks to crowdworkers based on workers’ historical trajectories and time budget limits, thus making recommendations personal and efficient. One major challenge we manage to address is the handling of crowdworker’s trajectory uncertainties. In this article, we explicitly allow multiple routine routes to be probabilistically associated with each worker. We formulate this problem as an integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures of the formulation and apply the Lagrangian relaxation technique to scale up computation. Numerical experiments have been performed over the instances generated using the realistic public transit dataset in Singapore. The results show that we can find significantly better solutions than the deterministic formulation, and in most cases we can find solutions that are very close to the theoretical performance limit. To demonstrate the practicality of our approach, we deployed our recommendation engine to a campus-scale field trial, and we demonstrate that workers receiving our recommendations incur fewer detours and complete more tasks, and are more efficient against workers relying on their own planning (25% more for top workers who receive recommendations). This is achieved despite having highly uncertain worker trajectories. We also demonstrate how to further improve the robustness of the system by using a simple multi-coverage mechanism.

Orienteering Problems (OPs) are used to model many routing and trip planning problems. OPs are a variant of the well-known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of vertices and has an overall travel time less than a specified deadline. However, the applicability of OPs is limited due to the assumption of deterministic and static travel times. To that end, Campbell et al. extended OPs to Stochastic OPs (SOPs) to represent uncertain travel times (Campbell et al. 2011). In this article, we make the following key contributions: (1) We extend SOPs to Dynamic SOPs (DSOPs), which allow for time-dependent travel times; (2) we introduce a new objective criterion for SOPs and DSOPs to represent a percentile measure of risk; (3) we provide non-linear optimization formulations along with their linear equivalents for solving the risk-sensitive SOPs and DSOPs; (4) we provide a local search mechanism for solving the risk-sensitive SOPs and DSOPs; and (5) we provide results on existing benchmark problems and a real-world theme park trip planning problem.

Multiagent sequential decision making has seen rapid progress with formal models such as decentralized MDPs and POMDPs. However, scalability to large multiagent systems and applicability to real world problems remain limited. To address these challenges, we study multiagent planning problems where the collective behavior of a population of agents affects the joint-reward and environment dynamics. Our work exploits recent advances in graphical models for modeling and inference with a population of individuals such as collective graphical models and the notion of finite partial exchangeability in lifted inference. We develop a collective decentralized MDP model where policies can be computed based on counts of agents in different states. As the policy search space over counts is combinatorial, we develop a sampling based framework that can compute open and closed loop policies. Comparisons with previous best approaches on synthetic instances and a real world taxi dataset modeling supply-demand matching show that our approach significantly outperforms them w.r.t. solution quality.

Decentralized (PO)MDPs provide an expressive framework for sequential decision making in a multiagent system. Given their computational complexity, recent research has focused on tractable yet practical subclasses of Dec-POMDPs. We address such a subclass called CDec-POMDP where the collective behavior of a population of agents affects the joint-reward and environment dynamics. Our main contribution is an actor-critic (AC) reinforcement learning method for optimizing CDec-POMDP policies. Vanilla AC has slow convergence for larger problems. To address this, we show how a particular decomposition of the approximate action-value function over agents leads to effective updates, and also derive a new way to train the critic based on local reward signals. Comparisons on a synthetic benchmark and a real world taxi fleet optimization problem show that our new AC approach provides better quality solutions than previous best approaches.

Traffic speed is a key indicator for the efficiency of an urban transportation system. Accurate modeling of the spatiotemporally varying traffic speed thus plays a crucial role in urban planning and development. This paper addresses the problem of efficient fine-grained traffic speed prediction using big traffic data obtained from static sensors. Gaussian processes (GPs) have been previously used to model various traffic phenomena, including flow and speed. However, GPs do not scale with big traffic data due to their cubic time complexity. In this work, we address their efficiency issues by proposing localGPs to learn from and make predictions for correlated subsets of data. The main idea is to quickly group speed variables in both spatial and temporal dimensions into a finite number of clusters, so that future and unobserved traffic speed queries can be heuristically mapped to one of such clusters. A local GP corresponding to that cluster can then be trained on the fly to make predictions in real-time. We call this method localization. We use non-negative matrix factorization for localization and propose simple heuristics for cluster mapping. We additionally leverage on the expressiveness of GP kernel functions to model road network topology and incorporate side information. Extensive experiments using real-world traffic data collected in the two U.S. cities of Pittsburgh and Washington, D.C., show that our proposed local GPs significantly improve both runtime performances and prediction accuracies compared to the baseline global and local GPs.

With the advent of e-commerce, logistics providers are faced with the challenge of handling fluctuating and sparsely distributed demand, which raises their operational costs significantly. As a result, horizontal cooperation are gaining momentum around the world. One of the major impediments, however, is the lack of stable and fair profit sharing mechanism. In this paper, we address this problem using the framework of computational cooperative games. We first present cooperative vehicle routing game as a model for collaborative logistics operations. Using the axioms of Shapley value as the conditions for fairness, we show that a stable, fair and budget balanced allocation does not exist in many instances of the game. By relaxing budget balance, we then propose an allocation scheme based on the normalized Shapley value. We show that this scheme maintains stability and fairness while requiring minimum subsidy. Finally, using numerical experiments we demonstrate the feasibility of the scheme under various settings.

Uncertainty in activity durations is a key characteristic of many real world scheduling problems in manufacturing, logistics and project management. RCPSP/max with durational uncertainty is a general model that can be used to represent durational uncertainty in a wide variety of scheduling problems where there exist resource constraints. However, computing schedules or execution strategies for RCPSP/max with durational uncertainty is NP-hard and hence we focus on providing approximation methods in this paper. We provide a principled approximation approach based on Sample Average Approximation (SAA) to compute proactive schedules for RCPSP/max with durational uncertainty. We further contribute an extension to SAA for improving scalability significantly without sacrificing on solution quality. Not only is our approach able to compute schedules at comparable runtimes as existing approaches, it also provides lower α-quantile makespan (also referred to as α-robust makespan) values than the best known approach on benchmark problems from the literature.

Collective graphical models (CGMs) provide a framework for reasoning about a population of independent and identically distributed individuals when only noisy and aggregate observations are given. Previous approaches for inference in CGMs work on a junction-tree representation, thereby highly limiting their scalability. To remedy this, we show how the Bethe entropy approximation naturally arises for the inference problem in CGMs. We reformulate the resulting optimization problem as a difference-of-convex functions program that can capture different types of CGM noise models. Using the concave-convex procedure, we then develop a scalable message-passing algorithm. Empirically, our approach is highly scalable and accurate for large graphs, more than an order-of-magnitude faster than a generic optimization solver, and is guaranteed to converge unlike the previous message-passing approach NLBP that fails in several loopy graphs.

Mobile crowd-tasking markets are growing at an unprecedented rate with increasing number of smartphone users. Such platforms differ from their online counterparts in that they demand physical mobility and can benefit from smartphone processors and sensors for verification purposes. Despite the importance of such mobile crowd-tasking markets, little is known about the labor supply dynamics and mobility patterns of the users.

Many conference mobile apps today lack the intelligent feature to automatically generates optimal schedules based on delegates' preferences. This entails two major challenges: (a) identifying preferences of users; and (b) given the preferences, generating a schedule that optimizes his preferences. In this paper, we specifically focus on academic conferences, where users are prompted to input their preferred keywords. Our key contribution is an integrated conference scheduling agent that automatically recognizes user preferences based on keywords, provides a list of recommended talks and optimizes user schedule based on these preferences. To demonstrate the utility of our integrated conference scheduling agent, we first demonstrated the app in the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2015) and conducted a survey to collect some data, which are used to verify the results presented in this paper. It is able to provide well calibrated results with respect to precision, accuracy and recall. We also tested the app in the 2015 WI-IAT International Conference (Singapore). The android and web-based apps have been demonstrated and deployed in AAMAS 2016 (Singapore) with positive responses from the users.

We consider the problem of trajectory prediction, where a trajectory is an ordered sequence of location visits and corresponding timestamps. The problem arises when an agent makes sequential decisions to visit a set of spatial locations of interest. Each location bears a stochastic utility and the agent has a limited budget to spend. Given the agent's observed partial trajectory, our goal is to predict the agent's remaining trajectory. We propose a solution framework to the problem that incorporates both the stochastic utility of each location and the budget constraint. We first cluster the agents into groups of homogeneous behaviors called “agent types”. Depending on its type, each agent's trajectory is then transformed into a discrete-state sequence representation. Based on such representations, we use reinforcement learning (RL) to model the underlying decision processes and inverse RL to learn the utility distributions of the spatial locations. We finally propose two decision models to make predictions: one is based on long-term optimal planning of RL and another uses myopic heuristics. We apply the framework to predict real-world human trajectories collected in a large theme park and are able to explain the underlying processes of the observed actions.

While mobile crowd-sourcing has become a game-changer for many urban operations, such as last mile logistics and municipal monitoring, we believe that the design of such crowd-sourcing strategies must better accommodate the real-world behavioral preferences and characteristics of users. To provide a real-world testbed to study the impact of novel mobile crowd-sourcing strategies, we have designed, developed and experimented with a real-world mobile crowd-tasking platform on the SMU campus, called TA&Sslash;Ker. We enhanced the TA$Ker platform to support several new features (e.g., task bundling, differential pricing and cheating analytics) and experimentally investigated these features via a two-month deployment of TA$Ker, involving 900 real users on the SMU campus who performed over 30,000 tasks. Our studies (i) show the benefits of bundling tasks as a combined package, (ii) reveal the effectiveness of differential pricing strategies and (iii) illustrate key aspects of cheating (false reporting) behavior observed among workers.

Consolidation lies at the heart of the last-mile logistics problem. Urban consolidation centers (UCCs) have been set up to facilitate such consolidation all over the world. To the best of our knowledge, most-if not all-of the UCCs operate on volume-based fixed-rate charges. To achieve environmental sustainability while ensuring economic sustainability in urban logistics, we propose, in this paper, a bicriteria auction mechanism for the automated assignment of last-mile delivery orders to transport resources. We formulate and solve the winner determination problem of the auction as a biobjective programming model. We then present a systematic way to generate the Pareto frontier to characterize the tradeoff between achieving economic and environmental sustainabilities in urban logistics. Finally, we demonstrate that our proposed bicriteria auction produces the solutions that significantly dominate those obtained from the fixed-rate mechanisms. Our sensitivity analysis on the willingness of carriers to participate in the UCC operation reveals that higher willingness is favorable toward achieving greater good for all, if UCC is designed to be nonprofit and self-sustaining.

The abundance of algorithms developed to solve different problems has given rise to an important research question: How do we choose the best algorithm for a given problem? Known as algorithm selection, this issue has been prevailing in many domains, as no single algorithm can perform best on all problem instances. Traditional algorithm selection and portfolio construction methods typically treat the problem as a classification or regression task. In this paper, we present a new approach that provides a more natural treatment of algorithm selection and portfolio construction as a ranking task. Accordingly, we develop a Ranking-Based Algorithm Selection (RAS) method, which employs a simple polynomial model to capture the ranking of different solvers for different problem instances. We devise an efficient iterative algorithm that can gracefully optimize the polynomial coefficients by minimizing a ranking loss function, which is derived from a sound probabilistic formulation of the ranking problem. Experiments on the SAT 2012 competition dataset show that our approach yields competitive performance to that of more sophisticated algorithm selection methods.

In emergency medical systems, arriving at the incident locationa few seconds early can save a human life. Thus, this paper is motivated by the need to reduce the response time– time taken to arrive at the incident location after receivingthe emergency call — of Emergency Response Vehicles, ERVs(ex: ambulances, fire rescue vehicles) for as many requests as possible. We expect to achieve this primarily by positioning the ”right” number of ERVs at the ”right” places and at the ”right” times. Given the exponentially large action space(with respect to number of ERVs and their placement) and the stochasticity in location and timing of emergency incidents,this problem is computationally challenging. To that end, ourcontributions building on existing data-driven approaches are three fold:1. Based on real world evaluation metrics, we provide a riskbased optimization criterion to learn from past incident data. Instead of minimizing expected response time, we minimize the largest value of response time such that the risk of finding requests that have a higher value is bounded(ex: Only 10% of requests should have a response time greater than 8 minutes).2. We develop a mixed integer linear optimization formulation to learn and compute an allocation from a set of inputrequests while considering the risk criterion.3. To allow for ”live” reallocation of ambulances, we provide a decomposition method based on Lagrangian Relaxation to significantly reduce the run-time of the optimization formulation.Finally, we provide an exhaustive evaluation on real-world datasets from two asian cities that demonstrates the improvement provided by our approach over current practice and the best known approach from literature.

Profitable tour problem (PTP) belongs to the class of vehicle routing problem (VRP) with profits seeking to maximize the difference between the total collected profit and the total cost incurred. Traditionally, PTP involves single vehicle. In this paper, we consider PTP with multiple vehicles. Unlike the classical VRP that seeks to serve all customers, PTP involves the strategic-level customer selection so as to maximize the total collected profit and the operational-level route optimization to minimize the total cost incurred. Therefore, PTP is essentially the knapsack problem at the strategic level with VRP at the operational level. That means the evolutionary bi-level programming would be a suitable choice of methodology for solving the NP-hard PTP. Employing some evolutionary method to solve the bi-level program naively would undoubtedly be prohibitively expensive. We thus present in this paper the notion of knowledge adoption to approximate the initial solution to the lower-level optimization problem for a given trial solution of the upper-level decision variables. One may consider the knowledge adoption as a special case of knowledge transfer in which the transfer takes place within the same problem domain. Refining the approximate initial solution with local search forces it to quickly converge to some locally optimal solution. The better the estimation of the initial solution, the closer the local optimum will be to the global one. PTP finds its important application in the fields of transportation and logistics. In addressing last-mile problem using auction at the urban consolidation center (UCC), PTP plays a significant role in the winner determination problem (WDP) that follows. Empirical study demonstrates the efficacy of the proposed approach in solving the PTP-based WDP, yielding significantly higher profit, utilization, and service level compared to when the UCC adopts the conventional WDP based on multiple knapsack problem (i.e. the MKP-based WDP).

Researchers have introduced the Dynamic Distributed Constraint Optimization Problem (Dynamic DCOP) formulation to model dynamically changing multi-agent coordination problems, where a dynamic DCOP is a sequence of (static canonical) DCOPs, each partially different from the DCOP preceding it. Existing work typically assumes that the problem in each time step is decoupled from the problems in other time steps, which might not hold in some applications. Therefore, in this paper, we make the following contributions: (i) We introduce a new model, called Markovian Dynamic DCOPs (MD-DCOPs), where the DCOP in the next time step is a function of the value assignments in the current time step; (ii) We introduce two distributed reinforcement learning algorithms, the Distributed RVI Q-learning algorithm and the Distributed R-learning algorithm, that balance exploration and exploitation to solve MD-DCOPs in an online manner; and (iii) We empirically evaluate them against an existing multi-arm bandit DCOP algorithm on dynamic DCOPs.

In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at the single-agent level: given a limited time budget, an agent tra

This special issue particularly focuses on using agent-based methods to solve the complex computational problems arising in Big Data environments. It covers the recent advances in the areas of distributed problem solving, agent-based data mining, as

Automated algorithm configuration methods have proven to be instrumental in deriving high-performing algorithms and such methods are increasingly often used to configure evolutionary algorithms. One major challenge in devising automatic algorithm configuration techniques is to handle the inherent stochasticity in the configuration problems. This article analyses a post-selection mechanism that can also be used for this task. The central idea of the post-selection mechanism is to generate in a first phase a set of high-quality candidate algorithm configurations and then to select in a second phase from this candidate set the (statistically) best configuration. Our analysis of this mechanism indicates its high potential and suggests that it may be helpful to improve automatic algorithm configuration methods.

Mass Rapid Transit using rail is a popular mode of transport employed by millions of people in many urban cities across the world. Typically, these networks are massive, used by many and thus, can be a soft target for criminals. In this paper, we consider the problem of scheduling randomised patrols for improving security of such rail networks. Similar to existing work in randomised patrols for protecting critical infrastructure, we also employ Stackelberg Games to represent the problem. In solving the Stackelberg games for massive rail networks, we make two key contributions. Firstly, we provide an approach called RaPtoR for computing randomized strategies in patrol teams, which guarantees (i) Strong Stackelberg equilibrium (SSE); and (ii) Optimality in terms of distance traveled by the patrol teams for specific constraints on schedules. Secondly, we demonstrate RaPtoR on a real world data set corresponding to the rail network in Singapore. Furthermore, we also show that the algorithm scales easily to large rail networks while providing SSE randomized strategies.

In hotly contested product categories dominated by a few powerful firms, it is quite common for weaker or late entrants to focus only on particular segments of the whole market. The rationale for such strategy is intuitive: to avoid direct confrontation with heavy-weight firms, and to concentrate in segments where these weaker firms have comparative advantages. In marketing, this is what people called "go niche or go home". The niche-building strategy may rely on "homophily", which implies that consumers in a particular market segment might possess certain set of attributes that cause them to appreciate certain products better (in other words, weaker firms would customize their products to target some particular market segments and not the mass market). On the other hand, the niche-building strategy may also rely on the network effect, which implies that consumers having social relationship would reinforce each other via their respective adoptions. In this case, weaker firms should recognize such inter-customer network and concentrate only on customers belonging to certain set of strategic clusters. In this paper, we present the model for building effective niche-seeking strategies. For simplicity, we assume that the adoption choice depends only on the network effects (in other words, a customer will choose the product that is chosen by the majority of her neighbor). The social network is directed, and there will be two firms, one with significantly more marketing budget than the other firm. Firms take turns making investment choices on which customer to convert. For both firms, their budgets are fixed over time and unused budget will not carry over to future time periods. With this model, we manage to show that a simple strategy based on the evaluation of individual customer's "value" can effectively identify and secure niches within randomly generated scale-free networks. We also show that such niche-building strategy indeed performs better in the long run than a myopic strategy that only cares about immediate market gains.

B2B auctions play a key role in a firm's procurement process. Even though it is known that repetition is a key characteristic of procurement auctions, traditional auctioneers typically have not put in place a suitable mechanism that supports repetitive auctions effectively. In this paper, we empirically investigate what has taken place in repeated procurement auctions based on real world data from a major outsourcing company of MRO (Maintenance, Repair and Operations) items in Korea. From this empirical study, we discovered the followings. First, we discovered that the repeated bidders contribute majority of all bids, and that the number of new entrants declined significantly as time passes. Second, repeated bidders become inactive and virtually leave the market, particularly if they fail to win in the auctions even though their bid prices were competitive. This implies that repeated bidders with lower winning rates have a higher possibility of becoming inactive. Third, the number of bidders along with the purchase amount and the bidder's previous winning rates are critical factors in determining both the winning bid price in the auction level and the bid price of each bidder. According to these research findings, we recognize that retaining a sufficient number of repeated bidders is crucial in the repeated procurement auction market. This motivates auctioneers to provide incentives to the repeated bidders to retain them in future auctions.

Scheduling problems in manufacturing, logistics and project management have frequently been modeled using the framework of Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the importance of these problems, providing scalable solution schedules for RCPSP/max problems is a topic of extensive research. However, all existing methods for solving RCPSP/max assume that durations of activities are known with certainty, an assumption that does not hold in real world scheduling problems where unexpected external events such as manpower availability, weather changes, etc. lead to delays or advances in completion of activities. Thus, in this paper, our focus is on providing a scalable method for solving RCPSP/max problems with durational uncertainty. To that end, we introduce the robust local search method consisting of three key ideas: (a) Introducing and studying the properties of two decision rule approximations used to compute start times of activities with respect to dynamic realizations of the durational uncertainty; (b) Deriving the expression for robust makespan of an execution strategy based on decision rule approximations; and (c) A robust local search mechanism to efficiently compute activity execution strategies that are robust against durational uncertainty. Furthermore, we also provide enhancements to local search that exploit temporal dependencies between activities. Our experimental results illustrate that robust local search is able to provide robust execution strategies efficiently.

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinator

Many spectrum-based fault localization measures have been proposed in the literature. However, no single fault localization measure completely outperforms others: a measure which is more accurate in localizing some bugs in some programs is less accurate in localizing other bugs in other programs. This paper proposes to compose existing spectrum-based fault localization measures into an improved measure. We model the composition of various measures as an optimization problem and present a search-based approach to explore the space of many possible compositions and output a heuristically near optimal composite measure. We employ two search-based strategies including genetic algorithm and simulated annealing to look for optimal solutions and compare the effectiveness of the resulting composite measures on benchmark software systems. Compared to individual spectrum-based fault localization techniques, our composite measures perform statistically significantly better.

In this paper, we consider the problem of allocating machine resources among multiple agents, each of which is responsible to solve a flowshop scheduling problem. We present an iterated combinatorial auction mechanism in which bid generation is performed within each agent, while a price adjustment procedure is performed by a centralized auctioneer. While this approach is fairly well-studied in the literature, our primary innovation is in an adaptive price adjustment procedure, utilizing variable step-size inspired by adaptive PID-control theory coupled with utility pricing inspired by classical microeconomics. We compare with the conventional price adjustment scheme proposed in Fisher (1985), and show better convergence properties. Our secondary contribution is in a fast bid-generation procedure executed by the agents based on local search. Putting both these innovations together, we compare our approach against a classical integer programming model as well as conventional price adjustment schemes, and show drastic run time improvement with insignificant loss of global optimality.

This paper introduces the SoI problem, that of finding non-optimal solutions of interest for constrained optimization models. SoI problems subsume finding FoIs (feasible solutions of interest), and IoIs (infeasible solutions of interest). In all cases, the interest addressed is post-solution analysis in one form or another. Post-solution analysis of a constrained optimization model occurs after the model has been solved and a good or optimal solution for it has been found. At this point, sensitivity analysis and other questions of import for decision making (discussed in the paper) come into play and for this purpose the SoIs can be of considerable value. The paper presents examples that demonstrate this and reports on a systematic approach, using evolutionary computation, for obtaining both FoIs and IoIs.

Given an existing stock allocation in an inventory system, it is often necessary to perform reallocation over multiple time points to address inventory imbalance and maximize availability. In this paper, we focus on the situation where there are two opportunities to perform reallocation within a replenishment cycle. We derive a mathematical model to determine when and how to perform reallocation. Furthermore, we consider the extension of this model to the situation allowing an arbitrary number of reallocations. Experimental results show that the two-reallocation approach achieves better performance compared with the single-reallocation approach found in the literature. We also illustrate how to apply the proposed model to design cost-optimal periodic resupply policies.

The success of an auction design often hinges on its ability to set parameters such as reserve price and bid levels that will maximize an objective function such as the auctioneer revenue. Works on designing adaptive auction mechanisms have emerged recently, and the challenge is in learning different auction parameters by observing the bidding in previous auctions. In this paper, we propose a non-parametric method for determining discrete bid levels dynamically so as to maximize the auctioneer revenue. First, we propose a non-parametric kernel method for estimating the probabilities of closing price with past auction data. Then a greedy strategy has been devised to determine the discrete bid levels based on the estimated probability information of closing price. We show experimentally that our non-parametric method is robust to changes in parameters such as the distributions of participating bidders as well as the individual bidder evaluation, and it consistently outperforms different competitors with various settings with respect to auctioneer revenue maximization.

Making software systems service-oriented is becoming the practice, and an increasingly large number of service systems play important roles in today's business and industry. Currently, not enough attention has been paid to the issue of optimization of service systems. In this paper, we argue that the key elements to be considered in optimizing service systems are robustness, system orientation, and being dynamic and transparent. We present our solution to optimizing service systems based on application-level QoS management. Our solution incorporates three capabilities, i.e., 1) the ability to cater to the varying rigidities on Web service QoS in distinct application domains and of various users in a robust and heuristic manner, 2) the ability to formulate the overall system utility of a service system perceived by a particular system end user and to suggest its maximization using a utility model incorporated into a three-dimensional weighting scheme, and 3) the ability to dynamically achieve a higher perceived system utility of a service system via transparent negotiations. The calculation of the system utility encompasses a negotiation algorithm and a robust search algorithm for selecting heuristically best Web services. The effectiveness of the proposed algorithms and our solution is demonstrated by simulation experiments and our demo deployment, SSO.

An integer programming (IP) model is proposed for integrated resource allocation and operation scheduling for a multiple job-agents system. Each agent handles a specific job-list in a bidirectional flowshop. For the individual agent scheduling problem, a formulation is proposed in continuous time domain and compared with an IP formulation in discrete time domain. Of particular interest is the formulation of the machine utilization function-both in continuous time and discrete time. Fast heuristic methods are proposed with the relaxation of the machine capacity. For the integrated resource allocation and scheduling problem, a linear programming relaxation approach is applied to solve the global resource allocation and a fast heuristic method is applied to solve each scheduling subproblem. The proposed solution is compared experimentally with that from the integer programming solver by CPLEX.

Game theory has gained popularity as an approach to analysing and understanding distributed systems with self-interested agents. Central to game theory is the concept of Nash equilibrium as a stable state (solution) of the system, which comes with a

10.1145/1409540.1409547

While e-procurement auction has helped firms to achieve lower procurement costs, auction mechanisms that prevail at present in procurement markets need to address an important issue that concerns the ability to maintain long term relationships with the partners, especially in repeated e-procurement settings. In this paper, we propose a Relationship Preserving Auction (RPA) mechanism that augments the conventional auction mechanism with a bidder relationship scoring model. Our proposed mechanism gives increased chances of winning to the bidders who have bidden at relatively competitive price but had comparatively less wins so far. Keeping these bidders in the auction over time will lead to more competitive bidding prices and eventually reduce the auctioneer's total procurement cost in repeated auctions. From simulation experiments, we show how RPA works under different bidders' behavior. We show that RPA is able to obtain lower procurement cost compared to conventional procurement auctions when bidders bid opportunistically and renege readily to other markets.

Temporal constraint networks are embedded in many planning and scheduling problems. In dynamic problems, a fundamental challenge is to decide whether such a network can be executed as uncertainty is revealed over time. Very little work in this domain has been done in the probabilistic context. In this paper, we propose a temporal constraint network (TCN) model where durations of uncertain activities are represented by random variables. We wish to know whether such a network is robust controllable, i.e. can be executed dynamically within a given failure probability, and if so, how one might find a feasible schedule as the uncertainty variables are revealed dynamically. We present a computationally tractable and efficient approach to solve this problem. Experimentally, we study how the failure probability is affected by various network properties of the underlying TCN, and the relationship of failure rates between robust and weak controllability

In this paper, we describe an interesting driver assignment problem that is computationally intensive to solve due to its combinatorial nature. A hybrid approach involving mixed integer programming (MIP) and a heuristic is used to give good solutions to the problem within reasonable computation time. This approach attempts to utilize the strengths of MIP to search for an optimal solution, while letting the heuristic component address the complexity involved in the driver assignment problem so as to improve the time required to obtain a solution. Computational results are used to illustrate the performance of the approach

NP-hard combinatorial optimization problems are common in real life. Due to their intractability, local search algorithms are often used to solve such problems. Since these algorithms are heuristic-based, it is hard to understand how to improve or tune them. We propose an interactive visualization tool, VIZ, meant for understanding the behavior of local search. VIZ uses animation of abstract search trajectories with other visualizations which are also animated in a VCR-like fashion to graphically playback the algorithm behavior. It combines generic visualizations applicable on arbitrary algorithms with algorithm and problem specific visualizations. We use a variety of techniques such as alpha blending to reduce visual clutter and to smooth animation, highlights and shading, automatically generated index points for playback, and visual comparison of two algorithms. The use of multiple viewpoints can be an effective way of understanding search behavior and highlight algorithm behavior which might otherwise be hidden.

In this paper, we propose the robust temporal constraint network (RTCN) model for simple temporal constraint networks where activity durations are bounded by random variables. The problem is to determine whether such temporal network can be executed with failure probability less than a given 0 /spl les/ /spl epsi/ /spl les/ 1 for each possible instantiation of the random variables, and if so, how one might find a feasible schedule with each given instantiation. The advantage of our model is that one can vary the value of /spl epsi/ to control the level of conservativeness of the solution. We present a computationally tractable and efficient approach to solve these RTCN problems. We study the effects the density of temporal constraint networks have on its makespan under different confidence levels. We also apply RTCN to solve the stochastic project crashing problem.

While meta-heuristics are effective for solving large-scale combinatorial optimization problems, they result from time-consuming trial-and-error algorithm design tailored to specific problems. For this reason, a software tool for rapid prototyping of algorithms would save considerable resources. This work presents a generic software framework that reduces development time through abstract classes and software reuse, and more importantly, aids design with support of user-defined strategies and hybridization of meta-heuristics. Most interestingly, we propose a novel way of redefining hybridization with the use of the "request and response" metaphor, which form an abstract concept for hybridization. Different hybridization schemes can now be formed with minimal coding, which gives our proposed metaheuristics development framework its uniqueness. To illustrate the concept, we restrict to two popular metaheuristics ants colony optimization and tabu search, and demonstrate MDF through the implementation of various hybridized models to solve the traveling salesman problem.

Coalition formation has become a key topic in multiagent research. In this paper, we propose a preliminary classification for the coalition formation problem based on three driving factors (demands, resources and profit objectives). We divide our analysis into 5 cases. For each case, we present algorithms and complexity results. We anticipate that with future research, this classification can be extended in similar fashion to the comprehensive classification for the job scheduling problem.

An intelligent agent-based framework that supports fourth-party logistics (4PL) operations on the Web is proposed. In our system, customers specify job requests over the Web dynamically. An e-marketplace allows intelligent third-party logistics (3PL) agents to bid for customers' job requests. The intelligence lies in the e-marketplace optimally deciding which agents' bids should be satisfied based on a set of predetermined factors (pricing, preferences and fairness). We model the underlying brokering problem as a set packing problem (SPP), an NP-hard optimization problem. An iterative greedy approximation algorithm is proposed to solve the SPP, and experimental results show its effectiveness against the classical greedy method proposed by Chvatal (1979).

In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good solutions when compared with the benchmarking solutions.