rose.blog

Imagine you are given a map of South America and are asked to assign colors to each country. Here is the map you are given:

There are a bunch of constraints you also have to satisfy as described here. One of these is a hard constraint: you can’t use the same color to label countries that share a border, and you want (in this example) to minimize the total cost of the coloring.

This type of problem has a long history, and can be applied in many different scenarios with different types of constraints (both hard and soft). In this case, an application would involve accessing geographical information systems for regions separated by boundaries, convert this information into a labeled graph, and solve the coloring problem using the Orion web services by reduction to QUBO. The “colors” could represent allocation of any general set of resources to the geographical regions in question.