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 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.