A robust approach for scheduling in hospitals using multiple objectives

Scheduling in hospitals is a challenging task and stochastic influences have a major impact on the final schedule. Therefore, uncertainties of treatment durations and of emergency arrivals have to be taken into account explicitly. In order to avoid re-scheduling we integrate information on stochastic parameters into a scenario-based mixed-integer optimization model. Besides, we focus on different stakeholders’ objectives that are simultaneously considered within a multi-criteria optimization model. Individually optimal solutions are likely to differ and the overall aim is to identify a good and acceptable compromise solution. The presented approach is based on fuzzy sets and merges the interests of several stakeholders. Different schedules are calculated and later on evaluated with randomly generated scenarios for surgery times and emergencies. The resulting objective function values are close to the individually optimal solutions. Finally, the schedules lead to a high rate of utilization and a low amount of overtime.     

Bias phenomenon and compensation in multiple target tracking algorithms

Bias phenomenon in multiple target tracking has been observed for a long time. This paper is devoted to a study of the bias resulting from the miscorrelation in data association. One result of this paper is a necessary condition for miscorrelation to cause bias. Relying on the necessary condition and a model for data association process, techniques are developed to give general directions for where and how to compensate the bias related to miscorrelation in general tracking algorithms. Case studies on the bias phenomenon in two tracking algorithms, i.e., global nearest neighborhood (GNN) and joint probabilistic data association (JPDA), are launched as a practice of the ideas and results presented in this paper. The outcome of the examples illustrates and strongly supports our results. A discussion of several statistical issues is given in the end of this paper, in which the behavior for the bias in GNN and JPDA is studied.     

A correlative classifiers approach based on particle filter and sample set for tracking occluded target

Target tracking is one of the most important issues in computer vision and has been applied in many fields of science, engineering and industry. Because of the occlusion during tracking, typical approaches with single classifier learn much of occluding background information which results in the decrease of tracking performance, and eventually lead to the failure of the tracking algorithm. This paper presents a new correlative classifiers approach to address the above problem. Our idea is to derive a group of correlative classifiers based on sample set method. Then we propose strategy to establish the classifiers and to query the suitable classifiers for the next frame tracking. In order to deal with nonlinear problem, particle filter is adopted and integrated with sample set method. For choosing the target from candidate particles, we define a similarity measurement between particles and sample set. The proposed sample set method includes the following steps. First, we cropped positive samples set around the target and negative samples set far away from the target. Second, we extracted average Haar-like feature from these samples and calculate their statistical characteristic which represents the target model. Third, we define the similarity measurement based on the statistical characteristic of these two sets to judge the similarity between candidate particles and target model. Finally, we choose the largest similarity score particle as the target in the new frame. A number of experiments show the robustness and efficiency of the proposed approach when compared with other state-of-the-art trackers.     

An optimum approach in target tracking with bearing measurements

We consider a two-state tracking problem with bearing measurements on a stationary target. The observer's speed is assumed constant and an optimum course is sought. An integral representing a lower bound for the Fisher information matrix is derived, and optimality of the observer's course is defined as maximizing the lower bound. The problem is solved within the framework of optimal control theory. A sufficiency theorem involving the Hamilton-Jacobi equation is invoked to determine the optimal course. It is shown that the optimal course is such that the observer proceeds at a fixed deviated angle and the optimal trajectory is a deviated pursuit curve.This work was supported by the Naval Underwater Systems Center, Newport, Rhode Island, under Contract No. N00140-85-VQ98. The author would like to thank V. Aidella and V. Bailey for discussions.     

BerkMin: A fast and robust Sat-solver

We describe a SAT-solver, BerkMin, that inherits such features of GRASP, SATO, and Chaff as clause recording, fast BCP, restarts, and conflict clause “aging”. At the same time BerkMin introduces a new decision-making procedure and a new method of clause database management. We experimentally compare BerkMin with Chaff, the leader among resolution-based SAT-solvers. Experiments show that our program is more robust than Chaff being able to solve more instances than Chaff in a reasonable amount of time.     

A fast algorithm for robust regression with penalised trimmed squares

The presence of groups containing high leverage outliers makes linear regression a difficult problem due to the masking effect. The available high breakdown estimators based on Least Trimmed Squares often do not succeed in detecting masked high leverage outliers in finite samples. An alternative to the LTS estimator, called Penalised Trimmed Squares (PTS) estimator, was introduced by the authors in Zioutas and Avramidis (2005) Acta Math Appl Sin 21:323–334, Zioutas et al. (2007) REVSTAT 5:115–136 and it appears to be less sensitive to the masking problem. This estimator is defined by a Quadratic Mixed Integer Programming (QMIP) problem, where in the objective function a penalty cost for each observation is included which serves as an upper bound on the residual error for any feasible regression line. Since the PTS does not require presetting the number of outliers to delete from the data set, it has better efficiency with respect to other estimators. However, due to the high computational complexity of the resulting QMIP problem, exact solutions for moderately large regression problems is infeasible. In this paper we further establish the theoretical properties of the PTS estimator, such as high breakdown and efficiency, and propose an approximate algorithm called Fast-PTS to compute the PTS estimator for large data sets efficiently. Extensive computational experiments on sets of benchmark instances with varying degrees of outlier contamination, indicate that the proposed algorithm performs well in identifying groups of high leverage outliers in reasonable computational time.     

A multi-space data association algorithm for target tracking systems

In this paper, a multi-space data association algorithm based on the wavelet transform is proposed. In addition to carrying out the traditional hard logic data association in measurement space, the new algorithm updates the state of the target in the pattern space. Such a function significantly reduces the complicated environment misassociation effects on the data association. Simulation results show that the performance of the multi-spaced data association is much better than the existing data association algorithms in complicated clutter environments, such as the nearest-neighbor standard filter (NNSF), the probabilistic data association (PDA) and the joint probabilistic data association (JPDA). The computation of the multiple-space data association is much less than the aforementioned other existing data associations, and this new data association does not need any priori information of the environment. In complicated clutter environments, compared with the other data association, the new data association proposed in this paper is very robust, reliable and stable.     

A surrogate based multi-fidelity approach for robust design optimization

Robust design optimization (RDO) is a field of optimization in which certain measure of robustness is sought against uncertainty. Unlike conventional optimization, the number of function evaluations in RDO is significantly more which often renders it time consuming and computationally cumbersome. This paper presents two new methods for solving the RDO problems. The proposed methods couple differential evolution algorithm (DEA) with polynomial correlated function expansion (PCFE). While DEA is utilized for solving the optimization problem, PCFE is utilized for calculating the statistical moments. Three examples have been presented to illustrate the performance of the proposed approaches. Results obtained indicate that the proposed approaches provide accurate and computationally efficient estimates of the RDO problems. Moreover, the proposed approaches outperforms popular RDO techniques such as tensor product quadrature, Taylor’s series and Kriging. Finally, the proposed approaches have been utilized for robust hydroelectric flow optimization, demonstrating its capability in solving large scale problems.     

A robust multigrid approach for variational image registration models

Variational registration models are non-rigid and deformable imaging techniques for accurate registration of two images. As with other models for inverse problems using the Tikhonov regularization, they must have a suitably chosen regularization term as well as a data fitting term. One distinct feature of registration models is that their fitting term is always highly nonlinear and this nonlinearity restricts the class of numerical methods that are applicable. This paper first reviews the current state-of-the-art numerical methods for such models and observes that the nonlinear fitting term is mostly ‘avoided’ in developing fast multigrid methods. It then proposes a unified approach for designing fixed point type smoothers for multigrid methods. The diffusion registration model (second-order equations) and a curvature model (fourth-order equations) are used to illustrate our robust methodology. Analysis of the proposed smoothers and comparisons to other methods are given. As expected of a multigrid method, being many orders of magnitude faster than the unilevel gradient descent approach, the proposed numerical approach delivers fast and accurate results for a range of synthetic and real test images.     

A robust multigrid approach for variational image registration models

Variational registration models are non-rigid and deformable imaging techniques for accurate registration of two images. As with other models for inverse problems using the Tikhonov regularization, they must have a suitably chosen regularization term as well as a data fitting term. One distinct feature of registration models is that their fitting term is always highly nonlinear and this nonlinearity restricts the class of numerical methods that are applicable. This paper first reviews the current state-of-the-art numerical methods for such models and observes that the nonlinear fitting term is mostly ‘avoided’ in developing fast multigrid methods. It then proposes a unified approach for designing fixed point type smoothers for multigrid methods. The diffusion registration model (second-order equations) and a curvature model (fourth-order equations) are used to illustrate our robust methodology. Analysis of the proposed smoothers and comparisons to other methods are given. As expected of a multigrid method, being many orders of magnitude faster than the unilevel gradient descent approach, the proposed numerical approach delivers fast and accurate results for a range of synthetic and real test images.     

A homogenization approach for the motion of motor proteins

We consider the asymptotic behavior of an evolving weakly coupled Fokker–Planck system of two equations set in a periodic environment. The magnitudes of the diffusion and the coupling are, respectively, proportional and inversely proportional to the size of the period. We prove that, as the period tends to zero, the solutions of the system either propagate (concentrate) with a fixed constant velocity (determined by the data) or do not move at all. The system arises in the modeling of motor proteins which can take two different states. Our result implies that, in the limit, the molecules either move along a filament with a fixed direction and constant speed or remain immobile.     

A new infinitesimal approach to robust estimation

Summary The infinitesimal robustness of the asymptotic variance of location M-estimators is investigated by means of the change-of-variance curve (CVC), which bears some resemblance to the influence curve (IC). It is proved that this CVC leads to a more stringent robustness property than the IC and that the Huber estimators are still optimal in this new sense.     

A unified approach for constructing fast two-step Newton-like methods

We introduce some new very general ways of constructing fast two-step Newton-like methods to approximate a locally unique solution of a nonlinear operator equation in a Banach space setting. We provide existence-uniqueness theorems as well as an error analysis for the iterations involved using Newton-Kantorovich-type hypotheses and the majorant method. Our results depend on the existence of a Lipschitz function defined on a closed ball centered at a certain point and of a fixed radius and with values into the positive real axis. Special choices of this function lead to favorable comparisons with results already in the literature. Some applications to the solution of nonlinear integral equations appearing in radiative transfer as well as to the solution of integral equations of Uryson-type are also provided.     

A fast and robust unconstrained optimization method requiring minimum storage

This paper describes a new unconstrained optimisation procedure employing conjugate directions and requiring only threen-dimensional vectors. The method has been tested for computational efficiency and stability on a large set of test functions and compared with numerical data of other major methods. Results show that the method possesses strong superiority over other existing conjugate gradient methods on all problems and can out-perform or is at least as efficient as quasi-Newton methods on many tested problems.     

Optimal searching for a Helix target motion

This paper discusses a search problem for a Helix target motion in which any information of the target position is not available to the searchers. There exist three searchers start searching for the target from the origin. The purpose of this paper is to formulate a search model and finds the conditions under which the expected value of the first meeting time between one of the searchers and the target is finite. Also, the existence of the optimal search plan that minimizes the expected value of the first meeting time is shown. Furthermore,this optimal search plan is found. The effectiveness of this method is illustrated by using an example with numerical results.     

A hybrid optimization approach to index tracking

Index tracking consists in reproducing the performance of a stock-market index by investing in a subset of the stocks included in the index. A hybrid strategy that combines an evolutionary algorithm with quadratic programming is designed to solve this NP-hard problem: Given a subset of assets, quadratic programming yields the optimal tracking portfolio that invests only in the selected assets. The combinatorial problem of identifying the appropriate assets is solved by a genetic algorithm that uses the output of the quadratic optimization as fitness function. This hybrid approach allows the identification of quasi-optimal tracking portfolios at a reduced computational cost.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

A dynamic programming approach to adjustable robust optimization

In this paper we consider the adjustable robust approach to multistage optimization, for which we derive dynamic programming equations. We also discuss this from the point of view of risk averse stochastic programming. We consider as an example a robust formulation of the classical inventory model and show that, like for the risk neutral case, a basestock policy is optimal.     

Computational complexity analysis for multiple hypothesis tracking

This paper presents a detailed analysis of computational complexity of Multiple Hypothesis Tracking (MHT). The result proves that the computational complexity of MHT is dominated by the number of hypotheses. Effects of track merging and pruning are analyzed also. Certain common design parameters of MHT, such as thresholds, are also discussed in detail. The results of this paper provide a guidance for selecting parameters in an MHT tracker and predicting its performance.Among the design parameters discussed in this paper, track merging appears to be the most important way for controlling the computational complexity of MHT. Thresholds for track deletion are also critical. If not all measurements are allowed to initiate new tracks, the number of new tracks can also be used for tuning the computation requirement of MHT, but it is not as significant as thresholds.