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.