307 research outputs found
The Shortest Path Problem on Real Road Networks: Theory, Algorithms and Computations
No full textThis thesis contains the following subjects: - Several shortest path algorithms, both label-setting and label-correcting; - Unidirectional and bidirectional methods; - A* algorithms; - Symmetric and balanced estimators; - Preprocessing techniques. This thesis contains an elaborate, comparative evaluation of the various methods described. Bidirectional A* algorithms are commonly based on balanced heuristic estimators, since such estimators can easily be embedded in a bidirectional variant of Dijkstra's algorithm. In this thesis a check is provided, such that symmetric estimators can compete with balanced estimators. If these estimators are based on Euclidean distances, the work can be divided over the forward and backward searches with the use of scalar projections. This way, symmetric estimators are even prefered over balanced estimators. A well-known preprocessing technique includes the use of landmarks. If the estimators are based on landmarks, a balanced approach turns out to be faster than a symmetric approach. In this thesis, an initial step is proposed in a unidirectional A*-algorithm, which uses a landmark-based estimator, in order to decrease the running time of that algorithm. For one of the preprocessing techniques described, unidirectional methods are preferred over bidirectional methods. It is that particular preprocessing technique where the proposed initial step will prove an additional value.EWIElectrical Engineering, Mathematics and Computer Scienc
On Lattice Methods in Integer Optimization
No full textInteger optimization is a powerful modeling tool both for problems of practical and more abstract origin. Since the 1970s we have seen huge progress in the size of problem instances that can be tackled. This progress is mostly due to the many results in polyhedral combinatorics and to algorithms and implementations related to the polyhedral results. In the theory of integer optimization we have also seen exciting results related to the algebraic structure of the set of integer points in polyhedra together with algorithms that exploit them. This thesis presents results that make a step in the direction of merging the approach of polyhedral combinatorics with a reformulation technique built on lattices, an algebraic concept generalizing the structure of the integer points.Applied mathematicsElectrical Engineering, Mathematics and Computer Scienc
The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs
No full textThis thesis is about maximum independent set and chromatic number problems on certain kinds of infinite graphs. A typical example comes from the Witsenhausen problem: For , let be the unit sphere in , and let be the graph with , in which two points in are adjacent if and only if their inner product is equal to . What is the largest possible Lebesgue measure of an independent set in ? The problem is reminiscent of a coding theory problem, in which one asks for the size of a largest set of distinct points in some metric space so that the distance between each pair of points is at least some specified constant . Such a problem can be framed as a maximum independent set problem: Define a graph whose vertex set is the metric space, and join two points with an edge whenever their distance is less than . The codes of minimum distance are then precisely the independent sets in this graph. In the Witsenhausen problem, rather than asking for a set of points in the sphere in which all the distances less than are forbidden, we ask for a set of points in which only one distance is forbidden. And it turns out that the \emph{Delsarte} (also called \emph{linear programming}) upper bounds for the size of codes \cite{delsarte73} can be adjusted to give upper bounds for the measure of an independent set in the Witsenhausen graph. This was first done in \cite{bachoc09} and \cite{oliveira09}. The Witsenhausen problem was stated in \cite{witsenhausen74}, and in the same note it was shown that the fraction of the -dimensional sphere which can be occupied by any measurable independent set is upper bounded by the function . Frankl and Wilson \cite{frankl-wilson81} made a breakthrough in 1981 when they proved an upper bound which decreases exponentially in . Despite this progress on asymptotics, the upper bound in the case has not moved since the original statement of the problem until now. In Chapter \ref{ch:opp} we give one of the main results of the thesis, which is an improvement of this upper bound to . The proof works by strengthening the Delsarte-type bounds using some combinatorial arguments deduced in Chapters \ref{ch:opp-background} and \ref{ch:circular}. The next main result of the thesis answers a natural question about the graphs , whose vertex set is and where two points are joined with an edge if and only if their inner product belongs to the set of forbidden inner products. These graphs generalize the Witsenhausen graph, and are called \emph{forbidden inner product graphs}. One may ask, Does there exist a measurable independent set of maximum measure? There is a graph (many, in fact) having no such independent set. In Chapter \ref{ch:circular} we construct for every \e>0 an independent set in having measure at least 1/2 - \e, but we show that there is no independent set of measure equal to . In Chapters \ref{ch:adjacency} and \ref{ch:attainment} we build on the theory of adjacency operators for infinite graphs developed in \cite{bachoc13} to prove that maximum measurable independent sets exist in for all , and for all sets . As a relatively easy application of the machinery developed here, we also obtain a third result, which is that the supremum of the measures of independent sets in depends only on the topological closure of in . In particular, every independent set has measure zero if belongs to the closure of . Almost everything in this thesis relates to the Lov\'asz -function of a graph, introduced in \cite{lovasz79}. The Delsarte bounds for binary codes can be regarded as coming from the -function, and Delsarte's bounds for spherical codes \cite{delsarte77} can be thought of as coming from an extension of the -function to forbidden inner product graphs on the unit sphere. Approaches inspired by the -function have been successful in improving lower bounds for the measurable chromatic number of Euclidean space (see for instance \cite{bachoc09}, \cite{oliveira09}, \cite{filho+vallentin:10}, \cite{bachoc14}). In Chapters \ref{ch:pt-functions} to \ref{ch:dense-theta} we develop two extensions of the -function to (possibly infinite) Cayley graphs over compact groups, which apply respectively to what we call \emph{sparse} and \emph{dense} graphs. Dense Cayley graphs have enough edges to guarantee that their independence numbers are finite, and in this case the applicable -function gives an upper bound for the cardinality of any independent set. Infinite sparse Cayley graphs have infinite independent sets, and the applicable -function then gives an upper bound for the Haar measure of any measurable independent set. The extensions we develop are based on the formulations of the -function for finite Cayley graphs given in \cite{decorte14}. We also show how many of the -function approaches taken in the literature can be seen as natural examples of our general framework. The -function for finite graphs has formulations both as maximization and as minimization semidefinite programs which are mutually dual. In the approaches mentioned above in which the -function is extended to infinite graphs, it is also common to make use of duality, although in the infinite case it had not been shown that the primal and dual problems have equal values, a property known as \emph{strong duality}. In this thesis we prove strong duality for our -functions using a different approach from the known strong duality proofs in the finite case. The definitions and proofs related to the -function build on a theory of positive type functions and measures which is developed in Chapters \ref{ch:pt-functions} to \ref{ch:cones}. In \cite{montina11}, Montina gives an application in quantum communication complexity of a natural conjecture about the Witsenhausen problem, the so-called \emph{Double Caps Conjecture}. The extremal example for a spherical set in any dimension avoiding orthogonal pairs of points is conjectured \cite{kalai09} to be the union of two opposite open spherical caps of geodesic radius . In dimension , this configuration occupies about a -fraction of the unit sphere, so our new upper bound of gets roughly halfway from the previous upper bound to the Double Caps Conjecture. Assuming the Double Caps Conjecture, Montina is able to deduce a new lower bound on the cost of classically simulating a quantum channel.MathematicsElectrical Engineering, Mathematics and Computer Scienc
An optimization model for a Train-Free-Period planning for ProRail based on the maintenance needs of the Dutch railway infrastructure
No full textThe thesis reports on the Dutch railway infrastructure manager ProRail, on the literature study, on the determined Top 10 of maintenance activities that are determining the maintenance schedule, on the developing of the optimization model that finds such a maintenance schedule, and finally on the results and conclusions.Applied mathematicsElectrical Engineering, Mathematics and Computer Scienc
Space-filling Curves Heuristics for the 4D Travelling Salesman Problem in Chip Manufacturing Machines
No full textElectrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied Mathematic
Adapting the Chudak-Shmoys approximation algorithm to the k-level uncapacitated facility location problem
No full textOptimizationElectrical Engineering, Mathematics and Computer Scienc
Vehicle Scheduling of Electric City Buses: A Column Generation Approach
No full textThe public transport sector in the Netherlands strives to zero emission. One way to reach this goal is to replace diesel buses with electric buses. A problem that arises is that the vehicle scheduling problem (VSP) changes. In this thesis we will develop two models for solving the electric vehicle scheduling problem (e-VSP). One of these models uses the column generation technique to come to a solution. Both models were tested on seven lines in the city of Eindhoven in the Netherlands.Electrical Engineering, Mathematics and Computer ScienceApplied Mathematic
Minimaliseren van het aantal kruisingen in een multi-level graaf
No full textIn deze scriptie bestuderen we het aantal kruisingen in een graaf waarbij de knopen in verschillende horizontale levels verdeeld zijn, ook wel het MLCM (Multi-Level Crossing Minimization) probleem genoemd. Vaak wordt een gerichte graaf afgebeeld als een multi-level graaf. We bekijken een voorbeeld van een gerichte graaf: de stamboom van TU Delft medewerkers bij de afdeling Toegepaste Wiskunde, die ontwikkeld is door Kees Roos. In deze stamboom zitten veel kruisingen waardoor de graaf niet heel goed leesbaar is. Door het aantal kruisingen te minimaliseren zal dit verbeterd worden. Dit doen we door de knopen in nieuwe horizontale levels te verdelen en de knopen in de levels in een andere volgorde te zetten. Om een ordening van de knopen in de levels te vinden waardoor het aantal kruisingen minimaal is, zullen we het probleem omschrijven als een semi-definiet programma (SDP). Maar voordat we zover zijn stellen we eerst een integer lineair programma (ILP) op waarop onze SDP is gebaseerd. Voor het SDP moeten we een kostenmatrix defini ëren die het aantal kruisingen tussen twee levels weergeeft. Daarnaast moeten we voorwaarden opstellen zodat de ordening in de levels ook toegelaten is. Omdat het SDP erg moeilijk op te lossen is, gaan we kijken naar een relaxatie. Deze relaxatie is nog erg zwak en zullen we versterken met meer voorwaarden. Uiteindelijk krijgen we een relaxatie die sterker is dan de lineaire relaxatie van het ILP. Na het vinden van de sterke SDP-relaxatie willen we het probleem natuurlijk oplossen. We gebruiken hierbij twee verschillende oplossingsmethoden om alle voorwaarden mee te kunnen nemen. Ten slotte wordt dit allemaal gebruikt om de stamboom beter leesbaar te maken.Electrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied Mathematics (DIAM
Strengthening the integrality gap for the capacitated facility location problem with LP-based rounding algorithms
No full textThis thesis studies the capacitated facility location problem, in which all clients have unit demand and all facilities have integral capacity. A linear relaxation is researched, with corresponding integrality gap bounded by a constant. Recently, such a linear relaxation has been found and proven using an LP-bounding algorithm. The formulation of the relaxation and the proof were very complex and intuitively hard to understand, however. Therefore, this thesis provides a simpler, more formulation and proof. This thesis has two main contributions. First, a structured overview of all the theory prior to the construction of the relaxation is provided. To do so, the minimum knapsack problem is treated, which is a simplied version of the capacitated facility location problem. An LP-based rounding algorithm is presented to illustrate general ow-network techniques for facility location problems. Second, the rounding algorithm for the capacitated facility location problem is illustrated and explained more accessible to readers less familiar with LP-based rounding algorithms. The existing rounding algorithm for the capacitated facility location problem is treated, illustrated and extended with Matlab code. The rounding algorithm proves an integral solution for the capacitated facility location can be constructed from the linear optimal solution, with cost no more than 288 times the cost of the fractional optimal solution. This proves that the integrality gap of the proposed relaxation is bounded by 288.Electrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied Mathematic
Basic principles of the traveling salesman problem and radiation hybrid mapping
No full textEvery biological aspect of a create is described in the DNA. The DNA consists of very long strings that contain every biological information. Because these strings are very long, finding the right piece of information is a tough job. Fortunately, we have developed multiple ways to do this more quickly. Radiation hybrid mapping is such a method, it creates a map that shows us the locations of some essential pieces of information. We create a map with the help of the traveling salesman problem. The traveling salesman problem is a mathematical way to describe the desire to find tour through a set of places of minimal costs. The problem is not easy to solve, but many methods have been developed to make the search for the optimal solution easier. Dantzig, Fulkerson and Johnson constructed a combination of algorithms that solves the traveling salesman problem quickly in most practical efforts. With their technique we can construct the radiation hybrid map. Finally, there are many factors that determine the success rate of the map. With the right adjustments, we can create some large maps with a fairly good success rate, but doing so appears to be quiet difficult.Electrical Engineering, Mathematics and Computer ScienceDelft Institute of Applied Mathematic
- …
