A logic language for combinatorial optimization

CHIP (Constraint Handling In Prolog) is a new logic programming language combining the declarative aspect of logic programming for stating search problems with the efficiency of constraint handling techniques for solving them. CHIP has been applied to many real-life problems in Operations Research and hardware design with an efficiency comparable to specific programs written in procedural languages. The main advantage of CHIP is the short development time of the programs and their great modifiability and extensibility. In this paper, we discuss the application of the finite domain part of CHIP to the solving of discrete combinatorial problems occurring in Operations Research. The basic mechanisms underlying CHIP are explained through simple examples. Solutions in CHIP of several real-life problems (e.g., cutting stock, warehouses location problems) are presented and compared with usual approaches, showing the versatility and the interest of the approach.