Combining optimization and constraint programming by logic-based methods

It has been considered for a long time that combinatorial optimization problems should be solved with techniques in operations research. In the past decade, computer science has advanced at such an eye dazzling speed that it has changed industry in many ways. Along with the progress of computer science, constraint programming, as a subfield of artificial intelligence, has grown from logic programming and theory of constraint satisfaction. Recently constraint programming has proved its strength by solving classes of combinatorial optimization problems obtained from industry applications, which accordingly provoked a new area of research in OR/CS interface. Since constraint programming has grown from a totally different background from operations research, it is distinctive in many aspects—such as modeling and solution methods. Constraint programming may have even been considered as a competing paradigm because problems solved by constraint programming techniques are traditionally in the domain of optimization of operations research. This dissertation will show that constraint programming and optimization are not competing but rather complementary to each other and will propose how to combine optimization and constraint programming in logic-based methods to solve problems. The contents of this book consists of four papers which were previously published or are in process of publication. The first proposes a new general declarative modeling framework that combines the two fields. The second discusses which properties are common in the solution methods of optimization and constraint programming and suggests a scheme to integrate the techniques from optimization and constraint programming. The third paper discusses how to combine tightly techniques of constraint propagation and linear programming into a specific integration, the mixed logic/linear programming. Finally, the last paper describes how to solve a specific class of problems, the fixed-charge network flow problem, under the new hybrid approach.