Solving the Partridge square packing problem using MiniZinc
14 days ago
- #minizinc
- #packing-problem
- #combinatorial-optimization
- The Partridge Packing Problem involves packing squares of varying sizes into a larger square, with sizes from 2 to 33 known to have solutions.
- MiniZinc is used to model and solve the problem, with initial models being inefficient but improved through implied and symmetry-breaking constraints.
- Key improvements include exact fill constraints and restrictions on edge placements, significantly reducing solving time.
- OR-Tools CP-SAT performs best among solvers tested, solving sizes up to 11, while specialized solvers like SICStus show promise with custom implementations.
- The problem illustrates the importance of model refinement and solver selection in combinatorial optimization.