From 5 Seconds to 1.2 Milliseconds: Rewriting a Combinatorial Optimizer with GitHub Copilot

This is a submission for the GitHub Finish-Up-A-Thon Challenge

What I Built

Cijene ("Prices") is Croatia's premier open-source grocery price tracker and shopping cart optimizer, designed to help families fight double-digit inflation. It began as a hackathon prototype that won first place at a national software development competition in Croatia, built under high-pressure, 24-hour constraints. Since then, it has evolved into a production-ready application that serves thousands of Croatian families, allowing them to track, compare, and optimize their grocery expenses.

The core innovation of Cijene is its Košarica (Smart Shopping Cart Optimizer). Instead of simply comparing prices item-by-item, Cijene optimizes a user's entire shopping list across all major Croatian grocery chains (including Konzum, Lidl, Spar, Kaufland, Plodine, Tommy, Studenac, Eurospin, Metro, Žabac, Vrutak, Ribola, and NTL) based on their geographical location, search radius, and shopping preferences.

Users can choose between three optimization modes:

1. Greedy: Prioritizes the absolute lowest cost, even if it requires visiting up to 5 different stores.
2. Balanced: Strikes a perfect trade-off between savings and travel convenience.
3. Conservative: Minimizes travel distance and the number of stores visited, selecting the closest stores that offer reasonable prices.

By refactoring the backend API and redesigning the core cart optimizer from the ground up, we turned a struggling prototype into a highly scalable, enterprise-grade system capable of handling concurrent production traffic.

---

Demo

Below you will find the links, interactive video walkthrough, and screenshots demonstrating Cijene's live optimization engine, user interface, and real-time savings calculations.

• Live Application: cijene.netlify.app
• GitHub Repository: github.com/karilca/Cijene-CroatianGroceryPrices-english
• Video Walkthrough: YouTube Video Walkthrough (English subtitles available)

Screenshots

• Interactive Cart View: Users build their shopping list with real-time autocomplete suggestions
• Optimization Results: Detailed breakdown of which items to buy at Konzum, Lidl, or Spar to maximize savings, complete with Haversine-computed distances.
• Dynamic Alternatives: Live side-by-side comparison of Greedy, Balanced, and Conservative modes.

---

The Comeback Story

The Prototype's Bottleneck

In the original competition prototype, the Python API service struggled under even minor loads. The shopping cart calculation function was a massive performance bottleneck. The old algorithm utilized a naive exact solver: to optimize a cart of $N$ items across $S$ nearby stores, it generated and evaluated every single combination of stores up to size $K$ (where $K \le 5$ ).

In a dense urban area like Zagreb, with 28+ stores within a 15 km radius and a store limit of 5, the number of combinations exploded to:

$$\binom{28}{1} + \binom{28}{2} + \binom{28}{3} + \binom{28}{4} + \binom{28}{5} = 28 + 378 + 3,276 + 20,475 + 98,280 = 122,437 \text{ subsets}$$

For every single combination, the prototype:

1. Iterated through all products in the cart.
2. Queried nested Python dictionaries using string-hashed keys (e.g., product_prices.get(store_id)) to check availability and find the minimum price.
3. Evaluated whether the combination could fully satisfy the cart.
4. Serialized and sorted assignments using string representation keys like signature = tuple((product_id, assignment[product_id]) for product_id in sorted(assignment)) to eliminate duplicate solutions.

This approach resulted in massive memory allocation overhead, excessive garbage collection cycles, and CPU starvation. A simple 10-item cart in a dense area took 2 to 5 seconds to execute. Under concurrent user traffic, this synchronous blocking behavior quickly led to request timeouts and server crashes.

The Production-Ready Architecture

To transition the prototype to a production-grade system, we refactored the backend into a highly optimized, asynchronous architecture. The optimization pipeline was completely rewritten to incorporate advanced algorithms and data structures:

1. Combinatorial Pruning via Mandatory Stores

The optimizer now begins with a pre-analysis pass that scans the cart items and identifies "mandatory stores"—stores that are the only option within the user's radius for at least one item. If the number of mandatory stores exceeds the user-configured store limit ( $M > K$ ), the algorithm immediately exits. Otherwise, those $M$ stores are fixed, and we only generate combinations of size $K - M$ from the remaining non-mandatory stores.

For instance, if $M = 2$ and $K = 5$ , we only need to choose 3 additional stores from the remaining 26 non-mandatory options:

$$\binom{26}{3} = 2,600 \text{ combinations}$$

This single architectural shift reduced the combinatorial search space from 98,280 to 2,600—a 97.4% reduction in iterations.

2. Bitmask Set Cover Pre-check

Rather than verifying cart feasibility in a nested loop using dictionary lookups, we mapped each product in the cart to a specific bit index in an integer (e.g., product $i$ corresponds to 1 << i).

• Each store's inventory is precompiled into a single integer bitmask.
• For any candidate subset of stores, we compute the union of their inventories using a fast bitwise OR.
• We perform a bitwise check: if subset_mask != target_mask: continue. If a subset is infeasible, the check fails in a single CPU cycle, completely skipping expensive price calculations.

3. Pre-indexed Price Matrix and Distance Caches

We replaced nested string-hashed dictionary lookups in the hot loop with contiguous memory structures. Store prices are now pre-indexed into a flat tuple of floats where the position corresponds to the product's index in the cart. Finding the best price for product $i$ in a store subset is now a direct array lookup:

price = store_prices_indexed[store_id][i]

This is an $O(1)$ operation that bypasses Python's dictionary hashing overhead entirely. Furthermore, store distances are pre-cached in a flat dictionary (store_distances) to prevent redundant distance recalculations.

4. Dominated Store Pruning with Early Breaks

In _prune_dominated_stores, stores are sorted by distance first. For any two stores $A$ and $B$ , if store $B$ is further away than store $A$ and does not offer a better price for any product, $B$ is pruned as "dominated." Because the stores are sorted by distance, the algorithm breaks out of the loop early the moment distance_b > distance_a, saving thousands of redundant iterations.

5. Heuristic Fallback with 2-Opt Local Swap Search

When the number of stores after pruning still exceeds the enumeration limit (enum_store_limit = 12), exact enumeration is bypassed in favor of a heuristic solver (_heuristic_optimize). The heuristic:

1. Ranks candidate stores based on product coverage and potential savings.
2. Builds a greedy initial solution by iteratively adding stores that cover the most remaining items.
3. Performs a 2-Opt local search (_improve_candidate_by_swaps), iteratively swapping active stores with high-ranking pool stores to minimize the multi-objective score (cost, distance, store count). This heuristic solver guarantees a near-optimal recommendation in less than 5 milliseconds.

6. Location-Grid Cache Bucketing

To protect the backend from duplicate queries, we implemented CartOptimizeCache using Redis and an in-memory TTL fallback. To ensure high cache hit rates for geographic queries, we implemented location bucketing. Instead of caching on raw GPS coordinates, we round latitude and longitude to a configurable grid (~200 meters):

def _bucket_coordinate(latitude: float, longitude: float) -> tuple[float, float]:
    lat_step = bucket_size_m / 111_320.0
    lon_scale = max(0.01, cos(radians(latitude)))
    lon_step = bucket_size_m / (111_320.0 * lon_scale)
    return (round(round(latitude / lat_step) * lat_step, 6), round(round(longitude / lon_step) * lon_step, 6))

If multiple users in the same neighborhood search for the same cart items, they hit the cache even if their exact coordinates differ by a few meters.

7. Dynamic Tuning via Feedback Loops

To align recommendations with actual user behavior, we added a feedback endpoint (POST /v1/cart/optimize/feedback) and run tracking database tables. If the user acceptance rate for a particular optimization mode falls below a threshold (e.g., 25% over a 30-day window), the system dynamically adjusts the weights (cost, distance, store count) in $\pm 0.05$ increments, automatically fine-tuning the algorithm to user preferences over time.

---

My Experience with GitHub Copilot

GitHub Copilot acted as an expert pair programmer throughout the refactoring process. It didn't just write boilerplate code; it helped redesign our core data structures and mathematical models.

Here is how Copilot accelerated our development and achieved the 1000x speedup:

1. Suggesting the Bitmask Optimization

While explaining the bottleneck of the subset feasibility check to Copilot, it suggested mapping the cart items to a bitmask and utilizing bitwise operations for set cover evaluation. It generated the code to transform our complex product lists into bitwise integers:

product_to_bit = {item.product_id: (1 << idx) for idx, item in enumerate(cart_items)}
target_mask = (1 << num_products) - 1

This suggestion eliminated the slow set-union logic and replaced it with ultra-fast bitwise math, reducing the feasibility checking time to near-zero.

2. Designing the Heuristic Swap Solver

When writing the heuristic solver for large store sets, Copilot co-authored the 2-opt local search swap loop (_improve_candidate_by_swaps). It perfectly implemented the logic to remove a store from the active subset, find the best replacement candidate from the ranked pool, evaluate if the swap improved the multi-objective utility score, and apply the swap. This ensured that even when falling back to the heuristic solver, our recommendation quality remained exceptionally high.

3. Creating the Benchmarking Suite

To verify the performance improvements, Copilot helped write cart_optimizer_benchmark.py. The tool generates mock shopping carts, simulates store coordinates, assigns randomized prices, and benchmarks the latency and quality gap between the exact and heuristic solver across different optimization modes.

Running this benchmark confirmed:

• Latency Reduction: Average computation time dropped from over 2,000 ms in the prototype to 1.2 ms in the refactored version (a 1,600x speedup).
• Quality Preservation: The heuristic solver achieved a median cost gap of 0.000% compared to the exact solver, meaning users receive virtually identical savings recommendations in a fraction of the time.

4. Database Query Optimization

Copilot analyzed our database interaction layer (psql.py) and identified a sub-optimal SQL join. It suggested refactoring the product price query to target the primary key index prices.store_id directly instead of referencing the outer joined stores.id. This simple suggestion cut database query latency in half, allowing the API to fetch price matrices for large carts in under 15 ms.

Conclusion

With GitHub Copilot, we successfully converted a slow hackathon prototype into a highly optimized, production-ready backend. Cijene now runs on a lean, asynchronous stack that provides real-time grocery savings recommendations to thousands of users, proving that with the right tools, even complex combinatorial problems can be optimized to run in milliseconds.

Comments

[Karlo Kolak]

Thanks for stopping by to read this post!