Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems

DOI10.1504/IJMHEUR.2010.034201MaRDI QIDQ537995zbMATH OpenOpenAlexFDO

Authors Fred Glover, Jin-Kao Hao

Publication date 23 May 2011

Published in International Journal of Metaheuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijmheur.2010.034201

zbMATH Keywords

computational efficiencymetaheuristicstabu searchtwo-flip movesunconstrained quadratic programmingzero-one optimisation

Mathematics Subject Classification ID

Boolean programming (90C09) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.

Recommendations

• Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
• Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems
• Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
• f-flip strategies for unconstrained binary quadratic programming
• Multistart tabu search strategies for the unconstrained binary quadratic optimization problem

Cited in

(7)

• Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
• Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
• f-flip strategies for unconstrained binary quadratic programming
• Solving the maximum vertex weight clique problem via binary quadratic programming
• Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation
• A hybrid metaheuristic approach to solving the UBQP problem
• A large population island framework for the unconstrained binary quadratic problem

This page was built for publication: Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537995)