We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random sizes that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a big-M and a 0-1 bilinear formulation of this problem. We analyze the bilinear structure of the formulation and use the lifting techniques to identify cover, clique, and projection inequalities to strengthen the formulation. We show that in certain cases these inequalities are facet-defining for a bilinear knapsack constraint that arises in the reformulation. An extensive computational study is conducted for the operating room planning problem that minimizes the number of open operating rooms. The computational tests are performed using problems generated based on real data from a hospital. A lower-bound improvement heuristic is combined with the cuts proposed in this paper in a branch-and-cut framework. The computations illustrate that the techniques developed in this paper can significantly improve the performance of the branch-and-cut method. Problems with up to 1,000 scenarios are solved to optimality in less than an hour. A safe approximation based on conditional value at risk (CVaR) is also solved. The computations show that the CVaR approximation typically leaves a gap of one operating room (e.g., six instead of five) to satisfy the chance constraint. Summary of Contribution: This paper investigates a branch-and-cut algorithm for a chance-constrained bin packing problem with multiple bins. The chance-constrained bin packing provides a modeling framework for applied operations research problems, such as health care, scheduling, and so on. This paper studies alternative computational approaches to solve this problem. Moreover, this paper uses real data from a hospital operating room planning setting as an application to test the algorithmic ideas. This work, therefore, is at the intersection of computing and operations research. Several interesting ideas are developed and studied. These include a strengthened big-M reformulation, analysis of a bilinear reformulation, and identifying certain facet-defining inequalities for this formulation. This paper also gives a lower-bound generation heuristic for a model that minimizes the number of bins. Computational experiments for an operating room planning model that uses data from a hospital demonstrate the computational improvement and importance of the proposed approaches. The techniques proposed in this paper and computational experiments further enhance the interface of computing and operations research.

We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition (SLC) is satisfied. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation in iOptimize maintains global linear and polynomial time convergence properties, while achieving practical performance. It either successfully solves the problem, or concludes that the SLC is not satisfied. When compared with the mature software package MOSEK (barrier solver version 6.0.0.106), iOptimize solves convex quadratic programming problems, convex quadratically constrained quadratic programming problems, and general convex programming problems in fewer iterations. Moreover, several problems for which MOSEK fails are solved to optimality. We also find that iOptimize detects infeasibility more reliably than the general nonlinear solvers Ipopt (version 3.9.2) and Knitro (version 8.0).

This paper will focus on bed angle detection in hospital room automatically using the latest Kinect sensor. The developed system is an ideal application for nursing staff to monitoring the bed status for patient, especially under the situation that the patient is alone. The patient bed is reconstructed from point cloud data using polynomial plane fitting. The analysis to the detected bed angle could help the nursing staff to understand the potential developed hospital acquired infection (HAI) and the health situation of the patient, and acquire informative knowledge of the relation between bed angle and disease recovery to decide appropriate treatment strategy.

BACKGROUND AND OBJECTIVE: Electronic medical record (EMR) databases offer significant potential for developing clinical hypotheses and identifying disease risk associations by fitting statistical models that capture the relationship between a binary response variable and a set of predictor variables that represent clinical, phenotypical, and demographic data for the patient. However, EMR response data may be error prone for a variety of reasons. Performing a manual chart review to validate data accuracy is time consuming, which limits the number of chart reviews in a large database. The authors' objective is to develop a new design-of-experiments-based systematic chart validation and review (DSCVR) approach that is more powerful than the random validation sampling used in existing approaches. METHODS: The DSCVR approach judiciously and efficiently selects the cases to validate (i.e., validate whether the response values are correct for those cases) for maximum information content, based only on their predictor variable values. The final predictive model will be fit using only the validation sample, ignoring the remainder of the unvalidated and unreliable error-prone data. A Fisher information based D-optimality criterion is used, and an algorithm for optimizing it is developed. RESULTS: The authors' method is tested in a simulation comparison that is based on a sudden cardiac arrest case study with 23 041 patients' records. This DSCVR approach, using the Fisher information based D-optimality criterion, results in a fitted model with much better predictive performance, as measured by the receiver operating characteristic curve and the accuracy in predicting whether a patient will experience the event, than a model fitted using a random validation sample. CONCLUSIONS: The simulation comparisons demonstrate that this DSCVR approach can produce predictive models that are significantly better than those produced from random validation sampling, especially when the event rate is low.

We present and compare implementations of an affine interior-point algorithm for real-time collision detection on a GPGPU and an FPGA. This particular interior-point algorithm is distinguished from other collision detection methods by its ability to perform detection between pairs of objects undergoing fast rotational and translational movement. This enables inter-frame collision detection, i.e. collision that might occur during the transition from one frame to another. In our design for the FPGA, we implemented the algorithm both in single-precision floating point and 32-bit fixed point and analyzed the trade-off between resource usage, data accuracy/precision, and system efficiency. Then, we compare them to a floating point implementation on a GPGPU using CUDA. With an object resolution of 45 vertices (45 vertices representing each polyhedral object), our FPGA implementation processes 1562 frames/sec for floating point and 1350 frames/second for fixed point and offers an 11× speedup over the GPGPU implementation. With object resolutions greater than 242 vertices, our GPGPU implementation outperforms our FPGA implementations.

BACKGROUND: The data from DNA microarrays are increasingly being used in order to understand effects of different conditions, exposures or diseases on the modulation of the expression of various genes in a biological system. This knowledge is then further used in order to generate molecular mechanistic hypotheses for an organism when it is exposed to different conditions. Several different methods have been proposed to analyze these data under different distributional assumptions on gene expression. However, the empirical validation of these assumptions is lacking. RESULTS: Best fit hypotheses tests, moment-ratio diagrams and relationships between the different moments of the distribution of the gene expression was used to characterize the observed distributions. The data are obtained from the publicly available gene expression database, Gene Expression Omnibus (GEO) to characterize the empirical distributions of gene expressions obtained under varying experimental situations each of which providing relatively large number of samples for hypothesis testing. All data were obtained from either of two microarray platforms--the commercial Affymetrix mouse 430.2 platform and a non-commercial Rosetta/Merck one. The data from each platform were preprocessed in the same manner. CONCLUSIONS: The null hypotheses for goodness of fit for all considered univariate theoretical probability distributions (including the Normal distribution) are rejected for more than 50% of probe sets on the Affymetrix microarray platform at a 95% confidence level, suggesting that under the tested conditions a priori assumption of any of these distributions across all probe sets is not valid. The pattern of null hypotheses rejection was different for the data from Rosetta/Merck platform with only around 20% of the probe sets failing the logistic distribution goodness-of-fit test. We find that there are statistically significant (at 95% confidence level based on the F-test for the fitted linear model) relationships between the mean and the logarithm of the coefficient of variation of the distributions of the logarithm of gene expressions. An additional novel statistically significant quadratic relationship between the skewness and kurtosis is identified. Data from both microarray platforms fail to identify with any one of the chosen theoretical probability distributions from an analysis of the l-moment ratio diagram.

The interior-point algorithm is a powerful method for solving a linear program (LP). A variety of optimization problems can be formulated as LPs. Often times the limiting factor of deploying an algorithm to solve LPs in a high performance system is the run-time efficiency. In this paper, we present the FPGA implementation of an affine interior-point algorithm that is designed to solve LPs. Specifically, we present the application of this algorithm to solving the LP for the real-time collision detection. The most important feature that distinguishes this particular algorithm from other collision detection methods is its superior ability to perform detection between pairs of objects undergoing fast rotational and translational motions.

BACKGROUND: Proteins are the primary regulatory agents of transcription even though mRNA expression data alone, from systems like DNA microarrays, are widely used. In addition, the regulation process in genetic systems is inherently non-linear in nature, and most studies employ a time-course analysis of mRNA expression. These considerations should be taken into account in the development of methods for the inference of regulatory interactions in genetic networks. RESULTS: We use an S-system based model for the transcription and translation process. We propose an optimization-based regulatory network inference approach that uses time-varying data from DNA microarray analysis. Currently, this seems to be the only model-based method that can be used for the analysis of time-course "relative" expressions (expression ratios). We perform an analysis of the dynamic behavior of the system when the number of experimental samples available is varied, when there are different levels of noise in the data and when there are genes that are not considered by the experimenter. Our studies show that the principal factor affecting the ability of a method to infer interactions correctly is the similarity in the time profiles of some or all the genes. The less similar the profiles are to each other the easier it is to infer the interactions. We propose a heuristic method for resolving networks and show that it displays reasonable performance on a synthetic network. Finally, we validate our approach using real experimental data for a chosen subset of genes involved in the sporulation cascade of Bacillus anthracis. We show that the method captures most of the important known interactions between the chosen genes. CONCLUSION: The performance of any inference method for regulatory interactions between genes depends on the noise in the data, the existence of unknown genes affecting the network genes, and the similarity in the time profiles of some or all genes. Though subject to these issues, the inference method proposed in this paper would be useful because of its ability to infer important interactions, the fact that it can be used with time-course DNA microarray data and because it is based on a non-linear model of the process that explicitly accounts for the regulatory role of proteins.

MOTIVATION: Identification of the regulatory structures in genetic networks and the formulation of mechanistic models in the form of wiring diagrams is one of the significant objectives of expression profiling using DNA microarray technologies and it requires the development and application of identification frameworks. RESULTS: We have developed a novel optimization framework for identifying regulation in a genetic network using the S-system modeling formalism. We show that balance equations on both mRNA and protein species led to a formulation suitable for analyzing DNA-microarray data whereby protein concentrations have been eliminated and only mRNA relative concentrations are retained. Using this formulation, we examined if it is possible to infer a set of possible genetic regulatory networks consistent with observed mRNA expression patterns. Two origins of changes in mRNA expression patterns were considered. One derives from changes in the biophysical properties of the system that alter the molecular-interaction kinetics and/or message stability. The second is due to gene knock-outs. We reduced the identification problem to an optimization problem (of the so-called mixed-integer non-linear programming class) and we developed an algorithmic procedure for solving this optimization problem. Using simulated data generated by our mathematical model, we show that our method can actually find the regulatory network from which the data were generated. We also show that the number of possible alternate genetic regulatory networks depends on the size of the dataset (i.e. number of experiments), but this dependence is different for each of the two types of problems considered, and that a unique solution requires fewer datasets than previously estimated in the literature. This is the first method that also allows the identification of every possible regulatory network that could explain the data, when the number of experiments does not allow identification of unique regulatory structure.

Linear programs that arise in two-stage stochastic programming offer a particularly difficult test of the robustness of interior-point methods. These LPs are typically very large, yet incorporate “dense columns”—corresponding to the first-stage variables—that rule out the standard approach of solving the so-called normal equations. We compare two alternative approaches by running tests on six groups of stochastic linear programs that have been used in previous studies. We find that the augmented system approach consistently requires an amount of work that is very nearly linear in the number of scenarios, whereas the column-splitting approach requires a less predictable amount of work that grows worse than quadratically in some cases. We conclude by explaining how the differences between the two approaches can be viewed as a consequence of the way in which myopic elimination strategies deal with the block-structured matrices involved. Our analysis also leads to a useful comparison of the augmented system approach with the Schur complement approach considered in other recent research. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The conjugate gradient method has been proposed for solving system of linear equations arising at each iteration of interior point methods. This paper studies several problems associated with developing such implementations. This includes development of a termination criteria, computation of an effective preconditioner, and the lack of positive definiteness of the matrix. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.