Advanced search
Start date
Betweenand

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
Principal Investigator:Cid Carvalho de Souza
Grantee:Allan Sapucaia Barboza
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

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.