Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems
Summary: We provide a method for efficiently evaluating moves that complement values of 0-1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.
- scientific article; zbMATH DE number 4116303
- scientific article; zbMATH DE number 1382838
- scientific article; zbMATH DE number 3848110
- An Algorithm for Large-Scale Quadratic Programming
- Testing optimality for quadratic 0?1 unconstrained problems
- Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- scientific article; zbMATH DE number 13594
- Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- Partial evaluation in rank aggregation problems
- UOBYQA: unconstrained optimization by quadratic approximation
- Path relinking for unconstrained binary quadratic programming
- Polynomial unconstrained binary optimisation -- part 1
- Polynomial unconstrained binary optimisation -- part 2
- Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
- Building an iterative heuristic solver for a quantum annealer
- Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
- Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
- A tabu search algorithm with controlled randomization for constructing feasible university course timetables
- 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
- The bipartite quadratic assignment problem and extensions
- Testing optimality for quadratic 0?1 unconstrained problems
- The bipartite QUBO
- Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking
- Quadratic reformulations of nonlinear binary optimization problems
- Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems
- 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: Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537985)
