Human interaction with autonomous technologies has been extensively studied, mostly focusing on one-to-one dyadic interactions. In contrast, this study examines human altruistic and compliance behaviors in multiple-operator single-agent (MOSA) interaction. We developed a testbed where multiple players perform an evacuation task, assisted by an AI agent that plans the optimal route for everyone. During the evacuation, players could exhibit altruism by reporting additional information, albeit at a personal cost. A lab study with 32 participants, each completing four trials under varying display configurations that manipulated the communication of altruistic actions, yielded 1,012 and 3,865 data points on altruism and compliance, respectively. Using mixed-effects logistic regression, we identified key predictors of altruistic and compliance behaviors and developed prediction models, with accuracies of 73.36% and 91.07%, respectively. These findings offer valuable insights into the role of information transparency, reciprocal altruism, and compliance in MOSA interaction, with implications for designing AI-assisted collaborative systems.

Supply chain (SC) risk management is influenced by both spatial and temporal attributes of different entities (suppliers, retailers, and customers). Each entity has given capacity and lead time to process and transport products to downstream entities. In disruptive events, lead times and capacities may vary, which affects the overall performance of SC. There have been many studies on SC disruption mitigation, but often without considering lead time and the magnitude of lateness. In this paper, we formulate a mixed integer programming (MIP) model to optimize SC operations via a routing and scheduling approach, to model the delivery time of products at different entities as they flow throughout the SC network. We minimize a weighted sum of multiple objectives that involve costs related to transportation, shortages, and delivery lateness. We further develop a Benders decomposition algorithm for speeding up the computation of the NP-hard MIP model. We also develop a discrete-event simulation framework to evaluate the performance of solutions to the MIP model under lead time uncertainty. Through extensive numerical studies, we show how the attributes of SC entities affect the performance, so that we can improve the SC design and operations under various uncertainties.

Optimizing the controls of quantum systems plays a crucial role in advancing quantum technologies. The time-varying noises in quantum systems and the widespread use of inhomogeneous quantum ensembles raise the need for high-quality quantum controls under uncertainties. In this paper, we consider a stochastic discrete optimization formulation of a discretized binary optimal quantum control problem involving Hamiltonians with predictable uncertainties. We propose a sample-based reformulation that optimizes both risk-neutral and risk-averse measurements of control policies, and solve these with two gradient-based algorithms using sum-up-rounding approaches. Furthermore, we discuss the differentiability of the objective function and prove upper bounds of the gaps between the optimal solutions to binary control problems and their continuous relaxations. We conduct numerical simulations on various sized problem instances based on two applications of quantum pulse optimization; we evaluate different strategies to mitigate the impact of uncertainties in quantum systems. We demonstrate that the controls of our stochastic optimization model achieve significantly higher quality and robustness compared with the controls of a deterministic model. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. Accepted for Special Issue. Funding: This work was supported by the US Department of Energy, Advanced Scientific Computing Research [Grants DE-AC02-06CH11357, DE-SC0018018]; Defense Sciences Office, DARPA [Grant IAA-8839-annex-130]; the US National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation [Grant 2041745]; and the US National Aeronautics and Space Administration (NASA) Ames Research Center [Grant 80ARC020D0010]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0560 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0560 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We consider a risk-averse stochastic capacity planning problem under uncertain demand in each period. Using a scenario tree representation of the uncertainty, we formulate a multistage stochastic integer program to adjust the capacity expansion plan dynamically as more information on the uncertainty is revealed. Specifically, in each stage, a decision maker optimizes capacity acquisition and resource allocation to minimize certain risk measures of maintenance and operational cost. We compare it with a two-stage approach that determines the capacity acquisition for all the periods up front. Using expected conditional risk measures, we derive a tight lower bound and an upper bound for the gaps between the optimal objective values of risk-averse multistage models and their two-stage counterparts. Based on these derived bounds, we present general guidelines on when to solve risk-averse two-stage or multistage models. Furthermore, we propose approximation algorithms to solve the two models more efficiently, which are asymptotically optimal under an expanding market assumption. We conduct numerical studies using randomly generated and real-world instances with diverse sizes, to demonstrate the tightness of the analytical bounds and efficacy of the approximation algorithms. We find that the gaps between risk-averse multistage and two-stage models increase as the variability of the uncertain parameters increases and decrease as the decision maker becomes more risk averse. Moreover, a stagewise-dependent scenario tree attains much higher gaps than a stagewise-independent counterpart, whereas the latter produces tighter analytical bounds. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work of Dr. X. Yu was partially supported by the U.S. National Science Foundation Division of Information and Intelligent Systems [Grant 2331782]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0396 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0396 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Modern supply chain networks (SCN) are becoming increasingly complex, with vulnerable entities exposed to uncertain disruptions that affect local or global supply chain attributes. We model a stochastic mixed-integer program to minimize the overall cost of SCN design and operations, in response to lead-time and demand uncertainties following given probability distributions. We formulate a heterogeneous risk-aware model to trade off between cost and delay/shortage by considering different risk-attitudes amongst supply chain agents. In particular, we employ the Conditional Value-at-Risk (CVaR) as a coherent risk measure for quantifying risk while attaining solution tractability. We derive managerial insights from our numerical studies, finding the most benefit from diversifying agents in the root tier, since their disruptions affect all other tiers in the SCN. We find that as agents become more risk averse, the optimal solutions for key agents (such as assemblers), seek more backup suppliers and allocate extra capacities to achieve resiliency and reliability. Practitioners can use the outcomes of our framework and studies to guide SCN design considering heterogeneous risk attitudes between agents. Note to Practitioners—With growing uncertainties in global supply chains, inefficient responses to disruptions can lead to large penalties and long-term impacts such as customer dissatisfaction. This research is motivated by the challenges arising during the operations of supply chains under both lead-time and demand uncertainties. We employ optimization and centralized control approaches to optimize supply-chain network design as well as response strategies to disruptions, and our framework can handle heterogeneous risk preferences as it models the risk attitude of each individual entity or agent in supply chains. Our model can be utilized to completely or partially re-design resilient supply chains, to better prepare for unknown features and uncertainties. Our case study provides insights about risk-averse supply-chain designs that can reduce response cost, but increase initial investments on backups and redundancies.

Quantum optimal control is a technique for controlling the evolution of a quantum system and has been applied to a wide range of problems in quantum physics. We study a binary quantum control optimization problem, where control decisions are binary-valued and the problem is solved in diverse quantum algorithms. In this paper, we utilize classical optimization and computing techniques to develop an algorithmic framework that sequentially optimizes the number of control switches and the duration of each control interval on a continuous time horizon. Specifically, we first solve the continuous relaxation of the binary control problem based on time discretization and then use a heuristic to obtain a controller sequence with a penalty on the number of switches. Then, we formulate a switching time optimization model and apply sequential least-squares programming with accelerated time-evolution simulation to solve the model. We demonstrate that our computational framework can obtain binary controls with high-quality performance and also reduce computational time via solving a family of quantum control instances in various quantum physics applications.

Bilevel programs (BPs) find a wide range of applications in fields such as energy, transportation, and machine learning. As compared to BPs with continuous (linear/convex) optimization problems in both levels, the BPs with discrete decision variables have received much less attention, largely due to the ensuing computational intractability and the incapability of gradient-based algorithms for handling discrete optimization formulations. In this paper, we develop deep learning techniques to address this challenge. Specifically, we consider a BP with binary tender, wherein the upper and lower levels are linked via binary variables. We train a neural network to approximate the optimal value of the lower-level problem, as a function of the binary tender. Then, we obtain a single-level reformulation of the BP through a mixed-integer representation of the value function. Furthermore, we conduct a comparative analysis between two types of neural networks: general neural networks and the novel input supermodular neural networks, studying their representational capacities. To solve high-dimensional BPs, we introduce an enhanced sampling method to generate higher-quality samples and implement an iterative process to refine solutions. We demonstrate the performance of these approaches through extensive numerical experiments, whose lower-level problems are linear and mixed-integer programs, respectively.

In recent years, the frequent occurrence of disruptions has had a negative impact on global supply chains. To stay competitive, enterprises strive to remain agile through the implementation of efficient and effective decision-making strategies in reaction to disruptions. A significant effort has been made to develop these agile disruption mitigation approaches, leveraging both centralized and distributed decision-making strategies. Though trade-offs of centralized and distributed approaches have been analyzed in existing studies, no related work has been found on understanding supply chain performance based on the networkattributesof the disrupted supply chain entities. In this paper, we characterize supply chains from a capability and network topological perspective and investigate the use of a distributed decision-making approach based on classical multi-agent frameworks. The performance of the distributed framework is evaluated through a comprehensive case study that investigates the performance of the supply chain as a function of the network structure and agent attributes within the network in the presence of a disruption. Comparison to a centralized decision-making approach highlights trade-offs between performance, computation time, and network communication based on the decision-making strategy and network architecture. Practitioners can use the outcomes of our studies to design response strategies based on agent capabilities, network attributes, and desired supply chain performance.Note to Practitioners—This research is motivated by the challenges in determining agile decision-making strategies that enable a supply chain enterprise to adapt to disruptions while taking into account the network-based attributes of the disrupted agent and the requirements of the supply chain system. Existing approaches in the literature focus on providing one feasible decision-making strategy based on specific performance metrics. This paper investigates both centralized and distributed approaches to better understand the differences between the response strategies in the case of supplier loss. More specifically, we design a supply chain instance and conduct a case study to evaluate the performance of the centralized and distributed approaches in terms of several common performance metrics used in practice. The case study provides insights for users to select a decision-making approach based on the network attributes and agent capabilities of the supply chain. The impact of network uncertainties and risk assessment are not considered in this work. Future studies will investigate a stochastic supply chain environment and heterogeneous risk management framework in the context of agile decision-making for disrupted supply chain enterprises.

We consider a price-based revenue management problem with reusable resources over a finite time horizon $T$. The problem finds important applications in car/bicycle rental, ridesharing, cloud computing, and hospitality management. Customers arrive following a price-dependent Poisson process and each customer requests one unit of $c$ homogeneous reusable resources. If there is an available unit, the customer gets served within a price-dependent exponentially distributed service time; otherwise, she waits in a queue until the next available unit. The decision maker assumes that the inter-arrival and service intervals have an unknown linear dependence on a $d_f$-dimensional feature vector associated with the posted price. We propose a rate-optimal online learning and pricing algorithm, termed Batch Linear Confidence Bound (BLinUCB), and prove that the cumulative regret is $\tilde{O}( d_f \sqrt{T } )$. In establishing the regret, we bound the transient system performance upon price changes via a coupling argument, and also generalize linear bandits to accommodate sub-exponential rewards.

We consider a price-based network revenue management problem with multiple products and multiple reusable resources. Each randomly arriving customer requests a product (service) that needs to occupy a sequence of reusable resources (servers). We adopt an incomplete information setting where the firm does not know the price-demand function for each product and the goal is to dynamically set prices of all products to maximize the total expected revenue of serving customers. We propose novel batched bandit learning algorithms for finding near-optimal pricing policies, and show that they admit a near-optimal cumulative regret bound of $\tilde{O}(J\sqrt{XT})$, where $J$, $X$, and $T$ are the numbers of products, candidate prices, and service periods, respectively. As part of our regret analysis, we develop the first finite-time mixing time analysis of an open network queueing system (i.e., the celebrated Jackson Network), which could be of independent interest. Our numerical studies show that the proposed approaches perform consistently well.

We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems.

Through smartphone apps, drivers and passengers can dynamically enter and leave ride-hailing platforms. As a result, ride-pooling is challenging due to complex system dynamics and different objectives of multiple stakeholders. In this paper, we study ride-pooling with no more than two passenger groups who can share rides in the same vehicle. We dynamically match available drivers to randomly arriving passengers and also decide pick-up and drop-off routes. The goal is to minimize a weighted sum of passengers' waiting time and trip delay time. A spatial-and-temporal decomposition heuristic is applied and each subproblem is solved using Approximate Dynamic Programming (ADP), for which we show properties of the approximated value function at each stage. Our model is benchmarked with the one that optimizes vehicle dispatch without ride-pooling and the one that matches current drivers and passengers without demand forecasting. Using test instances generated based on the New York City taxi data during one peak hour, we conduct computational studies and sensitivity analysis to show (i) empirical convergence of ADP, (ii) benefit of ride-pooling, and (iii) value of future supply-demand information.

Surgery planning decisions include which operating rooms (ORs) to open, allocation of surgeries to ORs, sequence, and time to start each surgery. They are often made under uncertain surgery durations with limited data that lead to unknown distributional information. Moreover, cost parameters for criteria such as overtime and surgery delays are often difficult or impossible to estimate in practice. In this paper, we formulate distributionally robust (DR) chance constraints on surgery waiting and OR overtime, which recognize practical limitations on data availability and cost parameter accuracy. We use [Formula: see text]-divergence measures to build an ambiguity set of possible distributions of random surgery durations, and derive a branch-and-cut algorithm for optimizing a mixed-integer linear programming reformulation based on finite samples of the random surgery durations. We test instances generated from real hospital-based surgery data. The results show computational efficacy of our approaches, and provide insights for DR surgery planning.

In this paper, we extend a recently proposed scenario decomposition algorithm for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider two-stage risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the considered problem. We then develop three variants of the scenario decomposition algorithm for this minimax formulation based on different relaxations of the nonanticipaticity constraints. The algorithms proceed by solving scenario subproblems to obtain candidate solutions and bounds and subsequently cutting off the candidate solutions from the search space to achieve convergence to an optimal solution. We design three parallelization schemes for implementing the algorithms with different tradeoffs between overhead time and computation time. Our computational results with risk-averse extensions of two standard stochastic 0-1 programming test instances demonstrate the scalability of the proposed decomposition and parallelization framework.

We consider a Stackelberg game in a network where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer than a given threshold, interpreted by a chance constraint. Under the assumption of a wait-and-see follower—i.e., the follower selects a shortest path after seeing realizations of the random arc cost—we propose a branch-and-cut algorithm and apply lifting techniques to exploit the combinatorial structure of the risk-averse leader’s interdiction problem. We demonstrate the computational efficacy of our approaches, risk-averse interdiction solution patterns, and result sensitivity, by testing instances of randomly generated grid networks and real-world transportation networks.

We consider a balance-constrained stochastic bottleneck spanning tree problem (BCSBSTP) where edge weights are independently distributed but may follow arbitrary continuous distributions. The goal is to minimize a threshold variable that may be exceeded by the maximum edge weight at certain risk, subject to the minimum edge weight being no less than a fixed threshold with a probability guarantee. We characterize these two requirements as chance constraints, which are typically used for bounding the risk of undesirable random outcomes. Given independently distributed edge weights, we reformulate BCSBSTP as a mixed-integer nonlinear program, approximated by two mixed-integer linear programs based on special ordered set of type one (SOS1) and special ordered set of type two (SOS2) variables. By relaxing the probabilistic guarantee on the minimum edge weight in BCSBSTP, we also consider a stochastic bottleneck spanning tree problem (SBSTP), of which optimal tree solutions are approximated via a bisection algorithm in pseudopolynomial time. We demonstrate computational results of our models and algorithms by testing randomly generated instances with edge weights following a diverse set of independent distributions.

Abstract This article considers the problem of using synchronous mobile agents to decontaminate the nodes of a graph given a spreading contamination. We begin by considering the problem of minimizing cleaning time, given initial agent, and contamination locations. Then, we take as input a set of all possible locations in which a contamination can start and examine problems in which we strategically preposition agents. In one problem, we minimize the number of agents and prescribe their initial locations, so that the graph can be cleaned within a time limit for any potential initial contamination. We also determine the best initial locations for some predetermined number of agents to minimize expected cleaning time, given probability estimates of potential initial contamination locations. We analyze the complexity of each variant and formulate the problems as mixed‐integer programs. As an alternative method, we also provide a construction heuristic for the cleaning problem and cutting‐plane algorithms for the agent location problems. Computational results using these approaches demonstrate the efficacy of our procedures. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of network interdiction and graph theory research and are relevant to several practical optimization problems. The two different connectivity metrics that we consider regard the number of maximal connected components (which we attempt to maximize) and the largest component size (which we attempt to minimize). We develop optimal polynomial‐time dynamic programming algorithms for solving these problems on tree structures and on series‐parallel graphs, corresponding to each graph‐connectivity metric. We also extend our discussion by considering node deletion costs, node weights, and solving the problems on generalizations of tree structures. Finally, we demonstrate the computational efficacy of our approach on randomly generated graph instances. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012