A note on node packing polytopes on hypergraphs

A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph.     

Routing and wavelength assignment in optical networks using bin packing based algorithms

This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been developed to solve it. We suggest very efficient, yet simple, heuristic algorithms for the RWA problem developed by applying classical bin packing algorithms. The heuristics were tested on a series of large random networks and compared with an efficient existing algorithm for the same problem. Results indicate that the proposed algorithms yield solutions significantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths. Comparison with lower bounds shows that the proposed heuristics obtain optimal or near optimal solutions in many cases.     

Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

Stability evaluation of a railway timetable at station level

This research deals with a real-world planning problem in railway infrastructure operations. It is part of the RECIFE project, which seeks to develop a decision support software to help evaluate the capacity of a rail junction or station. To this end, the project is working on a timetable optimization model, as well as timetable evaluation modules. This paper presents a module for evaluating timetable stability, which uses an original method based on delay propagation and using shortest path problem resolution. A didactic example and a complete case study applying this method to the Pierrefitte-Gonesse junction are also presented.     

Staff rostering for the station personnel of a railway company

This paper presents a case study commissioned by the Spanish railway carrier Ferrocariles Españoles de Vía Estrecha for the annual rostering of work schedules for station personnel. A mixed rostering process is used. The first part of the process is carried out manually with the aid of a spreadsheet and Visual Basic, and consists of designing an initial graphic with 4-week patterns for each station, assigning those patterns in a rotating schedule over the year and factoring in vacation time. The second part consists of assigning relief shifts to cover those shifts left vacant in such a way as to minimize the distance travelled by personnel from other stations brought in for relief shift duty. To that end, basic programmes are designed using binary programming and a4-week time frame. The results obtained are a clear improvement on the system previously used at FEVE and the company has decided to implement the model.     

A fast heuristic approach for train timetabling in a railway node

We consider a conflict-free scheduling problem which arises in railway networks, where ideal timetables have been provided for a set of trains, but where these timetables may be conflicting. We use a space-time graph approach from the railway scheduling literature in order to develop a fast heuristic which resolves conflicts by adjusting the ideal timetables while attempting to minimize the deviation from the ideal timetable. Our approach is tested on realistic data obtained from the railway node of Milan.     

Sensitivity analysis of a railway station track layout with respect to a given timetable

An important step in the process of designing a railway station track layout is the verification of the robustness of the layout with respect to the timetables it is based on. For this purpose we develop in this paper an algorithm to randomly perturb a given timetable such that the perturbation is feasible and has the same structure as the given timetable. Mathematically, in this paper we study the problem of, given a set of integer variables and a set of binary relations stating minimal and maximal differences between the variables, to generate solutions uniformly at random. The algorithm involves the simulation of a Markov chain whose state space is a particular subset of the set of feasible timetables and whose limiting and equilibrium distribution is the uniform distribution. Whereas this idea seems simple, some technical pitfalls need to be overcome to make it sound.     

一个基于Sidrauski宏观经济动力学模型的分析

Abstract. This paper formulates a kind of dynamical macro-economic model based onSidrauski‘s work,then presents the sufficient and necessary conditions of the stability of modelat equilibrium states ,and shows some results for special production functions.     

Asset replacement for an urban railway using a modified two-cycle replacement model

This paper considers the application of capital replacement models at Mass Transit Railway Corporation Limited (MTRCL), Hong Kong. A particular characteristic of the replacement problems considered is that costs relating to existing equipment are generally constant or increasing only slowly. Consequently, replacement is often driven by technical obsolescence, but other criteria are used for informing decisions. The applicability of traditional OR models of replacement is then problematic. We recommend the use of a modified two-cycle replacement model and compare this model to existing capital replacement models. Issues relating to the estimation of delay costs and failure consequences and their influence on the replacement decision are also considered—this is done using a fixed horizon model, which is a special case of the modified two-cycle model. Track points and escalators are used as particular examples. In addition to modelling recommendations, we discuss the management of asset replacement with emphasis on the procedures necessary to ensure that asset replacement requirements are considered appropriately and effectively. The paper treats, in particular, the procedural issues of asset replacement, and the discussion of asset replacement system methodology reflects the current practise at MTRCL, Hong Kong, and developments within that organization through collaboration with academia. The modified two-cycle replacement model is recommended by us for general replacement applications. The asset replacement procedure is presented as an exemplar for business and industry.     

Effects of stenosis on arterial rheology through a mathematical model

The paper presents an analytical study of blood flow through a stenosed artery using a suitable mathematical model. The artery is modelled as an anisotropic viscoelastic cylindrical tube containing a non-Newtonian viscous incompressible fluid representing blood. The blood flow is assumed to be characterized by the Herschel–Bulkley model. The effect of the surrounding connective tissues on the motion of the arterial wall has been incorporated. Initially, the relevant solutions of the boundary value problem are obtained in the Laplace transform space, through the use of a suitable finite difference technique. Laplace inversion is carried out by employing suitable numerical techniques. Finally, the variations of the vascular wall displacements, the velocity distribution of the blood flow, the flux, the resistance to flow and the wall shear stress in the stenotic region are quantified through numerical computations and presented graphically.     

Local improvement algorithms for a path packing problem: A performance analysis based on linear programming

Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.     

Spin-boson model through a Poisson-driven stochastic process

We give a functional integral representation of the semigroup generated by the spin-boson Hamiltonian by making use of a Poisson point process and a Euclidean field. We present a method of constructing Gibbs path measures indexed by the full real line which can be applied also to more general stochastic processes with jump discontinuities. Using these tools we then show existence and uniqueness of the ground state of the spin-boson, and analyze ground state properties. In particular, we prove super-exponential decay of the number of bosons, Gaussian decay of the field operators, derive expressions for the positive integer, fractional and exponential moments of the field operator, and discuss the field fluctuations in the ground state.     

A note on a selfish bin packing problem

In this paper, we consider a selfish bin packing problem, where each item is a selfish player and wants to minimize its cost. In our new model, if there are k items packed in the same bin, then each item pays a cost 1/k, where k ≥ 1. First we find a Nash Equilibrium (NE) in time O(n log n) within a social cost at most 1.69103OPT + 3, where OPT is the social cost of an optimal packing; where n is the number of items or players; then we give tight bounds for the worst NE on the social cost; finally we show that any feasible packing can be converged to a Nash Equilibrium in O(n ²) steps without increasing the social cost.     

Estimating a model through the conditional MLE

The estimation problem of a model through the conditional maximum likelihood estimator (MLE) is explored. The estimated model is compared using the two dual Kullback-Leibler losses with that through the unconditional MLE. The former is found to be superior to the latter under familiar models. This result is applicable to the model selection problem. These suggest a novel extensive use of the conditional likelihood, since the traditional use of the conditional likelihood was restricted only on inference for the structural parameter.     

A conjugate-direction method based on a nonquadratic model

A conjugate-gradient method for unconstrained optimization, which is based on a nonquadratic model, is proposed. The technique has the same properties as the Fletcher-Reeves algorithm when applied to a quadratic function. It is shown to be efficient when tried on general functions of different dimensionality.     

Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].