Constraint Programming and Mathematical ProgrammingTutorialJohn HookerCarnegie Mellon UniversityCP02September 2002This tutorial is available athttp://ba.gsia.cmu.edu/jnhgWhy Integrate CP and MP?Search/Inference DualityDecompositionRelaxationPutting It TogetherOther OR Methods of Interest to CPSurveys/Tutorials on Hybrid MethodsgProgrammingProgrammin≠• 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 methodMotivation 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.• “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.Motivation to Integrate CP and MPIntegration SchemesRecent 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.• Exchange information - bounds, infeasibility, etc.• Dual modeling is a feature of other more specific schemes and will not be considered separately.Search-Inference Duality• CP and MP have a fundamental isomorphism: search and inference work together in a duality relationship, such as branch and infer (Bockmayr & Kasper).• Search (a primal method) examines possible solutions.• Branching (domain splitting), local search, etc.• Inference (a dual method) deduces facts from the constraint set.• Domain reduction (CP), cutting planes (MP). • Both the search and inference phases can combine CP/MP.Decomposition• Some problems can be decomposed into a master problem and subproblem.• Master problem searches over some of the variables.• For each setting of these variables, subproblemsolves the problem over the remaining variables.• One scheme is a generalized Benders decomposition.• CP is natural for subproblem, which can be seen as an inference (dual) problem.Relaxation• MP relies heavily on relaxations to obtain bounds on the optimal value.• Continous relaxations, Lagrangean relaxations, etc.• Global constraints can be associated with relaxations as well as filtering algorithms.• This can prune the search tree in a branch-and-infer approach.• Relaxation of subproblem can dramatically improve decomposition if included in master problem.Search/Inference DualityLinear ProgrammingInteger ProgrammingGomory Cuts (dual method)Branch and InferDiscrete Lot SizingExample: Linear Programming Duality(Dantzig, Von Neumann)Primal problem:0)(subject tominimize≥≥xubAx cxPrimal: Search for optimal value x* of x.Dual problem:0)(subject tomaximize≥≤uxcuA ubDual: Prove that cx* is optimal value of primal:Identify a linear combination u of the primal constraints uAx ≥ ubthat implies cx ≥ cx*≥≥Example: Linear Programming Duality• In this case, the solution of the dual has polynomial size.• LP belongs to NP and co-NP.• Dual is itself an LP.• LP can be solved by primal-dual algorithm.• In general, the dual solution tends to be exponential in size.• For example, integer programming.Example: Integer Programminginteger and 0,32231427subject to4maximize212122121≥≤−≤≤−−xxxxxxxxxExample from Wolsey, 1998.• Can be solved by branching on values of xj(to be illustrated shortly). This is a primal method.• Can also be solved by generating cutting planes. This is a dual method.A Cutting Plane Approach(Gomory)• Solve continuous relaxation of problem.)32( ,76=x1x2x• Generate Gomory cuts.)1,2(=x• Re-solve relaxation (solution is now integer).• Can now solve the original problem by solving continuous relaxation (a linear programming problem).• In the worst case, cutting plane proofs are exponentially long.• In practice, cutting planes are combined with branching (branch and cut).0,2132231427subject to4maximize211212122121≥≤≤−≤−≤≤−−xxxxxxxxxxxx• The problem with the two cutting planes is:Solution of this relaxation is (x1,x2) = (2,1)GomorycutsThese Gomory cuts are rank 1 Chvátal cuts obtained by taking a nonnegative linear combination of constraints and rounding.00,020103222311427subject to4maximize211212122121≥≤≤−≤−≤≤−−xxxxxxxxxxxxMultipliers in linear combination2220717611≤≤≤xxxCan round down RHSDo this recursively to generate all valid cutting planes & convex hull.(Chvátal)Cutting planeBranch and Infer}4,,1{},,{different-all30353subject to585min321321321K∈≥++++jxxxxxxxxxxWe will illustrate how search and inference may be combined to solve this problem by:• constraint programming• integer programming• a hybrid approachSolve as a constraint programming problem}4,,1{},,{different-all30253485321321321K∈≥++≤++jxxxxxxxzxxxStart with z = ∞.Will decrease as feasible solutions are found.Search: Domain splittingInference: Domain reduction and constraint propagationDomain reduction for inequalities• Bounds propagation on30253485321321≥++≤++xxxzxxximpliesFor example,30253321≥++xxx258123052330312=−−≥−−≥xxxSo the domain of x2is reduced to {2,3,4}.Domain reduction for all-different (e.g., Régin)• Maintain hyperarc consistency on},,{different-all321xxxSuppose for example:12121234Domain of x1Domain of x2Domain of x3Then one can reduce the domains:1212341. z =