IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v30y2018i2p295-308.html
   My bibliography  Save this article

Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study

Author

Listed:
  • Krešimir Mihić

    (Oracle Labs, Belmont, California 94002)

  • Kevin Ryan

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Alan Wood

    (Oracle Labs, Belmont, California 94002)

Abstract

This paper presents a new local search approach, called randomized decomposition (RD), for solving nonlinear, nonconvex mathematical programs. Starting from a feasible solution, RD partitions the problem’s decision variables into a randomly ordered list of randomly generated subsets. RD then optimizes over the variables in each subset, keeping all other variables fixed. Unlike most other decomposition methods, no knowledge of the problem structure is required. RD has been combined with a metaheuristic RDPerturb, for escaping local optima, to create a generic framework for solving mathematical programs, especially hard combinatorial nonconvex problems. The framework has been implemented as an optimization platform we call RDSolver and successfully applied to over 400 instances of the quadratic assignment problem (QAP). The results obtained by RDSolver are competitive with the solutions obtained by heuristics specially tailored for those problems, even though RDSolver is a general purpose mathematical programming solver. In addition to a strong performance on previously solved problems, RDSolver has found two new best known solutions and provided solutions to 68 large QAP problems for which no solutions have been previously reported.

Suggested Citation

  • Krešimir Mihić & Kevin Ryan & Alan Wood, 2018. "Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 295-308, May.
    • Handle: RePEc:inm:orijoc:v:30:y:2018:i:2:p:295-308
    DOI: 10.1287/ijoc.2017.0781
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2017.0781
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2017.0781?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    2. Gordon C. Armour & Elwood S. Buffa, 1963. "A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities," Management Science, INFORMS, vol. 9(2), pages 294-309, January.
    3. Drezner, Zvi, 2005. "The extended concentric tabu for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 160(2), pages 416-422, January.
    4. Stutzle, Thomas, 2006. "Iterated local search for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1519-1539, November.
    5. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    6. Zvi Drezner & Peter Hahn & Éeric Taillard, 2005. "Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods," Annals of Operations Research, Springer, vol. 139(1), pages 65-94, October.
    7. James, Tabitha & Rego, Cesar & Glover, Fred, 2009. "A cooperative parallel tabu search algorithm for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 810-826, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam, 2021. "Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1066-1084.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Paul, G., 2011. "An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 209(3), pages 215-218, March.
    2. James, Tabitha & Rego, Cesar & Glover, Fred, 2009. "A cooperative parallel tabu search algorithm for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 810-826, June.
    3. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam, 2021. "Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1066-1084.
    4. T. G. Pradeepmon & Vinay V. Panicker & R. Sridharan, 2021. "A variable neighbourhood search enhanced estimation of distribution algorithm for quadratic assignment problems," OPSEARCH, Springer;Operational Research Society of India, vol. 58(1), pages 203-233, March.
    5. Mădălina M. Drugan, 2015. "Generating QAP instances with known optimum solution and additively decomposable cost function," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 1138-1172, November.
    6. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    7. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    8. Stefan Helber & Daniel Böhme & Farid Oucherif & Svenja Lagershausen & Steffen Kasper, 2016. "A hierarchical facility layout planning approach for large and complex hospitals," Flexible Services and Manufacturing Journal, Springer, vol. 28(1), pages 5-29, June.
    9. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2015. "Solving the planar p-median problem by variable neighborhood and concentric searches," Journal of Global Optimization, Springer, vol. 63(3), pages 501-514, November.
    10. Mario Inostroza-Ponta & Regina Berretta & Pablo Moscato, 2011. "QAPgrid: A Two Level QAP-Based Approach for Large-Scale Data Analysis and Visualization," PLOS ONE, Public Library of Science, vol. 6(1), pages 1-18, January.
    11. Nyberg, Axel & Westerlund, Tapio, 2012. "A new exact discrete linear reformulation of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 314-319.
    12. Zvi Drezner, 2010. "On the unboundedness of facility layout problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(2), pages 205-216, October.
    13. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    14. Eduardo G. Pardo & Mauricio Soto & Christopher Thraves, 2015. "Embedding signed graphs in the line," Journal of Combinatorial Optimization, Springer, vol. 29(2), pages 451-471, February.
    15. Palubeckis, Gintaras, 2015. "Fast simulated annealing for single-row equidistant facility layout," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 287-301.
    16. Monique Guignard, 2020. "Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints," Annals of Operations Research, Springer, vol. 286(1), pages 173-200, March.
    17. Jingyang Zhou & Peter E.D. Love & Kok Lay Teo & Hanbin Luo, 2017. "An exact penalty function method for optimising QAP formulation in facility layout problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2913-2929, May.
    18. Lin, Jin-Ling & Foote, Bobbie & Pulat, Simin & Chang, Chir-Ho & Cheung, John Y., 1996. "Solving the failure-to-fit problem for plant layout: By changing department shapes and sizes," European Journal of Operational Research, Elsevier, vol. 89(1), pages 135-146, February.
    19. Anurag Agarwal, 2009. "Theoretical insights into the augmented-neural-network approach for combinatorial optimization," Annals of Operations Research, Springer, vol. 168(1), pages 101-117, April.
    20. Ali Derakhshan Asl & Kuan Yew Wong & Manoj Kumar Tiwari, 2016. "Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy, particle swarm optimisation, and genetic algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 799-823, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:30:y:2018:i:2:p:295-308. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.