In this work, we consider an online robust Markov Decision Process (MDP) where we have the information of finitely many prototypes of the underlying transition kernel. We consider an adaptively updated ambiguity set of the prototypes and propose an algorithm that efficiently identifies the true underlying transition kernel while guaranteeing the performance of the corresponding robust policy. To be more specific, we provide a sublinear regret of the subsequent optimal robust policy. We also provide an early stopping mechanism and a worst-case performance bound of the value function. In numerical experiments, we demonstrate that our method outperforms existing approaches, particularly in the early stage with limited data. This work contributes to robust MDPs by considering possible prior information about the underlying transition probability and online learning, offering both theoretical insights and practical algorithms for improved decision-making under uncertainty.

Accurate demand forecasting for products in the parts supply chain system (PSCS) is critical for enterprises to optimize production and inventory operations. To address the challenges of inadequate modeling of complex inter-product relationships and the limited accuracy of existing forecasting methods, this paper proposes a demand forecasting method based on a Graph Convolutional and LSTM Network with Embedded Multi-Head Self-Attention (GL-MHSA). The method first extracts hybrid distance features, including Euclidean and pattern distances, from product sales data in the PSCS to mine product associations and construct graph-structured relational data. A Graph Convolutional Network (GCN) is then used to capture structural association features among products, while an LSTM network models the temporal dependencies in the demand sequences. The extracted features are fused through a Multi-Head Self-Attention (MHSA) mechanism to obtain a comprehensive feature representation. This representation is concatenated with other auxiliary features to form the final input for demand prediction. Experimental results on an automotive PSCS dataset show that the proposed GL-MHSA model achieves more accurate modeling of product associations and significantly improves demand forecasting performance compared to existing approaches.

We consider assortment and inventory planning problems with dynamic stockout-based substitution effects, and without replenishment, in two different settings: (1) Customers can see all available products when they arrive, a typical scenario in physical stores. (2) The seller can choose to offer a subset of available products to each customer, which is more common on online platforms. Both settings are known to be computationally challenging, and the current approximation algorithms for the two settings are quite different. We develop a unified algorithm framework under the MNL choice model for both settings. Our algorithms improve on the state-of-the-art algorithms in terms of approximation guarantee and runtime, and the ability to manage uncertainty in the total number of customers and handle more complex constraints. In the process, we establish various novel properties of dynamic assortment planning (for the MNL choice model) that may be useful more broadly. A full version of this paper can be found at https://arxiv.org/abs/2404.03604.

A solar power plant provides green electricity to the public via a power grid. As governments worldwide have pledged to reduce carbon emissions and achieve carbon neutrality, large-scale grid-connected solar power plants are booming. Developing such a plant requires significant investment, a large proportion of which covers construction costs. Such costs, together with the energy yield, critically depend on the plant’s layout. The layout planning of a solar power plant involves a series of complex optimization problems such as district partitioning, photovoltaic (PV) component location, and cable routing problems in a solar power plant. These problems have received limited attention in the literature and are highly challenging because they involve large-scale instances, complex design principles, and complicated physical constraints. Motivated by our collaborative projects with an electrical engineering company in China, this paper specifically focuses on the integrated location and routing (ILR) problem, which involves locating service ways, inverters, combiner boxes, and routing cables to connect them. We develop exact algorithms to effectively solve the ILR problem via a decomposition framework (leading to a variant of Benders decomposition (BD)), which is proven to produce an optimal solution. We also develop an exact branch-and-cut scheme to solve each subproblem in the decomposition framework by incorporating cutting planes and separation algorithms. Our solution approach is evaluated on 50 real-world data instances via extensive numerical experiments. Compared with the manual method based on greedy heuristics used in practice, our approach reduces the total cost by approximately 20%. Our decomposition method also achieves an average gap of 0.02% between the obtained lower and upper bounds, significantly smaller than the 16.08% gap achieved with the traditional BD. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was partially supported by the Research Grants Council of Hong Kong [Grant 15501221], the National Natural Science Foundation Program of China [Grants 72122006, 72471100, and 72131008], Huazhong University of Science and Technology Double First-Class Funds for Humanities and Social Sciences (Digital Intelligence Decision Optimization Innovation Team), the Interdisciplinary Research Program of HUST [Grant 5003300129], and the Fundamental Research Funds for the Central Universities [Grant 2023WKFZZX101]. 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.0223 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0223 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study Concave Constrained Markov Decision Processes (Concave CMDPs) where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Primal-Dual Policy Gradient Algorithm (VR-PDPG), which updates the primal variable via policy gradient ascent and the dual variable via projected sub-gradient descent. Despite the challenges posed by the loss of additivity structure and the nonconcave nature of the problem, we establish the global convergence of VR-PDPG by exploiting a form of hidden concavity. In the exact setting, we prove an O(T-1/3) convergence rate for both the average optimality gap and constraint violation, which further improves to O(T-1/2) under strong concavity of the objective in the occupancy measure. In the sample-based setting, we demonstrate that VR-PDPG achieves an O(ε-4) sample complexity for ε-global optimality. Moreover, by incorporating a diminishing pessimistic term into the constraint, we show that VR-PDPG can attain a zero constraint violation without compromising the convergence rate of the optimality gap. Finally, we validate our methods through numerical experiments.

Nonprogressive diffusion describes the spread of behavior on a social network, where agents are allowed to reverse their decisions as time evolves. It has a wide variety of applications in service adoption, opinion formation, epidemiology, etc. Two common approaches to analyzing network diffusion are: microfounded methods, which capture the detailed network topology and the stochastic evolution of agent states but often lead to computational challenges, and macroscopic methods, which simplify the diffusion process.

Non-ferrous metals, as important basic raw materials, are the strategic supports for national economic development. For non-ferrous metal smelting enterprises, raw material procurement is the focal and most important session. Due to the fluctuation of production volumes and the future changes in raw-material prices, the procurement cost of raw materials is high and with a high risk of shortage. In this paper, we propose a multi-period rolling robust procurement model considering price and demand uncertainties. In particular, we design a data-driven method to construct the budget-based uncertainty sets and derive the robust counterpart of the robust procurement model. Comparative experiments on the real data with classic and advanced procurement policies show that our proposed solution approach achieves the lowest cost under the premise of continuous supply of raw materials. Interestingly, we observe that limited capital and warehouse capacity can effectively restrain unreasonable behavior and thus not to cause big losses in uncertain environments. In addition, a relatively long planning horizon can be counterproductive. These valuable and actionable insights can well guide practical decision-making.Note to Practitioners—For the raw material procurement of non-ferrous metal smelter, this article proposes a multi-period rolling robust procurement model considering price and demand uncertainties. Taking account of the dynamic characteristics of raw-material prices and the seasonal characteristics of raw-material demands, a data-driven method to construct budget-based uncertainty sets is designed. In particular, we derive the solvable robust counterpart of the robust procurement model. The proposed approach can reduce costs ensuring the continuous supply of raw materials. Some interesting and actionable managerial insights are obtained that can well guide practical decision-making, and the proposed data-driven approach is realizable.

We study convex Constrained Markov Decision Processes (CMDPs) in which the objective is concave and the constraints are convex in the state-action occupancy measure. We propose a policy-based primal-dual algorithm that updates the primal variable via policy gradient ascent and updates the dual variable via projected sub-gradient descent. Despite the loss of additivity structure and the nonconvex nature, we establish the global convergence of the proposed algorithm by leveraging a hidden convexity in the problem, and prove the O(T^-1/3) convergence rate in terms of both optimality gap and constraint violation. When the objective is strongly concave in the occupancy measure, we prove an improved convergence rate of O(T^-1/2). By introducing a pessimistic term to the constraint, we further show that a zero constraint violation can be achieved while preserving the same convergence rate for the optimality gap. This work is the first one in the literature that establishes non-asymptotic convergence guarantees for policy-based primal-dual methods for solving infinite-horizon discounted convex CMDPs.

This work is dedicated to the algorithm design in a competitive framework, with the primary goal of learning a stable equilibrium. We consider the dynamic price competition between two firms operating within an opaque marketplace, where each firm lacks information about its competitor. The demand follows the multinomial logit (MNL) choice model, which depends on the consumers' observed price and their reference price, and consecutive periods in the repeated games are connected by reference price updates. We use the notion of stationary Nash equilibrium (SNE), defined as the fixed point of the equilibrium pricing policy for the single-period game, to simultaneously capture the long-run market equilibrium and stability. We propose the online projected gradient ascent algorithm (OPGA), where the firms adjust prices using the first-order derivatives of their log-revenues that can be obtained from the market feedback mechanism. Despite the absence of typical properties required for the convergence of online games, such as strong monotonicity and variational stability, we demonstrate that under diminishing step-sizes, the price and reference price paths generated by OPGA converge to the unique SNE, thereby achieving the no-regret learning and a stable market. Moreover, with appropriate step-sizes, we prove that this convergence exhibits a rate of $\mathcal{O}(1/t)$.

Contextual decision-making problems have witnessed extensive applications in various fields such as online content recommendation, personalized healthcare, and autonomous vehicles, where a core practical challenge is to select a suitable surrogate model for capturing unknown complicated reward functions. It is often the case that both high approximation accuracy and explicit uncertainty quantification are desired. In this work, we propose a neural network-accompanied Gaussian process (NN-AGP) model, which leverages neural networks to approximate the unknown and potentially complicated reward function regarding the contextual variable, and maintains a Gaussian process surrogate model with respect to the decision variable. Our model is shown to outperform existing approaches by offering better approximation accuracy thanks to the use of neural networks and possessing explicit uncertainty quantification from the Gaussian process. We also analyze the maximum information gain of the NN-AGP model and prove regret bounds for the corresponding algorithms. Moreover, we conduct experiments on both synthetic and practical problems, illustrating the effectiveness of our approach.

Quantum computing is expected to have transformative influences on many domains, but its practical deployments on industry problems are underexplored. We focus on applying quantum computing to operations management problems in industry, and in particular, supply chain management. Many problems in supply chain management involve large state and action spaces and pose computational challenges on classic computers. We develop a quantized policy iteration algorithm to solve an inventory control problem and demonstrative its effectiveness. We also discuss in-depth the hardware requirements and potential challenges on implementing this quantum algorithm in the near term. Our simulations and experiments are powered by IBM Qiskit and the qBraid system.

We address a dynamic covering location problem of an unmanned aerial vehicle base station (UAV-BS), in which the location sequence of a single UAV-BS in a wireless communication network is determined to satisfy data demand arising from ground users. This problem is especially relevant in the context of smart grid and disaster relief. The vertical movement ability of the UAV-BS and nonconvex covering functions in wireless communication restrict utilizing classical planar covering location approaches. Therefore, we develop new formulations to this emerging problem for a finite time horizon to maximize the total coverage. In particular, we develop a mixed-integer nonlinear programming formulation that is nonconvex in nature and propose a Lagrangean decomposition algorithm (LDA) to solve this formulation. Because of the high complexity of the problem, the LDA is still unable to find good local solutions to large-scale problems. Therefore, we develop a continuum approximation (CA) model and show that CA would be a promising approach in terms of both computational time and solution accuracy. Our numerical study also shows that the CA model can be a remedy to build efficient initial solutions for exact solution algorithms. Summary of Contribution: This paper addresses a facet of mixed integer nonlinear programming formulations. Dynamic facility location problems (DFLPs) arise in a wide range of applications. However, classical DFLPs typically focus on the two-dimensional spaces. Emerging technologies in wireless communication and some other promising application areas, such as smart grids, have brought new location problems that cannot be solved with classical approaches. For practical reasons, many research attempts to solve this new problem, especially by researchers whose primary research area is not OR, have seemed far from analyzing the characteristics of the formulations. Rather, solution-oriented greedy heuristics have been proposed. This paper has two main objectives: (i) to close the gap between practical and theoretical sides of this new problem with the help of current knowledge that OR possesses to solve facility location problems and (ii) to support the findings with an exhaustive computational study to show how these findings can be applied to practice.

Apiculture has gained worldwide interest because of its contributions to economic incomes and environmental conservation. In view of these, migratory beekeeping, as a high-yielding technique, is extensively adopted. However, because of the lack of an overall routing plan, beekeepers who follow the experiential migratory routes frequently encounter unexpected detours and suffer losses when faced with problems such as those related to nectar source capacities and the production of bee products. The migratory beekeeping routing problem (MBRP) is proposed based on the practical background of the commercial apiculture industry to optimize the global revenue for beekeepers by comprehensively considering nectar source allocation, migration, production and sales of bee products, and corresponding time decisions. The MBRP is a new variant of the vehicle routing problem but with significantly different production time decisions at the vertices (i.e., nectar sources). That is, only the overlaps between residence durations and flowering periods generate production benefits. Different sales visits cause different gains from the same products; in turn, these lead to different production time decisions at previously visited nectar source locations and even change the visits for production. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Summary of Contribution. Based on the practical background of commercial apiculture industry, this paper proposes a new type of routing problem named the migratory beekeeping routing problem (MBRP), which incorporates the selection of productive nodes and sales nodes as well as the production time decision at the productive nodes on a migratory beekeeping network. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Therefore, this paper is congruent with, and contributes to, the scope and mission of INFORMS Journal on Computing, especially the area of Network Optimization: Algorithms & Applications.

We study the energy consumption minimization problems of natural gas transmission in gunbarrel structured networks. In particular, we consider the transient-state dynamics of natural gas and the compressor’s nonlinear working domain and min-up-and-down constraints. We formulate the problem as a two-level dynamic program (DP), where the upper-level DP problem models each compressor station as a decision stage and each station’s optimization problem is further formulated as a lower-level DP by setting each time period as a stage. The upper-level DP faces the curse of high dimensionality. We propose an approximate dynamic programming (ADP) approach for the upper-level DP using appropriate basis functions and an exact approach for the lower-level DP by exploiting the structure of the problem. We validate the superior performance of the proposed ADP approach on both synthetic and real networks compared with the benchmark simulated annealing (SA) heuristic and the commonly used myopic policy and steady-state policy. On the synthetic networks (SNs), the ADP reduces the energy consumption by 5.8%–6.7% from the SA and 12% from the myopic policy. On the test gunbarrel network with 21 compressor stations and 28 pipes calibrated from China National Petroleum Corporation, the ADP saves 4.8%–5.1% (with an average of 5.0%) energy consumption compared with the SA and the currently deployed steady-state policy, which translates to cost savings of millions of dollars a year. Moreover, the proposed ADP algorithm requires 18.4%–61.0% less computation time than the SA. The advantages in both solution quality and computation time strongly support the proposed ADP algorithm in practice.

A robotic mobile fulfillment system (RMFS) performs the order fulfillment process by bringing inventory to workers at pick-pack-and-ship warehouses. In the RMFS, robots lift and carry shelving units, called inventory pods, from storage locations to picking stations where workers pick items off the pods and put them into shipping cartons. The robots then return the pods to the storage area and transport other pods. In this article, we consider an item assignment problem in the RMFS in order to maximize the sum of similarity values of items in each pod. We especially focus on a reoptimization heuristic to address the situation where the similarity values are altered so that a good assignment solution can be obtained quickly with the changed similarity values. A constructive heuristic algorithm for the item assignment problem is developed, and then, a reoptimization heuristic is proposed based on the constructive heuristic algorithm. Then, computational results for several instances of the problem with 10-500 items are presented. We further analyze the case for which an item type can be placed into two pods. Note to Practitioners-This article proposes an efficient heuristic algorithm for assigning items to pods in a robotic mobile fulfillment system (RMFS) so that items ordered together frequently are put into the same pod. Computational results with 10-500 items show that the gaps from upper bounds are very small on average. For cases where the similarity values between items change or their estimation is not accurate due to the fluctuations in demand, a reoptimization heuristic algorithm that alters the original assignment is developed. The experimental results show that the reoptimization algorithm is robust when perturbation levels are approximately 40%-50% of the original similarity values with much less computation times. We believe that this research work can be very helpful for operating the RMFS efficiently.

In the past decade, Electroencephalogram (EEG) has been applied in many fields, such as Motor Imagery (MI) and Emotion Recognition. Traditionally, for classification tasks based on EEG, researchers would extract features from raw signals manually which is often time consuming and requires adequate domain knowledge. Besides that, features manually extracted and selected may not generalize well due to the limitation of human. Convolutional Neural Networks (CNNs) plays an important role in the wave of deep learning and achieve amazing results in many areas. One of the most attractive features of deep learning for EEG-based tasks is the end-to-end learning. Features are learned from raw signals automatically and the feature extractor and classifier are optimized simultaneously. There are some researchers applying deep learning methods to EEG analysis and achieving promising performances. However, supervised deep learning methods often require large-scale annotated dataset, which is almost impossible to acquire in EEG-based tasks. This problem limits the further improvements of deep learning models for classification based on EEG. In this paper, we propose a novel deep learning method DMTL-BCI based on Multi-Task Learning framework for EEG-based classification tasks. The proposed model consists of three modules, the representation module, the reconstruction module and the classification module. Our model is proposed to improve the classification performance with limited EEG data. Experimental results on benchmark dataset, BCI Competition IV dataset 2a, show that our proposed method outperforms the state-of-the-art method by 3.0%, which demonstrates the effectiveness of our model.

The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a one-dimensional PS and solve a series of PAPs. We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds.

Routing service considering uncertainty is at the core of intelligent transportation systems and has attracted increasing attention. Existing stochastic shortest path models require the exact probability distributions of travel times and usually assume that they are independent. However, the distributions are often unavailable or inaccurate due to insufficient data, and correlation of travel times over different links has been observed. This paper presents a robust shortest path (RSP) model that only requires partial distribution information of travel times, including the support set, mean, variance, and correlation matrix. We introduce a concept of robust mean-excess travel time to hedge against the risk from both the uncertainty of the random travel times and the uncertainty in their distributions. To solve the RSP problem, an equivalent dual formulation is derived and used to design tight lower and upper bound approximation methods, which adopt the scenario approach and semi-definite programming approach, respectively. To solve large problems, we further propose an efficient primal approximation method, which only needs to solve two deterministic shortest path problems and a mean-standard deviation shortest path problem, and analyze its approximation performance. Experiments validate the tightness of the proposed bounds and demonstrate the impact of uncertainty on the relative benefit and cost of robust paths.

We consider reliable facility location models in which facilities are subject to unexpected failures, and customers may be reassigned to facilities other than their regular facilities. The objective is to minimize the total expected costs in normal and failure scenarios. We allow facilities to have different failure rates and do not limit the number of facilities that might be assigned to a customer. Lower bounds for reliable uncapacitated fixed-charge location problem (RUFLP) are derived and used to introduce a class of efficient algorithms for solving the RUFLP problem.

We study a reliable facility location problem wherein some facilities are subject to failure from time to time. If a facility fails, customers originally assigned to it have to be reassigned to other (operational) facilities. We formulate this problem as a two-stage stochastic program and then as a nonlinear integer program. Several heuristics that can produce near-optimal solutions are proposed for this NP-hard problem. For the special case where the probability that a facility fails is a constant (independent of the facility), we provide an approximation algorithm with a worst-case bound of 4. The effectiveness of our heuristics is tested by extensive computational studies, which also lead to some managerial insights.

Abstract We consider a metric uncapacitated facility location problem where we must assign each customer to a facility and meet the demand of the customer in future time periods through production and inventory decisions at the facility. We show that the problem, in general, is as hard to approximate as the set cover problem. We therefore focus on developing approximation algorithms for special cases of the problem. These special cases come in two forms: (i) specialize the production and inventory cost structure and (ii) specialize the demand pattern of the customers. In the former, we offer reductions to variants of the metric uncapacitated facility location problem that have been previously studied. The latter gives rise to a class of metric uncapacitated facility location problems where the facility cost function is concave in the amount of demand assigned to the facility. We develop a modified greedy algorithm together with the idea of cost‐scaling to provide an algorithm for this class of problems with an approximation guarantee of 1.52. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

The paper presents an information infrastructure for supporting Internet-based scalable e-business enterprises (ISEE). The information infrastructure is formed by a network of ISEE hubs, each of which has a number of replicable e-business servers providing various e-services to individuals and businesses. The servers are the implementations of a number of core technologies developed to facilitate collaborative e-business, including business event and rule management, active distributed objects, constraint satisfaction processing, and cost benefit analysis and selection. Using the e-services provided by these servers, other e-services such as constraint-based brokering, supplier selection, active business process management, and automated negotiation can be developed. Supply chain management is used as an example of collaborative e-business in the descriptions of these technologies and their implementations.