Automating dynamic programs
AssigneeNational ICT Australia Limited
InventorsJakob Puchinger, Peter Stuckey
Life of this patent
Estimating the term…
Abstract
Solving combinatorial optimisation problems using dynamic programming involves automating the integration of bounds propagation into compilation of a dynamic program. This is done by extracting bounds from partial results obtained during dynamic programming, and tightening the bounds throughout execution of the dynamic program. This dramatically reduces the number of “good” solutions that need to be constructed at each stage, improving speed and scalability of algorithms using such dynamic programming.
Claims13
A method of solving a combinatorial optimization problem using dynamic programming, the method comprising:
- automating integration of bounds propagation into compilation of a dynamic program, by extracting bounds from partial results obtained during dynamic programming, and tightening the bounds throughout execution of the dynamic program.
A non-transitory machine readable medium that provides instructions for compiling a dynamic program for solving a combinatorial optimization problem, which when executed by a machine, cause the machine to perform operations, comprising:
- automating integration of bounds propagation into compilation of a dynamic program, by extracting bounds from partial results obtained during dynamic programming, and tightening the bounds throughout execution of the dynamic program.
Dependencies are inferred from the claim text.