Combinatorial optimization problems

(image from arxiv:2006.11190)

Two relevant combinatorial optimization problems are explored

• finding the Maximum Independent Set (MIS) of a graph
• scheduling workers on work lines

We leverage the or-tools python library and the JuMP Julia library.

MIS

A possible point of view on MIS is to express it as a linear programming problem. We do so and demonstrate in a Julia notebook how to use the JuMP library to solve the problem. A python script using or-tools is also available as a standalone solver.

A simple Go CLI randomly samples the set of maximal independent sets of its input graph with a pool of workers to get the largest possible maximal independent set with a given sample budgets.

Scheduling

Scheduling is a constraint optimization problem, which can be solved by the CP-SAT solver. script.py demonstrate how to do so. For now planning.py reads problem data from standard input and solves it with hard-coded constraints on length of work and rest time spans.

Todo

• Constraints and custom rules from user input
• Clone mis in go using goroutines, compare benchmarks

---

Note

Linear programming is not the canonical approach to solve the MIS (and it should less efficient, I presume). Specialized libraries use either an exact algorithm, or give an approximate solution by sampling in maximal independent sets:

• igraph (python, C): exact, with this algorithm which gets all the maximal independent sets.
• networkx (python): approximate, see this method
• mis (Rust): approximate, claims to be faster (?) than networkx
• LightGraphs (Julia): exact