We prove a result concerning objective functions that can be used to obtain efficient and balanced solutions to the multi-commodity network flow problem. This type of solution is of interest when routing traffic in the Internet. A particular case of the result proved here (see Corollary 2 below) was stated without proof in a previous paper.
This paper introduces two Mixed Integer Linear Programming (MILP) models for railway traffic planning using a cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems from the railway domain and for two of them, where tasks have unitary resource consumption, we also compare them with two more conventional models. In the experiments, the solver performance of one of the cumulative models is clearly the best and is also shown to scale very well for a large scale practical railway scheduling problem.
This paper introduces two MILP models for the cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems and for two of them, where tasks have unitary resource consumption, we also compare them with two models based on a geometric placement constraint. In the experiments, the solver performance of one of the cumulative models, is clearly the best and is also shown to scale very well for a large scale industrial transportation scheduling problem.
This project is concerned with how to improve the capacity allocation process. In particular the project aims at proposing an enhanced format for train path applications, study the technical limitations for timetabling support tools and in the longer term to implement support systems for the train path allocation process. This report describes the various factors that affect the application process, and report the opinions from several actors in the field. Since the deregulation of the Swedish railway, and with new EU directives, the foundations for the capacity allocation process is changing rapidly. There is a strong need for clear and predictable principles that are fair and operator neutral and implements the prioritisation given to different types of traffic and for improved methodologies and decision support tools in the capacity allocation process. This is crucial to support both the possibility for the traffic operators to state demands and the timetable designers in judging conflicting train paths. A conclusion is that almost all the requirements on the timetable presented in this report can in fact be stated as properties and relations of events in the timetable.
Denna rapport beskriver status hos den forskning som är relevant för tåglägestilldelning samt analyserar och kommenterar några av de reglerande dokument såsom lagar och förordningar samt instruktioner och information som Banverket och Tågtrafikledningen tagit fram. för att styra tåglägestilldelningsprocessen. Rapporten ger också en översikt av forskningsfronten vad gäller systemstöd för tåglägestilldelningen och ger en kortfattad en beskrivning av några av de tekniker som kan vara användbara i ett stödsystem för tåglägestilldelning samt lyfter fram deras respektive för och nackdelar.
We present a crew scheduling problem with time windows in the context of scheduling train personnel, which encompasses not only assignment of resources to tasks but also the introduction of extra tasks, passive journeys, depending on the problem instance. The representation of the problem is made as a constraint program, which relies heavily on some global constraints, notably a constraint for expressing non-overlap between rectangles on a surface. A search algorithm is described and we also point out some problems and deficiencies of the current model and its computational behaviour.
This paper presents a MIP model for a locomotive routing and scheduling problem from the domain of freight railways. Innovative features of the model include the use of binary variables to separate the integer and continuous parts of the problem to maintain the flow character of the integer part of the problem. The model has been developed with, and has found practical Green Cargo, the largest rail freight operator in Sweden.
This paper presents an IP model for a vehicle routing and scheduling problem from the domain of freight railways. The problem is non-capacitated but allows non-binary integer flows of vehicles between transports with departure times variable within fixed intervals. Innovative features of the model include the use of boolean variables to separate the integer and continuous parts of the problem and maintaining the flow character of the integer part of the problem. The model has been developed with and has found practical use at Green Cargo, the largest freight rail operator in Sweden
TUFF är ett verktyg för strategisk planering av tågrörelser och resursomlopp (f.n. lok). Det unika med TUFF är inte att kunna utföra dessa planeringar var för sig, utan att de kan samverka. Detta är möjligt dels genom att de ingående komponenterna kan hantera vagare data, t.ex. tidsintervall i stället för fasta tider vilket är det vanliga annars bland kommersiella lösningar, dels att det finns en samordningsfunktion, som vi kallar samordningsagent, som samordnar olika planer från olika planeringsfunktioner. Denna samordnare är programmerbar via ett speciellt språk, så att ett stort problem kan splittras upp i mindre delar, och resultat från olika planeringar av dessa delar kan sedan kombineras och nya resultat genereras. Tanken med denna integrering av olika planeringsfunktioner är att åstadkomma globalt bättre lösningar, jämfört med när varje problem löses var för sig, genom att ta hänsyn till varje planeringsproblems krav tidigt i planeringscykeln.
There is provided a method of tracking user terminals in a mobile communication network. The method comprising, at a tracking node, determining that a user terminal is located in a tracking area, storing data associated with the tracking area, the data comprising a number of observations of all user terminals at the tracking area at a first time, receiving a page response from the user terminal located in one of the tracking area and a further tracking area, and in the event that the user terminal remains located at the tracking area, updating the data to include the number of page responses received at the tracking area after a first time interval, and in the event that the user terminal is located at the further tracking area, updating the data to include the number of page responses received at the further tracking area after the first time interval.
This document summarizes the results obtained by SICS in project GENFUNK (2001). The project was carried out in collaboration with Global Genomics AB (Stockholm, Sweden). Jointly obtained results will be presented separately. Main funding was provided by Swedish Research Agency VINNOVA. Project GENFUNK studied a novel approach of measuring the global gene expression. In the method, mRNA is extracted from a tissue sample and transformed into cDNA captured on magnetic beads. This is then acted on by type IIS restriction endonucleases, which recognize certain short DNA sequences and cut the DNA close to those sequences. The resulting fragments are amplified in PCR with selected ligation fragments, and displayed in capillary electrophoresis. Determining the gene expression levels from the peak data is combinatorial optimization problem, which can in principle be solved, to give expression levels of most genes active in sampled cells, with good accuracy.
We describe the implementation and deployment of a software decision support tool for the maintenance planning of gas turbines. The tool is used to plan the maintenance for turbines manufactured and maintained by Siemens Industrial Turbomachinery AB (SIT AB) with the goal to reduce the direct maintenance costs and the often very costly production losses during maintenance downtime. The optimization problem is formally defined, and we argue that feasibility in it is NP-complete. We outline a heuristic algorithm that can quickly solve the problem for practical purposes, and validate the approach on a real-world scenario based on an oil production facility. We also compare the performance of our algorithm with results from using mixed integer linear programming, and discuss the deployment of the application. The experimental results indicate that downtime reductions up to 65% can be achieved, compared to traditional preventive maintenance. In addition, using our tool is expected to improve availability with up to 1% and reduce the number of planned maintenance days with 12%. Compared to a mixed integer programming approach, our algorithm not optimal, but is orders of magnitude faster and produces results which are useful in practice. Our test results and SIT AB’s estimates based on operational use both indicate that significant savings can be achieved by using our software tool, compared to maintenance plans with fixed intervals.
Preventive maintenance schedules occurring in industry are often suboptimal with regard to maintenance coal-location, loss-of-production costs and availability. We describe the implementation and deployment of a software decision support tool for the maintenance planning of gas turbines, with the goal of reducing the direct maintenance costs and the often costly production losses during maintenance downtime. The optimization problem is formally defined, and we argue that the feasibility version is NP-complete. We outline a heuristic algorithm that can quickly solve the problem for practical purposes and validate the approach on a real-world scenario based on an oil production facility. We also compare the performance of our algorithm with results from using integer programming, and discuss the deployment of the application. The experimental results indicate that downtime reductions up to 65% can be achieved, compared to traditional preventive maintenance. In addition, the use of our tool is expected to improve availability with up to 1% and reduce the number of planned maintenance days by 12%. Compared to a integer programming approach, our algorithm is not optimal, but is much faster and produces results which are useful in practice. Our test results and SIT AB’s estimates based< on operational use both indicate that significant savings can be achieved by using our software tool, compared to maintenance plans with fixed intervals.
In this work we present a novel method to automate the computation of global constraints cost for local search. The method is based on the representation of a global constraints as graph properties on a binary constraint network. This formulation simplifies the implementation of global constraints in local search, and provides a cost that can be readily compared to one obtained for subproblems using binary constraints exclusively. The cost obtained can be efficiently updated during the search using incremental methods. The representation of a global constraint as outlined above can also be used for generation of suitable neighborhoods for the constraint. This is done using simple repair functions applied on the elementary constraints in the global constraint graph. We show the usability of our approach by presenting formulations of global constraints in non-overlapping and cumulative scheduling.
Rapporten beskriver möjliga ansatser för att lösa det abstraherade tidtabellproblemet som bl.a. diskuteras i rapporten "Leveranstågplan: Specifikation och åtagande" (DDTP Arbetsdokument SICS-DDTP-002). Till grund för de olika ansatserna ligger en modell med avgångstider och hålltider (dvs. väntetider och i viss mån traverseringstider) som tillåts variera inom vissa tidsintervall. Huvudidén är att arbeta med förenklade kapacitetsvillkor på bana och bangård, för att på ett effektivt sätt kunna beräkna tidtabeller på en nivå som tillåter anpassning av tidtabellen till det gällande transportbehovet och den rådande trafiksituationen.
This paper describes a flow maximization problem in steel manufacturing, decomposes it into three sub-problems, and models them in terms of finite domain constraints. Greedy algorithms are used for solving the sub-problems. The constraints are used for maintaining consistency rules, not for optimization. A tool implementing these algorithms and equipped with a GUI has been implemented.
As design, deployment and operation complexity increase in mobile systems, adaptive self-learning techniques have become essential enablers in mitigation and control of the complexity problem. Artificial intelligence and, in particular, reinforcement learning has shown great potential in learning complex tasks through observations. The majority of ongoing reinforcement learning research activities focus on single-Agent problem settings with an assumption of accessibility to a globally observable state and action space. In many real-world settings, such as LTE or 5G, decision making is distributed and there is often only local accessibility to the state space. In such settings, multi-Agent learning may be preferable, with the added challenge of ensuring that all agents collaboratively work towards achieving a common goal. We present a novel cooperative and distributed actor-critic multi-Agent reinforcement learning algorithm. We claim the approach is sample efficient, both in terms of selecting observation samples and in terms of assignment of credit between subsets of collaborating agents.
The number of connected mobile devices is increasing rapidly with more than 10 billion expected by 2022. Their total aggregate energy consumption poses a significant concern to society. The current 3gpp (3rd Generation Partnership Project) LTE/LTE-Advanced standard incorporates an energy saving technique called discontinuous reception (DRX). It is expected that 5G will use an evolved variant of this scheme. In general, the single selection of DRX parameters per device is non trivial. This paper describes how to improve energy efficiency of mobile devices by selecting DRX based on the traffic profile per device. Our particular approach uses a two phase data-driven strategy which tunes the selection of DRX parameters based on a smart fast energy model. The first phase involves the off-line selection of viable DRX combinations for a particular traffic mix. The second phase involves an on-line selection of DRX from this viable list. The method attempts to guarantee that latency is not worse than a chosen threshold. Alternatively, longer battery life for a device can be traded against increased latency. We built a lab prototype of the system to verify that the technique works and scales on a real LTE system. We also designed a sophisticated traffic generator based on actual user data traces. Complementary method verification has been made by exhaustive off-line simulations on recorded LTE network data. Our approach shows significant device energy savings, which has the aggregated potential over billions of devices to make a real contribution to green, energy efficient networks.
Modern mobile networks are increasingly complex from a resource management perspective, with diverse combinations of software, infrastructure elements and services that need to be configured and tuned for correct and efficient operation. It is well accepted in the communications community that appropriately dimensioned, efficient and reliable configurations of systems like 5G or indeed its predecessor 4G is a massive technical challenge. One promising avenue is the application of machine learning methods to apply a data-driven and continuous learning approach to automated system performance tuning. We demonstrate the effectiveness of policy-gradient reinforcement learning as a way to learn and apply complex interleaving patterns of radio resource block usage in 4G and 5G, in order to automate the reduction of cell edge interference. We show that our method can increase overall spectral efficiency up to 25% and increase the overall system energy efficiency up to 50% in very challenging scenarios by learning how to do more with less system resources. We also introduce a flexible phased and continuous learning approach that can be used to train a bootstrap model in a simulated environment after which the model is transferred to a live system for continuous contextual learning.
Modern telecommunication and mobile networks are increasingly complex from a resource management perspective, with diverse combinations of software and infrastructure elements that need to be configured and tuned for efficient operation with high quality of service. Increased real-time automation at all levels and time-frames is a critical tool in controlling this complexity. A key component in automation is practical and accurate simulation methods that can be used in live traffic scenarios. This paper introduces a new method with supporting algorithms for sampling key parameters from live or recorded traffic which can be used to generate large volumes of synthetic traffic with very similar rate distributions and temporal characteristics. Multiple spatial renewal processes are used to generate fractional Gaussian noise, which is scaled and transformed into a log-normal rate distribution with discrete arrival events, fitted to the properties observed in given recorded traces. This approach works well for modelling large user aggregates but is especially useful for medium sized and relatively small aggregates, where existing methods struggle to reproduce the most important properties of recorded traces. The technique is demonstrated through experimental comparisons with data collected from an operational LTE network to be highly useful in supporting self-learning and automation algorithms which can ultimately reduce complexity, increase energy efficiency, and reduce total network operation costs.
Detta är slutrapporten till projektet "Beslutsstöd för utredning av kapacitetsfrågor vid signalprojektering," utfört av SICS AB under perioden januari 2002 - mars 2003 och finansierat av Banverkets FoU-program. Rapporten beskriver en metod att beräkna kapacitet, där kapacitet avser antalet tåg som per tidsenhet går att framföra genom ett spårområde. Metoden beräknar minsta tiden för en upprepning hos en periodiskt upprepad trafik. I rapporten införs begreppen fri väg och trafikering för att resonera om kapacitet. Dessa begrepp är centrala för metoden och delar upp beräkningen i två delar. Den ena delen utgörs av framtagandet av värden som hör samman med de införda begreppen, från data om bland annat fordon och infrastruktur. Beräkningen av kapacitet från dessa värden utgör den andra delen. Rapporten ger en detaljerad beskrivning av hur man går till väga för att använda metoden, bevis av det grafteoretiska påstående som metoden baseras på och uppskattning av metodens beräkningskomplexitet. Rapporten innehåller också en diskussion kring vad utredning av kapacitet innebär, resonemang kring målet med ett visst kapacitetskrav och förslag på hur kapacitet kravställs. Vid signalprojektering kan metoden användas både till snabba ungefärliga och till noggranna uppskattningar av kapacitet. Lämpliga sätt att använda metoden är att jämföra olika sätt att placera signaler, jämföra ett antal trafiklösningar på en bangård och att jämföra olika val av mötesstationer på en enkelspårssträcka.
Idag konfliktregleras tågtrafiken i Sverige på sekundnivå redan i tidtabelläggningsfasen då operatörernas ansökningar har kommit in till Banverket, trots hög osäkerhet i planeringsunderlaget. Den här rapporten beskriver en tidtabelläggningsprocess där den detaljerade planeringen skjuts upp tills mer tillförlitliga fakta finns att tillgå. För den tidiga fasen föreslås i stället en mer översiktlig -- grov -- planering, vilken huvudsakligen mynnar ut i ett antal ankomster och avgångar som Banverket åtar sig att leverera punktligt till operatörerna. Poängen är att Banverket på så vis kan skjuta på besluten angående det som ska hända mellan åtagandepunkterna, och vi presenterar en konkret metod för hur detaljeringen som följer på den grova planeringen kan gå till. Metoden producerar en plan med en detaljeringsnivå som i stort överensstämmer med den i Banverkets tidtabelläggningssystem TrainPlan
While mathematical optimization and operations research receive growing attention in the railway sector, computerized timetabling tools that actually make significant use of optimization remain relatively rare. SICS has developed a prototype tool for non-periodic timetabling that minimizes resource conflicts, enabling the user to focus on the strategic decisions. The prototype is called the Maraca and has been used and evaluated during the railway timetabling construction phase at the Swedish Transport Administration between April and September 2010.
Today, detailed railway timetables in Sweden are published up to a year in advance, despite being based on volatile facts. We describe a new railway planning concept for Banverket, the Swedish Rail Administration, that aims to reduce the workload and increase the timetable quality, thus making railway traffic more cost-effective and attractive. The concept distinguishes between deliverables and production plans. The former are settled early and involve a selection of arrival and departure times that Banverket promises to deliver to the operators. The latter are fixed later, and only when sufficient information is available.
This report describes the gmdl modeling and analysis environment. gmdl was designed to provide powerful data analysis, modeling, and visualization with simple, clear semantics and easy to use, well defined syntactic conventions. It provides an extensive set of necessary for general data preparation, analysis, and modeling tasks.
Industrial process data is often stored in a wide variety of formats and in several different repositories. Efficient methodologies and tools for data preparation and merging are critical for efficient analysis of such data. Experience shows that data analysis projects involving industrial data often spend the major part of their effort on these tasks, leaving little room for model development and generating applications. This paper identifies and classifies the needs and individual steps in data preparation of industrial data. A methodology for data preparation specifically suited for the domain is proposed and a practically useful set of primitive operations to support the methodology is defined. Finally, a proof of concept data preparation system implementing the proposed operations and a scripting facility to support the iterations in the methodology is presented along with a discussion of necessary and desirable properties of such a tool.
Mobile communication networks constitute large-scale sensor networks that generate huge amounts of data that can be refined into collective mobility patterns. In this paper we propose a method for using these patterns to autonomously monitor and detect accidents and other critical events. The approach is to identify a measure that is approximately time-invariant on short time-scales under regular conditions, estimate the short and long-term dynamics of this measure using Bayesian inference, and identify sudden shifts in mobility patterns by monitoring the divergence between the short and long-term estimates. By estimating long-term dynamics, the method is also able to adapt to long-term trends in data. As a proof-of-concept, we apply this approach in a vehicular traffic scenario, where we demonstrate that the method can detect traffic accidents and distinguish these from regular events, such as traffic congestions.
Denna rapport beskriver resultatet av en dataanalys gjord på produktionsdata från Outokumpu:s valsverk i Avesta. Syftet har varit att fastställa samband mellan övriga produktionsparametrar och uppkomsten av sk. "slivers" en typ av ytlig sprick- eller veck-bildning i det färdiga stålet. Ett annat syfte har varit att studera metodologiska frågor i ett arbete av detta slag.
Technology trends such as Cloud, SDN, and NFV are transforming the telecommunications business, promising higher service flexibility and faster deployment times. They also allow for increased programmability of the infrastructure layers. We propose to split selected monitoring control functionality onto node-local control planes, thereby taking advantage of processing capabilities on programmable nodes. Our software defined monitoring approach provides telecom operators with a way to handle the trade off between high-granular monitoring information versus network and computation loads at central control and management layers. To illustrate the concept, a link rate monitoring function is implemented using node-local control plane components. Furthermore, we introduce a messaging bus for simple and flexible communication between monitoring function components as well as control and management systems. We investigate scalability gains with a numerical analysis, demonstrating that our approach would generate thousand fold less monitoring traffic while providing similar information granularity as a naive SNMP implementation or an Open Flow approach.
The symmetric cardinality constraint is described in terms of a set of variables X={x1,...,xk}, which take their values as subsets of values V={v1,...,vn}. It constraints the cardinality of the set assigned to each variable to be in an interval [lxi,cxi] and at the same time it restricts the number of occurrences of each value vj in V in the sets assigned to variables in X to be in an other interval [lvj,cvj]. In this paper we introduce the symmetric cardinality constraint and define set constraint satisfaction problem as a framework for dealing with this type of constraints. Moreover, we present effective filtering methods for the symmetric cardinality constraint.
The symmetric cardinality constraint is described in terms of variables X = {x_1,...,x_k} which take values in the subset of values V={v_1,...,v_n}. It constraints the number of times a value can be assigned to a variable in X to be in an interval [l_{x_i},c_{x_i}] and at the same time it restricts the number of values in V which any variable can take to an interval [l_{v_j},c_{v_j}]. In this paper we introduce the symmetric cardinality constraint and define set constraint satisfaction problem as a framework for dealing with this type of constraints. Moreover, we present effective filtering methods for the symmetric cardinality constraint.
Many applications in the mobile radio network domain employ simulations to explore e.g. parameter configurations, robustness of protocols and buffer allocation algorithms. User mobility is (together with traffic and radio propagation models), one of the main components of such simulations, and has large impact on e.g. load distribution, cell handover frequency, signal fading and interference. In many simulations, detailed user mobility is as crucial as the physical infrastructure, where the exact position affect fading and reflections, but in others, e.g. load balancing, handover management and radio resource scheduling, coarser models are often sufficient. But even in these cases, properties of the trajectories of individual users will affect the results of the simulation, e.g. where distribution of positions, rest times, and displacement magnitudes and velocities, need to be considered.
This paper describes an implementation of some of the ideas presented by F.C.N. Pereira in [1]. Pereira uses a sequent-calculus like system to produce Montague semantics from natural language. The lefthand sequent can be interpreted as a set of constraints under which a given sentence fragment has a certain interpretation. Pereira presents a few complementary "discharge-rules" to reduce the number of such constraints. These conditional interpretations constitute a uniform way to represent partial knowledge during the parsing process. The implementation this paper describes is done in Lambda Prolog [2]. Lambda Prolog is a generalization of horn-clause logic to higher order logic, based on the higher order unification procedure of Huet [3]. It appears that the implementation of Pereira's system in Lambda Prolog becomes very natural. The higher order unification mechanism of Lambda takes care of the complicated binding mechanisms in Pereira's "discharge-rules" in a very simple and elegant way. Finally, the paper discusses some problems with the implementation and gives a few suggestions on how these could be overcome.
This paper describes a procedure for unification in extensional higher order logics. The procedure is due to Gerard Huet and was described in /Hu75/. In this paper we consider unification in extensional theories' which is a significantly simpler problem and is not described in detail in Huet's paper. In addition, the description here focuses on computation of substitutions rather than deciding inifiability, as in Huet's paper. To this some explanatory and clarifying material has been added.
The higher order unification procedure as formulated by Huet [Hu 75] unifies terms in the simple theory of types [Ch 40]. In this language types are expressed in a very weak language (no quantification, "->" being the only operator). In many applications a stronger type-system is desirable. Lambda Prolog [MN 86], e.g. uses a type system that is in some ways similar to that of ML. This type-system uses implicitly universally quantified variables in the type-expressions. It is not trivial to reformulate the higher order unification procedure for such a theory. This paper describes an implementation of the procedure that tries to overcome some of the problems encountered in such an endeavor. The basic approach taken is to let the types be an integral part of the representation of the terms to be unified. This makes it simpler to instanciate type-variables during the unification process, and to delay the unification of terms with completely unspecified types until such time as more information is gained.
This paper describes the history of and some conclusions from a series of projects run at SICS KBS-lab during the period from 1986 to 1992. The projects have in common that they all are applications of the theory of partial inductive definitions.
In proof-systems based on calculi of Partial Inductive Definitions (PID), the notion of an A-sufficient substitution is of central importance. Applying an A-sufficient substitution to an atom before computing its definiens is necessary for the rule of definitional reflection to be sound. So far computation of A-sufficient substitutions have been restricted to the case where all variables in a query (sequent to be proved) are existentially quantified, i.e. logical variables in the sense of Prolog. From a proof theoretic point of view this kind of variable can be regarded as metavariables i.e. place-holders for as yet unknown terms. In a finitary calculus of PID's these eigenvariables have to be bound by the rule of definitional reflection in order to preserve soundness (with respect to an underlying infinitary system of PID's). This property makes these calculi different from most (if not all) calculi based on more traditional logics. This note explores some computational issues in connectin with such caluculi.
This paper introduces a restricted form of the axiom rule in calculi of Partial Inductive Definitions (PID). The paper argues that in calculi of PIDs the distinction between atomic and non-atomic formulae is not asclear as in traditional sequent calculi. Therefore the common restriction of the axiom rule to the atomic case is not adequate for this type of calculi.A novel proviso for the axiom rule and corresponding provisos for the left and right definition rules are introduced with an accompanying discussion and suggestions for possible applications in the domain of declarative specification of operational behaviour of logic programs.
We report results on a maintenance scheduling problem. The problem consists of allocating maintenance task instances to and scheduling the performances of a suitable number of maintenance packages. The number of maintenance packages is not fixed, nor is, in general, the dates or durations of their performances. A constraint programming (CP) model and solver for the problem is presented together with preliminary computational results.