imported>Altenmann: Reverted 1 edit by IsaacFG12345 (talk)

2024-07-12T15:49:38Z

New page

{{Short description|Branch of mathematical optimization}}
'''Discrete optimization''' is a branch of [[Optimization (mathematics)|optimization]] in [[applied mathematics]] and [[computer science]]. As opposed to [[continuous optimization]], some or all of the [[Variable (mathematics)|variables]] used in a discrete optimization problem are restricted to be [[discrete variable]]s—that is, to assume only a [[discrete mathematics|discrete]] set of values, such as the [[integer]]s.<ref>{{citation|title=A First Course in Combinatorial Optimization|volume=36|series=Cambridge Texts in Applied Mathematics|first=Jon|last=Lee|publisher=Cambridge University Press|year=2004|isbn=9780521010122|page=1|url=https://books.google.com/books?id=3pL1B7WVYnAC&pg=PA1}}.</ref>

==Branches==
Three notable branches of discrete optimization are:<ref>{{citation
| last1 = Hammer | first1 = P. L.
| last2 = Johnson | first2 = E. L.
| last3 = Korte | first3 = B. H.
| contribution = Conclusive remarks
| pages = 427–453
| publisher = Elsevier
| series = Annals of Discrete Mathematics
| title = Discrete Optimization II
| volume = 5
| year = 2000}}.</ref>
* [[combinatorial optimization]], which refers to problems on [[Graph (discrete mathematics)|graph]]s, [[matroid]]s and other discrete structures
* [[integer programming]]
* [[constraint programming]]
These branches are all closely intertwined however, since many combinatorial optimization problems
can be modeled as integer programs (e.g. [[Shortest path#Linear programming formulation|shortest path]]) or constraint programs,
any constraint program can be formulated as an integer program and vice versa,
and constraint and integer programs can often be given a combinatorial interpretation.

==See also==
*[[Diophantine equation]]

==References==
{{reflist}}

{{Authority control}}
{{Mathematical optimization}}

[[Category:Mathematical optimization]]

Discrete optimization - Revision history

imported>Altenmann: Reverted 1 edit by IsaacFG12345 (talk)