Discrete optimization

From Wikipedia, the free encyclopedia

This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (March 2008)

This article is in need of attention from an expert on the subject. WikiProject Mathematics or the Mathematics Portal may be able to help recruit one. (April 2009)

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

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

Two notable branches of discrete optimization are:

• combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures
• integer programming

These branches are closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.g. shortest path) and conversely, integer programs can often be given a combinatorial interpretation.