Binary paint shop problem
It is highly recommended to read the Independent set problem chapter before reading this one.
Problem Definition
The binary paint shop problem is defined as follows: we are given a $2m$ length sequence containing $m$ cars, where each car appears twice. Each car need to be colored red in one occurrence, and blue in the other. We need to choose which occurrence for each car to color with which color — the goal is to minimize the number of times we need to change the current color.
In the following, we use a character to represent a car, and defined a binary paint shop problem as a string that each character appear exactly twice.
using GenericTensorNetworks, Graphs
sequence = collect("iadgbeadfcchghebif")18-element Vector{Char}:
'i': ASCII/Unicode U+0069 (category Ll: Letter, lowercase)
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
'g': ASCII/Unicode U+0067 (category Ll: Letter, lowercase)
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
'f': ASCII/Unicode U+0066 (category Ll: Letter, lowercase)
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
'h': ASCII/Unicode U+0068 (category Ll: Letter, lowercase)
'g': ASCII/Unicode U+0067 (category Ll: Letter, lowercase)
'h': ASCII/Unicode U+0068 (category Ll: Letter, lowercase)
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
'i': ASCII/Unicode U+0069 (category Ll: Letter, lowercase)
'f': ASCII/Unicode U+0066 (category Ll: Letter, lowercase)We can visualize this paint shop problem as a graph
rot(a, b, θ) = cos(θ)*a + sin(θ)*b, cos(θ)*b - sin(θ)*a
locations = [rot(0.0, 100.0, -0.25π - 1.5*π*(i-0.5)/length(sequence)) for i=1:length(sequence)]
graph = path_graph(length(sequence))
for i=1:length(sequence)
j = findlast(==(sequence[i]), sequence)
i != j && add_edge!(graph, i, j)
end
show_graph(graph, locations; texts=string.(sequence), format=:svg, edge_colors=
[sequence[e.src] == sequence[e.dst] ? "blue" : "black" for e in edges(graph)])
Vertices connected by blue edges must have different colors, and the goal becomes a min-cut problem defined on black edges.
Generic tensor network representation
We can define the binary paint shop problem with the PaintShop type as
pshop = PaintShop(sequence)PaintShop{Char}(['i', 'a', 'd', 'g', 'b', 'e', 'a', 'd', 'f', 'c', 'c', 'h', 'g', 'h', 'e', 'b', 'i', 'f'], Bool[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0])The tensor network representation of the binary paint shop problem can be obtained by
problem = GenericTensorNetwork(pshop)GenericTensorNetwork{PaintShop{Char}, OMEinsum.DynamicNestedEinsum{Char}, Char}(PaintShop{Char}(['i', 'a', 'd', 'g', 'b', 'e', 'a', 'd', 'f', 'c', 'c', 'h', 'g', 'h', 'e', 'b', 'i', 'f'], Bool[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]), ae, ea ->
├─ afeg, feg -> ae
│ ├─ bgaf, geb -> afeg
│ │ ├─ abf, agf -> bgaf
│ │ │ ├─ abi, if -> abf
│ │ │ │ ├─ ia, bi -> abi
│ │ │ │ │ ⋮
│ │ │ │ │
│ │ │ │ └─ if
│ │ │ └─ ad, gfd -> agf
│ │ │ ├─ ad, ad -> ad
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ dg, df -> gfd
│ │ │ ⋮
│ │ │
│ │ └─ gb, be -> geb
│ │ ├─ gb
│ │ └─ be, eb -> be
│ │ ├─ be
│ │ └─ eb
│ └─ feh, hg -> feg
│ ├─ fh, he -> feh
│ │ ├─ fc, hc -> fh
│ │ │ ├─ fc
│ │ │ └─ cc, ch -> hc
│ │ │ ⋮
│ │ │
│ │ └─ he
│ └─ hg, gh -> hg
│ ├─ hg
│ └─ gh
└─ ea
, Dict{Char, Int64}())Theory (can skip)
Type PaintShop can be used for constructing the tensor network with optimized contraction order for solving a binary paint shop problem. To obtain its tensor network representation, we associating car $c_i$ (the $i$-th character in our example) with a degree of freedom $s_{c_i} \in \{0, 1\}$, where we use $0$ to denote the first appearance of a car is colored red and $1$ to denote the first appearance of a car is colored blue. For each black edges $(i, i+1)$, we define an edge tensor labeled by $(s_{c_i}, s_{c_{i+1}})$ as follows: If both cars on this edge are their first or second appearance
\[B^{\rm parallel} = \left(\begin{matrix} x & 1 \\ 1 & x \\ \end{matrix}\right),\]
otherwise,
\[B^{\rm anti-parallel} = \left(\begin{matrix} 1 & x \\ x & 1 \\ \end{matrix}\right).\]
It can be understood as, when both cars are their first appearance, they tend to have the same configuration so that the color is not changed. Otherwise, they tend to have different configuration to keep the color unchanged.
Counting properties
graph polynomial
The graph polynomial defined for the maximal independent set problem is
\[I_{\rm max}(G, x) = \sum_{k=0}^{\alpha(G)} b_k x^k,\]
where $b_k$ is the number of maximal independent sets of size $k$ in graph $G=(V, E)$.
max_config = solve(problem, GraphPolynomial())[]Since it only counts the maximal independent sets, the first several coefficients are 0.
Counting properties
graph polynomial
The graph polynomial of the binary paint shop problem in our convention is defined as
\[P(G, x) = \sum_{k=0}^{\delta(G)} p_k x^k\]
where $p_k$ is the number of possible coloring with number of color changes $2m-1-k$.
paint_polynomial = solve(problem, GraphPolynomial())[]Configuration properties
finding best solutions
best_configs = solve(problem, ConfigsMin())[](4.0, {000000110, 111111001})ₜOne can see to identical bitstrings corresponding two different vertex configurations, they are related to bit-flip symmetry.
painting1 = paint_shop_coloring_from_config(pshop, read_config(best_configs)[1])
show_graph(graph, locations; format=:svg, texts=string.(sequence),
edge_colors=[sequence[e.src] == sequence[e.dst] ? "blue" : "black" for e in edges(graph)],
vertex_colors=[isone(c) ? "red" : "black" for c in painting1], config=GraphDisplayConfig(;vertex_text_color="white"))
Since we have different choices of initial color, the number of best solution is 2.
The following function will check the solution and return you the number of color switches
num_paint_shop_color_switch(sequence, painting1)4This page was generated using Literate.jl.