Search

Problem definition: Content promotion policies are crucial for online content platforms to improve content consumption and user engagement. However, traditional promotion policies generally neglect the diffusion effect within a crowd of users. In this paper, we study the candidate generation and promotion optimization (CGPO) problem for an online content platform, emphasizing the incorporation of the diffusion effect. Methodology/results: We propose a diffusion model that incorporates platform promotion decisions to characterize the adoption process of online content. Based on this diffusion model, we formulate the CGPO problem as a mixed-integer program with nonconvex and nonlinear constraints, which is proved to be NP-hard. Additionally, we investigate methods for estimating the diffusion model parameters using available online platform data and introduce novel double ordinary least squares (D-OLS) estimators. We prove the submodularity of the objective function for the CGPO problem, which enables us to find an efficient (1−1/e) -approximation greedy solution. Furthermore, we demonstrate that the D-OLS estimators are consistent and have smaller asymptotic variances than traditional ordinary least squares estimators. By utilizing real data from a large-scale video-sharing platform, we show that our diffusion model effectively characterizes the adoption process of online content. Compared with the policy implemented on the platform, our proposed promotion policy increases total adoptions by 49.90%. Managerial implications: Our research highlights the essential role of diffusion in online content and provides actionable insights for online content platforms to optimize their content promotion policies by leveraging our diffusion model. Funding: R. Zhang is grateful for the financial support from the Hong Kong Research Grants Council General Research Fund [Grants 14502722 and 14504123] and the National Natural Science Foundation of China [Grant 72293560/72293565]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0172. [ABSTRACT FROM AUTHOR]

Problem definition: We investigate the effects of waiting time, mainly due to production in a make-to-batch-order (MTBO) system, on consumer choice behavior, pricing, assortment, and model estimation. In an MTBO system, the seller/manufacturer first collects orders placed within a certain period of time into a batch and then starts the production process. After the production of all orders in a batch are complete, the products are then shipped and delivered to individual consumers. Because of batch production and shipping, the disutility of the waiting time exhibits negative externality. Methodology/results: We adopt the widely used multinomial logit (MNL) model as a starting point and incorporate the anticipated wait into consumers' decision making. The derived model, referred to as the MNL with wait model, is a solution of the rational expectation equilibrium and is capable of capturing the effects of negative externality induced by anticipated wait that may change the substitution patterns dramatically. We characterize the multiproduct price optimization problem under the MNL with wait model by establishing a one-to-one mapping between the price vector and the choice probability vector. We find that firms tend to charge higher prices for time-consuming items and charge lower prices for time-saving items compared with the optimal prices under the standard MNL model. In addition to price competition, we also study the Cournot-type competition, in which the decision is the choice probability for each firm and establish the existence of a Nash equilibrium. For assortment optimization, we identify mild conditions under which the optimality of revenue-ordered assortments still holds. However, the assortment problem under the MNL with wait model is generally NP-hard, so we develop approximation algorithms with performance guarantees and provide an easy-to-compute tight upper bound. Moreover, we develop an efficient maximum likelihood-based algorithm for model calibration and further conduct numerical studies to showcase the importance of incorporating disutility due to wait in estimation, pricing, and assortment planning problems. Managerial implications: The MNL with wait model can increase prediction accuracy for consumers' choice behavior especially when they are aware of the potential wait. Failure to take into account the effects of anticipated wait in firms' decision making may lead to substantial losses. Funding: The research of C. Ke is supported in part by the National Natural Science Foundation of China [Grant 72101113]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2020.0346. [ABSTRACT FROM AUTHOR]

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. 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.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72371157, 61903144, 72031007]. 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.2022.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In "Sequential Competitive Facility Location: Exact and Approximate Algorithms," Qi et al. consider a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets and maximize their market shares of demand following a probabilistic choice model. They derive an equivalent, single-level mixed-integer nonlinear program (MINLP) reformulation of the bilevel MINLP and exploit the problem structures to derive valid inequalities based on submodularity and concave overestimation. They also develop an approximation algorithm with a constant approximation guarantee. They further study several extensions of CFLP that have general facility-opening costs, outside competitors, and diverse facility-planning decisions. Their approaches significantly accelerate the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods. We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs and outside competitors as well as diverse facility-planning decisions, and we discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand. Funding: M. Qi was partially supported by the National Natural Science Foundation of China [Grant 71772100] to work on this project. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2339. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. 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.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of 2 ≤ N ≤ 400 and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of 2 ≤ N ≤ 200 , whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 61703213 and 61933005]. 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.1290) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0004) at (http://dx.doi.org/10.5281/zenodo.7579558). [ABSTRACT FROM AUTHOR]

Problem definition: We consider a revenue management problem that arises from the selling of high-speed train tickets in China. Compared with traditional network revenue management problems, the new feature of our problem is the assign-to-seat restriction. That is, each request, if accepted, must be assigned instantly to a single seat throughout the whole journey, and later adjustment is not allowed. When making decisions, the seller needs to track not only the total seat capacity available, but also the status of each seat. Methodology/results: We build a modified network revenue management model for this problem. First, we study a static problem in which all requests are given. Although the problem is NP-hard in general, we identify conditions for solvability in polynomial time and propose efficient approximation algorithms for general cases. We then introduce a bid-price control policy based on a novel maximal sequence principle. This policy accommodates nonlinearity in bid prices and, as a result, yields a more accurate approximation of the value function than a traditional bid-price control policy does. Finally, we combine a dynamic view of the maximal sequence with the static solution of a primal problem to propose a "re-solving a dynamic primal" policy that can achieve uniformly bounded revenue loss under mild assumptions. Numerical experiments using both synthetic and real data document the advantage of our proposed policies on resource-allocation efficiency. Managerial implications: The results of this study reveal connections between our problem and traditional network revenue management problems. Particularly, we demonstrate that by adaptively using our proposed methods, the impact of the assign-to-seat restriction becomes limited both in theory and practice. Funding: S. Liu's research is partly supported by the National Natural Science Foundation of China (NSFC) [Grant NSFC-72072117]. Z. Wang's research is partly supported by the NSFC [Grant NSFC-72150002]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.1188. [ABSTRACT FROM AUTHOR]

We present a gradient-based algorithm for solving a class of simulation optimization problems in which the objective function is the quantile of a simulation output random variable. In contrast with existing quantile (quantile derivative) estimation techniques, which aim to eliminate the estimator bias by gradually increasing the simulation sample size, our algorithm incorporates a novel recursive procedure that only requires a single simulation sample at each step to simultaneously obtain quantile and quantile derivative estimators that are asymptotically unbiased. We show that these estimators, when coupled with the standard gradient descent method, lead to a multitime-scale stochastic approximation type of algorithm that converges to an optimal quantile value with probability one. In our numerical experiments, the proposed algorithm is applied to optimal investment portfolio problems, resulting in new solutions that complement those obtained under the classical Markowitz mean-variance framework. History: Accepted by Alice E. Smith, Editor-in-Chief; Bruno Tuffin, Area Editor for Simulation. Funding: The work of Y. Peng was supported in part by the National Natural Science Foundation of China (NSFC) [Grants 72022001, 92146003, and 71901003], and by the Key Research and Development Programof Beijing Municipal Science and Technology Commission. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1214. [ABSTRACT FROM AUTHOR]