Polynomial unconstrained binary optimisation -- part 1
Summary: 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 optimisation problems in the general polynomial unconstrained binary (PUB) domain. 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. In this Part 1 paper, we give fundamental results for carrying out the transformations. We also describe coding and decoding procedures that are relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In a sequel to this paper, Part 2, 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.
- Polynomial unconstrained binary optimisation -- part 2
- Quadratic reformulations of nonlinear binary optimization problems
- Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems
- The bipartite QUBO
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
- Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing
- \(\mathrm{PUBO}_i\): a tunable benchmark with variable importance
- Polynomial unconstrained binary optimisation -- part 2
- Quadratic reformulations of nonlinear binary optimization problems
- Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation
- New advances for quantum-inspired optimization
This page was built for publication: Polynomial unconstrained binary optimisation -- part 1
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256908)
