Chapter 1: What is a Combinatorial Optimization Problem?

Section 1: Optimization Problems and Combinatorial Optimization Problems

Annealing machines are specialized for combinatorial optimization problems.

Since the essential part of using an annealing machine is to formulate equations from real-world problems, we would like all visitors to learn a little more about the characteristics of the issues we deal with. First of all, we would like you to know that combinatorial optimization problems are one of the classifications of "optimization problems." An optimization problem is an effort to find an answer that makes something better. So, for example, the pastry selection problem of choosing the most satisfying pastry possible within a given budget, or finding the target amount of sales for each menu item giving the highest total sales using ingredients purchased are optimization problems. In stock trading, there are related stocks in which the price of one stock goes down when the price of the other stock goes up. Choosing such an interacting combination (portfolio) to avoid risk and increase profit is also an optimization problem. It is also an optimization problem to set up a shift at a certain workplace so that not a single person is dissatisfied because their wishes are not fulfilled, and good results are achieved in the business. Furthermore, it is also an optimization to determine the temperature and heating time for making Oyakodon (a bowl of rice topped with chicken and eggs) so that it is not too raw, not too firm, and at just the right desired point problem.

  1. Selecting Sweets Problem
  2. Restaurant's Profit Maximization Problem
  3. Portfolio Problem
  4. Shift Making Problem
  5. Oyakodon Problem

The above list showcases both problems that annealing machines are good at and problems that annealing machines are not ideal fits for. The explanation about each situation is a bit complicated, so let's learn the formulation necessary to solve such optimization problems mathematically first.

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

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.

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