Videos (Case Studies)

Videos that solve concrete problems with QUBO++. Each video takes one problem and covers its definition, the choice of variables, constraints and objective, the program, and an example run. Written explanations are on the Case Studies page (Python / C++). They are published on the YouTube channel QUBO++ and collected in the playlist QUBO++ Case Studies (English). Click an image to play the video on this page. How to use QUBO++ is on the Videos (Tutorials) page.

QUBO++ Case Study: Map Coloring (Python)(11:29, YouTube)Coloring a map so that neighboring regions differ, solved as graph coloring: variables, constraint and objective on a small map, written as a plain QUBO and with cons(), then the 48 contiguous US states colored with four colors.The programs in the video, chapter by chapter →

QUBO++ Case Study: Sudoku (Python)(10:52, YouTube)Sudoku with binary variables x[i][j][k] in a 3-D array: the cell, row and column constraints take one line each by changing the axis of qbpp.vector_sum, the blocks use slicing, and the variables the clues decide are registered in a dictionary and fixed with qbpp.replace (729 variables become 174).The programs in the video, chapter by chapter →

QUBO++ Case Study: Simulating a Quantum Annealer (Python)(11:56, YouTube)Solving the Ising model a quantum annealer solves, without the real machine: a random problem on the Chimera graph of the 2000Q, turned into a QUBO with spin_to_binary() and solved with EasySolver, why not every coupling can be satisfied, a check against exhaustive search, and the topologies of Advantage2 and others.The programs in the video, chapter by chapter →

QUBO++ Case Study: Image Halftoning (Python)(9:23, YouTube)Halftoning a grayscale image into black and white dots, solved as making the sum of squared errors between the blurred binary image and the original small, which is the energy of a QUBO: on a 256 × 256 photo of a cat, the well-known DBS (Direct Binary Search), ABS3, and ABS3 given the DBS image as a hint are compared with a graph of energy over time and the final images.The programs in the video, chapter by chapter →

QUBO++ Case Study: Nonogram (Python)(11:50, YouTube)A puzzle where you shade cells from number clues to complete a picture, on a 15 × 15 puzzle whose answer is the QUBO++ logo: each block's shift from the left-aligned position becomes domain wall variables, whether a block covers a cell becomes the difference of two strip values, and the color of a cell becomes a linear expression. It is solved with no auxiliary variables, and also as an expanded QUBO.The programs in the video, chapter by chapter →

QUBO++ Case Study: Graph Partitioning (Python)(13:09, YouTube)Three problems about how many edges are cut when a graph is cut, max cut, bisection width, and cutwidth, solved on the 4-dimensional hypercube (16 vertices, 32 edges). All three are built from the same cut expression: max cut by minimizing minus the cut, and bisection width by adding the equal halves constraint with qbpp.cons. For cutwidth, the number of each vertex becomes a domain wall, so that each column of the variable table is a split at a gap, and a ceiling integer variable minimizes the largest gap. The rook graph of a 4 × 4 board and K4 × K4 × K4 × K4 with 256 vertices (ABS3Solver) are tried too.The programs in the video, chapter by chapter →

QUBO++ Case Study: Machine Scheduling with Due Dates (Python)(11:32, YouTube)Twelve orders processed on three machines, every order by its due date. Each machine may process its orders in due-date order, so only the assignment becomes variables, and the assignment and due-date constraints are written with qbpp.cons. The program writes the sums with array operations and fixes variables such as those of the pairs that cannot be processed with qbpp.replace. After minimizing the total processing time, an integer variable z minimizes the makespan.The programs in the video, chapter by chapter →

QUBO++ Case Study: 48 US States in 3 Colors (Python)(10:39, YouTube)The 48 contiguous US states can be colored with 4 colors but not with 3. How few states must be removed for the rest to be colored with 3 colors (3-colorable vertex deletion)? With 144 binary variables for state × color, at most one color per state and different colors for neighbors are written as penalty expressions, and the number of colored states is maximized. ABS3Solver finds all 1728 best solutions: 2 states must be removed, in 24 possible pairs. The video explains why 2 states and why these 24 pairs, from the 3 shapes in which an odd ring of states surrounds a middle state.The programs in the video, chapter by chapter →

QUBO++ Case Study: Portfolio Optimization (Python)(15:54, YouTube)With 10 million yen, we decide which of 10 fictional stocks to buy, and how much. A comparison of a time deposit and a stock explains expected return, risk, and the risk premium; combining uncorrelated stocks lowers the risk, while a correlation of 1 does not. The formulas of the expected return R and the squared risk V give the mean-variance model that minimizes V − λR, written with integer variables for lots of 100 shares and qbpp.cons for the budget range. Limiting the purchase to at most 4 stocks selects 4 stocks from different sectors.The programs in the video, chapter by chapter →