A flexible optimisation model for the railway crew scheduling problem

Addressing the Crew Scheduling Problem (CSP) in transportation systems can be too complex to capture all details. The designed models usually ignore or simplify features which are difficult to formulate. This paper proposes an alternative formulation using a Mixed Integer Programming (MIP) approach to the problem. The optimisation model integrates the two phases of pairing generation and pairing optimisation by simultaneously sequencing trips into feasible duties and minimising total elapsed time of any duty. Crew scheduling constraints in which the crew have to return to their home depot at the end of the shift are included in the model. The flexibility of this model comes in the inclusion of the time interval of relief opportunities, allowing the crew to be relieved during a finite time interval. This will enhance the robustness of the schedule and provide a better representation of real-world conditions.

Two dynamic discrete choice estimation problems and simulation method solutions

This paper considers two problems that frequently arise in dynamic discrete choice problems but have not received much attention with regard to simulation methods. The first problem is how to simulate unbiased simulators of probabilities conditional on past history. The second is simulating a discrete transition probability model when the underlying dependent variable is really continuous. Both methods work well relative to reasonable alternatives in the application discussed. However, in both cases, for this application, simpler methods also provide reasonably good results.

Development of a log-quadratic model to describe microbial inactivation, illustrated by thermal inactivation of Clostridium botulinum

In the commercial food industry, demonstration of microbiological safety and thermal process equivalence often involves a mathematical framework that assumes log-linear inactivation kinetics and invokes concepts of decimal reduction time (DT), z values, and accumulated lethality. However, many microbes, particularly spores, exhibit inactivation kinetics that are not log linear. This has led to alternative modeling approaches, such as the biphasic and Weibull models, that relax strong log-linear assumptions. Using a statistical framework, we developed a novel log-quadratic model, which approximates the biphasic and Weibull models and provides additional physiological interpretability. As a statistical linear model, the log-quadratic model is relatively simple to fit and straightforwardly provides confidence intervals for its fitted values. It allows a DT-like value to be derived, even from data that exhibit obvious "tailing." We also showed how existing models of non-log-linear microbial inactivation, such as the Weibull model, can fit into a statistical linear model framework that dramatically simplifies their solution. We applied the log-quadratic model to thermal inactivation data for the spore-forming bacterium Clostridium botulinum and evaluated its merits compared with those of popular previously described approaches. The log-quadratic model was used as the basis of a secondary model that can capture the dependence of microbial inactivation kinetics on temperature. This model, in turn, was linked to models of spore inactivation of Sapru et al. and Rodriguez et al. that posit different physiological states for spores within a population. We believe that the log-quadratic model provides a useful framework in which to test vitalistic and mechanistic hypotheses of inactivation by thermal and other processes. Copyright © 2009, American Society for Microbiology. All Rights Reserved.

Log delta analysis: Interpretable differencing of Business process event logs

This paper addresses the problem of identifying and explaining behavioral differences between two business process event logs. The paper presents a method that, given two event logs, returns a set of statements in natural language capturing behavior that is present or frequent in one log, while absent or infrequent in the other. This log delta analysis method allows users to diagnose differences between normal and deviant executions of a process or between two versions or variants of a process. The method relies on a novel approach to losslessly encode an event log as an event structure, combined with a frequency-enhanced technique for differencing pairs of event structures. A validation of the proposed method shows that it accurately diagnoses typical change patterns and can explain differences between normal and deviant cases in a real-life log, more compactly and precisely than previously proposed methods.

Discrete families of Saffman–Taylor fingers with exotic shapes

The mathematical problem of determining the shape of a steadily propagating Saffman–Taylor finger in a rectangular Hele-Shaw cell is known to have a countably infinite number of solutions for each fixed surface tension value. For sufficiently large surface tension values, we find that fingers on higher solution branches are non-convex. The tips of the fingers have increasingly exotic shapes as the branch number increases.

Palliative care problem severity score: Reliability and acceptability in a national study

Background The Palliative Care Problem Severity Score is a clinician-rated tool to assess problem severity in four palliative care domains (pain, other symptoms, psychological/spiritual, family/carer problems) using a 4-point categorical scale (absent, mild, moderate, severe). Aim To test the reliability and acceptability of the Palliative Care Problem Severity Score. Design: Multi-centre, cross-sectional study involving pairs of clinicians independently rating problem severity using the tool. Setting/participants Clinicians from 10 Australian palliative care services: 9 inpatient units and 1 mixed inpatient/community-based service. Results A total of 102 clinicians participated, with almost 600 paired assessments completed for each domain, involving 420 patients. A total of 91% of paired assessments were undertaken within 2 h. Strength of agreement for three of the four domains was moderate: pain (Kappa = 0.42, 95% confidence interval = 0.36 to 0.49); psychological/spiritual (Kappa = 0.48, 95% confidence interval = 0.42 to 0.54); family/carer (Kappa = 0.45, 95% confidence interval = 0.40 to 0.52). Strength of agreement for the remaining domain (other symptoms) was fair (Kappa = 0.38, 95% confidence interval = 0.32 to 0.45). Conclusion The Palliative Care Problem Severity Score is an acceptable measure, with moderate reliability across three domains. Variability in inter-rater reliability across sites and participant feedback indicate that ongoing education is required to ensure that clinicians understand the purpose of the tool and each of its domains. Raters familiar with the patient they were assessing found it easier to assign problem severity, but this did not improve inter-rater reliability.

Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

A global convergence criterion for discrete-time multivariable adaptive systems

The paper deals with the basic problem of adjusting a matrix gain in a discrete-time linear multivariable system. The object is to obtain a global convergence criterion, i.e. conditions under which a specified error signal asymptotically approaches zero and other signals in the system remain bounded for arbitrary initial conditions and for any bounded input to the system. It is shown that for a class of up-dating algorithms for the adjustable gain matrix, global convergence is crucially dependent on a transfer matrix G(z) which has a simple block diagram interpretation. When w(z)G(z) is strictly discrete positive real for a scalar w(z) such that w-1(z) is strictly proper with poles and zeros within the unit circle, an augmented error scheme is suggested and is proved to result in global convergence. The solution avoids feeding back a quadratic term as recommended in other schemes for single-input single-output systems.

On the Cubicity of Interval Graphs

A k-cube (or ``a unit cube in k dimensions'') is defined as the Cartesian product R-1 x . . . x R-k where R-i (for 1 <= i <= k) is an interval of the form [a(i), a(i) + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i. e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Delta, cub(G) <= inverted right perpendicular log(2) Delta inverted left perpendicular + 4. This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to inverted right perpendicular log(2) Delta inverted left perpendicular.

Interval Data Classification under Partial Information: A Chance-Constraint Approach

This paper presents a Chance-constraint Programming approach for constructing maximum-margin classifiers which are robust to interval-valued uncertainty in training examples. The methodology ensures that uncertain examples are classified correctly with high probability by employing chance-constraints. The main contribution of the paper is to pose the resultant optimization problem as a Second Order Cone Program by using large deviation inequalities, due to Bernstein. Apart from support and mean of the uncertain examples these Bernstein based relaxations make no further assumptions on the underlying uncertainty. Classifiers built using the proposed approach are less conservative, yield higher margins and hence are expected to generalize better than existing methods. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle interval-valued uncertainty than state-of-the-art.

Assessing the effectiveness of High Intensity Interval Training (HIIT) for smoking cessation in women: HIIT to quit study protocol

Background: Smoking and physical inactivity are major risk factors for heart disease. Linking strategies that promote improvements in fitness and assist quitting smoking has potential to address both these risk factors simultaneously. The objective of this study is to compare the effects of two exercise interventions (high intensity interval training (HIIT) and lifestyle physical activity) on smoking cessation in female smokers. Method/design: This study will use a randomised controlled trial design. Participants: Women aged 18–55 years who smoke ≥ 5 cigarettes/day, and want to quit smoking. Intervention: all participants will receive usual care for quitting smoking. Group 1 - will complete two gym-based supervised HIIT sessions/week and one home-based HIIT session/week. At each training session participants will be asked to complete four 4-min (4 × 4 min) intervals at approximately 90 % of maximum heart rate interspersed with 3- min recovery periods. Group 2 - participants will receive a resource pack and pedometer, and will be asked to use the 10,000 steps log book to record steps and other physical activities. The aim will be to increase daily steps to 10,000 steps/day. Analysis will be intention to treat and measures will include smoking cessation, withdrawal and cravings, fitness, physical activity, and well-being. Discussion: The study builds on previous research suggesting that exercise intensity may influence the efficacy of exercise as a smoking cessation intervention. The hypothesis is that HIIT will improve fitness and assist women to quit smoking.

New light on the optical equivalence theorem and a new type of discrete diagonal coherent state representation

In many instances we find it advantageous to display a quantum optical density matrix as a generalized statistical ensemble of coherent wave fields. The weight functions involved in these constructions turn out to belong to a family of distributions, not always smooth functions. In this paper we investigate this question anew and show how it is related to the problem of expanding an arbitrary state in terms of an overcomplete subfamily of the overcomplete set of coherent states. This provides a relatively transparent derivation of the optical equivalence theorem. An interesting by-product is the discovery of a new class of discrete diagonal representations.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

A Joint Source-Channel Coding Scheme for Transmission of Correlated Discrete Sources over a Gaussian Multiple Access Channel

We consider the problem of transmission of correlated discrete alphabet sources over a Gaussian Multiple Access Channel (GMAC). A distributed bit-to-Gaussian mapping is proposed which yields jointly Gaussian codewords. This can guarantee lossless transmission or lossy transmission with given distortions, if possible. The technique can be extended to the system with side information at the encoders and decoder.

Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.