View Full Document

5 views

Unformatted text preview:

Constraint Programming and Mathematical Programming Tutorial John Hooker Carnegie Mellon University CP02 September 2002 This tutorial is available at http ba gsia cmu edu jnh g Why Integrate CP and MP Search Inference Duality Decomposition Relaxation Putting It Together Other OR Methods of Interest to CP Surveys Tutorials on Hybrid Methods Programming Programming Constraint programming is related to computer programming Mathematical programming has nothing to do with computer programming Programming historically refers to logistics plans George Dantzig s first application MP is purely declarative Why Integrate CP and MP Eventual goal View CP and MP as special cases of a general method Motivation to Integrate CP and MP Inference relaxation CP s inference techniques tend to be effective when constraints contain few variables Misleading to say CP is effective on highly constrained problems MP s relaxation techniques tend to be effective when constraints or objective function contain many variables For example cost and profit Motivation to Integrate CP and MP Horizontal vertical structure CP s idea of global constraint exploits structure within a problem horizontal structure MP s focus on special classes of problems is useful for solving relaxations or subproblems vertical structure Motivation to Integrate CP and MP Procedural declarative Parts of the problem are best expressed in MP s declarative solver independent manner Other parts benefit from search directions provided by user Integration Schemes Recent work can be broadly seen as using four integrative ideas Double modeling Use both CP and MP models and exchange information while solving Search inference duality View CP and MP methods as special cases of a search inference duality Decomposition Decompose problems into a CP part and an MP part using a Benders scheme Relaxation Exploit the relaxation technology of OR applies to all of the above Double Modeling Write part of the problem in CP part in MP part in both



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view HookerCP and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HookerCP and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?