These codes solve various combinatorial optimization problems using the integer programming solver Gurobi. All codes are written in Python and handle networks with NetworkX.
The IP models generally increase in implementation difficulty:
- knapsack
- vertex cover
- independent set
- clique (relaxations: k-plex, quasi-clique, 2-club, k-club) (extension: independent union of cliques)
- dominating set and connected dominating set
- matching
- min cut
- max flow
- shortest path
- assignment problem
- coloring (via labeling, asymmetric representatives, set cover)
- spanning tree (via single-commodity flow, multi-commodity flow, directed cut, Dantzig-Fulkerson-Johnson)
- traveling salesman (directed: MTZ, lifted MTZ, DFJ, CUT, MCF) (undirected: DFJ, CUT)