Making the best possible decisions is critical to the success of most businesses. This is particularly relevant today because companies have access to a large amount of high-quality data and they are interested in using this data to drive their decision making. The science of optimization can help businesses find the best solution among all possible solutions to maximize their performance and minimize their costs.
“The Optimization Division’s mission at 1QBit is to develop algorithms and tools for solving hard, real-world problems that leverage classical optimization algorithms as well as novel computational technologies.”
Businesses are not the only ones that use optimization to get better results. We all solve optimization problems in our day-to-day lives, whether it be in finding the fastest route to work, placing as many items as possible in the kitchen cabinets, or packing everything into just one suitcase when travelling. Often, we make these decisions intuitively by trial and error, reaching a good, but not necessarily optimal, solution. However, there are situations where the differences in outcomes are significant and the options are numerous, and that is where optimization matters.
Real-world optimization problems are much more complex than most of our daily choices, as they have a large number of decision variables, multiple conflicting objectives, and complicated interwoven constraints. An example of a real-world optimization application is the allocation and distribution of COVID-19 vaccines, perhaps the greatest optimization challenge of our lifetime. Millions of doses of vaccines need to be administered by deciding who is getting the vaccine, where, and when. There are conflicting objectives of vaccinating more people as quickly as possible and providing equal access to everyone in the population. Limited and uncertain supply, multiple vaccine types, special storage requirements, transportation, and administration are among the complicated constraints that need to be taken into account.
The Travelling Salesperson Problem
To better understand what is meant by “optimization”, let us consider a well-known example: the travelling salesperson problem. The goal is to find the shortest possible route for a salesperson to visit a given number of cities exactly once. The obvious approach for solving this problem is to use brute force. In this approach, we calculate the length of each possible route, and choose the route that has the shortest length. The total number of routes that we need to consider in an example with 50 cities is slightly more than 1064. Assuming that we can evaluate 1010 routes per second, it will take more than 1046 years to solve such a seemingly simple problem. Therefore, we need more-efficient approaches: optimization is the technology that provides us with efficient algorithms to solve this problem, as well as many other challenging real-world problems. To deal with the astronomical size of large, real-world optimization problems and capturing all of their complexity, we must use automated software toolkits and powerful computational hardware.
There are various powerful optimization solution techniques embedded in state-of-the-art commercial software solvers that can solve real-world optimization problems such as in typical (non-pandemic) vaccine allocation and distribution, portfolio optimization, or airline scheduling. These techniques are computationally intensive and their performance has noticeably benefitted from the steady exponential increase in available compute power. The fact that the performance of CPUs has doubled every two years (known as Moore’s law) has played a pivotal role in keeping these algorithms relevant to today’s real-world challenges.
The steady exponential increase in compute power is expected to come to an end because the density of transistors in integrated circuits cannot grow indefinitely beyond certain physical limits. To sustain the computational performance growth rate in the post–Moore’s law era, the attention has started to shift toward alternative computing platforms, such as graphics processing units (GPU), field-programmable gate arrays (FPGA), application-specific integrated chips (ASIC), and devices that exploit quantum mechanical effects. D-Wave’s quantum annealer, Fujitsu’s Digital Annealer, NTT’s Coherent Ising Machine, Hitachi’s FPGA-based Ising computers, and Toshiba’s Simulated Bifurcation Machine are examples of new technologies that are expected to benefit the computationally intensive field of optimization.
The 1QBit Optimization Division
The Optimization Division’s mission at 1QBit is to develop algorithms and tools for solving hard, real-world problems that leverage classical optimization algorithms as well as novel computational technologies. Our years of experience with solving real-world optimization problems in different industries such as energy, finance, and health care has resulted in the development of three products: the 1Qloud™ optimization platform enabled by advanced hardware, a flexible heuristic toolkit for constrained optimization known as FOCUS, and an automated benchmarking and parameter tuning toolkit for optimization known as HOPE. 1QBit’s tools allow industry to continually benefit from developments in advanced computing resources.
To stay up to date on 1QBit’s optimization products and research, subscribe to our blog and follow us on social media.