Back to search

McMaster University

UNIMODULARITY IN SOLVING ILP MODELS OF THE GLOBAL ROUTING PROBLEM

Abstract

dc:description.abstract

<p>The global routing problem is becoming more and more important in the design of today's integrated circuits. A small chip may contain up to millions of components and wires. Although global routing can be formulated as an integer linear programming problem, it is hard to solve directly using currently available solvers. We discuss a relaxation of the problem to a linear programming (LP) formulation with a fractional solution. However, the relaxation yields an NP-hard problem. In this thesis, we introduce three relaxations: the primal (<em>Pc</em>), the Lagrange dual (<em>Dc</em>), and the unimodular (<em>PI</em>) formulation. At optimality, all three problems have the same objective value. A new way to tackle the LP problem is introduced: first solve the <em>Dc</em> and try to find Lagrange multipliers in order to build the <em>PI</em> model, from which an integer solution can be obtained directly. An implementation based on the discussed approaches was tested using IBM benchmarks.</p>

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Jessie Min Jing
Advisors dc:contributor.advisor
  • Terlaky, Tamás
  • Deza, Antoine

Subjects

dc:subject × 2

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/4189
5207
2030196

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Liu, Jessie Min Jing. UNIMODULARITY IN SOLVING ILP MODELS OF THE GLOBAL ROUTING PROBLEM. 2009. http://hdl.handle.net/11375/9029