Weighted Problems

Overview

Many optimization problems involve weights associated with vertices or edges. This example demonstrates how to:

  • Define weighted problem instances
  • Solve for optimal configurations
  • Analyze the energy spectrum of solutions
  • Visualize weighted solutions

We'll use the Maximum Weighted Independent Set problem on the Petersen graph as our example.

using GenericTensorNetworks, GenericTensorNetworks.ProblemReductions, Graphs

Create a Petersen graph instance

graph = Graphs.smallgraph(:petersen)
{10, 15} undirected simple Int64 graph

Defining Weighted Problems

Create a weighted independent set problem where each vertex i has weight i

problem = GenericTensorNetwork(IndependentSet(graph, collect(1:10)))
GenericTensorNetwork{IndependentSet{SimpleGraph{Int64}, Int64, Vector{Int64}}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^8.044, space = 2^4.0, read-write = 2^8.758

Examine the weights assigned to each vertex

GenericTensorNetworks.weights(problem)
10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

The tensor labels associated with these weights can be accessed via:

ProblemReductions.local_solution_spec(problem.problem)
10-element Vector{ProblemReductions.LocalSolutionSize{Int64}}:
 LocalSolutionSize{Int64} on [1]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [2]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  2   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [3]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  3   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [4]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  4   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [5]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  5   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [6]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  6   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [7]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  7   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [8]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  8   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [9]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  9   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [10]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  10  │
└───────────────┴──────┘

Note: You can use a vector for custom weights or UnitWeight() for unweighted problems. Most solution space properties that work for unweighted graphs also work for weighted graphs.

Finding Optimal Solutions

Find the maximum weighted independent set:

max_config_weighted = solve(problem, SingleConfigMax())[]
(24.0, ConfigSampler{10, 1, 1}(0100100110))ₜ

Visualizing Solutions

Define vertex layout for visualization

rot15(a, b, i::Int) = cos(2i*π/5)*a + sin(2i*π/5)*b, cos(2i*π/5)*b - sin(2i*π/5)*a
locations = [[rot15(0.0, 60.0, i) for i=0:4]..., [rot15(0.0, 30, i) for i=0:4]...]
10-element Vector{Tuple{Float64, Float64}}:
 (0.0, 60.0)
 (57.06339097770921, 18.541019662496847)
 (35.267115137548394, -48.54101966249684)
 (-35.26711513754838, -48.54101966249685)
 (-57.06339097770922, 18.541019662496833)
 (0.0, 30.0)
 (28.531695488854606, 9.270509831248424)
 (17.633557568774197, -24.27050983124842)
 (-17.63355756877419, -24.270509831248425)
 (-28.53169548885461, 9.270509831248416)

Visualize the maximum weighted independent set

show_graph(graph, locations; format=:svg, vertex_colors=
    [iszero(max_config_weighted.c.data[i]) ? "white" : "red" for i=1:nv(graph)])

Note: The GraphPolynomial property is the only solution space property that cannot be defined for general real-weighted graphs (though it works for integer-weighted graphs).

Analyzing the Energy Spectrum

For weighted problems, it's often useful to examine the "energy spectrum" - the distribution of weights across different configurations.

Compute the 10 largest weights and their configurations:

spectrum = solve(problem, SizeMax(10))[]
ExtendedTropical{10, Tropical{Float64}}(Tropical{Float64}[20.0ₜ, 20.0ₜ, 20.0ₜ, 21.0ₜ, 21.0ₜ, 22.0ₜ, 22.0ₜ, 22.0ₜ, 23.0ₜ, 24.0ₜ])

The result is an ExtendedTropical object containing the ordered weights:

spectrum.orders
10-element Vector{Tropical{Float64}}:
 20.0ₜ
 20.0ₜ
 20.0ₜ
 21.0ₜ
 21.0ₜ
 22.0ₜ
 22.0ₜ
 22.0ₜ
 23.0ₜ
 24.0ₜ

Each element in orders is a Tropical number representing a solution weight.

Finding Multiple Top Solutions

Find the 5 independent sets with the highest weights:

max5_configs = read_config(solve(problem, SingleConfigMax(5))[])
5-element Vector{StaticBitVector{10, 1}}:
 0000100110
 0010000011
 0101010001
 1010000011
 0100100110

The return value contains CountingTropical{Float64,ConfigSampler} objects that store both the weights and configurations.

Visualize these top 5 configurations:

show_configs(graph, locations, [max5_configs[j] for i=1:1, j=1:5]; padding_left=20)
Example block output

Each configuration represents an independent set with one of the 5 highest total weights.

This page was generated using Literate.jl.