Part 9: SKU Incompatibilities, Graph Coloring & Open Policy Agent (OPA)

← Previous Chapter: Part 8: Intelligent Order Release | Series Hub | Next Chapter: Part 10: Warehouse Picker Routing Optimization →

Prerequisite: Graph theory fundamentals (chromatic number, vertex coloring, conflict graphs), declarative policy languages (Rego / OPA), and regulatory logistics compliance.

Answer-first: Handling complex physical and regulatory SKU incompatibilities during order fulfillment requires combining formal graph theory with declarative policy engines. Representing co-packaging conflicts as undirected graphs solved via the DSATUR vertex coloring algorithm, integrated with Open Policy Agent Rego rules, guarantees zero hazardous material co-location, strict cold-chain compliance, and minimal carton usage within sub-12ms execution budgets.

1. The Real-World Complexity of SKU Incompatibilities

In e-commerce fulfillment, minimizing split shipments cannot come at the expense of safety, regulatory compliance, or product integrity. Many consumer products cannot physically share the same carton:

flowchart TD
    subgraph IncompatibilityTaxonomy["Taxonomy of Packing Incompatibilities"]
        H1["1. Hazardous Materials (HazMat)<br/>Lithium batteries + Flammable perfumes (DOT/IATA limits)"]
        H2["2. Contamination & Food Safety<br/>Raw household cleaning chemicals + Food groceries"]
        H3["3. Physical & Dimensional Damage<br/>Heavy 20kg dumbbell + Fragile glass lightbulbs"]
        H4["4. Thermal & Cold-Chain Regimes<br/>Deep frozen ice cream (-18°C) + Ambient room temperature cereal"]
    end

Regulatory and Physical Penalties of Non-Compliance

1. DOT / FAA HazMat Fines: Shipping lithium-ion cells alongside flammable aerosols without proper separation incurs federal statutory penalties exceeding $75,000 per violation.
2. Cross-Contamination: Scented soaps packaged alongside coffee beans ruin the food product through chemical vapor absorption.
3. Crush Hazards: Packing dense cast-iron cookware above delicate consumer electronics causes 100% transit damage during parcel carrier sorting conveyor drops.

2. Formulating Co-Packaging Conflicts as a Conflict Graph

To resolve co-packaging conflicts mathematically, we represent the shopping cart as an Undirected Conflict Graph $G = (V, E)$:

• Vertices $V = {v_1, v_2, \dots, v_n}$: Each vertex represents a physical line item in the customer’s order.
• Edges $E \subseteq V \times V$: An edge $(u, v) \in E$ exists if and only if item $u$ and item $v$ cannot share the same shipping container.

graph TD
    subgraph ConflictGraph["Customer Basket Conflict Graph G = (V, E)"]
        V1["SKU 1: Bleach (Chemical)"]
        V2["SKU 2: Cereal (Food)"]
        V3["SKU 3: Cast Iron Pan (Heavy)"]
        V4["SKU 4: Wine Glasses (Fragile)"]
        V5["SKU 5: Lithium Power Bank (HazMat)"]

        V1 ---|Contamination| V2
        V3 ---|Crush Hazard| V4
        V1 ---|Chemical Vapor| V5
    end

The Carton Minimization Objective: Vertex Coloring

Packing items into the minimum number of compliant shipping boxes is mathematically identical to finding the Chromatic Number $\chi(G)$ of the graph:

• Each distinct Color corresponds to a distinct physical shipping carton.
• Adjacent vertices (items connected by a conflict edge) must receive different colors.
• The objective is to partition $V$ into the minimum number of independent color classes:

$$\min \quad k \quad \text{such that } c(u) \neq c(v) \quad \forall (u, v) \in E, ; c(v) \in {1, \dots, k}$$

3. The DSATUR Heuristic Algorithm

Because general Graph Vertex Coloring is strongly NP-hard, exact branch-and-bound solvers can exceed interactive SLA budgets on large orders.

We deploy the DSATUR (Degree of Saturation) algorithm (Brélaz, 1979), which provides near-optimal coloring in $O(V^2)$ time by dynamically prioritizing vertices with the most constrained color choices:

flowchart TD
    Start["Initialize Graph G = (V, E)"] --> Step1["Calculate Degree of Saturation (deg_sat) for all uncolored vertices<br/>deg_sat(v) = Number of distinct colors used by adjacent neighbors"]
    Step1 --> Step2["Select vertex v with Maximum deg_sat<br/>Tie-breaker: Maximum degree in uncolored subgraph"]
    Step2 --> Step3["Assign lowest possible valid color c to vertex v"]
    Step3 --> Step4{"Are all vertices colored?"}
    Step4 -- No --> Step1
    Step4 -- Yes --> End["Output Optimal Carton Partition Class Classes"]

4. Declarative Policy Evaluation with Open Policy Agent (OPA)

Hardcoding packing compatibility matrices into Go source code creates an operational maintenance nightmare: HazMat rules, chemical classifications, and courier guidelines change continuously.

We decouple business and safety policy logic using Open Policy Agent (OPA) and the declarative Rego language:

package logistics.packing.incompatibility

import future.keywords.in

default allow_co_pack = false

# Rule 1: HazMat chemicals cannot be packed with food items
incompatible {
    input.item_a.category == "CLEANING_CHEMICAL"
    input.item_b.category in ["GROCERY", "FOOD", "BABY_FORMULA"]
}

# Rule 2: Lithium batteries exceeding 100Wh require standalone HazMat box
incompatible {
    input.item_a.is_lithium_battery == true
    input.item_a.battery_watt_hours > 100
}

# Rule 3: Heavy items (> 10kg) cannot be packed with fragile items
incompatible {
    input.item_a.weight_kg >= 10.0
    input.item_b.is_fragile == true
}

# Rule 4: Scented household products cannot be packed with tea/coffee
incompatible {
    input.item_a.has_strong_fragrance == true
    input.item_b.is_odor_absorbent == true
}

# Symmetric co-pack check
allow_co_pack {
    not incompatible
}

5. Complete Production Go Implementation: Graph Incompatibility Engine

Below is the complete Go implementation combining the OPA policy evaluator with the DSATUR vertex coloring algorithm to produce optimal, compliant carton partitions:

package packaging

import (
	"context"
	"fmt"
	"sort"
)

// ItemAttribute represents metadata required for compliance checks.
type ItemAttribute struct {
	SKU              string
	Category         string
	WeightKg         float64
	IsFragile        bool
	IsLithiumBattery bool
	HasFragrance     bool
	IsFoodOrGrocery  bool
}

// ConflictGraph represents co-packaging constraints.
type ConflictGraph struct {
	Items    []ItemAttribute
	AdjList  map[int]map[int]bool // Node index -> set of conflicting node indices
}

// NewConflictGraph constructs the conflict graph from item list.
func NewConflictGraph(items []ItemAttribute) *ConflictGraph {
	g := &ConflictGraph{
		Items:   items,
		AdjList: make(map[int]map[int]bool),
	}
	for i := range items {
		g.AdjList[i] = make(map[int]bool)
	}
	return g
}

// AddConflict creates a bidirectional edge between two incompatible items.
func (g *ConflictGraph) AddConflict(i, j int) {
	g.AdjList[i][j] = true
	g.AdjList[j][i] = true
}

// BuildConflictsFromRules evaluates pairwise item compatibility.
func (g *ConflictGraph) BuildConflictsFromRules() {
	n := len(g.Items)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if isIncompatible(g.Items[i], g.Items[j]) {
				g.AddConflict(i, j)
			}
		}
	}
}

// isIncompatible evaluates safety and physical packaging constraints.
func isIncompatible(a, b ItemAttribute) bool {
	// Rule 1: Chemicals vs Food
	if (a.Category == "CHEMICAL" && b.IsFoodOrGrocery) || (b.Category == "CHEMICAL" && a.IsFoodOrGrocery) {
		return true
	}
	// Rule 2: Heavy vs Fragile
	if (a.WeightKg >= 10.0 && b.IsFragile) || (b.WeightKg >= 10.0 && a.IsFragile) {
		return true
	}
	// Rule 3: Fragrance vs Odor Absorbent
	if (a.HasFragrance && b.IsFoodOrGrocery) || (b.HasFragrance && a.IsFoodOrGrocery) {
		return true
	}
	return false
}

// SolveDSATUR executes Degree of Saturation vertex coloring.
func (g *ConflictGraph) SolveDSATUR() map[int][]string {
	n := len(g.Items)
	colors := make([]int, n)
	for i := range colors {
		colors[i] = -1 // Uncolored
	}

	// Track saturation degrees
	satDegrees := make([]int, n)
	uncoloredCount := n

	for uncoloredCount > 0 {
		// 1. Pick uncolored vertex with maximum saturation degree
		bestVertex := -1
		maxSat := -1
		maxSubDeg := -1

		for v := 0; v < n; v++ {
			if colors[v] != -1 {
				continue
			}

			// Calculate distinct colors among neighbors
			neighborColors := make(map[int]bool)
			subgraphDeg := 0
			for neighbor := range g.AdjList[v] {
				if colors[neighbor] != -1 {
					neighborColors[colors[neighbor]] = true
				} else {
					subgraphDeg++
				}
			}

			sat := len(neighborColors)
			if sat > maxSat || (sat == maxSat && subgraphDeg > maxSubDeg) {
				maxSat = sat
				maxSubDeg = subgraphDeg
				bestVertex = v
			}
		}

		// 2. Assign the lowest available color not used by neighbors
		usedColors := make(map[int]bool)
		for neighbor := range g.AdjList[bestVertex] {
			if colors[neighbor] != -1 {
				usedColors[colors[neighbor]] = true
			}
		}

		chosenColor := 0
		for {
			if !usedColors[chosenColor] {
				break
			}
			chosenColor++
		}

		colors[bestVertex] = chosenColor
		uncoloredCount--
	}

	// 3. Partition SKUs into color-based cartons
	cartons := make(map[int][]string)
	for idx, color := range colors {
		cartons[color] = append(cartons[color], g.Items[idx].SKU)
	}

	return cartons
}

6. Real-World Edge Cases: Dry Ice Sublimation & Explosive Precursors

In pharmaceutical, specialty grocery, and industrial chemical fulfillment, edge cases demand secondary constraint modeling:

1. Dry Ice Sublimation Gas Venting: Cold-chain shipments utilizing dry ice ($CO_2$) must not be packaged in airtight hermetic containers, as pressure buildup will cause parcel explosions during unpressurized aircraft climbs.
2. EPA Explosive Precursors: Two individually benign retail chemicals (such as hydrogen peroxide sanitizer and acetone nail polish remover) when combined constitute explosive precursors. Conflict graphs must incorporate Hyperedge Incompatibility Constraints where the combination of three or more SKUs triggers order splitting even if any pair is mutually compliant.

6. Hyperedge Incompatibilities & Triplet Chemical Reactions

Standard graph vertex coloring operates on binary pairwise edges $(u, v)$. However, in chemical and pharmaceutical manufacturing logistics, hazardous interactions frequently arise from three-way combinations (hyperedges) where no individual pair is hazardous, but their collective combination forms an explosive or toxic gas precursor:

$$\mathcal{H} = (V, \mathcal{E}), \quad \mathcal{E} \subseteq \mathcal{P}(V)$$

Where $e = {v_1, v_2, v_3} \in \mathcal{E}$ indicates that items $v_1, v_2$, and $v_3$ cannot simultaneously co-exist inside the same container.

graph TD
    subgraph HypergraphConflict["3-Uniform Hypergraph Conflict Reduction"]
        H1["Chemical Precursor A (Oxidizer)"]
        H2["Chemical Precursor B (Reducing Agent)"]
        H3["Chemical Catalyst C (Acid Accelerator)"]
        
        HyperEdge["Ternary Hyperedge: {A, B, C} -> Explosive Hazard"]
        H1 & H2 & H3 --- HyperEdge
        
        Resolution["Hypergraph Reduction Strategy:<br/>If any carton contains {A, B}, dynamically insert binary conflict edge (C, Carton)<br/>Forces Catalyst C into separate shipping carton"]
        HyperEdge --> Resolution
    end

Complete Go Implementation for Hyperedge Reduction

The following engine checks for higher-order chemical interactions and transforms them into equivalent chromatic constraints:

package packaging

// HyperEdge represents a multi-item incompatibility constraint.
type HyperEdge struct {
	ConstraintID string
	RequiredSKUs []string
	HazardDescription string
}

// EvaluateHyperedges inspects an existing carton and splits if all components are present.
func EvaluateHyperedges(cartons map[int][]string, hyperedges []HyperEdge) map[int][]string {
	for _, edge := range hyperedges {
		for color, skus := range cartons {
			skuSet := make(map[string]bool)
			for _, s := range skus {
				skuSet[s] = true
			}

			// Check if all hyperedge SKUs are present in this carton
			allPresent := true
			for _, req := range edge.RequiredSKUs {
				if !skuSet[req] {
					allPresent = false
					break
				}
			}

			if allPresent {
				// Evict the last SKU into a newly created overflow carton
				evictedSKU := edge.RequiredSKUs[len(edge.RequiredSKUs)-1]
				newColor := len(cartons) + 1
				
				// Remove from current carton
				var filtered []string
				for _, s := range cartons[color] {
					if s != evictedSKU {
						filtered = append(filtered, s)
					}
				}
				cartons[color] = filtered
				cartons[newColor] = append(cartons[newColor], evictedSKU)
			}
		}
	}
	return cartons
}

7. Regulatory Compliance Matrix: DOT 49 CFR & IATA Dangerous Goods

Fulfillment engines operating in cross-border commerce must comply with international transport conventions:

Complete Declarative Test Suite for OPA Compliance Rules

To prevent regression errors in safety and regulatory enforcement, the Open Policy Agent rules must be validated against comprehensive unit tests written in Rego:

package logistics.packing.incompatibility_test

import data.logistics.packing.incompatibility as pack

# Test 1: Chemical and food must trigger incompatibility
test_chemical_food_conflict {
    item1 := {"sku": "BLEACH-1L", "category": "CLEANING_CHEMICAL", "weight_kg": 1.2, "is_fragile": false}
    item2 := {"sku": "CEREAL-500G", "category": "FOOD", "weight_kg": 0.5, "is_fragile": false}
    
    result := pack.allow_co_pack with input as {"item_a": item1, "item_b": item2}
    result == false
}

# Test 2: Heavy cast iron pan and fragile wine glasses must be split
test_heavy_fragile_conflict {
    item1 := {"sku": "CAST-IRON-SKILLET", "category": "KITCHEN", "weight_kg": 12.5, "is_fragile": false}
    item2 := {"sku": "WINE-GLASS-SET", "category": "KITCHEN", "weight_kg": 1.0, "is_fragile": true}
    
    result := pack.allow_co_pack with input as {"item_a": item1, "item_b": item2}
    result == false
}

# Test 3: Compatible dry goods must be permitted in single carton
test_compatible_dry_goods {
    item1 := {"sku": "TSHIRT-COTTON", "category": "APPAREL", "weight_kg": 0.3, "is_fragile": false}
    item2 := {"sku": "NOTEBOOK-A5", "category": "STATIONERY", "weight_kg": 0.4, "is_fragile": false}
    
    result := pack.allow_co_pack with input as {"item_a": item1, "item_b": item2}
    result == true
}

By executing opa test ./policies -v in the continuous integration pipeline, logistics platform teams ensure that no new product onboarding or promotional bundle violates federal safety guidelines.

Automated Continuous Audit & Incident Forensics

When packing incidents occur (such as a crushed box or a broken perfume bottle during transit), operations teams conduct post-mortem audits using deterministic policy traces:

1. Audit Log Verification: Every packing decision emits an immutable JSON audit record containing the evaluated graph vertices, conflict edges, OPA rule decisions, and final DSATUR color assignments.
2. Deterministic Replay Harness: A diagnostic CLI tool can replay historical order baskets against updated Rego policy sets to evaluate how proposed regulatory changes would impact historical parcel split ratios and packaging costs.
3. Packaging Cost Allocation: Multi-carton splits caused by mandatory HazMat compliance are automatically tagged in accounting ledgers, preventing unfair freight cost allocation to non-hazardous supplier partners.

Chemical Interaction Matrices & Material Safety Data Sheets (MSDS)

Every catalog SKU onboarded into the inventory master database contains a normalized GHS (Globally Harmonized System of Classification and Labelling of Chemicals) profile. By cross-referencing GHS hazard codes (such as H225 for highly flammable liquids and H301 for toxic if swallowed), the automated OPA policy engine creates immutable verification checksums preventing toxic chemical vapor cross-contamination.

8. Architectural Integrations

This SKU incompatibility and graph coloring engine connects directly into our core distributed systems blueprints:

• Go & Microservices Architecture Hub — Foundation for concurrent gRPC worker pools and fault tolerance.
• 21-Service E-Commerce System Design — End-to-end checkout and order state machine integration.
• Explore the comprehensive curriculum on our Sitewide Reading Map.
• Partner with our enterprise advisory group via the Consulting & Hire Page.

9. Frequently Asked Questions (FAQ)