Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete optimization problem are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers.^[1]

YouTube Encyclopedic

1/3
Views:
1 391
345 309
893

Transcription

Branches

Three notable branches of discrete optimization are:^[2]

combinatorial optimization, which refers to problems on graphs, matroids 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) 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.

References

^ Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, vol. 36, Cambridge University Press, p. 1, ISBN 9780521010122.
^ Hammer, P. L.; Johnson, E. L.; Korte, B. H. (2000), "Conclusive remarks", Discrete Optimization II, Annals of Discrete Mathematics, vol. 5, Elsevier, pp. 427–453.

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions

Gradients

Convergence	Trust region Wolfe conditions
Quasi–Newton	Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1)
Other methods	Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton

Hessians

Newton's method

Constrained nonlinear

General	Barrier methods Penalty methods
Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar
Basis-exchange	Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Graph
algorithms

Minimum spanning tree	Borůvka Prim Kruskal

Shortest path	Bellman–Ford SPFA Dijkstra Floyd–Warshall

Network flows

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

Software

This page was last edited on 7 February 2024, at 01:01

From Wikipedia, the free encyclopedia

YouTube Encyclopedic

Transcription

Branches

See also

References