Search

For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove NP -hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268. [ABSTRACT FROM AUTHOR]

This paper develops a cost-effective sequential route recommender system to provide real-time routing recommendations for vacant taxis searching for the next passenger. We propose a prediction-and-optimization framework to recommend the searching route that maximizes the expected profit of the next successful passenger pickup based on the dynamic taxi demand-supply distribution. Specifically, this system features a deep learning-based predictor that dynamically predicts the passenger pickup probability on a road segment and a recursive searching algorithm that recommends the optimal searching route. The predictor integrates a graph convolution network (GCN) to capture the spatial distribution and a long short-term memory (LSTM) to capture the temporal dynamics of taxi demand and supply. The GCN-LSTM model can accurately predict the pickup probability on a road segment with the consideration of potential taxi oversupply. Then, the dynamic distribution of pickup probability is fed into the route optimization algorithm to recommend the optimal searching routes sequentially as route inquiries emerge in the system. The recursion tree-based route optimization algorithm can significantly reduce the computational time and provide the optimal routes within seconds for real-time implementation. Finally, extensive experiments using Beijing Taxi GPS data demonstrate the effectiveness and efficiency of the proposed recommender system. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: This work was partially supported by the Hong Kong Research Grants Council [Grants CityU 21500220, CityU 11504322] and the National Natural Science Foundation of China [Grant 72201222]. 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.2021.0112) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0112). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The ℓ 0 trend filtering ( ℓ 0 -TF) is a new effective tool for nonparametric regression with the power of automatic knot detection in function values or derivatives. It overcomes the drawback of ℓ 1 -TF that is known to have bias issues. To solve the ℓ 0 -TF problem, we propose an alternating minimization induced active set (AMIAS) search method based on the necessary optimality conditions derived from an augmented Lagrangian framework. The proposed method takes full advantage of the primal and dual variables with complementary supports, and decouples the high-dimensional problem into two subsystems on the active and inactive sets, respectively. A sequential AMIAS algorithm with warm start initialization is developed for efficient determination of the cardinality parameter, along with the output of solution paths. Theoretically, the oracle estimator of ℓ 0 -TF is justified to behave like regression splines under the continuous time setting with mild conditions. Our numerical experiments include simulation studies for comparing ℓ 0 -TF to ℓ 1 -TF and free-knot splines on several synthetic examples, and a real data application of time series segmentation on Hong Kong PM2.5 indexes. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms – Continuous. Funding: This work was supported in part by Hong Kong General Research Fund [No. 17306519]. C. Wen's research is partially supported by National Science Foundation of China [12171449] and Fundamental Research Funds for the Central Universities [WK3470000027, YD2040002019]. X. Wang's research is partially supported by National Natural Science Foundation of China [Grants 72171216, 12231017, 71921001, and 71991474], and the National Key R&D Program of China [No. 2022YFA1003803]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0313. 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.0313) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0313). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We extend the notion of globalized robustness to consider distributional information beyond the support of the ambiguous probability distribution. We propose the globalized distributionally robust counterpart that disallows any (respectively, allows limited) constraint violation for distributions residing (respectively, not residing) in the ambiguity set. By varying its inputs, our proposal recovers several existing perceptions of parameter uncertainty. Focusing on the type 1 Wasserstein distance, we show that the globalized distributionally robust counterpart has an insightful interpretation in terms of shadow price of globalized robustness, and it can be seamlessly integrated with many popular optimization models under uncertainty without incurring any extra computational cost. Such computational attractiveness also holds for other ambiguity sets, including the ones based on probability metric, optimal transport, ϕ-divergences, or moment conditions, as well as the event-wise ambiguity set. Numerical studies on an adaptive network lot-sizing problem demonstrate the modeling flexibility of our proposal and its emphases on globalized robustness to constraint violation. History: Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: Z. Chen was supported by [General Research Fund Grant 9043424, NSFC/RGC Joint Research Scheme N_CityU105/21] from the Hong Kong Research Grants Council. S. Wang was supported by the National Natural Science Foundation of China [Grants 71922020, 72171221, and 71988101, entitled "Econometric Modeling and Economic Policy Studies"] and the Fundamental Research Funds for the Central Universities [Grant UCAS-E2ET0808X2]. 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.0274) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0274). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [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]

We study adjustable distributionally robust optimization problems, where their ambiguity sets can potentially encompass an infinite number of expectation constraints. Although such ambiguity sets have great modeling flexibility in characterizing uncertain probability distributions, the corresponding adjustable problems remain computationally intractable and challenging. To overcome this issue, we propose a greedy improvement procedure that consists of solving, via the (extended) linear decision rule approximation, a sequence of tractable subproblems—each of which considers a relaxed and finitely constrained ambiguity set that can be iteratively tightened to the infinitely constrained one. Through three numerical studies of adjustable distributionally robust optimization models, we show that our approach can yield improved solutions in a systematic way for both two-stage and multistage problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Financial support by the Early Career Scheme from the Hong Kong Research Grants Council [Project No. CityU 21502820], the CityU Start-Up Grant [Project No. 9610481], the CityU Strategic Research Grant [Project No. 7005688], the National Natural Science Foundation of China [Project No. 72032005], and Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited [Project No. 9229076] is gratefully acknowledged. 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.2021.0181), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0181). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]