Retrieval-Augmented Generation (RAG) has emerged as a powerful solution to mitigate the limitations of Large Language Models (LLMs), such as hallucinations and outdated knowledge. However, deploying RAG-based tools in Small and Medium Enterprises (SMEs) remains a challenge due to their limited resources and lack of expertise in natural language processing (NLP). This paper introduces EASI-RAG, Enterprise Application Support for Industrial RAG, a structured, agile method designed to facilitate the deployment of RAG systems in industrial SME contexts. EASI-RAG is based on method engineering principles and comprises well-defined roles, activities, and techniques. The method was validated through a real-world case study in an environmental testing laboratory, where a RAG tool was implemented to answer operators queries using data extracted from operational procedures. The system was deployed in under a month by a team with no prior RAG experience and was later iteratively improved based on user feedback. Results demonstrate that EASI-RAG supports fast implementation, high user adoption, delivers accurate answers, and enhances the reliability of underlying data. This work highlights the potential of RAG deployment in industrial SMEs. Future works include the need for generalization across diverse use cases and further integration with fine-tuned models.

In this paper, we consider contextual stochastic optimization problems subject to endogenous uncertainty, where the decisions affect the underlying distributions. To implement such decisions in practice, it is crucial to ensure that their outcomes are interpretable and trustworthy. To this end, we compute relative counterfactual explanations, providing practitioners with concrete changes in the contextual covariates required for a solution to satisfy specific constraints. Whereas relative explanations have been introduced in prior literature, to the best of our knowledge, this is the first work focused on problems with binary decision variables and subject to endogenous uncertainty. We propose a methodology that uses Wasserstein distance as regularization and to compute a lower bound. It leads to a drastic reduction in computation times, compared to the unregularized counterpart. We illustrate the method using a choice-based competitive facility location problem, and present numerical experiments that demonstrate its ability to efficiently compute sparse and interpretable explanations.

Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.

This paper tackles optimization problems whose objective and constraints involve a trained Neural Network (NN), where the goal is to maximize $f(\Phi(x))$ subject to $c(\Phi(x)) \leq 0$, with $f$ smooth, $c$ general and non-stringent, and $\Phi$ an already trained and possibly nonwhite-box NN. We address two challenges regarding this problem: identifying ascent directions for local search, and ensuring reliable convergence towards relevant local solutions. To this end, we re-purpose the notion of directional NN attacks as efficient optimization subroutines, since directional NN attacks use the neural structure of $\Phi$ to compute perturbations of $x$ that steer $\Phi(x)$ in prescribed directions. Precisely, we develop an attack operator that computes attacks of $\Phi$ at any $x$ along the direction $\nabla f(\Phi(x))$. Then, we propose a hybrid algorithm combining the attack operator with derivative-free optimization (DFO) techniques, designed for numerical reliability by remaining oblivious to the structure of the problem. We consider the cDSM algorithm, which offers asymptotic guarantees to converge to a local solution under mild assumptions on the problem. The resulting method alternates between attack-based steps for heuristic yet fast local intensification and cDSM steps for certified convergence and numerical reliability. Experiments on three problems show that this hybrid approach consistently outperforms standard DFO baselines.

Once known to be used exclusively in military domain, unmanned aerial vehicles (drones) have stepped up to become a part of new logistic method in commercial sector called "last-mile delivery". In this novel approach, small unmanned aerial vehicles (UAV), also known as drones, are deployed alongside with trucks to deliver goods to customers in order to improve the service quality or reduce the transportation cost. It gives rise to a new variant of the traveling salesman problem (TSP), of which we call TSP with drone (TSP-D). In this article, we consider a variant of TSP-D where the main objective is to minimize the total transportation cost. We also propose two heuristics: "Drone First, Truck Second" (DFTS) and "Truck First, Drone Second" (TFDS), to effectively solve the problem. The former constructs route for drone first while the latter constructs route for truck first. We solve a TSP to generate route for truck and propose a mixed integer programming (MIP) formulation with different profit functions to build route for drone. Numerical results obtained on many instances with different sizes and characteristics are presented. Recommendations on promising algorithm choices are also provided.

In this brief note, we prove that the existence of Nash equilibria on integer programming games is $\Sigma^p_2$-complete.

Neighborhood search is a cornerstone of state-of-the-art traveling salesman and vehicle routing metaheuristics. While neighborhood exploration procedures are well developed for problems with individual services, their counterparts for one-to-one pickup-and-delivery problems have been more scarcely studied. A direct extension of classic neighborhoods is often inefficient or complex due to the necessity of jointly considering service pairs. To circumvent these issues, we introduce major improvements to existing neighborhood searches for the pickup-and-delivery traveling salesman problem and new large neighborhoods. We show that the classical Relocate-Pair neighborhood can be fully explored in $O(n^2)$ instead of $O(n^3)$ time. We adapt the 4-Opt and Balas-Simonetti neighborhoods to consider precedence constraints. Moreover, we introduce an exponential-size neighborhood called 2k-Opt, which includes all solutions generated by multiple nested 2-Opts and can be searched in $O(n^2)$ time using dynamic programming. We conduct extensive computational experiments, highlighting the significant contribution of these new neighborhoods and speed-up strategies within two classical metaheuristics. Notably, our approach permits to repeatedly solve small pickup-and-delivery problem instances to optimality or near-optimality within milliseconds, and therefore it represents a valuable tool for time-critical applications such as meal delivery or mobility on demand.

E-commerce operations are essentially online, with customer orders arriving dynamically. However, very little is known about the performance of online policies for warehousing with respect to optimality, particularly for order picking and batching operations, which constitute a substantial portion of the total operating costs in warehouses. We aim to close this gap for one of the most prominent dynamic algorithms, namely reoptimization (Reopt), which reoptimizes the current solution each time when a new order arrives. We examine Reopt in the Online Order Batching, Sequencing, and Routing Problem (OOBSRP), in both cases when the picker uses either a manual pushcart or a robotic cart. Moreover, we examine the noninterventionist Reopt in the case of a manual pushcart, wherein picking instructions are provided exclusively at the depot. We establish analytical performance bounds employing worst-case and probabilistic analysis. We demonstrate that, under generic stochastic assumptions, Reopt is almost surely asymptotically optimal and, notably, we validate its near-optimal performance in computational experiments across a broad range of warehouse settings. These results underscore Reopt's relevance as a method for online warehousing applications.

Electric vehicle (EV) public charging infrastructure planning faces significant challenges in competitive markets, where multiple service providers affect congestion and user behavior. This work extends existing modeling frameworks by incorporating the presence of competitors' stations and more realistic queueing systems. First, we analyze three finite queueing systems, M/M/1/K, M/M/s/K, and M/Er/s/K, with varying numbers of servers (charging outlets) and service time distributions, deriving analytic expressions for user behavior metrics. Second, we embed the queueing-based user behavior model into a bilevel program, where the upper level locates new charging stations to maximize accessibility (throughput), and the lower level captures users' station choices via a user equilibrium. Third, we apply a reformulation from competitive congested user-choice facility location models to approximately solve the bilevel problem and introduce a surrogate-based heuristic to enhance scalability. Fourth, we showcase our methodology on a real-world case study of an urban area in Montreal (Canada), offering managerial insights into how user-choice behavior assumptions and competition affect throughput and location decisions. The results demonstrate that our model yields (re)location strategies that outperform the existing network. More broadly, this approach provides a tool for incorporating charging service quality-through queueing metrics-and existing competition into station planning.

The many-to-one stable matching problem provides the fundamental abstraction of several real-world matching markets such as school choice and hospital-resident allocation. The agents on both sides are often referred to as residents and hospitals. The classical setup assumes that the agents rank the opposite side and that the capacities of the hospitals are fixed. It is known that increasing the capacity of a single hospital improves the residents' final allocation. On the other hand, reducing the capacity of a single hospital deteriorates the residents' allocation. In this work, we study the computational complexity of finding the optimal variation of hospitals' capacities that leads to the best outcome for the residents, subject to stability and a capacity variation constraint. First, we show that the decision problem of finding the optimal capacity expansion is NP-complete and the corresponding optimization problem is inapproximable within a certain factor. This result holds under strict and complete preferences, and even if we allocate extra capacities to disjoint sets of hospitals. Second, we obtain analogous computational complexity results for the problem of capacity reduction. Finally, we study the variants of these problems when the goal is to maximize the size of the final matching under incomplete preference lists.

This paper proposes a new integer L-shaped method for solving two-stage stochastic integer programs whose first-stage solutions can decompose into disjoint components, each one having a monotonic recourse function. In a minimization problem, the monotonicity property stipulates that the recourse cost of a component must always be higher or equal to that of any of its subcomponents. The method exploits new types of optimality cuts and lower bounding functionals that are valid under this property. The stochastic vehicle routing problem is particularly well suited to be solved by this approach, as its solutions can be decomposed into a set of routes. We consider the variant with stochastic demands in which the recourse policy consists of performing a return trip to the depot whenever a vehicle does not have sufficient capacity to accommodate a newly realized customer demand. This work shows that this policy can lead to a non-monotonic recourse function, but that the monotonicity holds when the customer demands are modeled by several commonly used families of probability distributions. We also present new problem-specific lower bounds on the recourse that strengthen the lower bounding functionals and significantly speed up the resolution process. Computational experiments on instances from the literature show that the new approach achieves state-of-the-art results.

Autonomous mobility-on-demand systems are a viable alternative to mitigate many transportation-related externalities in cities, such as rising vehicle volumes in urban areas and transportation-related pollution. However, the success of these systems heavily depends on efficient and effective fleet control strategies. In this context, we study online control algorithms for autonomous mobility-on-demand systems and develop a novel hybrid combinatorial optimization enriched machine learning pipeline which learns online dispatching and rebalancing policies from optimal full-information solutions. We test our hybrid pipeline on large-scale real-world scenarios with different vehicle fleet sizes and various request densities. We show that our approach outperforms state-of-the-art greedy, and model-predictive control approaches with respect to various KPIs, e.g., by up to 17.1% and on average by 6.3% in terms of realized profit.

We study EVs traveling from origin to destination in the shortest time, focusing on long-distance settings with energy requirements exceeding EV autonomy. The EV may charge its battery at public Charging Stations (CSs), which are subject to uncertain waiting times. We model CSs using appropriately defined queues, whose status is revealed upon the EV arrival. However, we consider the availability of real-time binary Occupancy Indicator (OI) information, signaling if a CS is busy or not. At each OI update, we determine the sequence of CSs to visit along with associated charging quantities. We name the resulting problem the Electric Vehicle Shortest Path Problem with charging station Occupancy Indicator information (EVSPP-OI). In this problem, we consider that the EV is allowed to partially charge its battery, and we model charging times via piecewise linear charging functions that depend on the CS technology. We propose an MDP formulation for the EVSPP-OI and develop a reoptimization algorithm that establishes the sequence of CS visits and charging amounts based on system updates. Specifically, we propose a simulation-based approach to estimate the waiting time of the EV at a CS as a function of its arrival time. As the path to a CS may consist of multiple intermediate CS stops, estimating the arrival times at each CS is fairly intricate. To this end, we propose an efficient heuristic that yields approximate lower bounds on the arrival time of the EV at each CS. We use these estimations to define a deterministic EVSPP, which we solve with an existing algorithm. We conduct a comprehensive computational study and compare the performance of our methodology with a benchmark that observes the status of CSs only upon arrival. Results show that our method reduces waiting times and total trip duration by an average of 23.7%-95.4% and 1.4%-18.5%, respectively.

Differentially-private (DP) mechanisms can be embedded into the design of a machine learning algorithm to protect the resulting model against privacy leakage. However, this often comes with a significant loss of accuracy due to the noise added to enforce DP. In this paper, we aim at improving this trade-off for a popular class of machine learning algorithms leveraging the Gini impurity as an information gain criterion to greedily build interpretable models such as decision trees or rule lists. To this end, we establish the smooth sensitivity of the Gini impurity, which can be used to obtain thorough DP guarantees while adding noise scaled with tighter magnitude. We illustrate the applicability of this mechanism by integrating it within a greedy algorithm producing rule list models, motivated by the fact that such models remain understudied in the DP literature. Our theoretical analysis and experimental results confirm that the DP rule lists models integrating smooth sensitivity have higher accuracy that those using other DP frameworks based on global sensitivity, for identical privacy budgets.

The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader's goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower's problem as a longest path problem using a dynamic programming model, and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to two distinct dynamic programming models, namely, a novel formulation designated as selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across three different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the two proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs.

The recently defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be fit in this class, and hence anticipating IPG outcomes is of crucial value for policy makers and regulators. Nash equilibria have been widely accepted as the solution concept of a game. Consequently, their computation provides a reasonable prediction of the games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop two general algorithmic approaches that are guaranteed to approximate an equilibrium under mild conditions. We also showcase how our methodology can be changed to determine other equilibria definitions. The performance of our methods is analyzed through computational experiments in a knapsack game, a competitive lot-sizing game, and a kidney exchange game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games have been designed and computationally tested.

Recent studies on many-to-one matching markets have explored agents with flexible capacity and truthful preference reporting, focusing on mechanisms that jointly design capacities and select a matching. However, in real-world applications such as school choice and residency matching, preferences are revealed after capacity decisions are made, with matching occurring afterward; uncertainty about agents' preferences must be considered during capacity planning. Moreover, even under strategy-proof mechanisms, agents may strategically misreport preferences based on beliefs about admission chances. We introduce a two-stage stochastic matching problem with uncertain preferences, using school choice as a case study. In the first stage, the clearinghouse expands schools' capacities before observing students' reported preferences. Students either report their true preferences, producing exogenous uncertainty, or act strategically, submitting reported preferences based on their true preferences and admission chances (which depend on capacities), introducing endogenous uncertainty. In the second stage, the clearinghouse computes the student-optimal stable matching based on schools' priorities and students' reported preferences. In strategic cases, endogenous reported preferences are utility-maximizing transformations of capacity decisions and exogenous true preferences; we handle uncertainty using sample average approximation(SAA). We develop behavior-based mathematical formulations and, due to problem complexity, propose Lagrangian- and local-search-based behavior-specific heuristics for near-optimal solutions. Our SAA-based approaches outperform the average scenario approach on students' matching preferences and admission outcomes, emphasizing the impact of stochastic preferences on capacity decisions. Student behavior notably influences capacity design, stressing the need to consider misreports.

Over the past thirty years, the vehicle routing problem with stochastic demands has emerged as a canonical application of the integer L-shaped method, leading to an extensive body of literature and several methodological refinements. Recently, the disaggregated integer L-shaped (DL-shaped) method, which decomposes the recourse function by customer rather than treating it as an aggregate cost, has been proposed and successfully applied under the detour-to-depot recourse policy. However, the validity of this new approach and its generalizability to other policies have not been thoroughly investigated. In this work, we provide a necessary and sufficient condition for the validity of the DL-shaped method, namely, the superadditivity of the recourse function under concatenation. We demonstrate that the optimal restocking policy satisfies this superadditivity property. Moreover, we rectify an incorrect argument from the original paper on the DL-shaped method to rigorously establish its validity under the detour-to-depot policy. We then develop a DL-shaped algorithm tailored to the optimal restocking policy. Our algorithm exploits new dynamic programming-based lower bounds on the optimal restocking recourse function. We also introduce new valid inequalities that generalize the original DL-shaped cuts and speed up computations by an order of magnitude. Computational experiments show that our DL-shaped algorithm significantly outperforms the state-of-the-art integer L-shaped algorithm from the literature. We solve several open instances to optimality, including 14 single-vehicle instances, which constitute the most challenging variant of the problem.

The goal of a kidney exchange program (KEP) is to maximize number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP can be modelled as a maximum matching problem in a graph. A KEP between incompatible patient-donor from pools of several hospitals, regions or countries has the potential to increase the number of transplants. These entities aim is to maximize the transplant benefit for their patients, which can lead to strategic behaviours. Recently, this was formulated as a non-cooperative two-player game and the game solutions (equilibria) were characterized when the entities objective function is the number of their patients receiving a kidney. In this paper, we generalize these results for $N$-players and discuss the impact in the game solutions when transplant information quality is introduced. Furthermore, the game theory model is analyzed through computational experiments on instances generated through the Canada Kidney Paired Donation Program. These experiments highlighting the importance of using the concept of Nash equilibrium, as well as, the anticipation of the necessity to further research for supporting police makers once measures on transplant quality are available.

An equitable distribution of workload is essential when deploying vehicle routing solutions in practice. For this reason, previous studies have formulated vehicle routing problems with workload-balance objectives or constraints, leading to trade-off solutions between routing costs and workload equity. These methods consider a single planning period; however, equity is often sought over several days in practice. In this work, we show that workload equity over multiple periods can be achieved without impact on transportation costs when the planning horizon is sufficiently large. To achieve this, we design a two-phase method to solve multi-period vehicle routing problems with workload balance. Firstly, our approach produces solutions with minimal distance for each period. Next, the resulting routes are allocated to drivers to obtain equitable workloads over the planning horizon. We conduct extensive numerical experiments to measure the performance of the proposed approach and the level of workload equity achieved for different planning-horizon lengths. For horizons of five days or more, we observe that near-optimal workload equity and optimal routing costs are jointly achievable.