Optimization is a mathematical discipline that concerns the finding of minima and maxima
of functions, subject to so-called constraints. Optimization originated in the 1940s, when
George Dantzig used mathematical techniques for generating "programs" (training
timetables and schedules) for military application. Since then, his "linear programming" techniques
and their descendents were applied to a wide variety of problems, from the scheduling of production
facilities, to yield management in airlines. Today, optimization comprises a wide variety
of techniques from Operations Research, artificial intelligence and computer science, and
is used to improve business processes in practically all industries.
Discrete optimization problems arise, when the variables occurring in the optimization function
can take only a finite number of discrete values. For example, the staff scheduler of a hospital
unit has a finite set of staff members available, and thus staff scheduling consists of taking
discrete decisions, one for each slot of the resulting schedule. Discrete optimization aims
at taking these decisions such that a given function is maximized (for example revenue) or
minimized (for example cost), subject to constraints, which express regulations or rules,
such as required numbers of rest days for the staff in a schedule.
Perhaps surprisingly, discrete optimization is more difficult than its "continuous" counterpart,
where variables are allowed to take fractional values or even "real numbers". In
fact, there is no general solution known for optimization problems that reliably and speedily
computes solutions to discrete optimization problems. A variety of computation techniques
compete for the best solution. In recent years, it has become clear that different application
domains lend themselves to different solution techniques. Linear programming has been applied
to discrete optimization using so-called "branch-and-bound" techniques, for example
to solve facility location problems. Heuristic search aims at finding good but not necessarily
optimal solutions quickly. This technique is successfully used in a wide variety of applications;
for example the Lin Kernighan heuristic for the Traveling Salesman problem finds solutions
that are extremely close to the optimal solution for very large problem instances. Constraint
programming is a solution technique that developed out of programming language research and
artificial intelligence. It employs specialized algorithms in the general framework of tree
search, and has been successfully applied to production scheduling problems.
Another recent trend is the combination of optimization techniques for problems that do
not lend themselves easily to one technique alone. Today, these techniques
prove to deliver robust engines that
provide very high quality solutions for even very large problem instances.
Further reading:
- The Science of Better: Website on Operations Research provided by the
Institute for Operations Research and the Management Sciences (INFORMS):
http://www.scienceofbetter.org
|