Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science.

As opposed to continuous optimization, the variables used in the objective function (or some of them) are restricted to assume only discrete values, such as the integers.

Problems of combinatorial optimization can be formulated in terms of discrete optimization, however methods of their solution are often different.

The sum of feasible solutions is discrete, thus not continuous, so the term discrete programming is used. An additional usual name is integer programming, where the term 'program' is used in the sense of planning and not in the sense of a computer program. It was already being used in the 1940s by George Dantzig, before computers were used to solve optimization problems.

Much faster than linear optimization, integer optimization has since the 1950s turned into a modeling and optimization tool for special practical problems for which no special algorithms are known. Due to significant progress in the development of solution processes in the 1980s and 1990s, integer programming is effectively applied today in production, in the planning of telecommunications, and in local traffic network and tour planning.

For some integer optimization problems there exist techniques which produce exact solutions like, for example, branch-and-bound and cutting plane algorithms which rely on the solution of many similar linear programs. On the other hand, there are problems which may be solved more effectively using heuristics. The solution of integer programs in praxis is yet a different task which, depending on the size and the structure of the problem, often requires terrific modeling and specially developed or adapted algorithms. Therefore, several solution methods are often combined.