Vertex Coloring Optimod

[Marika-K]

Why this Mod?

Graph problems are always nice and the picture for the gallery is already clear :) The problem is easy to understand and well-known.

What will the API be?

It can be done similarly to the maximum bipartite matching problem using networkx, scipy, and pandas As an example (for pandas): courses in university with information which of them are overlapping in time. Assign courses to rooms (colors) such that the number of rooms is minimal.

[maliheha]

@simonbowly @Marika-K Isn't this the same as the chromatic number that is going to be handled in #69?

[simonbowly]

Hmm, good point. I had read #69 as computing those graph properties (or bounds on them) using only results from MWIS formulations. But was your plan there to add max clique, vertex colouring, etc formulations to the mod?

[maliheha]

I am not sure how it is possible to find the graph properties below without solving optimization problems.

• To find the chromatic number, we need to solve the vertex coloring problem. The chromatic number of a graph equals the minimum number of colors required to color the vertices such that no two adjacent vertices share the same color.
• The clique number of a graph equals the maximum independent set (MIS) of its complement graph - We already have a formulation for the M(W)IS problem.
• The clique cover number of a graph equals the chromatic number of its complement graph.
• The stability number of a graph is exactly its MIS.

Of course, there are relationships between these properties. For example, the chromatic number of a graph is >= its clique number. Or the chromatic number of a graph divided by the graph number of vertices is <= its MIS (or stability number).

My understanding of the issue https://github.com/Gurobi/gurobi-optimods/issues/69 is to find the exact values for these properties via solving optimization problems because this is the main point of Optimod. These relationships are otherwise classical results and are well-known.

The idea was to rename this MWIS mod to something more general and include different methods which get the same input and calculate the above properties via solving a M(W)IS or a vertex coloring problem. This might have the disadvantage of mixing two different optimization problems together. Maybe the stability number and the clique number should be part of MWIS mod and the chromatic number and the clique cover number be part of the vertex coloring mod.

[Marika-K]

I will wait for issue #69 to be finished. We can then decide if something can be extended or if an additional optimod is of further value.