Constraint Solving by Martine Ceberio


Applications of Constraint Solving

Real-time applications that take advantage of constraint programming techniques have been increasing by leaps and bounds every year for more than a decade now. A lot of areas such as manufacturing, financial services, telecommunications, defense etc have been employing constraint and logic programming.


CP and combinatorial optimization in circuit verification

One of the three features of Constraint programming is modeling. A modeling language allows a software analyst to specify requirements of a software system on an architectural level. In designing and verifying VLSI circuits problem modeling is effectively achieved with constraints. Functional verification has become quite difficult these days what with increasing complexity in design issues. Automated functional vector generation has been made possible using CP. In recent years Boolean Satisfiability is being significantly used for various tasks in circuit verification. Using Boolean Constraint Propagation most of the SAT solvers perform very efficiently. BCP is implemented by representing the electric circuit using a Conjunctive Normal Form.

CP and Simulations

Simulations are the most important applications of constraints. Especially in the area of Physics all kinds of laws can be expressed as some or the other kind of a constraint. Animus is a constraint solving system that involves the concept of constraints and time. This has made possible the creation of animations using temporal constraints.

Scientific
Applications

Constraints and Molecular Biology

Constraints and Molecular Biology: Constraint Programming techniques can be efficiently used for predicting structure of a protein which is considered one of the most important problem in Computational Biology. The protein structure prediction problem has effectively been transformed to a constraint minimization problem with finite domain and Boolean variables. The Oz language was then used to implement the constraint problem. Certain variables have been defined for the entire constraint problem of predicting the protein structure. Later constraint optimization has been used to minimize the variable surface. A perfect conformation was found on all possible sequences in finding the sequence length and also the optimal surface. Hence constraint techniques can be effectively applied to solving problems in computational biology.

Read More

Commercial
Applications

XLufthansa

A project named PARROT was designed and implemented which was aimed at providing efficient means to address the highly complex and costly problem of airline crew scheduling by combining the techniques of Operations Research and Constraint Programming.

Read More

Industrial
Applications

HIC Project (Constraint Handling in Industry and Commerce)

This project aims at exploiting CLP in Industrial applications. A system for treasury planning based on CLP technology was developed which required as input the expected liquidity balances for the next 10 working days and the interest rates on the money market. As output it delivers a set of operations that covers all deficits a set of operations that covers all deficits and utilizes all surpluses…

Read More