One of the reasons that make combinatorial optimization problems so complex is that they treat "discrete values." The concept of combination is a relationship between elements that are discrete one by one. For example, let's consider there are three shortcakes. A family of three will eat them fairly and equally. However, if two friends visit, dividing the three shortcakes among five people fairly could be challenging. In other words, this is because the shortcake is not supposed to be divided. The antonym for discrete value is "continuous value". Consider a family of three dividing a pizza. In this case, everyone can eat fairly if the pizza is divided into three equal portions. If two of your friends come over, you can fairly divide the pizza into five equal pieces. Thanks to the continuous connection of the pizzas, they can be divided well into any number of pieces.
In another example, if you want to divide the members of a class into two teams, you can divide them fairly into two groups if the number of members is even. Still, if the number of members is odd, dividing them fairly into two teams becomes difficult. This is also a discrete problem.
In the real world, problems that must be considered discrete and continuous are intertwined. Familiar physical phenomena are often observed as changes in continuous values. For example, the optimal temperature and heating time for boiling eggs are continuous problems. Continuous value problems are latent in many advanced simulation calculations, such as those involving microparticles and the micro-world, which cannot be visually confirmed, as well as in machine learning. Thought inversely, combinatorial optimization problems may often be not a physical phenomenon but an artificial operation.
Did you find the article helpful? Please share it with others.
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.
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.
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.
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".