Article: Polynomial unconstrained binary optimisation – part 2 Journal: International Journal of Metaheuristics (IJMHEUR) 2011 Vol.1 No.4 pp.317 - 354 Abstract: The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimisation problem. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover et al., 2011) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms. Inderscience Publishers - linking academia, business and industry through research

Title: Polynomial unconstrained binary optimisation – part 2

Authors: Fred Glover; Jin-Kao Hao; Gary Kochenberger

Addresses: 1OptTek Systems, Inc., 2241 17th Street, Boulder, CO 80302, USA. ' Laboratoire d'Etude et de Recherche en Informatique (LERIA), Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France. ' School of Business Administration, University of Colorado at Denver, Denver, CO 80217, USA

Abstract: The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimisation problem. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover et al., 2011) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms.

Keywords: zero-one optimisation; unconstrained polynomial optimisation; metaheuristics; computational efficiency; polynomial unconstrained binary optimisation; quadratic optimisation.

DOI: 10.1504/IJMHEUR.2011.044356

International Journal of Metaheuristics, 2011 Vol.1 No.4, pp.317 - 354

Published online: 28 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Polynomial unconstrained binary optimisation – part 2

Keep up-to-date