1 March 2024 in Management Science
In this paper, we solve a class of two-stage distributionally robust optimization problems that have the property of supermodularity. We exploit the explicit worst case expectation of supermodular functions and derive the worst case distribution for the robust counterpart. This enables us to develop an efficient method to obtain an exact optimal solution to these two-stage problems. Further, we provide a necessary and sufficient condition for checking whether any given two-stage optimization problem has the supermodularity property. We also investigate the optimality of the segregated affine decision rules when problems have the property of supermodularity. We apply this framework to several classic problems, including the multi-item newsvendor problem, the facility location problem, the lot-sizing problem on a network, the appointment-scheduling problem, and the assemble-to-order problem. Whereas these problems are typically computationally challenging, they can be solved efficiently under our assumptions. Finally, numerical examples are conducted to illustrate the effectiveness of our approach. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the National Natural Science Foundation of China [Grant 71971187], and Hong Kong Research Grants Council [Collaborative Research Fund (C6103-20GF), General Research Fund (14210821, 16204521, 16212419)]. Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.4748 .
1 January 2023 in Operations Research
In the inventory routing problem, the supplier acts as a central decision maker who determines the replenishment quantities and also, the delivery times and routes to all retailers. In “Inventory Routing Problem Under Uncertainty”, Cui et al. develop a novel framework for the uncertain inventory routing problem and allow ambiguity in the probability distribution of each retailer's uncertain demand. Adopting a service-level viewpoint, they minimize the risk of uncertain inventory levels violating a prespecified acceptable range. They quantify that risk using a new decision criterion, the service violation index, that accounts for how often and how severely the inventory requirement is violated. The solutions proposed here are adaptive in the sense that they vary with the realization of uncertain demand. They provide algorithms to solve the problem exactly and then, demonstrate the superiority of their solutions by comparing them with several benchmarks.
1 January 2021 in Operations Research
The concept of supermodularity has received considerable attention in economics and operations research. It is closely related to the concept of complementarity in economics and has also proved to be an important tool for deriving monotonic comparative statics in parametric optimization problems and game theory models. However, only certain sufficient conditions (e.g., lattice structure) are identified in the literature to preserve the supermodularity. In this article, new concepts of mostly sublattice and additive mostly sublattice are introduced. With these new concepts, necessary and sufficient conditions for the constraint structures are established so that supermodularity can be preserved under various assumptions about the objective functions. Furthermore, some classes of polyhedral sets that satisfy these concepts are identified, and the results are applied to assemble-to-order systems.
1 May 2024 in Manufacturing & Service Operations Management
Problem definition: We consider a surgery sequencing and scheduling problem with uncertain durations of surgeries in the context of an operating theater. From real data collected from a hospital, we observe the common practice, namely, “to follow,” in which surgeries are conducted sequentially and immediately one after another, according to a specific schedule. Methodology/results: Based on this practice, we propose a mathematical framework to balance the risk of delay and idling using the punctuality index, which takes into consideration both the probability and intensity of delay and idle time. We develop a computationally efficient procedure based on Benders decomposition to derive exact solutions for the problem. The scheduling problem is solvable in polynomial time when the sequence is given. The framework can also accommodate a robust setting when the underlying probability distribution is not fully available. For practical use, we propose two effective heuristics for sequencing decisions by approximating the model. Using real data, we demonstrate that our framework is significantly better than the risk-neutral and probability-maximizing approaches in both performance and computational efficiency. Moreover, the robust setting can effectively lessen the risk of extremely long delay and idle time, and the heuristics are efficient with only a small sacrifice of performance. Managerial implications: With the to-follow policy, our sequencing and scheduling model describes the actual practice better. The two heuristics can be applied easily and directly to help managers of operating theaters to make decisions. Funding: J. Qi is supported by the Hong Kong Research Grants Council [Grants 26202016, 16212419, and 16204521]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0029 .
17 November 2025 in Production and Operations Management
We study a distributionally robust pricing model aimed at maximizing the worst-case profit under limited knowledge of consumers’ valuation distribution. In addition to mean and variance, we incorporate asymmetric distributional information through semivariance, and then explore the robust optimal posted and randomized pricing strategy. We obtain the robust posted price and show that several series of asymptotic three-point distributions can approach the worst case gradually. The inclusion of asymmetry enables sellers to design three distinct pricing strategies, each corresponding to a different level of asymmetry with explicitly defined thresholds. For the randomized pricing problem, we derive a near-optimal strategy by identifying three key pricing candidates. To avoid the complexity of implementing the optimal randomized price, we also explore a compromise strategy that employs a finite set of pricing candidates, which we formulate as a second-order cone program. Furthermore, we provide numerical evidence highlighting the advantages of incorporating asymmetric distributional information over the mean–variance approach, from both the worst-case profit and actual profit perspectives. Our numerical experiments also reveal that posted pricing is more effective for low-cost products, while randomized pricing is preferable for higher-cost items.