About Research Project
Combinatorial optimization problems lie at the heart of many real world problems. The current state of art for dealing with combinatorial problems has three different approaches: Linear and Integer Programming (LP/IP), boolean satisfiability (SAT), and Constraint Programming (CP). Each approach has its strengths and weaknesses. As combinatorial problen1s are intractable and NP-hard, it is unlikely that any single approach will be best either in practice or in theory. SAT and CP solvers primarily use techniques which reason about satisfiabi1ity and consistency because the problem definition is primarily about, satisfiability. In a nuttshell CP is about inference using propagation and SAT is about learning and heuristics. LP and IP, on the other hand, are designed for optimization problems.
This proposal is about combining some of the strengths of optimization approaches into CP solvers. At the same time, we want to keep the strengths of CP. We also want to incorporate some aspects of learning. We propose two directions. Firstly, the search heuristic is a key component of the solver and we propose to incorporate the objective function as part of the heuristic. We also want to use learning which we believe can lead to better and more robust black box solvers. Secondly, inference in CP solvers is about constraint consistency which is not strong coupled to the optimization goal in combinatorial optimization problems.
We propose to develop better ways of reasoning about the objective function in terms of the constraints of the problem. This involves using compact representations such as BDDs, MDDs, automata and others where both a sub-solution and its cost can be represented and the algorithms to operate on them. The deliverable will be new search heuristics and constraint consistency algorithms more suited for combinatorial optimization problems. We will build prototypes which can be used within existing CP solvers, thus, can be used to evaluate on existing benchmarks and used to solve complex optimization problems.
