The hidden Markov model (HMM) provides a natural framework for modeling the dynamic evolution of latent diseases. The unknown probability matrices of HMMs can be learned through the well-known Baum–Welch algorithm, a special case of the expectation-maximization algorithm. In many disease models, the probability matrices possess nontrivial properties that may be represented through a set of linear constraints. In these cases, the traditional Baum–Welch algorithm is no longer applicable because the maximization step cannot be solved by an explicit formula. In this paper, we propose a novel approach to efficiently solve the maximization step problem under linear constraints by providing a Lagrangian dual reformulation that we solve by an accelerated gradient method. The performance of this approach critically depends on devising a fast method to compute the gradient in each iteration. For this purpose, we employ dual decomposition and derive Karush–Kuhn–Tucker conditions to reduce our problem into a set of single variable equations, solved using a simple bisection method. We apply this method to a case study on sports-related concussion and provide an extensive numerical study using simulation. We show that our approach is in orders of magnitude computationally faster and more accurate than other alternative approaches. Moreover, compared with other methods, our approach is far less sensitive with respect to increases in problem size. Overall, our contribution lies in the advancement of accurately and efficiently handling HMM parameter estimation under linear constraints, which comprises a wide range of applications in disease modeling and beyond. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This research was funded by [Grant R01DE028283] from the National Institute of Dental and Craniofacial Research, National Institutes of Health. G.-G. Garcia was also funded by the Georgia Clinical & Translational Science Alliance National Institutes of Health award [Grant UL1-TR002378]. 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.0342 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0342 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Nash equilibrium is arguably the most fundamental concept in game theory, which is used to analyze and predict the behavior of the players. In many games, there exist multiple equilibria, with different expected payoffs for the players, which in turn raises the question of equilibrium selection. In this paper, we study the [Formula: see text]-hard problem of identifying a socially optimal Nash equilibrium in two-player normal-form games (called bimatrix games), which may be represented by a mixed integer linear program (MILP). We characterize the properties of the equilibria and develop several classes of valid inequalities accordingly. We use these theoretical results to provide a decomposition-based reformulation of the MILP, which we solve by a branch-and-cut algorithm. Our extensive computational experiments demonstrate superiority of our approach over solving the MILP formulation through feeding it into a commercial solver or through the “traditional” Benders’ decomposition. Of note, our proposed approach can find provably optimal solutions for many instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms. Funding: This work was supported by the National Institute of Dental and Craniofacial Research [Grant R01DE028283]. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health. The funding agreements ensured the authors’ independence in designing the study, interpreting the data, writing, and publishing the report. 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.0072 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0072 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Solving a large batch of linear programs (LPs) with varying parameters is needed in stochastic programming and sensitivity analysis, among other modeling frameworks. Solving the LPs for all combinations of given parameter values, called the brute-force approach, can be computationally infeasible when the parameter space is high-dimensional and/or the underlying LP is computationally challenging. This paper introduces a computationally efficient approach for solving a large number of LPs that differ only in the right-hand side of the constraints ([Formula: see text] of [Formula: see text]). The computational approach builds on theoretical properties of the geometry of the space of critical regions, where a critical region is defined as the set of [Formula: see text]’s for which a basis is optimal. To formally support our computational approach we provide proofs of geometric properties of neighboring critical regions. We contribute to the existing theory of parametric programming by establishing additional results, providing deeper geometric understanding of critical regions. On the basis of the geometric properties of critical regions, we develop an algorithm that solves the LPs in batches by finding critical regions that contain multiple [Formula: see text]’s. Moreover, we suggest a data-driven version of our algorithm that uses the distribution (e.g., shape) of a sample of [Formula: see text]’s for which the LPs need to be solved. We empirically compared our approach and three other methods on various instances. The results show the efficiency of our approach in comparison with the other methods but also indicate some limitations of the algorithm. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0838 .

Health care delivery processes consist of complex activity sequences spanning organizational, spatial, and temporal boundaries. Care is human-directed so these processes can have wide variations in cost, quality, and outcome making systemic care process analysis, conformance testing, and improvement challenging. We designed and developed an interactive visual analytic process exploration and discovery tool and used it to explore clinical data from 5784 pediatric asthma emergency department patients.