VLSI (Very Large Scale Integration) refers to the problem of placing a set of rectangular circuits of fixed height and width onto a silicon plate of width W in such a way that the plate’s final height H is minimized. This problem has become central in latter years, allowing modern smartphones to be small enough to carry comfortably around but to still contain a touchscreen, more than one camera and many other useful sensors (accelerometer, gyroscope, pedometer, temperature and lighting sensors, etc..). Note that in the precise application we are considering, rotation is not allowed. This is due to the fact that - in order for a device to work properly - each circuit should be placed with a fixed orientation with respect to the others. However, I still briefly explored how to modify our model in order to support rectangle rotation, abstracting away the details of the practical application we started from.

This project was realized for the Combinatorial Decision Making and Optimization course of my Master's degree in Artificial Intelligence and the problem was solved using two different approaches, Constraint Programming and Satisfiability Modulo a Theory. An example of the output of this work is shown below.

A detailed explaination of how to run the MiniZinc code for the CP approach can be found here, while that for the SMT approach - which uses the Python library Z3Py - can be found here.