Files in this item



application/pdfPAREKH-THESIS-2015.pdf (1MB)
(no description provided)PDF


Title:Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects
Author(s):Parekh, Pratik Mayur
Department / Program:Mechanical Sci & Engineering
Discipline:Mechanical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Deterministic Annealing Algorithm
Computational Aspects
Abstract:The deterministic annealing (DA) method, used for the solution of several nonconvex problems, offers the ability to avoid shallow local minima of a given cost surface and the ability to minimize the cost function even when there are many local minima. The method is established in a probabilistic framework through basic information-theoretic techniques such as maximum entropy and random coding. It arises naturally in the context of statistical mechanics by the emulation of a physical process whereby a solid is slowly cooled and at zero temperature assumes its minimum energy configuration. We start with the introduction to DA method and then present a tutorial to describe the algorithm steps. Also, we discuss the connections of DA method with Statistical Mechanics and Rate-Distortion Theory. Next, we present the application of DA method to pickup and deliver scheduling problem with time windows. Finally, a computational complexity analysis for DA is presented for a given temperature schedule. The case study focuses on the geometric cooling law $T(t)=\rho T(t-1), 0<\rho<1$, where $T(t)$ is the temperature at time $t$.
Issue Date:2015-04-30
Rights Information:Copyright 2015 Pratik Mayur Parekh
Date Available in IDEALS:2015-07-22
Date Deposited:May 2015

This item appears in the following Collection(s)

Item Statistics