Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC

Under high load, the automated dispatching of service vehicles for the German Automobile As- sociation (ADAC) must reoptimize a dispatch for 100–150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization mod- els. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP_dummy can keep up with ZIBDIP.     

Competitive strategies for an online generalized assignment problem with a service consecution constraint

This work studies a variant of the online generalized assignment problem, where there are m ? 2 heterogeneous servers to process n requests which arrive one by one over time. Each request must either be assigned to one of the servers or be rejected upon its arrival, before knowing any information of future requests. There is a corresponding weight (or revenue) for assigning each request to a server, and the objective is to maximize the total weights obtained from all the requests. We study the above problem with a service consecution constraint, such that at any time each server is only allowed to process up to d consecutive requests.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.     

Inventory models for perishable items with inventory level dependent demand rate

This paper presents inventory models for perishable items with inventory level dependent demand rate. The models with and without backlogging are studied. In the backlogging model, it is assumed that the backlogging rate is dependent on the waiting time and the amount of products already backlogged simultaneously. Two cases that holding inventory is profitable or not are studied, respectively. The smallest shelf space to ensure shortage not occur when holding inventory is not profitable is obtained. In the model without backlogging, it is assumed that the remaining stock at the end of the inventory cycle is disposed of with salvage value. The necessary and sufficient conditions for the existence and uniqueness of the optimal solution of these models are investigated. At last, some numerical examples are presented to illustrate the effectiveness of the proposed model. The model in this paper is generalization of present ones. In particularly, the model is reduced to Padmanabhan and Vrat’s when δ₁ = 0, and Dye and Ouyang’s when δ₂ = 0. If S = s and δ₂ = 0, it is Chang, Goyal and Teng’s model.     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

Nonsmooth minimax programming under locally Lipschitz (Φ, ρ)-invexity

Minimax programming problems involving locally Lipschitz (Φ, ρ)-invex functions are considered. The parametric and non-parametric necessary and sufficient optimality conditions for a class of nonsmooth minimax programming problems are obtained under nondifferentiable (Φ, ρ)-invexity assumption imposed on objective and constraint functions. When the sufficient conditions are utilized, parametric and non-parametric dual problems in the sense of Mond-Weir and Wolfe may be formulated and duality results are derived for the considered nonsmooth minimax programming problem. With the reference to the said functions we extend some results of optimality and duality for a larger class of nonsmooth minimax programming problems.     

Using different response-time requirements to smooth time-varying demand for service

Many service systems have demand that varies significantly by time of day, making it costly to provide sufficient capacity to be able to respond very quickly to each service request. Fortunately, however, different service requests often have very different response-time requirements. Some service requests may need immediate response, while others can tolerate substantial delays. Thus it is often possible to smooth demand by partitioning the service requests into separate priority classes according to their response-time requirements. Classes with more stringent performance requirements are given higher priority for service. Lower capacity may be required if lower-priority-class demand can be met during off-peak periods. We show how the priority classes can be defined and the resulting required fixed capacity can be determined, directly accounting for the time-dependent behavior. For this purpose, we exploit relatively simple analytical models, in particular, M_t/G/∞ and deterministic offered-load models. The analysis also provides an estimate of the capacity savings that can be obtained from partitioning time-varying demand into priority classes.     

Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models

We develop and experimentally compare policies for the control of a system of k elevators with capacity one in a transport environment with ? floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each request and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average squared waiting times can be implemented to run in real-time (1 s) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used policies like multi-server variants of greedy and nearest neighbor.     

Robustness of optimal designs for correlated random variables

Suppose that Y = (Y_i) is a normal random vector with mean Xb and covariance σ²I_n, where b is a p-dimensional vector (b_j), X = (X_ij) is an n × p matrix with X_ij ∈ {−1, 1}; this corresponds to a factorial design with −1, 1 representing low or high level respectively, or corresponds to a weighing design with −1, 1 representing an object j with weight b_j placed on the left and right of a chemical balance respectively. E-optimal designs Z are chosen that are robust in the sense that they remain E-optimal when the covariance of Y_i, Y_i′ is ρ > 0 for i ≠ i′. Within a smaller class of designs similar results are obtained with respect to a general class of optimality criteria which include the A- and D-criteria.     

Graphs for small multiprocessor interconnection networks

Let D be the diameter of a graph G and let λ₁ be the largest eigenvalue of its (0, 1)-adjacency matrix. We give a proof of the fact that there are exactly 69 non-trivial connected graphs with (D + 1)λ₁ ? 9. These 69 graphs all have up to 10 vertices and were recently found to be suitable models for small multiprocessor interconnection networks. We also examine the suitability of integral graphs to model multiprocessor interconnection networks, especially with respect to the load balancing problem. In addition, we classify integral graphs with small values of (D + 1)λ₁ in connection with the load balancing problem for multiprocessor systems.     

Error analysis of large-time approximations for decay chains

Consider a radioactive decay chain X₁ → ? → X_n→ and let N_n(t) be the amount of X_n at time t. This paper establishes error bounds for large-time approximations to N_n(t) that include and generalize the transient equilibrium approximations and other known approximations. The error bounds allow one to find the range of t for which these approximations can be used with a given degree of precision.     

Analysis of a queueing system with a general service scheduling function,with applications to telecommunication network traffic control

In this paper we analyze a queueing system with a general service scheduling function. There are two types of customer with different service requirements. The service order for customers of each type is determined by the service scheduling function α_k(i, j) where α_k(i, j) is the probability for type-k customer to be selected when there are i type-1 and j type-2 customers. This model is motivated by traffic control to support traffic streams with different traffic characteristics in telecommunication networks (in particular, ATM networks). By using the embedded Markov chain and supplementary variable methods, we obtain the queue-length distribution as well as the loss probability and the mean waiting time for each type of customer. We also apply our model to traffic control to support diverse traffics in telecommunication networks. Finally, the performance measures of the existing diverse scheduling policies are compared. We expect to help the system designers select appropriate scheduling policy for their systems.     

New types of 3-D systems of quadratic differential equations with chaotic dynamics based on Ricker discrete population model

The wide class of 3-D autonomous systems of quadratic differential equations, in each of which either there is a couple of coexisting limit cycles or there is a couple of coexisting chaotic attractors, is found. In the second case the couple consists of either Lorentz-type attractor and another attractor of a new type or two Lorentz-type attractors. It is shown that the chaotic behavior of any system of the indicated class can be described by the Ricker discrete population model: z_i+1 = z_i exp(r − z_i), r > 0, z_i > 0, i = 0, 1, … . The values of parameters, at which in the 3-D system appears either the couple of limit cycles or the couple of chaotic attractors, or only one limit cycle, or only one sphere-shaped chaotic attractor, are indicated. Examples are given.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

Some trace formulae involving the split sequences of a Leonard pair

Let K denote a field, and let V denote a vector space over K with finite positive dimension. We consider a pair of linear transformations A : V → V and A^∗ : V → V that satisfy (i) and (ii) below:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

We call such a pair a Leonard pair on V. Let diag(θ₀, θ₁, … , θ_d) denote the diagonal matrix referred to in (ii) above and let denote the diagonal matrix referred to in (i) above. It is known that there exists a basis u₀, u₁, … , u_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Au_i = θ_iu_i + u_i+1 (0 ? i ? d − 1), Au_d = θ_du_d, , . The sequence ?₁, ?₂, … , ?_d is called the first split sequence of the Leonard pair. It is known that there exists a basis v₀, v₁, … , v_d for V and there exist scalars ?₁, ?₂, … , ?_d in K such that Av_i = θ_d−iv_i + v_i+1 (0 ? i ? d − 1),Av_d = θ₀v_d, , . The sequence ?₁, ?₂, … , ?_d is called the second split sequence of the Leonard pair. We display some attractive formulae for the first and second split sequence that involve the trace function.     

Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan

This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u, v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u, v] (i.e. w ? v − u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.