Difference LP/MIP and CP

Question

what is the difference between Constraint Programming (CP) and Linear Programming (LP) or Mixed Integer Programming (MIP) ? I know what LP and MIP is but dont understand the difference to CP - or is CP just the same as MIP and LP ? I am a but confused on this ...

Answer 1

This may be a little exhaustive, but I will try to provide all the information to cover a good scope of this topic. I'll start with an example and the corresponding information will make more sense.

Example: Say we need to sequence a set of tasks on a machine. Each task i has a specific fixed processing time p_i. Each task can be started after its release date r_i , and must be completed before its deadline d_i. Tasks cannot overlap in time. Time is represented as a discrete set of time points, say {1, 2,…, H} (H stands for horizon)

MIP Model:

• Variables: Binary variable x_ij represents whether task i starts at time period j
• Constraints:
  
  • Each task starts on exactly one time point
    
    • ∑_j x_ij = 1 for all tasks i
      
  • Respect release date and deadline
    
    • j*x_ij = 0 for all tasks i and (j < r_i ) or (j > d_i - p_i )
      
  • Tasks cannot overlap
    
    • Variant 1: ∑_i x_ij ≤ 1 for all time points j we also need to take processing times into account; this becomes messy
      
    • Variant 2: introduce binary variable b_i representing whether task i comes before task k must be linked to x_ij; this becomes messy MIP models thus consists of linear/quadratic optimization functions, linear/ quadratic optimization constraints and binary/integer variables.

CP model:

• Variables: * Let start_i represent the starting time of task i takes a value from domain {1,2,…, H} - this immediately ensures that each task starts at exactly one time point
  
• Constraints: * Respect release date and deadline
  r_i ≤ start_i ≤ d_i - p_i * Tasks cannot overlap: for all tasks i and j (start_i + p_i < start_j) OR (start_i + p_i < start_i)
  and that is it!

You could probably say that the structure of the CP models and MIP models are the same: using decision variables, objective function and a set of constraints. Both MIP and CP problems are non-convex and make use of some systematic and exhaustive search algorithms.

However, we see the major difference in modeling capacity. With CP we have n variables and one constraint. In MIP we have nm variables and n+m constraints. This way to map global constraints to MIP constraints using binary variables is quite generic

CP and MIP solves problems in a different way. Both use a divide and conquer approach, where the problem to be solved is recursively split into sub problems by fixing values of one variable at a time. The main difference lies in what happens at each node of the resulting problem tree. In MIP one usually solves a linear relaxation of the problem and uses the result to guide search. This is a branch and bound search. In CP, logical inferences based on the combinatorial nature of each global constraint are performed. This is an implicit enumeration search.

Optimization differences:

• A constraint programming engine makes decisions on variables and values and, after each decision, performs a set of logical inferences to reduce the available options for the remaining variables' domains. In contrast, an mathematical programming engine, in the context of discrete optimization, uses a combination of relaxations (strengthened by cutting-planes) and "branch and bound."
  
• A constraint programming engine proves optimality by showing that no better solution than the current one can be found, while an mathematical programming engine uses a lower bound proof provided by cuts and linear relaxation.
  
• A constraint programming engine doesn't make assumptions on the mathematical properties of the solution space (convexity, linearity etc.), while an mathematical programming engine requires that the model falls in a well-defined mathematical category (for instance Mixed Integer Quadratic Programming (MIQP).
  

In deciding how you should define your problem - as MIP or CP, Google Optimization tools guide suggests: -

1. If all the constraints for the problem must hold for a solution to be feasible (constraints connected by "and" statements), then MIP is generally faster.
   
2. If many of the constraints have the property that just one of them needs to hold for a solution to be feasible (constraints connected by "or" statements), then CP is generally faster.
   

My 2 cents:
CP and MIP solves problems in a different way.  Both use a divide and conquer approach, where the problem to be solved is recursively split into sub problems by fixing values of one variable at a time.  The main difference lies in what happens at each node of the resulting problem tree.  In MIP one usually solves a linear relaxation of the problem and uses the result to guide search.  This is a branch and bound search.  In CP, logical inferences based on the combinatorial nature of each global constraint are performed.

There is no one specific answer to which approach would you use to formulate your model and solve the problem. CP would probably work better when the number of variables increase by a lot and the problem is difficult to formulate the constraints using linear equalities. If the MIP relaxation is tight, it can give better results - If you lower bound doesn't move enough while traversing your MIP problem, you might want to take higher degrees of MIP or CP into consideration. CP works well when the problem can be represented by Global constraints.

Some more reading on MIP and CP:
Mixed-Integer Programming problems has some of the decision variables constrained to integers (-n … 0 … n) at the optimal solution. This makes it easier to define the problems in terms of a mathematical program. MP focuses on special class of problems and is useful for solving relaxations or subproblems (vertical structure).
Example of a mathematical model:
Objective: minimize cT x    Constraints: A x = b (linear constraints) l ≤ x ≤ u (bound constraints) some or all xj must take integer values (integrality constraints)
Or the model could be define by Quadratic functions or constraints, (MIQP/ MIQCP problems)
Objective: minimize xT Q x + qT x    Constraints: A x = b (linear constraints) l ≤ x ≤ u (bound constraints) xT Qi x + qiT x ≤ bi (quadratic constraints) some or all x must take integer values (integrality constraints)

The most common algorithm used to converge MIP problems is the Branch and Bound approach.

CP: CP stems from a problems in AI, Operations Research and Computer Science, thus it is closely affiliated to Computer Programming.
- Problems in this area assign symbolic values to variables that need to satisfy certain constraints.
- These symbolic values have a finite domain and can be labelled with integers.
- CP modelling language is more flexible and closer to natural language.
Quoted from one of the IBM docs, constraint Programming is a technology where:

• business problems are modeled using a richer modeling language than what is traditionally found in mathematical optimization
  

• problems are solved with a combination of tree search, artificial intelligence and graph theory techniques
  

The most common constraint(global) is the "alldifferent" constraint, which ensures that the decision variables assume some permutation (non-repeating ordering) of integer values. Ex. If the domain of the problem is 5 decision variables viz. 1,2,3,4,5, they can be ordered in any non-repetitive way.