Keeltide

Pack the block. Beat the clock.

Comment

Inspiration

In a shipyard, every giant section of a ship.. a "block", is built inside a fixed workspace called a bay. Deciding where each block sits, how it's rotated, and when it enters and leaves, all while a single overhead crane lowers and lifts blocks without hitting anything, and while deadlines loom.. is a brutal blend of 2D packing and scheduling.

The Optimization Grand Challenge 2026 captured it perfectly: "Pack the Block, Beat the Clock." What pushed us further was the provided baseline: it solved only 9 of 20 instances and even ran 223 seconds on a 60-second budget. We wanted a solver that is always feasible, always on time, and genuinely good, and a way to actually see it work. That became Keeltide.

What it does

Keeltide decides, for every block: which bay, its position (x, y), its orientation, and its entry/exit days, minimizing a weighted blend of tardiness + bay-load imbalance + bay-preference penalty, while guaranteeing crane access, zero collisions, and bay-boundary fit.

  1. It ingests a problem instance (bays + blocks with shapes, release/due dates, workloads, preferences).
  2. It produces a fully feasible plan for all blocks within a wall-clock time limit.
  3. A React + Three.js visualizer animates the bays day-by-day, with a Gantt timeline, a live objective breakdown, and a baseline-vs-ours compare view.

On the 20 training instances it is feasible 20/20 (baseline: 9/20) and 64–98% better on every comparable instance.

How we built it

  1. Feasible-by-construction packing (Python): within a bay, blocks that are present at the same time are given disjoint footprints.. so crane access, collisions, and boundaries are satisfied structurally, with no fragile repair loop.
  2. Best-of multi-start: we construct from both the classic Earliest-Due-Date order and a learned ML ordering policy, and keep whichever is better.
  3. Large Neighborhood Search: GRASP-randomized destroy-and-reinsert over the layout, scored by a Shapely-free objective so thousands of moves fit in the budget.
  4. CP-SAT (OR-Tools): an exact disjunctive-scheduling pass that re-times the layout optimally as a final polish.
  5. ML policy (PyTorch, REINFORCE, trained on Google Colab): a small network scores blocks to choose the placement order; it plugs in as a non-harmful seed.
  6. Visualizer: React + Vite + Three.js, 2D top-view with the real polygons, an orbitable 3D view, a time scrubber, a Gantt, and the compare mode.

Challenges we ran into

  1. The crane-feasibility trap: the baseline placed blocks and then tried to repair violations, which neither converged nor respected the time limit. We flipped the whole approach to feasible-by-construction.
  2. Integer rounding: the official judge rounds coordinates to integers. We place at exact integer reference points with a 1-unit safety gap, so footprint disjointness survives rounding.
  3. The ML bottleneck: the placement simulator is pure-Python and CPU-bound, so the GPU barely helps. We built a slim bbox-only dataset and a fast arithmetic objective so training and iteration stay practical.
  4. Knowing when to stop optimizing: CP-SAT proved the per-layout timing was already near-optimal, so the real lever was the layout and the learned seed, not more scheduling effort.

Accomplishments that we're proud of

  1. 20/20 feasible vs the baseline's 9/20, 64–98% lower objective, and never overrunning the time budget.
  2. ML that genuinely helps: the learned policy lifts the solver +11.6% overall and −87% on prob_1, with zero regressions (it's strictly best-of).
  3. A presentation-grade visualizer whose baseline-vs-ours compare makes the improvement undeniable at a glance.

What we learned

  1. Design the constraint away, don't repair it: structural feasibility is far more robust than fixing violations after the fact.
  2. Find the real bottleneck: CP-SAT showed timing was solved, which redirected our effort to the layout instead of over-tuning the wrong stage.
  3. ML as a seed, not a replacement : when a strong classical solver already exists, a learned policy used as a best-of multi-start can only help, which is the right risk profile.

What's next for Keeltide

  1. Neural-LNS: learn which blocks to destroy and re-pack.. higher upside than learning the order.
  2. Stronger policy: longer training with richer features and an attention encoder over blocks.
  3. Wider reach: a geometric MIP for small instances, and a public deployment of the visualizer.

Built With

Share this project:

Updates