Alpha QUBO Solver

QUBO models can be used to successfully model challenging combinatorial optimization problems arising in many industries.

Our advanced QUBO solver can currently solve QUBO instances with up to 1,000,000 variables.  AlphaQUBO 2.0 replaced AlphaQUBO 1.0 in 2019

For access to our AlphaQUBO solver, go to QUBO Solver at AWS Marketplace. 

For our tutorial on formulating QUBO models, go to QUBO Tutorial.

 

Advanced Pre-processing Methods

  • Identifies variables that can be set to 0 or 1 in advance, without changing the set of optimal solutions.
  • This allows many problems to be reduced in size and solved more efficiently.
  • Can provide a big boost for solving large problems.
  • The pre-processing code can be used as a stand-alone or integrated with our primary solvers.

GPU Implementation

  • A conversion of our code to a GPU implementation is in beta testing and will be available for commercial use soon.
  • This is expected to deliver a 30X improvement in performance.

Partitioning

  • We have produced an algorithm for partitioning QUBO problems into subproblems.
  • Our approach is different from schemes D-Wave and others are attempting to use.
  • Coding and Testing just underway.
  • Represents the potential for solving much larger instances and a variety of QUBO-related problems

Alpha QUBO-Plus

  • Includes more general QUBO-related problems that can be solved more effectively by an extended method instead of reformulating them as QUBOs.
  • These more general problems have important applications and typically consist of QUBO problems with additional constraints. Examples are:
  • Cardinality constrained QUBO problems –where the sum of the variables must equal a specified value or lie between specified bounds, arising in a variety of practical applications, especially in finance.
  • Assignment constrained QUBO problems – where multiple assignment or cardinality constraints exist, arising both in finance and in resource allocation applications.
  • Knapsack and Multiple Knapsack constrained QUBO problems, arising in resource allocation, machine learning, and distribution applications.

Alpha PUBO

  • Handles more general problems where the quadratic optimization QUBO model is replaced by a polynomial optimization PUBO model.