Graph Decomposition Approaches to Discrete Optimization

Many problems of planning (capital budgeting, facility location and portfolio selection), design problems (telecommunication and transportation networks optimal design, VLSI circuit design), scheduling, robotics, pattern recognition, theorem proving, and artificial intelligence can be expressed as discrete optimization (DO) problems. Unfortunately, many real-life DO problems have large sizes and are intractable for current state-of-the-art DO solvers. To meet the challenge of solving large scale DO problems in reasonable time, there is an urgent need to develop new decomposition approaches. Large-scale DO problems are characterized not only by their huge size but also by special or sparse structure exploitable by a DO solver. The aim of this project is to develop effective algorithms for solving DO problems combining graph theoretic decomposition approaches from mathematical optimization like nonserial dynamic programming (NSDP) schemes, tree decomposition, and local decomposition algorithms with constraint satisfaction approaches. Decomposition and sensitivity analysis in DO are closely related. Decomposition methods consist of generating and solving families of related DO problems that have the same structure but differ in the values of coefficients. Sensitivity analysis allows using information obtained during solving one DO problem of the family of related DO problems in solving other problems of this family. Structural decomposition approaches (NSDP, tree decomposition combined with local decomposition algorithm) use parametric DO problems where some variables are fixed and to find a solution one should enumerate all binary values of these variables. This results as a family of DO problems with different right-hand sides. When blocks of DO problem are not too large, it is possible to build a binary decision diagram (BDD) for each block and compute solutions of the family of parameterized DO problems using a procedure of seeking a shortest path in a BDD. It is natural to develop hybrid approaches involving both constraint satisfaction approaches such as inference-based sensitivity and binary decision diagrams and graph decomposition approaches such as NSDP, tree decomposition, in order to find the solution of large-scale DO problems. The main aims of this project are: to show that dynamic programming algorithms based on structural decomposition of the interaction graph of The DO problem can be an alternative for known DO techniques to solve hard DO problems; the analysis of the possibilities how to combine graph decomposition schemes (nonserial dynamic programming, local decomposition algorithms, tree decomposition) with logic-based approaches like inference sensitivity and binary decision diagrams to develop effective algorithms for solving DO problems. This research will allow to develop and implement new methodology using NSDP and tree decomposition combined with binary decision diagrams for solving large scale DO problems. Methods of the research include: 1. Elimination approaches (nonserial dynamic programming, local elimination algorithm, tree decomposition) for solving DO problems with special structure; 2. postoptimality analysis in DO for solving families of related discrete optimization problems; 3. constraint satisfaction techniques and their transfer to optimization field; 4. condensation and condensed structural graphs of DO problem, development of efficient schemes of condensation; 5. Using the COCONUT API (application programmer`s interface) allows making the development of the various module types independent of each other and independent of the internal model representation; 6. postoptimality analysis embedded into elimination algorithms (block NSDP, tree decomposition combined with dynamic programming).

Many problems of planning (capital budgeting, facility location and portfolio selection), design problems (telecommunication and transportation networks optimal design, VLSI circuit design), scheduling, robotics, pattern recognition, theorem proving, and artificial intelligence can be expressed as discrete optimization (DO) problems. Unfortunately, many real-life DO problems have large sizes and are intractable for current state-of-the-art DO solvers. To meet the challenge of solving large scale DO problems in reasonable time, there is an urgent need to develop new decomposition approaches. Large-scale DO problems are characterized not only by their huge size but also by special or sparse structure exploitable by a DO solver. The aim of this project is to develop effective algorithms for solving DO problems combining graph theoretic decomposition approaches from mathematical optimization like nonserial dynamic programming (NSDP) schemes, tree decomposition, and local decomposition algorithms with constraint satisfaction approaches. Decomposition and sensitivity analysis in DO are closely related. Decomposition methods consist of generating and solving families of related DO problems that have the same structure but differ in the values of coefficients. Sensitivity analysis allows using information obtained during solving one DO problem of the family of related DO problems in solving other problems of this family. Structural decomposition approaches (NSDP, tree decomposition combined with local decomposition algorithm) use parametric DO problems where some variables are fixed and to find a solution one should enumerate all binary values of these variables. This results as a family of DO problems with different right-hand sides. When blocks of DO problem are not too large, it is possible to build a binary decision diagram (BDD) for each block and compute solutions of the family of parameterized DO problems using a procedure of seeking a shortest path in a BDD. It is natural to develop hybrid approaches involving both constraint satisfaction approaches such as inference-based sensitivity and binary decision diagrams and graph decomposition approaches such as NSDP, tree decomposition, in order to find the solution of large-scale DO problems. The main aims of this project are: to show that dynamic programming algorithms based on structural decomposition of the interaction graph of The DO problem can be an alternative for known DO techniques to solve hard DO problems; the analysis of the possibilities how to combine graph decomposition schemes (nonserial dynamic programming, local decomposition algorithms, tree decomposition) with logic-based approaches like inference sensitivity and binary decision diagrams to develop effective algorithms for solving DO problems. This research will allow to develop and implement new methodology using NSDP and tree decomposition combined with binary decision diagrams for solving large scale DO problems. Methods of the research include: 1. Elimination approaches (nonserial dynamic programming, local elimination algorithm, tree decomposition) for solving DO problems with special structure; 2. postoptimality analysis in DO for solving families of related discrete optimization problems; 3. constraint satisfaction techniques and their transfer to optimization field; 4. condensation and condensed structural graphs of DO problem, development of efficient schemes of condensation; 5. Using the COCONUT API (application programmer`s interface) allows making the development of the various module types independent of each other and independent of the internal model representation; 6. postoptimality analysis embedded into elimination algorithms (block NSDP, tree decomposition combined with dynamic programming).