Optimisation binaire quadratique sans contraintes (QUBO)
Depuis R2023a
De nombreux problèmes d’optimisation combinatoire peuvent être formulés en tant que problèmes d’optimisation binaire quadratique sans contraintes (QUBO). Il s’agit notamment des problèmes suivants : Traveling Salesperson Problem with QUBO, Capacitated Vehicle Routing Problem et Feature Selection QUBO (Quadratic Unconstrained Binary Optimization). Pour des informations générales, consultez What Is a QUBO Problem?
Par ailleurs, de nombreux ordinateurs quantiques actuels et en projet utilisent QUBO (ou le modèle d’Ising équivalent) comme type de problème. Pour essayer de trouver une solution quantique à un problème d’optimisation combinatoire, vous devez formuler un problème QUBO puis le transmettre au hardware quantique afin de le résoudre. À l’heure actuelle, MATLAB® Support Package for Quantum Computing ne supporte directement aucun hardware quantique pour la résolution de problèmes QUBO.
Objets
qubo | Quadratic Unconstrained Binary Optimization |
quboResult | Result of solving QUBO problem |
tabuSearch | Tabu search algorithm for QUBO
solve |
tabuSearchResult | Result of solve for Tabu search algorithm |
Fonctions
evaluateObjective | Evaluate QUBO (Quadratic Unconstrained Binary Optimization) objective |
solve | Solve QUBO (Quadratic Unconstrained Binary Optimization) problem |
Rubriques
- What Is a QUBO Problem?
This topic introduces the basics of Quadratic Unconstrained Binary Optimization (QUBO) problems.
- Workflow for QUBO Problems
Learn the steps for formulating and solving a QUBO problem.
- Constraints in QUBO Problems
Include constraints in a QUBO problem by adding penalty terms.
- Tabu Search Algorithm
Learn about the tabu search heuristic algorithm used to solve QUBO problems.
- Verify Optimality by Solving QUBO as MILP
Convert a QUBO problem to a mixed-integer linear programming (MILP) problem, and solve the problem using
intlinprog
. - Traveling Salesperson Problem with QUBO
Convert a Traveling Salesperson Problem (TSP) to a QUBO problem and solve the problem.
- Capacitated Vehicle Routing Problem
Express and solve a capacitated vehicle routing problem using QUBO.
- Feature Selection QUBO (Quadratic Unconstrained Binary Optimization)
Find the most relevant predictors in a data set using a QUBO problem formulation.