Research of Key Technologies in Program Synthesis for Combinatorial Optimization Problems
Published:
The goal of program synthesis is to automatically generate a computer program for solving a practical problem described by the user. The goal of combinatorial optimization problem solving is to find an assignment to all decision variables, so that all the constraints are satisfied and the value of the objective function is optimal. How to solve combinatorial optimization problems efficiently is an important topic in artificial intelligence. This thesis proposes an effective program synthesis method for solving combinatorial optimization problems. The major innovations of this thesis are:
This thesis proposes a new approach for automatically solving combinatorial optimization problems, including the design of a combinatorial optimization problem description language COPDL, and the design and implementation of a solving program synthesis tool COPDL2C based on COPDL. Compared with traditional solvers which focus on solving an instance of a problem, the new approach proposed by this thesis focuses on solving the whole class of a problem.
This thesis proposes a method that automatically analyzes problem properties statically, and inserts branch pruning and dynamic programming optimizations into the solving programs according to these properties, in order to improve the efficiency of solving. In addition to the original COPDL2C, this method automatically designs and implements the corresponding branch pruning and dynamic programming optimizations, so that the efficiency of a solving program can be significantly improved.
This thesis establishes a dataset of natural language descriptions of 40 combinatorial optimization problems, along with their test cases. This thesis also proposes a natural language-COPDL automatic translation method—NL2COPDL—for this dataset, which is based on templates and rules, as well as sketches. Combining NL2COPDL and COPDL2C, each problem in this dataset can be translated from its natural language description into a correct solving program.
This thesis designs and develops a problem modeling training system COPDLOpenJudge based on COPDL2C, which is used for improving the efficiency of training programmers. The whole solving process from understanding the natural language description of the problem to implementing the solving program can be naturally divided into two stages by NL2COPDL and COPDL2C: the problem modeling stage and the model solving stage. The experiment results show that such task division can enhance students’ confidence and improve learning efficiency.
In conclusion, this thesis selects combinatorial optimization problems as the research object, investigates the research progress and major problems of both combinatorial optimization problem solving and program synthesis, analyzes the challenges and key points of program synthesis for combinatorial optimization problems, and proposes a new approach for solving problem synthesis, which differs from traditional combinatorial optimization problem solvers. This approach tackles the major challenges and derives several software tools, including (1) a combinatorial optimization problem description language COPDL and the solving program synthesis tool COPDL2C; (2) a natural language-COPDL automatic translation tool NL2COPDL; (3) a problem modeling training platform COPDLOpenJudge (has already been applied to teaching practical courses). The products of this thesis are not only software tools for automatically generating solving programs for combinatorial optimization problems, but also aided educating tools for training programmers.
In the future, the research can be further improved in two aspects: first, extending COPDL and optimizing COPDL2C in order to efficiently solve more problems; second, extending the application scope of NL2COPDL by applying the state-of-the-art technologies of natural language understanding.
Recommended citation: Shu Lin, "Research of Key Technologies in Program Synthesis for Combinatorial Optimization Problems," (in Chinese), Doctoral Dissertation, School of Electronics Engineering and Computer Science, Peking University, Beijing, China, 2021
Download Paper | Download Bibtex