Publication detail

From Exact Methods to Heuristics

ŠEDA, M.

Original Title

From Exact Methods to Heuristics

Type

journal article - other

Language

English

Original Abstract

In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound method and dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics) that define a general framework for computations and the user must find suitable problem-specific parameter settings and verify them using benchmarks. A genetic algorithm was found to work efficiently in many situations. It provides good results in a reasonable amount of time for hundreds of input parameters and tens of capacity constraints. Finally, we showed that using stochastic heuristics need not be the only way of solving NP-complete problems and proposed approaches based on geometric data structures such as Delaunay triangulation and Voronoi diagrams. They were applied in network optimisation to find a minimal Euclidean Steiner tree and in robotics to plan trajectories of a moving object in a scene with obstacles. While being able to provide good approximations of the optimum, the proposed deterministic heuristics do not require so much tuning as stochastic heuristics and, moreover, they run in a polynomial time. Therefore they are also applicable in real time computation. Using generalised Voronoi diagrams gives an efficient tool for robot motion planning and generates smooth trajectories in a scene with movable obstacles.

Keywords

optimisation, NP-hard problems, heuristic methods, genetic algorithm, scheduling, robotics, computational geometry, Voronoi diagram, Delaunay triangulation

Authors

ŠEDA, M.

RIV year

2008

Released

15. 9. 2008

Publisher

VUTIUM

Location

Brno

ISBN

1213-418X

Periodical

Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy

Year of study

2008

Number

276

State

Czech Republic

Pages from

1

Pages to

40

Pages count

40

BibTex

@article{BUT47998,
  author="Miloš {Šeda}",
  title="From Exact Methods to Heuristics",
  journal="Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy",
  year="2008",
  volume="2008",
  number="276",
  pages="1--40",
  issn="1213-418X"
}