Packing problems on generalised regular grid: Levels of abstraction using integer linear programming

Abstract

Packing a designated set of shapes on a regular grid is an important class of operations research problems that has been intensively studied for more than six decades. Representing a d-dimensional discrete grid as Zd, we formalise the generalised regular grid (GRG) as a surjective function from Zd to a geometric tessellation in a physical space, for example, the cube coordinates of a hexagonal grid or a quasilattice. This study employs 0-1 integer linear programming (ILP) to formulate the polyomino tiling problem with adjacency constraints. Rotation & reflection invariance in adjacency are considered. We separate the formal ILP from the topology & geometry of various grids, such as Ammann-Beenker tiling, Penrose tiling and periodic hypercube. Based on cutting-edge solvers, we reveal an intuitive correspondence between the integer program (a pattern of algebraic rules) and the computer codes. Models of packing problems in the GRG have wide applications in production system, facility layout planning, and architectural design. Two applications in planning high-rise residential apartments are illustrated.

Keywords

• Integer programming
• Packing problem
• Layout planning
• Quasilattice
• Adjacency