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.
Related Articles
What is a 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.
Optimize an insurer's 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.
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".