Binary Paint Shop Example

Download Notebook

The Binary Paint Shop Problem minimizes color changes in an automotive paint line. Cars pass through in sequence and each car type must receive one car of each color, while minimizing switches between consecutive cars.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.binary_paint_shop import (
    BinaryPaintShopCollection,
    BinaryPaintShopData,
    BinaryPaintShopFormulation,
    BinaryPaintShopInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a paint sequence of 12 cars from 6 types, each type appearing exactly twice.

data = BinaryPaintShopData.from_sequence(
    n_car_types=6,
    sequence=[4, 0, 0, 2, 1, 1, 4, 3, 2, 5, 5, 3],
)

Plot Data

Each car type is shown as a distinct silhouette in the paint-line sequence.

data.plot()

<Axes: title={'center': 'Binary Paint Shop — Car Sequence'}>

Create Formulation

Minimize color changes along the paint sequence.

formulation = BinaryPaintShopFormulation()
print(formulation.to_string(data))

Binary Paint Shop Formulation:
  Car types: 6
  Sequence length: 12

Decision Variables:
  c[t] in {0,1} for t = 1, ..., 5  (c[0] = 0 fixed WLOG)
  c[t] = color of the first appearance of car type t (second gets 1 - c[t])
  d[p] in {0,1} for p = 0, ..., 10  (p = position in sequence)
  d[p] = 1 if color changes between positions p and p+1
  Total: 17 binary variables

Objective:
  minimize sum_p d[p]  (number of color changes)

Constraints:
  1. Color change linearization (22 constraints):
     d[p] >= color_at_p - color_at_{p+1}  for all p = 0, ..., 10
     d[p] >= color_at_{p+1} - color_at_p  for all p = 0, ..., 10
     where color_at_p = c[type_p] if first appearance, 1 - c[type_p] if second

Create Instance

Combine data and formulation into a solvable instance.

instance = BinaryPaintShopInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Binary Paint Shop Data:
  Number of car types: 6
  Sequence length: 12
  Sequence: [4 0 0 2 1 1 4 3 2 5 5 3]
Formulation:Binary Paint Shop Formulation:
  Car types: 6
  Sequence length: 12

Decision Variables:
  c[t] in {0,1} for t = 1, ..., 5  (c[0] = 0 fixed WLOG)
  c[t] = color of the first appearance of car type t (second gets 1 - c[t])
  d[p] in {0,1} for p = 0, ..., 10  (p = position in sequence)
  d[p] = 1 if color changes between positions p and p+1
  Total: 17 binary variables

Objective:
  minimize sum_p d[p]  (number of color changes)

Constraints:
  1. Color change linearization (22 constraints):
     d[p] >= color_at_p - color_at_{p+1}  for all p = 0, ..., 10
     d[p] >= color_at_{p+1} - color_at_p  for all p = 0, ..., 10
     where color_at_p = c[type_p] if first appearance, 1 - c[type_p] if second

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

2026-05-29 11:33:32 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:39 INFO     Sleeping for 10.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:50 INFO     Sleeping for 15.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:34:07 INFO     Sleeping for 20.0 seconds. Waiting and checking a function in a loop.

Binary Paint Shop Solution:
  Color assignment: [1 0 1 1 1 0 0 0 0 0 1 1]
  Color changes: 4
  Valid: True

Plot Solution

Cars are now painted: each type has one car in each color. Red arrows mark color changes.

uc_solution.plot(data)

<Axes: title={'center': 'BPS Solution — 4 color changes'}>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = BinaryPaintShopCollection.from_random(
    min_size=4,
    max_size=6,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)

Model: binary_paint_shop<binary_paint_shop>
Minimize
  d_0 + d_1 + d_2 + d_3 + d_4 + d_5 + d_6
Subject To
  change_pos_0: -c_0 + c_2 + d_0 >= 0
  change_neg_0: c_0 - c_2 + d_0 >= 0
  change_pos_1: -c_2 + d_1 >= 0
  change_neg_1: c_2 + d_1 >= 0
  change_pos_2: -c_2 + d_2 >= -1
  change_neg_2: c_2 + d_2 >= 1
  change_pos_3: -c_0 + c_2 + d_3 >= 0
  change_neg_3: c_0 - c_2 + d_3 >= 0
  change_pos_4: c_0 + c_1 + d_4 >= 1
  change_neg_4: -c_0 - c_1 + d_4 >= -1
  change_pos_5: -c_1 + d_5 >= -1
  change_neg_5: c_1 + d_5 >= 1
  change_pos_6: -c_1 + d_6 >= 0
  change_neg_6: c_1 + d_6 >= 0
Binary
  c_0 c_1 c_2 d_0 d_1 d_2 d_3 d_4 d_5 d_6