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.
