{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/9029"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/9029","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"UNIMODULARITY IN SOLVING ILP MODELS OF THE GLOBAL ROUTING PROBLEM","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>","abstract_html":"&lt;p&gt;The global routing problem is becoming more and more important in the design of today&#x27;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 (&lt;em&gt;Pc&lt;/em&gt;), the Lagrange dual (&lt;em&gt;Dc&lt;/em&gt;), and the unimodular (&lt;em&gt;PI&lt;/em&gt;) formulation. At optimality, all three problems have the same objective value. A new way to tackle the LP problem is introduced: first solve the &lt;em&gt;Dc&lt;/em&gt; and try to find Lagrange multipliers in order to build the &lt;em&gt;PI&lt;/em&gt; model, from which an integer solution can be obtained directly. An implementation based on the discussed approaches was tested using IBM benchmarks.&lt;/p&gt;","abstract_has_math":false,"creators":["Liu, Jessie Min Jing"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computational Engineering and Science","school":null,"contributors":[],"advisors":["Terlaky, Tamás","Deza, Antoine"],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-11-18T19:30:48Z","subjects":["Computational Engineering and Science","Computational Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/8468"],"render_values":[{"text":"https://doi.org/10.71548/8468","href":"https://doi.org/10.71548/8468","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4189","5207","2030196"],"render_values":[{"text":"opendissertations/4189","href":null,"code":true},{"text":"5207","href":null,"code":true},{"text":"2030196","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/9029","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/9029","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F9029","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Terlaky, Tamás","Deza, Antoine"]},{"key":"dc:contributor.department","label":"Department","values":["Computational Engineering and Science"]},{"key":"dc:creator","label":"Author","values":["Liu, Jessie Min Jing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T16:45:12Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T16:45:12Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2011-05-25"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Engineering and Science","Computational Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4189","5207","2030196"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/9029","https://doi.org/10.71548/8468"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<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>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Applied Science (MASc)"]},{"key":"dc:title","label":"Title","values":["UNIMODULARITY IN SOLVING ILP MODELS OF THE GLOBAL ROUTING PROBLEM"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Terlaky, Tamás","Deza, Antoine"],"dc:contributor.department":["Computational Engineering and Science"],"dc:creator":["Liu, Jessie Min Jing"],"dc:date.accessioned":["2014-06-18T16:45:12Z"],"dc:date.available":["2014-06-18T16:45:12Z"],"dc:date.created":["2011-05-25"],"dc:date.issued":["2009"],"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>"],"dc:description.degree":["Master of Applied Science (MASc)"],"dc:identifier.other":["opendissertations/4189","5207","2030196"],"dc:identifier.uri":["http://hdl.handle.net/11375/9029","https://doi.org/10.71548/8468"],"dc:subject":["Computational Engineering and Science","Computational Engineering"],"dc:title":["UNIMODULARITY IN SOLVING ILP MODELS OF THE GLOBAL ROUTING PROBLEM"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:30:48Z"}