Demonstrate a max independent set problem with antennas
This code was taken from the webinar, Quantum Programming with the Ocean Tools
Suite [2].
The graph below represents antenna coverage. Each of the seven nodes below
represents an antenna with some amount of coverage. Note that the coverage
provided by each antenna is identical. The edges between each node represent
antennas with overlapping coverage.
Problem: Given the above set of antennas, which antennas should you choose such
that you maximize antenna coverage without any overlaps?
Solution: One possible solution is indicated by the red nodes below.
This problem is an example of an optimization problem known as the maximum
independent set problem. Our objective is to maximize the number of nodes in a
set, with the constraint that no edges be contained in the set. To solve on a
D-Wave system, we can reformulate this problem as a quadratic unconstrained
binary optimization problem (QUBO). There are a wide variety of applications
for this problem, such as scheduling and error correcting codes (as shown in
[1]).
To run the demo:
python antennas.py
After running, the largest independent set found in the graph will be printed
to the command line and two images (.png files) will be created. An image of
the original graph can be found in the file antenna_plot_original.png, and
an image of the graph with the nodes in the independent set highlighted in a
different color can be found in the file antenna_plot_solution.png.
To run the program on a different problem, modify graph G to represent a
different antenna network.
The program antennas.py creates a graph using the Python package networkx,
and then uses the Ocean software tools to run the maximum_independent_set
function from within the dwave_networkx package.
Germany is well-known for their iconic television towers. Given the locations
of existing television towers, where should new ones be built to minimize
interference? Using the LeapHybridCQMSampler we can solve this problem,
formulated as a constrained quadratic model (CQM) in the following way. Rather
than formulating this problem as an independent set problem where no
interference is tolerated, we will optimize to find the minimum amount of
interference since it’s unlikely that in the real-world we will be able to
eliminate it entirely.
A map of Germany with the locations of 30 towers is provided, and 100 new
potential tower locations are identified randomly within the country borders.
Our objective is to select a subset of these potential new tower locations so
that the pairwise distances between all towers (existing and new) is as large
as possible. In the code, we do this by first calculating all pairwise
distances. Note that if we simply sum these raw distances we might end up with
a variety of distance distrubtions. For example, we might have pairs of towers
with distance 1 and 9, and other pairs with distance 5 and 5, each of which has
a sum of 10. In our scenario, we will prefer the pairs with distance 1 and 9.
To rectify this, we square the distances before summing them. Squaring the
distances provides a more even distribution. In our example, this provides us
with distance sums 1+81=82 and 25+25=50, prefering the pairs with distances 1
and 9 (since we are maximizing the sum).
Additionally, since interference only affects towers within a certain proximity
of each other, we set a cutoff radius. Every pair of towers with distance
greater than the cutoff radius receives a minimum-value bias so that they are
not penalized for both being selected. Each pair of towers with distance less
than the cutoff radius receives a bias of the negative of the distance squared.
Lastly, we add a constraint to choose exactly 10 new towers and fix the
existing tower variables to have value 1.0. This ensures that the existing
towers are identified as locations where towers must exist.
To run the demo:
python demo.py
Once the program has run, an image will be saved as map.png that visualizes
the initial scenario (left) and solution (right), as shown below.
[1] Sergiy Butenko and Panagote M. Pardalos. “Maximum independent set and
related problems, with applications.” PhD dissertation, University of
Florida, 2003.
[2] Victoria Goliber, “Quantum Programming with the Ocean Tools Suite”,
https://www.youtube.com/watch?v=ckJ59gsFllU
[3] Andrew Lucas, “Ising formulations of many NP problems”, doi:
10.3389/fphy.2014.00005
[4] Towers in Germany, https://www.latlong.net/category/towers-83-45.html
Released under the Apache License 2.0. See LICENSE file.
