Applications of Constraint Solving
Few of the important real-time, scientific and commercial applications that take advantage of Constraint Programming concepts.
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 - VLSI: 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: 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.
- Constraints and Combinatorial problems: Constraint programming framework can be a very good tool for combinatorial problems such as planning, scheduling and resource allocation problems. Advantage of CP framework is that a decision making problem can be very well expressed as a CSP. Leximin preorder which is otherwise called the lexicographic preorder over ordered utility vectors can be determined using a generic constraint programming algorithm. Three different algorithms have been proposed in the paper - one using a sorting constraint, the second using a meta-constraint and the third one using a multi-set ordering constraint. These algorithms have been applied to real-world scenario of combinatorial auctions where the goal is to maximize the revenue of the auctioneer which is the sum of the selected bids whoever receives them. In this particular example the constraint programming framework shows how effective constraints can be in dealing with optimization problems such as this one.
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. A rostering constraint library for use of crew rostering was developed and also a parallel solver was designed to run on different platforms which proved quite efficient in identifying in the context of airline crew rostering.
- Hong Kong International Airport The counter allocation problem that is usually encountered in big Airports is about allocating enough counters for any given aircraft (which of course depends on the size of the aircraft). However the point is that the counters for each flight form one island and all the counters of a flight should be grouped in the same island. Several models have been proposed to tackle this problem and different kinds of constraints have been developed like the overlapping and non-overlapping constraints to solve this problem.
- The Munich Rent Advisor (MRA) MRA won the prize for best application at JFPLC, Clermont Ferrand, France, June 1996. MRA is a small expert system that allows one to calculate the typical rent of a flat in Munich based on your input to a questionnaire. With advanced constraint technology provided by constraint handling rules, the computations can be performed even when some questions are left unanswered. This is a very good example of combining the concepts of Interval Computations and Constraint Programming. This application was characterized by a simple web server, Interval constraints over linear equations, a constraint database and some if-then-else rules.
- Siemens - A project named POPULAR: Planning of Picocellular Radio Cordless Communication was developed at Siemens research and development department for circuit verification. This tool optimizes the placement of radio transmitters for local wireless communications at company site. Given a blue-print of the building and information about the materials used for walls and ceilings, POPULAR computes the minimal number of transmitters and their location by simulation and subsequent optimization. The constraint handling library rules of ECLiPSe were put to use for the implementation of geometric constraints that appear in this placement problem.
Industrial Applications
- CHIC 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 while optimizing profit. It was also used to manage Asset and Liability management. The end results have proved to be very useful as the declarative style simplifies the task of modeling the problem and also both qualitative and quantitative models can be expressed efficiently.