click image for larger photo
The study of combinatorial optimization and its role in operations research has always been one of the major connections between industry and mathematics. A broad spectrum of mathematics research, from highly theoretical to wholly applied, has provided the basis for a variety of practical tools. These days, most of these tools are manifest in software, which provides the basis for modeling and understanding complex processes.
While the mathematics of combinatorial optimization has evolved over several decades, its application has more recently relied on increasingly sophisticated computational ideas. The developing science of computing and combinatorial optimization have much in common, but it is clear that there have been separate threads of evolution. For example, Dijkstra's shortest path algorithm has seeded common research in both areas, but there has been too little interaction, with the reinvention of ideas on both sides.
The solution of complex combinatorial problems within computing science has most recently been successfully addressed by constraint programming, which itself admits two separate histories. The key claim is that serious combinatorial problems need to be tackled with theories that admit both incremental specification and incremental search. Computing is clearly the discipline with the most experience in developing and experimenting with incremental computation.
Finally, the logical formalization of knowledge within the area of knowledge representation has given rise to the area of belief revision. Belief revision is generally concerned with the formalization of the principles behind changing collections of formal theories. The underlying computational mechanisms required for belief revision are exactly those developed for so-called "over constrained" optimization problems.
There are related concepts and ideas in these three areas, as well as unique strengths. For example, combinatorial optimization has concentrated on the mathematical formalization of modeling combinatorial problems, so that provable properties of general algorithmic solutions can be established. Constraint programming has taken simple relational formalizations of combinatorial problems, and concentrated on the computational complexity of search within those constraint frameworks, and the logic programming thread has promoted the expressive ease of constraint logic programming systems to help guide search with formalized knowledge of problem domains. Finally, the area of belief revision has concentrated on the formal properties of logical theory change and update, in order to define sensible properties of accumulating beliefs.
There are two fundamental goals. First, it is vital that the three communities meet, to establish some kind of consensus on the real strengths and weaknesses of each discipline. The hypothesis is that there is much to be shared, and---even stronger---much to be lost should these fields not collaborate. So the first goal is to have leaders in the fields identify what they believe are the strengths and weaknesses of the fields.
The second goal is to articulate a set of challenge problems, which are designed to help force the confirmation of the strengths and weaknesses identified within the context of the first goal.
As an example, the combination of constraint programming and belief revision provides the basis for formalizing the idea of dynamic incremental optimization. But the modeling languages available are certainly powerful enough to easily describe model problems that do not have the convex properties of simple optimization theory. How can one formalize an optimization system whose list of provable properties regarding optimality change as the problem specification evolves?
Many similar questions can be formulated.