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

Section 3: Quadratic optimization problems (portfolio optimization)

So when does this second-order term appear in a real problem? One example is the portfolio optimization problem in Chapter 1, Optimization Problem 3. Suppose $s_i$ represents whether or not to buy the stock $x_i$ ($+1$ to buy, $-1$ not to buy) and $s_j$ represents whether or not to buy the stock $x_j$. Now, if the price of the stock $x_i$ goes up when the price of the stock $x_j$ also goes up (i.e., positively correlated), we can represent a risk as a cost function by multiplying those two values and a positive coefficient $a_{ij}$. If you buy both $x_i$ and $x_j$ stocks, when the price of the $x_i$ stock drops, the price of the $x_j$ stock also drops, indicating that you would lose a lot of money. In other words, the positive larger value of $a_{ij}s_is_j$ indicates a larger risk. On the other hand, if $x_i$ and $x_j$ move in opposite directions with respect to the market price movement (i.e., negatively correlated), that is, if the price of $x_j$ falls when the price of $x_i$ rises, while the price of $x_i$ rises when the price of $x_j$ falls, then buying them simultaneously will prevent the prices from falling all at once. Thus, setting the correlation coefficient $a_{ij}$ to a negative value indicates lower risk. As you see above, well-designed correlation functions can express whether you should or should not buy a stock.
The correlation appears not only in portfolio optimization but also in other combinatorial optimization problems when considering the relationship between variables affected by each other's choices. The shift optimization problem in (4) is another example. Suppose there are three staff members, Mr. A, Mr. B, and Mr. C, and there is a time slot to which anyone should be assigned. If Mr. A is assigned to the slot, Mr. B and Mr. C will not need to be assigned. A relationship like that assigning someone affects another's assignment is called "interaction."

The selecting sweets problem described in "What is the combinatorial optimization problem?" is also a linear equation, similar to the mixed juice problem described in Section 1. However, if the satisfaction level changes with the combination of sweets, an interaction represented by a quadratic function appears. Suppose that the satisfaction level of chocolate was 10 points and the satisfaction level of potato chips was 8 points when eaten alone. If satisfaction is not particularly dependent on the combination of sweets, the total satisfaction would be 18 points when you eat chocolate and potato chips. However, in reality, some people feel that satisfaction increases when they eat something sweet and something salty. We can model such a situation as their satisfaction will be 36 points if you eat both chocolate and potato chips. In this case, a second-order term appears in the cost function because the combination of sweets makes satisfaction more than just an addition. Thus, a problem that looks the same may be first-order or second-order if the modeling is slightly different. Optimization problems with interactions are very difficult to solve with solvers for first-order formulas but are suit for annealing machines.

It is essential to select problems with interaction to take maximum advantage of annealing machines.

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".