Goal is to solve optimization problems that are best modelled discretely. A continuous model is preferred because gradient based methods like stochastic gradient descent will work much faster (so try to make the problem continuous before falling back on these methods).
Recent research has looked into embedding discrete spaces in continuous latent space: auto chemical design
Problems can be modelled using a graph or integer linear programming.
Either exact (complete) or heuristic. Use heuristic when:
- problem too large or high dimensional
- formulating problem in exact form too difficult
- feasible solution needed quickly
Just enumerate all solutions, check feasibility and cost function. Often O(n!)
Common general method of dividing into subproblems. Avoid full enumeration by pruning by bounds checking.
- Construction: incrementally build up solution, such as greedily selecting best
- Improvement: modify initial feasible solution to improve cost via some kind of neighbourhood (local search, such as with simulated annealing)
- Partitioning: divide into subproblems which are solved separately (DP)
- Parallel search: several solutions considered simultaneously then compared against each other (genetic)