RecPac is a Python project that implements and compares several optimization algorithms for the rectangle packing problem.
The repository includes:
- Multiple optimization strategies (Greedy, Local Search, Backtracking, Simulated Annealing)
- A simple graphical interface for configuration and visualization
- A test environment for running structured performance evaluations
The codebase is designed to be extensible. New problems can be integrated by implementing their logic and connecting them to the algorithm framework in base_classes/algorithms.py.
This project was developed as part of the course Optimization Algorithms taught by Prof. Dr. Karsten Weihe at TU Darmstadt.
A detailed problem description can be found in OptAlg.pdf.
The goal of this project is to implement general-purpose optimization algorithms and apply them to a constrained rectangle packing problem.
Key aspects include:
- Implementation of Greedy and Local Search approaches with multiple neighborhood definitions
- Separation between algorithm logic and problem-specific details
- Support for experimentation through visualization and configurable test scenarios
The framework currently includes four approaches:
A constructive method that places rectangles sequentially based on predefined selection rules (e.g., largest area first). It is computationally efficient and serves as a baseline for other methods.
An iterative improvement approach using three neighborhood definitions:
- Geometry-based: modifies positions of rectangles within or across boxes
- Rule-based: adjusts the ordering of rectangles
- Overlap-tolerant: allows temporary overlaps and resolves them over time
These variants enable exploration of different regions of the solution space.
A stochastic extension of local search that accepts worse solutions with a decreasing probability. This helps avoid local optima and improves solution quality over time.
A recursive exact method that explores feasible placements exhaustively. Due to its complexity, it is primarily suitable for smaller instances or comparison purposes.
Solutions are evaluated using a weighted objective function that considers:
- Number of used boxes
- Space utilization
- Unused space
- Overlapping area
Score = (w1 * numBoxes) + (w2 * (1 - utilization)) + (w3 * unusedSpace) + (w4 * totalOverlapArea)
The objective is to minimize the overall score.
Several optimizations were implemented to improve runtime performance:
- Use of NumPy for vectorized operations and overlap checks
- Numba (
njit) to compile performance-critical functions - Custom deep copy utilities to reduce overhead
- Integral image techniques for constant-time spatial queries
These measures allow the system to handle instances with up to ~1000 rectangles within a reasonable runtime.
A Tkinter-based interface is provided for:
- Generating problem instances
- Selecting algorithms and parameters
- Visualizing packing results
- Comparing different runs
The interface is intentionally simple but sufficient for experimentation and demonstration.
The test environment supports batch evaluation of algorithm performance.
Features include:
- Configurable instance generation (size, number of rectangles, box dimensions)
- Multiple test modes (quick vs. larger-scale runs)
- Generation of runtime logs and result summaries
# Install dependencies
pip install -r requirements.txt
# Launch the GUI
python main.py
# Run test environment
python test_env.py
# View saved solutions
python solution_viewer.pyThis project provides a working foundation, but several areas could be extended:
- Support for additional optimization problems (e.g., scheduling, routing, knapsack variants)
- Implementation of further algorithms (e.g., genetic algorithms, constraint programming approaches)
- Improved memory handling and caching of intermediate computations
- Refactoring to simplify dependencies and improve modularity
- Enhancements to the user interface (e.g., migration to PyQt or a web-based frontend)
- Export icon: Chanut (Flaticon)
- Import icon: Ferdinand (Flaticon)
- Zoom-in icon: Stasy (Flaticon)
- Zoom-out icon: nahumam (Flaticon)
This project was primarily developed as a practical exercise alongside coursework. It serves both as an implementation of standard optimization techniques and as a small experimental framework for comparing them.
Contributions and suggestions are welcome.