Introduction to Stochastic Processes and Simulation

12Optimization and Simulation

CONCEPTS DISCUSSED IN THIS CHAPTER.– We will begin by presenting some optimization problems, such as the search for extremum of a function, and looking, in particular, at combinatorial optimization by quoting the “famous” problems: the traveling salesman problem, the vehicle routing problem and the knapsack problem.

A broad range of local methods is proposed by applying examples for the problems introduced above, such as the greedy algorithm, the gradient descent method, the simulated annealing method and the tabu method.

Finally, we describe and analyze, with examples, two methods that are increasingly used to approach optimal solutions: the genetic algorithms method and the ant colony method.

Recommended reading: [CON 06, DER 16, DOR 04, FAU 14, GOL 06, SIA 14].

12.1. Introduction

Optimization problems are an important class of operational research problems. They often do not have an exact analytical solution, at least not one which can be obtained in a reasonable time using computers. We are then led to look for approximations of the optimal solution(s) by using iterative algorithms.

EXAMPLE 12.1(1).– Search for the minimum of the function:

for x varying from 0 to 8.

The problem is analytically solvable, in principle, by equalizing the derivative of f(x) to zero. However, the calculation is not simple and leads to the global minimum (x = 1.89, ...