You are in the center of Oslo and want to get to SINTEF, in Forskningsveien 1, as fast as you can. You know what you can do: you can ask google to find the best way for you. What you maybe do not know is that google is actually representing and solving your query as an optimization problem. Indeed, you want to find the shortest path from your location to a specific location in the city, chosen among the set of all possible paths. This particular optimization problem is called the shortest path problem.
In mathematical optimization, both the set of available elements (feasible region) and the quality criteria (objective function) are expressed by means of variables, functions, equations, inequalities, etc.
The feasible region is a subset S ⊆ Rn, whereas the objective is a function f : S → R. The mathematical optimization problem writes as
min f(x): x ∈ S.
The set S is the set of vectors x ∈ Rn satisfying a finite number of equations or inequalities of the type gi(x) ≤ bi , for i = 1, ..., m, with gi : Rn → R. These inequalities are called constraints, because the actually limit the range of values that the variables can assume. Back to our shortest path problem, each variable xe (i.e. each component of vector x ∈ S) is associated with a specific link or street e. The last street in my path must be Forskningsveien: this is a constraint. Also, for any intermediate street I take in my path, the next must be an adjacent street. This is another constraint.
There are several classifications of mathematical optimization problems, depending on the form of the objectives and of the constraints. If the feasible set S is a polyhedron and the objective function f is linear, then we have a linear programming problem, and if f is quadratic, then we have quadratic programming. If S is finite, then we have a combinatorial optimization problem also called discrete optimization problem. The shortest path problem is combinatorial optimization, because we only have a finite (although huge) set of alternative paths.
