Vorlesung vom 15.03.2013

Vorlesungsfolien

Summary

In this lecture we got to know a class of software applications, that is used to find optimal business decisions. You find lots of examples

here

, but we do not exclusively focus on operations research methods in this lecture.

Using the example of a traveling salesman problem with time windows we examined two distinct ways for getting an automated solution. The first way was to program the solution with the help of artificial intelligence methods. However, we found it very difficult to write a new solver for each problem that occurs in practice.

We noticed that there are similarities in the structure of decision problems. They can be formulated as

constraint satisfaction problems

or constraint optimization problems. We proved that it is possible to implement a solver that can solve each decision problem presented as CSP. For this, we generalized our backtracking algorithm for the TSPTW. You can read about the

generalized backtracking algorithm in this text

, page 142.

The use of general CSP-solvers allows us to formulate decision problems declaratively, rather than imperatively.