Discrete optimization

From Wikipedia, the free encyclopedia

This article or section is missing citations or needs footnotes. Using inline citations helps guard against copyright violations and factual inaccuracies. (March 2008)

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 used in the 1940s by George Dantzig, before computer were used to solve optimization problems.

Much faster than the linear optimization, it was the integer optimization which was since the 1950s turned to a modelling and optimization tool for special practical problems for which no special algorithms were known. Significant progress in the development of solution processes in the 1980s and 1990s, the integer programming today has many applications, e.g. in production, in the planning of telecommunications and local traffic network and tour planning.

To the solution of integer optimization there is once exact solution approaches like for example branch-and-bound and cutting plane algorithms which rely on the solution of many similar linear programs and on the other side many heuristics. The solution of integer programs in praxis is still a different task which has depending on the size and the structure of the problem to solve and needs a terrific modelling and more or less specially developed or adapted algorithms. Therefore, several solution methods are often combined.