> What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible?
- Polyhedral combinatorics (Books: "Alexander Schrijver - Combinatorial Optimization: Polyhedra and Efficiency" (more focus on polyhedral combinatorics; IMHO the best book, but not the most approachable), "Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms" (more focus on algorithms; easier to read). This of course includes (mixed-)integer linear programming ((M)ILP).
- Of course learning about (M)ILPs means understanding linear programming (LP). Here I personally prefer "Alexander Schrijver - Theory of Linear and Integer Programming" (this books also covers ILP aspects, but not MILPs).
- Other books for learning about ILPs are "Dimitris Bertsimas, Robert Weismantel - Optimization Over Integers" (main focus is ILP, nevertheless a good book) and "Conforti, Cornuejols, Zambelli - Integer Programming". There are no really good books about MILPs that I know of, but these two books at least will cover some aspects of it.
- Sometimes semidefinite relaxations will occur (most famous example: Goemans-Williamson Algorithm; less famous, but also important: Lovasz-Schrijver hierarchy, Sherali-Adams hierarchy, Lasserre hierarchy)