Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computat...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2002-02, Vol.91 (3), p.563-588
Main Authors: ANSTREICHER, Kurt, BRIXIUS, Nathan, GOUX, Jean-Pierre, LINDEROTH, Jeff
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assignment problem
Distributed processing
Eigenvalues
Exact sciences and technology
Linear programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Optimization
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c358t-e1d1c32bc47f74f8b1004aa062d436c7e9e07b4af42f9ded71d13714925b6ee93
cites
container_end_page 588
container_issue 3
container_start_page 563
container_title Mathematical programming
container_volume 91
creator ANSTREICHER, Kurt
BRIXIUS, Nathan
GOUX, Jean-Pierre
LINDEROTH, Jeff
description The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported.
doi_str_mv 10.1007/s101070100255
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_232852112</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>703727541</sourcerecordid><originalsourceid>FETCH-LOGICAL-c358t-e1d1c32bc47f74f8b1004aa062d436c7e9e07b4af42f9ded71d13714925b6ee93</originalsourceid><addsrcrecordid>eNpVkE1LxDAQhoMoWFeP3oPgsZpJ0qY96uIXLHhQzyVNk9KlbbqZVvDfm2UXxMMwMDzz8vAScg3sDhhT9wgMmIrDeJadkASkyFOZy_yUJPtbmuXAzskF4pYxBqIoEvL44fvvbmxpr0Nr6W7RTdBzZ6hG7NpxsONMp-Dr3g5I_UiNH6ZljoQfdU_b0DV4Sc6c7tFeHfeKfD0_fa5f0837y9v6YZMakRVzaqEBI3htpHJKuqKOnlJrlvMmehplS8tULbWT3JWNbVTkhQJZ8qzOrS3FitwccqPPbrE4V1u_hKiBFRe8yDgAj1B6gEzwiMG6agrdoMNPBazat1T9aynyt8dQjUb3LujRdPj3JKUEEFL8AgRxZo8</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>232852112</pqid></control><display><type>article</type><title>Solving large quadratic assignment problems on computational grids</title><source>ABI/INFORM global</source><source>Access via Business Source (EBSCOhost)</source><source>Springer Nature</source><creator>ANSTREICHER, Kurt ; BRIXIUS, Nathan ; GOUX, Jean-Pierre ; LINDEROTH, Jeff</creator><creatorcontrib>ANSTREICHER, Kurt ; BRIXIUS, Nathan ; GOUX, Jean-Pierre ; LINDEROTH, Jeff</creatorcontrib><description>The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported.</description><identifier>ISSN: 0025-5610</identifier><identifier>EISSN: 1436-4646</identifier><identifier>DOI: 10.1007/s101070100255</identifier><identifier>CODEN: MHPGA4</identifier><language>eng</language><publisher>Heidelberg: Springer</publisher><subject>Algorithms ; Applied sciences ; Assignment problem ; Distributed processing ; Eigenvalues ; Exact sciences and technology ; Linear programming ; Mathematical programming ; Operational research and scientific management ; Operational research. Management science ; Optimization</subject><ispartof>Mathematical programming, 2002-02, Vol.91 (3), p.563-588</ispartof><rights>2003 INIST-CNRS</rights><rights>Copyright Springer-Verlag 2002</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c358t-e1d1c32bc47f74f8b1004aa062d436c7e9e07b4af42f9ded71d13714925b6ee93</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/232852112?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>309,310,314,780,784,789,790,11688,23930,23931,25140,27924,27925,36060,44363</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=14441134$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>ANSTREICHER, Kurt</creatorcontrib><creatorcontrib>BRIXIUS, Nathan</creatorcontrib><creatorcontrib>GOUX, Jean-Pierre</creatorcontrib><creatorcontrib>LINDEROTH, Jeff</creatorcontrib><title>Solving large quadratic assignment problems on computational grids</title><title>Mathematical programming</title><description>The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Assignment problem</subject><subject>Distributed processing</subject><subject>Eigenvalues</subject><subject>Exact sciences and technology</subject><subject>Linear programming</subject><subject>Mathematical programming</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Optimization</subject><issn>0025-5610</issn><issn>1436-4646</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2002</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNpVkE1LxDAQhoMoWFeP3oPgsZpJ0qY96uIXLHhQzyVNk9KlbbqZVvDfm2UXxMMwMDzz8vAScg3sDhhT9wgMmIrDeJadkASkyFOZy_yUJPtbmuXAzskF4pYxBqIoEvL44fvvbmxpr0Nr6W7RTdBzZ6hG7NpxsONMp-Dr3g5I_UiNH6ZljoQfdU_b0DV4Sc6c7tFeHfeKfD0_fa5f0837y9v6YZMakRVzaqEBI3htpHJKuqKOnlJrlvMmehplS8tULbWT3JWNbVTkhQJZ8qzOrS3FitwccqPPbrE4V1u_hKiBFRe8yDgAj1B6gEzwiMG6agrdoMNPBazat1T9aynyt8dQjUb3LujRdPj3JKUEEFL8AgRxZo8</recordid><startdate>20020201</startdate><enddate>20020201</enddate><creator>ANSTREICHER, Kurt</creator><creator>BRIXIUS, Nathan</creator><creator>GOUX, Jean-Pierre</creator><creator>LINDEROTH, Jeff</creator><general>Springer</general><general>Springer Nature B.V</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope></search><sort><creationdate>20020201</creationdate><title>Solving large quadratic assignment problems on computational grids</title><author>ANSTREICHER, Kurt ; BRIXIUS, Nathan ; GOUX, Jean-Pierre ; LINDEROTH, Jeff</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c358t-e1d1c32bc47f74f8b1004aa062d436c7e9e07b4af42f9ded71d13714925b6ee93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2002</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Assignment problem</topic><topic>Distributed processing</topic><topic>Eigenvalues</topic><topic>Exact sciences and technology</topic><topic>Linear programming</topic><topic>Mathematical programming</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Optimization</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>ANSTREICHER, Kurt</creatorcontrib><creatorcontrib>BRIXIUS, Nathan</creatorcontrib><creatorcontrib>GOUX, Jean-Pierre</creatorcontrib><creatorcontrib>LINDEROTH, Jeff</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Access via ABI/INFORM (ProQuest)</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM global</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Mathematical programming</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>ANSTREICHER, Kurt</au><au>BRIXIUS, Nathan</au><au>GOUX, Jean-Pierre</au><au>LINDEROTH, Jeff</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Solving large quadratic assignment problems on computational grids</atitle><jtitle>Mathematical programming</jtitle><date>2002-02-01</date><risdate>2002</risdate><volume>91</volume><issue>3</issue><spage>563</spage><epage>588</epage><pages>563-588</pages><issn>0025-5610</issn><eissn>1436-4646</eissn><coden>MHPGA4</coden><abstract>The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported.</abstract><cop>Heidelberg</cop><pub>Springer</pub><doi>10.1007/s101070100255</doi><tpages>26</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0025-5610
ispartof Mathematical programming, 2002-02, Vol.91 (3), p.563-588
issn 0025-5610
1436-4646
language eng
recordid cdi_proquest_journals_232852112
source ABI/INFORM global; Access via Business Source (EBSCOhost); Springer Nature
subjects Algorithms
Applied sciences
Assignment problem
Distributed processing
Eigenvalues
Exact sciences and technology
Linear programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Optimization
title Solving large quadratic assignment problems on computational grids
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T11%3A56%3A16IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Solving%20large%20quadratic%20assignment%20problems%20on%20computational%20grids&rft.jtitle=Mathematical%20programming&rft.au=ANSTREICHER,%20Kurt&rft.date=2002-02-01&rft.volume=91&rft.issue=3&rft.spage=563&rft.epage=588&rft.pages=563-588&rft.issn=0025-5610&rft.eissn=1436-4646&rft.coden=MHPGA4&rft_id=info:doi/10.1007/s101070100255&rft_dat=%3Cproquest_cross%3E703727541%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c358t-e1d1c32bc47f74f8b1004aa062d436c7e9e07b4af42f9ded71d13714925b6ee93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=232852112&rft_id=info:pmid/&rfr_iscdi=true