Binary Paint Shop Problem

Overview

The Binary Paint Shop Problem involves a sequence of cars, each appearing exactly twice. Each car must be painted red in one occurrence and blue in the other. The goal is to minimize the number of color changes when processing the sequence in order.

This example demonstrates:

Formulating the paint shop problem
Converting it to a tensor network
Finding optimal coloring sequences
Visualizing solutions

We'll use a character sequence where each character represents a car.

using GenericTensorNetworks, Graphs, GenericTensorNetworks.ProblemReductions

Define our sequence (each character appears exactly twice)

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)

Problem Visualization

We can represent this problem as a graph:

Vertices are positions in the sequence
Blue edges connect the same car's two occurrences
Black edges connect adjacent positions in the sequence

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)])

Note: Vertices connected by blue edges must have different colors, and our goal becomes a min-cut problem on the black edges.

Tensor Network Formulation

Define the binary paint shop problem:

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 objective is to minimize color changes:

objectives(pshop)

17-element Vector{ProblemReductions.LocalSolutionSize{Bool}}:
 LocalSolutionSize{Bool} on [1, 2]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [2, 3]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [3, 4]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [4, 5]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [5, 6]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [6, 2]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ false │
│    [0, 1]     │ false │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [2, 3]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [3, 7]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ false │
│    [0, 1]     │ false │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [7, 8]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

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

 LocalSolutionSize{Bool} on [8, 9]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ false │
│    [0, 1]     │ false │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [9, 4]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ false │
│    [0, 1]     │ false │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [4, 9]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [9, 6]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

 LocalSolutionSize{Bool} on [6, 5]
┌───────────────┬───────┐
│ Configuration │ Size  │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

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

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

Convert to tensor network representation:

problem = GenericTensorNetwork(pshop)

GenericTensorNetwork{PaintShop{Char}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^7.524, space = 2^4.0, read-write = 2^8.234

Mathematical Background

For each car $c_i$, we assign a boolean variable $s_{c_i} \in \{0,1\}$, where:

$0$ means the first appearance is colored red
$1$ means the first appearance is colored blue

For adjacent positions $(i,i+1)$, we define edge tensors:

If both cars are at their first or both at their second appearance:
\[B^{\text{parallel}} = \begin{pmatrix} x & 1 \\ 1 & x \end{pmatrix}\]
(Cars tend to have the same configuration to avoid color changes)
Otherwise (one first, one second appearance):
\[B^{\text{anti-parallel}} = \begin{pmatrix} 1 & x \\ x & 1 \end{pmatrix}\]
(Cars tend to have different configurations to avoid color changes)

Solution Analysis

1. Paint Shop Polynomial

The paint shop polynomial $P(G,x) = \sum_i p_i x^i$ counts colorings by number of color changes, where $p_i$ is the number of colorings with $(2m-1-i)$ color changes

paint_polynomial = solve(problem, GraphPolynomial())[]

2∙x⁴ + 28∙x⁵ + 32∙x⁶ + 80∙x⁷ + 60∙x⁸ + 88∙x⁹ + 104∙x¹⁰ + 48∙x¹¹ + 50∙x¹² + 12∙x¹³ + 8∙x¹⁴

2. Optimal Coloring Configurations

Find all optimal coloring configurations:

best_configs = solve(problem, ConfigsMin())[]

(4.0, {000000110, 111111001})ₜ

Note: We get two identical bitstrings corresponding to different vertex configurations due to bit-flip symmetry (we can start with either red or blue)

3. Solution Visualization

Convert the optimal configuration to a coloring sequence:

painting1 = ProblemReductions.paint_shop_coloring_from_config(pshop, read_config(best_configs)[1])

18-element Vector{Bool}:
 0
 0
 0
 0
 0
 0
 1
 1
 1
 1
 0
 0
 1
 1
 1
 1
 1
 0

Visualize the optimal coloring:

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"))

4. Verification

Verify the solution by counting the number of color switches:

num_paint_shop_color_switch(sequence, painting1)

More APIs

The Independent Set Problem chapter has more examples on how to use the APIs.

This page was generated using Literate.jl.