Difference LP/MIP and CP

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.

The answer to this question depends on whether you see MIP and CP as algorithms, as problems, or as scientific fields of study.

E.g., each MIP problem is clearly a CP problem, as the definition of a MIP problem is to find a(n optimal) solution to a set of linear constraints, while the definition of a CP problem is to find a(n optimal) solution to a set of (non-specified) constraints. On the other hand, many important CP problems can straightforwardly be converted to sets of linear constraints, so seeing CP problems through a MIP perspective makes sense as well.

Algorithmically, CP algorithms historically tend to involve more search branching and complex constraint propagation, while MIP algorithms rely heavily on solving the LP relaxation to a problem. There exist hybrid algorithms though (e.g., SCIP, which literally means "Solving Constraint Integer Programs"), and state-of-the-art solvers often borrow techniques from the other side (e.g., no-good learning and backjumps originated in CP, but are now present in MIP solvers as well).

From a scientific field of study point of view, the difference is purely historical: MIP is part of Operations Research, originating at the end of WWII out of a need to optimize large-scale "operations", while CP grew out of logic programming in the field of Artificial Intelligence to model and solve problems declaratively. But there is a good case to be made that both these fields study the same problem. Note that there even is a big shared conference: CPAIOR.

So all in all, I would say MIP and CP are the same in most respects, except on the main techniques used in typical algorithms for each.