7 October 2021 (144 words)

Maximal clique

Vamshi Jandhyala has an interesting series of blog posts about Optimization using linear models.

Each article includes a description of the topic, along with several examples written in Python and solved using the Gurobi commercial solver:

  • Modeling using Linear Programming. Illustrates some concepts of linear programming via the formulation and solution of a resource allocation problem.
  • Modeling using Integer Programming. Describes several applications of integer programming, including an assignment problem, graph coloring, the 0-1 knapsack problem, a set covering problem, and a class scheduling example.
  • Graphs and Integer Programming. Explores some graph theory applications of integer programming, including finding a maximal independent set and finding the maximal clique of a set.

The examples include Python source code, though they are sufficiently small that they could be translated to use your preferred modelling tool and solver.