Welcome to the Optimization Framework — a modular, extendable, and performance-focused system for solving complex combinatorial optimization problems using intelligent algorithmic strategies.
At its core, this project was more than just a course assignment — it was a chance to build a general-purpose optimization engine that combines powerful techniques with real-world visualization and testing capabilities. Whether you’re exploring classic Greedy logic or experimenting with Simulated Annealing, this framework lays the groundwork for scalable and reusable algorithmic exploration.
It was also a lot of fun to implement this, which is why the documentation is so thorough at this point.
Currently, the framework supports the Rectangle Packing Problem, complete with:
- 🔁 Multiple optimization strategies (Greedy, Local Search, Backtracking, Simulated Annealing)
- 🎨 A user interface for configuration and visualization
- 🧪 A test environment for performance evaluations
And it's designed to grow — just implement a new problem’s logic and plug into the existing algorithm architecture in base_classes/algorithms.py.
This project was developed as part of the "Optimization Algorithms" course taught by Prof. Dr. Karsten Weihe at TU Darmstadt.
The full problem description is available in the included OptAlg.pdf.
The primary challenge: implement generalized optimization algorithms and use them to solve a rectangle packing problem under multiple constraints — both computational and visual.
- Implement Greedy and Local Search with three distinct neighborhoods
- Ensure algorithm implementations remain problem-agnostic
- Enable visual interaction and flexible testing for different configurations
The framework includes four implemented strategies:
- Selects rectangles using one of four rules (e.g., largest area first, smallest aspect ratio first)
- Places rectangles accordingly, without revisiting prior placements
- Fast and simple, ideal for generating quick base solutions
- Geometry-based: Rectangles are physically moved across boxes or inside their current box
- Rule-based: Treats solutions as permutations and tweaks rectangle orderings
- Overlap-tolerant: Allows overlaps initially and progressively removes them to improve layout
Each neighborhood brings its own strengths and allows deeper exploration of the solution space.
- Probabilistically accepts worse solutions to escape local optima
- Cools down gradually using customizable parameters
- Uses geometry-based neighborhood for generating candidate states
- Classic recursive placement with backtracking when no valid configuration is found
- Best suited for smaller instances or educational comparison
A flexible evaluation function assesses:
- Number of used boxes
- Space utilization
- Unused space
- Overlapping areas
The goal? Minimize the score:
Python isn’t always fast — but we took care to squeeze performance where it counts:
- NumPy for vectorized computations and overlap detection
- Numba (njit) to compile bottleneck functions to native machine code
- Used especially in
find_valid_placement()with occupancy grids and integral images
- Used especially in
- Custom deep copy utilities (faster than
copy.deepcopy) - Integral image optimizations for O(1) spatial queries
Result: up to 1000 rectangles packed in under 10 seconds — and often, the solutions are visually near-optimal.
We built a basic but functional UI for:
- Generating rectangle datasets
- Selecting algorithms and neighborhood types
- Comparing runs and replays
- Visualizing packing layouts
Usability matters — even if it's tkinter. Contrast, clarity, and ease of experimentation were key goals.
The test environment runs batch simulations to evaluate algorithm robustness.
Features:
- Fully parameterized: number of rectangles, instance size, box dimensions
- Two modes: quick test (few small instances) and heavy test (large, challenging inputs)
- Generates runtime protocols and output summaries
# 1. Install dependencies
pip install -r requirements.txt
# 2. Launch the main GUI
python main.py
# 3. Run the test suite
python test_env.py
# 4. Review solution outputs
python solution_viewer.pyThis project is a good foundation to build up on. These are some ideas we had, this might go to in the future:
- more optimization problems: use this repo as a launchpad for scheduling, routing, or knapsack variants.
- more algorithms: generic algorithms for genetic algos or maybe cp
- smarter memory usage: cache and reuse calculations like integral images
- cleaner architecture: resolve circular import issues, enfore stricter modularity
- ui upgrades: this was the first time we used tkinter excessively, so maybe we can think of some improvements with PyQt or web-based visualization.
- Export Icon: Chanut - Flaticon
- Import Icon: Ferdinand - Flaticon
- Zoom-In Icon: Stasy - Flaticon
- Zoom-Out Icon: nahumam - Flaticon
This project is a blend of theory and practical algorithm design. It's been a rewarding way to apply what we've learned in optimiziation, performance tuning, and user-centric design. We are eager to see where this goes next, as soon as we have time of course.
Pull requests, ideas or new problem types are more than welcome!