17806440. COMPUTING INVERSE TEMPERATURE UPPER AND LOWER BOUNDS simplified abstract (Microsoft Technology Licensing, LLC)
COMPUTING INVERSE TEMPERATURE UPPER AND LOWER BOUNDS
Organization Name
Microsoft Technology Licensing, LLC
Inventor(s)
COMPUTING INVERSE TEMPERATURE UPPER AND LOWER BOUNDS - A simplified explanation of the abstract
This abstract first appeared for US patent application 17806440 titled 'COMPUTING INVERSE TEMPERATURE UPPER AND LOWER BOUNDS
Simplified Explanation
The abstract describes a computing device that can solve combinatorial optimization problems using a Markov chain Monte Carlo (MCMC) algorithm. The device computes an inverse temperature lower bound and an inverse temperature upper bound to estimate the maximum and minimum changes in the energy function of the problem. It then executes the MCMC algorithm over multiple timesteps, setting the inverse temperature to the lower bound initially and the upper bound at the end, to find the solution. The device outputs the solution.
- Computing device for solving combinatorial optimization problems
- Uses a Markov chain Monte Carlo (MCMC) algorithm
- Computes inverse temperature lower bound and upper bound
- Estimates maximum and minimum changes in the energy function
- Executes MCMC algorithm over multiple timesteps
- Sets inverse temperature to lower bound initially and upper bound at the end
- Outputs the solution to the problem
Potential Applications
- Optimization problems in various fields such as logistics, scheduling, and resource allocation
- Network routing and traffic optimization
- Financial portfolio optimization
- DNA sequence alignment and protein folding
Problems Solved
- Solves complex combinatorial optimization problems efficiently
- Provides a solution to problems that are difficult to solve using traditional methods
- Enables optimization in real-time or near-real-time scenarios
Benefits
- Faster and more efficient solution to combinatorial optimization problems
- Can handle large-scale problems with many variables and constraints
- Provides accurate estimates of the energy function changes
- Enables real-time decision-making and optimization
Original Abstract Submitted
A computing device including a processor configured to receive an energy function of a combinatorial optimization problem. The processor may be further configured to compute an inverse temperature lower bound, which may include estimating a maximum change in the energy function between successive timesteps. The processor may be further configured to compute an inverse temperature upper bound, which may include estimating a minimum change in the energy function between successive timesteps. The processor may be further configured to compute the solution to the combinatorial optimization problem at least in part by executing a Markov chain Monte Carlo (MCMC) algorithm over the plurality of timesteps. An inverse temperature of the MCMC algorithm may be set to the inverse temperature lower bound during an initial timestep and may be set to the inverse temperature upper bound during a final timestep. The processor may be further configured to output the solution.
