60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
Refine
Document Type
- ZIB-Report (5)
- Article (1)
- Master's Thesis (1)
Language
- English (7)
Is part of the Bibliography
- no (7)
Keywords
Institute
- Mathematical Optimization (7) (remove)
The topic of this thesis is the examination of an optimization model
which stems from the clustering process of non-reversible markov processes.
We introduce the cycle clustering problem und formulate it as a mixed
integer program (MIP).
We prove that this problem is N P-hard and discuss polytopal aspects
such as facets and dimension. The focus of this thesis is the development of
solving methods for this clustering problem. We develop problem specific
primal heuristics, as well as separation methods and an approximation
algorithm. These techniques are implemented in practice as an application
for the MIP solver SCIP.
Our computational experiments show that these solving methods result
in an average speedup of ×4 compared to generic solvers and that our
application is able to solve more instances to optimality within the given
time limit of one hour.
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade.
We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models,
which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP
are technologies that should be considered along with CP for solving scheduling problems.
The paper deals with the workload and busy period for the M/GI/1
system under FCFS discipline, where the customers may become
impatient during their waiting for service with generally
distributed maximal waiting times and also during their service
with generally distributed maximal service times depending
on the time waited for service. This general impatience mechanism,
originally introduced by Kovalenko (1961) and considered
by Daley (1965), too, covers the special cases of impatience
on waiting times as well as impatience on sojourn times,
for which Boxma et al. (2010), (2011) gave new results
and outlined special cases recently. Our unified approach
bases on the vector process of workload and busy time.
Explicit representations for the LSTs of workload and
busy period are given in case of phase-type distributed
impatience.
We deal with an infinite-server system where the
service speed is governed by a stationary and ergodic
process with countably many states. Applying a random
time transformation such that the service speed
becomes one, the sojourn time of a class of virtual
requests with given required service time is equal
in distribution to an additive functional defined
via a stationary version of the time-changed process.
Thus bounds for the expectation of functions of additive
functionals yield bounds for the expectation
of functions of virtual sojourn times, in particular
bounds for fractional moments and the distribution
function. Interpreting the $GI(n)/GI(n)/\infty$ system or
equivalently the $GI(n)/GI$ system under state-dependent
processor sharing as an infinite-server system with
random states given by the number $n$ of requests
in the system provides results for sojourn times
of virtual requests. In case of $M(n)/GI(n)/\infty$,
the sojourn times of arriving and added requests are
equal in distribution to sojourn times of virtual
requests in modified systems, which yields many results
for the sojourn times of arriving and added requests.
In case of integer moments, the bounds generalize
earlier results for $M/GI(n)/\infty$. In particular,
the mean sojourn times of arriving and added requests
in $M(n)/GI(n)/\infty$ are proportional to the required
service time, generalizing Cohen's famous result
for $M/GI(n)/\infty$.