Optimising LEGO constructions

Given any 3D layout, how can you build it with a set of LEGO bricks? Relatively few bricks open up for a colossal amount of possible brick combinations. Here we limit ourselves to consider a predefined outer shape made by a designer that also specifies which colours to use. The inner shape, on the other hand, can be constructed as desired as long as the construction is stable. There are several objectives to optimise in this problem The structural stability, the cost of bricks and the aesthetics. Here we describe an approach to optimise LEGO constructions using metaheuristics. A prototype of the software has been developed, which provided stable constructions for small models. Other approaches in the literature have focused on Local Search algorithms, which we believe limits the search space significantly. Currently we are working on applying various advanced techniques in Operations Research to make the metaheuristic more efficient in order to apply it on larger models.