Sample Programs

Table of Contents

• QUBO Solvers
  • QUBO++ EasySolver
  • QUBO++ ExhaustiveSolver
  • ABS2 QUBO Solver
  • Gurobi Optimizer
• QUBO Problems
  • Partitioning Problem
  • Knapsack Problem
  • Bin Packing Problem
  • Shift Scheduling Problem
  • Change Making Problem
  • NQueens Problem
  • Integer Linear Programming (ILP) Problem
  • Graph Coloring Problem
  • Traveling Salesman Problem (TSP)
  • Simple Factorization
  • Factorization/Multiplication

Several sample programs that solve optimization problems using EasySolver, ExhaustiveSolver, ABS2 QUBO Solver, and Gurobi Optimizer through the QUBO++ library are provided:

QUBO Solvers

QUBO++ EasySolver

A basic QUBO solver included in the QUBO++ library, designed to run on a CPU.

• qbpp_easy_solver.hpp: A basic QUBO solver based on the Positive Min search algorithm.

QUBO++ ExhaustiveSolver

A simple QUBO solver included in the QUBO++ library, designed to run on a CPU.

• qbpp_exhaustive_solver.hpp: A basic QUBO solver that performs an exhaustive search of all possible solutions to identify the optimal ones.

ABS2 QUBO Solver

A QUBO solver that runs on Linux servers with CUDA-enabled GPUs. It is available for non-commercial research and evaluation purposes but comes without any guarantees.

• qbpp_abs2.hpp: This header provides the QUBO++ interface for the ABS2 QUBO Solver, allowing it to be executed through the QUBO++ Library.
• abs2.hpp: The C++ API for the ABS2 QUBO Solver, used to invoke GPU-based solvers directly. This API enables access to the ABS2 QUBO Solver without relying on the QUBO++ Library.

Sample programs using the ABS2 QUBO Solver require setting the path that includes libabs2.so to the environment variable LD_LIBRARY_PATH in order to execute them.

Gurobi Optimizer

A commercial MIP solver that runs on multi-core CPUs, requiring a valid license.

• qbpp_grb.hpp: QUBO++ interface for the Gurobi Optimizer.

Sample programs using the Gurobi Optimizer require specifying the path that includes gurobi_c++.h either by the environment variable CPLUS_INCLUDE_PATH or by the -I compiler option. Additionally, they require setting the Gurobi library path that includes libgurobi_c++.a to the environment variable LD_LIBRARY_PATH in order to execute them.

QUBO Problems

Partitioning Problem

Given a list of numbers, partition them into two sets such that the sums of the numbers in each set are as close as possible.

• partition_easy.cpp: Solves the Partitioning Problem using the EasySolver.
• partition_exhaustive.cpp: Finds all optimal solutions of the Partitioning Problem using the ExhaustiveSolver.

Knapsack Problem

Given a set of items with values and weights, select the items that maximize the total value without exceeding the given weight limit.

• knapsack_exhaustive.cpp: Solves the knapsack problem using the ExhaustiveSolver.

Bin Packing Problem

Given a set of items with weights, distribute them into bins such that the weight of each bin does not exceed the specified limit.

• bin_packing_easy.cpp: Solves the bin packing problem using the EasySolver.

Shift Scheduling Problem

The problem is to assign 7 workers to 24 time slots so that the total working hours is minimized.

• shift_scheduling_easy.cpp: Solves the shift scheduling problem using the EasySolver.

Change Making Problem

Given coins of denominations 1, 5, 10, and 25, determine the minimum number of coins needed to achieve a specified amount.

• change_making_exhaustive.cpp: Solves the change making problem using the Exhaustive Solver.

NQueens Problem

Find a placement of queens on a chessboard so that no two queens attack each other.

• qbpp_nqueen.hpp: Provides a function to generate a QUBO expression for the specified board dimension.
• nqueen_easy.cpp: Solves the NQueens Problem using the EasySolver.

Integer Linear Programming (ILP) Problem

Given an objective and constraints involving integer variables, find the values of the variables that maximize the objective.

• ilp_easy.cpp: Solves an ILP problem using the EasySolver.
• ilp_exhaustive.cpp: Solves an ILP problem using the ExhaustiveSolver.
• ilp_abs2.cpp: Solves an ILP problem using the ABS2 Solver.
• ilp_grb.cpp: Solves an ILP problem using the Gurobi Optimizer.

Graph Coloring Problem

Solves the Graph Coloring Problem for randomly generated graphs.

• qbpp_graph_color.hpp: Provides the following functions:
  • Randomly places nodes on a 2-dimensional plane.
  • Connects nodes by their proximity or Delaunay triangulation.
  • Outputs an image file displaying the solution.
• graph_color_easy.cpp: Solves an Graph Coloring Problem using the EasySolver.
• graph_color_abs2.cpp: Solves an Graph Coloring Problem using the ABS2 QUBO Solver.
• graph_color_grb.cpp: Solves an Graph Coloring Problem using the Gurobi Optimizer.

Traveling Salesman Problem (TSP)

Find a tour that visits all nodes placed in a 2-dimensional plane with the minimum total tour length.

• qbpp_tsp.hpp: Provides the following functions:
  • Randomly places nodes on a 2-dimensional plane.
  • Generates a QUBO expression for the TSP with the given nodes.
  • Outputs an image file displaying the solution.
• tsp_easy.cpp: Solves the TSP using the EasySolver.
• tsp_abs2.cpp: Solves the TSP using the ABS2 QUBO Solver.
• tsp_grb.cpp: Solves the TSP using the Gurobi Optimizer.

Simple Factorization

Find the factorization of the product \(p\), where two prime numbers \(x\) and \(y\) satisfy the given product \(p\). The QUBO model is derived from the reduction of a HUBO expression, \((xy-p)^2\).

• simple_factorization_easy.cpp: Factorization using the EasySolver.
• simple_factorization_abs2.cpp: Factorization using the ABS2 QUBO Solver.
• simple_factorization_grb.cpp: Factorization using the Gurobi Optimizer.

Factorization/Multiplication

Computes the product of two prime numbers or factorizes it using a QUBO emulation of a binary multiplier.

• qbpp_multiplier.hpp: Provides functions to emulate a binary multiplier for integers through QUBO models.
• factorization.cpp: Given two numbers \(x\) and \(y\), computes the product \(xy\) using a QUBO model simulating a binary multiplier circuit. By inverting this simulation, the two factors \(x\) and \(y\) are computed from the product \(xy\). Three solvers EasySolver, ABS2 QUBO Solver, and Gurobi Optimizer are executed simultaneously, and their best solutions are exchanged as they are obtained to improve search performance.