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

Krešimir Mihić (), Kevin Ryan () and Alan Wood ()
Additional contact information
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

INFORMS Journal on Computing, 2018, vol. 30, issue 2, 295-308

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.

Keywords: integer programming; heuristic algorithms; nonlinear programming (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0781 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:2:p:295-308

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().