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.
Famous quotes containing the word discrete:
“The mastery of one’s phonemes may be compared to the violinist’s mastery of fingering. The violin string lends itself to a continuous gradation of tones, but the musician learns the discrete intervals at which to stop the string in order to play the conventional notes. We sound our phonemes like poor violinists, approximating each time to a fancied norm, and we receive our neighbor’s renderings indulgently, mentally rectifying the more glaring inaccuracies.”
—W.V. Quine (b. 1908)