Advanced search
Start date

Mathematical models and algorithmic study for rectangle escape problems

Grant number: 15/06975-9
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): June 01, 2015
Effective date (End): November 30, 2015
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Cid Carvalho de Souza
Grantee:Allan Sapucaia Barboza
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


In this project, we study integer linear programming formulations and heuristics for the Rectangle Escape Problems, that arise in integrated circuit design. Given a rectangular base board and components represented by rectangles with axes parallel to the board, we want to connect the components to the bus located in the board edges. This connection is made by projecting one of the component sides towards one of the edges. The density at a point on the board is defined as the number of extended rectangles that contain the point. Two problems are defined. In the first, we want to connect all components minimizing the maximum density and in the second we want to connect the most components respecting a fixed maximum density. Both problems are NP-hard. Our goal is to investigate these problems through a polyhedral study leading to an exact algorithm and developing heuristics, analyzing these alternatives empirically using a benchmark that should be available in the public domain. Furthermore, we intend to develop a graphical interface to visualize instances and evaluate the solutions generated by the implemented algorithms.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: