Square Tree, or How To Pack 200 X-mas Trees 🎄🎄

Distributed Geometric Packing via Crystallographic Lattices

Figure 1: High-density packing configurations achieved via crystallographic lattice generation and gradient descent relaxation. Left: 75-item solution. Right: 20-item solution. One can clearly see 3 eigen-directions in crystallized solution.

---

📜 Abstract

SquareTree is a high-performance computational geometry engine designed to solve non-convex packing problems (inspired by the Santa 2025 Challenge). Unlike traditional heuristic solvers that rely on random stochastic search, SquareTree leverages crystallographic lattice theory to identify optimal "locking" configurations.

We utilize a Modified Sparrow Search Algorithm (SSA) adapted specifically for fixed-dimension square bins. While the original Sparrow heuristic ( Gardeyn et al. ) excels at strip packing (minimizing infinite length) via random initialization, our engine introduces a "Seeded Crystal" capability. Rather than beginning with high-entropy random placement, the solver accepts a pre-loaded, geometrically derived lattice structure. This allows the optimization pipeline to bypass the chaotic "cold start" phase and immediately focus on high-density relaxation.

---

🧠 Core Logic: The Crystallized Approach

The fundamental innovation of SquareTree is the rejection of continuous space search in favor of discrete "eigen"-alignments and hybrid initialization.

1. The Advantage of "Eigen"-Directions

Standard packing algorithms view the placement of a polygon as a continuous search over coordinates and rotation . This creates an infinite search space riddled with local minima where shapes get "stuck" in suboptimal tangencies.

Our Insight: Non-convex polygons (like stars or trees) do not pack randomly; they achieve maximum density only when "locked" along specific translation vectors. We pre-compute these "eigen"-directions -- the precise vectors where a shape's concavities interlock perfectly with a neighbor.

• Dimensionality Reduction: By restricting the primary search to these vectors, we effectively discretize the continuous problem into a finite set of "perfect fits."
• Geometric Resonance: The solver "snaps" shapes into these natural grooves. Instead of hoping a random rotation fits, we force the geometry to adhere to its most efficient tiling pattern before optimization even begins.

2. Modified Sparrow Algorithm (SSA)

We have significantly adapted the open-source Sparrow heuristic. While the original algorithm treats packing as a physics simulation to separate overlapping items in an infinite strip, our modification introduces two critical constraints:

A. Square Bin Topology vs. Strip Packing

• Original Sparrow: Optimizes for Strip Packing. It assumes infinite height and pushes items upwards/outwards to minimize total used length.
• SquareTree Mod: Optimizes for Bin Packing. We enforce hard boundary constraints on a fixed square. The fitness function is rewritten to penalize boundary violations as heavily as item overlaps, forcing the population to optimize for aspect ratio preservation rather than uni-directional compaction.

B. Hybrid Initialization (Seed vs. Dust)

• Standard Random Init: Agents start at random coordinates. They must spend thousands of iterations just finding a valid non-overlapping state, often settling into a loose, semi-ordered glass-like texture.
• Pre-Loaded Configuration: We feed the algorithm a "Crystallized Core" -- a dense, mathematically generated lattice derived from the eigen-directions.
• The Benefit: The "Explorers" (producers) in the algorithm don't waste cycles finding a valid state; they start in a valid, ultra-high-density state.
• The Result: The algorithm is repurposed from "search" to "relaxation." It performs micro-adjustments to the lattice, allowing the crystal to "breathe" and accommodate imperfections without losing its global structure.

3. The Optimization Pipeline

Figure 2: The "DoubleTree" lattice generation. The vectors shown represent the pre-computed eigen-directions used to seed the initial crystallized core.

The solver follows a strict thermodynamic-style process:

1. Crystallization: Generate a "DoubleTree" lattice using eigen-directions.
2. Seeding: Inject this lattice into the Modified Sparrow engine as the population.
3. Optimisation: Freezes eigen-directions for 75-90% of polygons and runs modified sparrow solver for square packing.
4. Relaxation and defect curing: Use scipy.optimize (L-BFGS-B) to "melt" the crystal slightly, allowing shapes to drift off their lattice points just enough to resolve overlaps while maintaining the global structure.

---

🚀 Key Features

• Pre-Computed Geometry: Solves for optimal interlocking vectors before placement begins.
• Square-Bin Sparrow: Custom SSA implementation with boundary-enforced fitness functions.
• Hyperscale Compute: Serverless MPP pipeline dispatching thousands of vCPUs via GCP Batch.
• Physics-Based Relaxation: "Melt and refreeze" strategy to resolve microscopic overlaps to machine precision.

---

🏗️ Cloud Architecture

Figure 3: System design. We use cheap spot instances and Cloud Batch Jobs to run 100s of optimisations in parallel. Overall cost is approx $1.6 for 167 core-hours (10 min/task, 5 tasks/solution)

The system operates as a distributed batch processing pipeline.

1. Orchestration: The run_epoch.sh script stages local JSON configurations and uploads them to a uniquely versioned GCS bucket.
2. Execution: Google Cloud Batch spins up c3d-highcpu-4 Spot instances. A Docker container pulls the inputs, runs the solver (Rust/C++ binary), and writes results.
3. Synchronization: The sync_epoch.py utility downloads results, parses successful optimizations, and merges them into a master CSV for analysis.

---

📂 Project Structure

The codebase is organized to separate infrastructure from geometric logic.

operation-lattice/
├── configs/                   # Generated JSON payloads
├── notebooks/                 # EDA and Lattice visualization
├── scripts/
│   ├── deploy_infra.sh        # Infrastructure setup (APIs, Buckets, AR)
│   ├── run_epoch.sh           # Main batch dispatch script
│   └── set_env.sh             # Environment variables (Region, Project ID)
├── sync_epoch.py
├── generate_solution.py
├── validate_submission_v2.py  # Shapely intersection checks
└── README.md

---

⚡ Quick Start

1. Dev Environment Setup

Ensure you have the Google Cloud SDK installed and authenticated.

1. Clone the repository

git clone https://github.com/akaliutau/square-tree.git
cd square-tree

2. Create and activate a Conda environment

conda create -n squaretree python=3.10 -y
conda activate squaretree

3. Install dependencies

pip install -r requirements.txt

Set environment variables

source scripts/set_env.sh

2. Infrastructure Deployment

Initialize the required GCP services (Batch, Artifact Registry, GCS Buckets).

./scripts/deploy_infra.sh

3. Build & Push Container

Build the solver image and push it to the Google Artifact Registry.

IMAGE_URI="$REGION-docker.pkg.dev/$PROJECT_ID/$REPO_NAME/$IMAGE_NAME:latest"
sudo docker build -t $IMAGE_URI .
gcloud auth configure-docker us-central1-docker.pkg.dev
sudo docker push $IMAGE_URI

One can test image locally before deploying to registry:

sudo docker run --rm \
  -v /square-trees/configs:/mnt/share/inputs \
  -v /square-trees/results_data:/mnt/share/outputs \
  -e BATCH_TASK_INDEX=0 \
  -e SEED=23 \
  -e EXPLORE=100 \
  -e COMPRESS=100 \
  $IMAGE_URI

4. Run an Epoch

Dispatch a batch job. The script handles input staging and job submission.

# Usage: ./run_epoch.sh <EPOCH_ID> [CONFIG_DIR]
./scripts/run_epoch.sh 1 ./configs/experiment_alpha

5. Sync Results

Pull the processed data back to your local machine for analysis.

python scripts/sync_epoch.py 1

---

📊 Optimization & Validation

The project includes a rigorous validation pipeline validate_subm2.py. It employs a multi-stage check:

1. Broad Phase: Uses shapely.strtree for rapid bounding box intersection detection.
2. Narrow Phase: Performs exact polygon intersection checks.
3. Solver: If overlaps exist, it triggers scipy.optimize.minimize with L-BFGS-B to nudge polygons into valid positions, penalizing movement and rotation.

---

📜 License

Distributed under the MIT License. See LICENSE for more information.

---

Note: This project utilizes Google Cloud Spot instances. Ensure your quota for c3d-highcpu-4 is sufficient in the target region.