Chapter 3: Annealing Machines, Quadratic Expressions, and Discrete Values

Section 1: Linear programming problems

A linear programming problem is a problem that can be represented by a linear function It is one of the easiest optimization problems to solve. Although it can be represented in an Ising model, there is little benefit in solving it with an annealing machine. To give you a feel for what kind of problem it is, let's consider the example of the restaurant profit maximization problem described in the second example in Chapter 1. How can we maximize the most profit in a mixed juice restaurant? The store has three menu items: a strawberry special, a mango special, and a banana special.
The strawberry special is made with 100g of strawberries and 40g of mangoes. The Mango Special contains 80g of mango and 30g of banana. The banana special contains 110g of bananas and 50g of strawberries. On a particular day, we purchased 1000g of strawberries, 500g of mangoes, and 1500g of bananas. The selling prices of the strawberry special, mango special, and banana special are 700 yen, 900 yen, and 500 yen, respectively. How many of each should be sold to achieve the highest sales?

Table: Mixed Juice Menu and Ingredients for Each

Menu / Ingredients Strawberry 1000g Mango 500g Banana 1500g unit price
Strawberry Special Strawberry 100g Mango 40g - 700 yen
Mango Special - Mango 80g Banana 30g 900 yen
Banana Special Strawberry 50g - Banana 110g 500 yen

If the numbers of strawberry specials, mango specials, and banana specials sold denote $x, y, z$, then sales can be expressed by the following equation.

It is the optimization problem we want to solve to find a combination of $x, y, z$ that satisfies these conditions.

The cost function (1) is called a linear equation. Its solution can be determined by how many variables are multiplied: the $700x$ term, $900y$ term, and $500z$ term are all of the first order. If any of these have $x^2$ or $xy$, it is a quadratic equation.

The answer to this problem is 4 strawberry specials, 4 mango specials, and 12 banana specials. When solving this mixed juice problem on one's own, one of the popular ways is to represent the constraint equations on a three-dimensional graph and find the intersections. On a computer, a mechanism called a "solver" is provided to solve the problem efficiently. Some such solvers are provided as add-ins to spreadsheet software and can be used immediately. Therefore, it is not the case that an annealing machine is the best tool for such a linear optimization problem.

SNS Sharing

Did you find the article helpful? Please share it with others.

If you want to know specific examples of solving combinatorial optimization problems with an annealing machine

What is the combinatorial optimization problem?

Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.

Optimization of researcher shifts with consideration for COVID-19 infection control

In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.

Optimizing reinsurance portfolio

This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.

If you want to know how to use an annealing machine

Easy-to-learn optimization flow

For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".