Content area
Dynamic programming (DP) is a framework used in multiple disciplines to solve decision-making problems. In particular, in computer science and operations research (OR), DP algorithms have been developed for combinatorial optimization, a class of problems to make a finite set of decisions to optimize an objective function. In such work, DP algorithms were typically implemented specifically for individual combinatorial optimization problems.
In contrast to problem-specific algorithms, model-based paradigms use general-purpose solvers to solve any problem formulated in a particular form of mathematical model. They aim to decouple modeling and solving a problem: the ‘holy grail’ of declarative problem-solving. In practice, model-based paradigms such as mixed-integer programming (MIP) and constraint programming (CP) are widely used to solve various combinatorial optimization problems.
We propose domain-independent dynamic programming (DIDP), a novel model-based paradigm for combinatorial optimization based on DP. In DIDP, a user formulates a DP model using a declarative modeling language and then uses a general-purpose DP solver to solve the model. Throughout this dissertation, we develop the modeling language and general-purpose solvers for DIDP.
Our language is based on a state-transition system, inspired by artificial intelligence (AI) planning. However, it is specifically designed for combinatorial optimization: similar to MIP and CP, a user can declaratively include redundant information in a model, which is implied by other parts of the model but may be useful for a solver when made explicit. We demonstrate the modeling capability of our language by formulating eleven combinatorial optimization problems as DP models.
We investigate DIDP solvers using heuristic search, a class of algorithms widely used in the AI community. First, we develop anytime and exact solvers, which improve the solution quality over time and eventually solve the problem optimally. Then, we develop a DIDP solver based on large neighborhood search, which is used to quickly obtain high-quality solutions in MIP and CP. Finally, we develop multi-thread DIDP solvers using parallel heuristic search algorithms. With the developed modeling language and solvers, we demonstrate that DIDP is a promising approach: it empirically outperforms MIP and CP in multiple classes of combinatorial optimization problems.
