At first glance both approaches appear to be very similar.
What are the major differences between integer programming and constraint programming?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ This is a very broad question. Integer programming (IP) has been around for a long time and therefore a lot of literature deals with IP techniques and models. Constraint Programming is conceptually also old (I think), but as a practical, fast solution method has gotten more traction in more recent years. Traditionally scheduling problems has benefitted the most from being model as a CP. I would suggest reading this piece and maybe try to narrow the question a bit if possible informs.org/ORMS-Today/Public-Articles/… $\endgroup$– Tue ChristensenJun 3, 2019 at 8:29
-
1$\begingroup$ There is also Constraint Integer Programming (CIP) which unifies both (to some extend) and implemented as a solver by SCIP. $\endgroup$– Robert SchwarzJun 3, 2019 at 8:37
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
You have asked a broad question, so I will provide a broad answer.
Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a system of linear inequalities. A single objective function is to be minimized which is again linear in the decision vector. Very often certain decision variables are constrained to take $\{0,1\}$ values to model logical constraints. Linear integer programming optimization models are solved by taking advantage of lower bounds found by solving linear programming problems in branch-and-bound and branch-and-cut algorithms.
I know less about constraint programming but it is a slightly different modeling and solution paradigm. Again decision variables are defined and each is specified on a domain; the domains used in practice are similar to those used in integer programming models. A set of constraints is defined on the decision variables and these constraints can be more general than those used in integer programming to allow direct modeling of logical constraints. The primary constraint programming problem is to find a decision vector that satisfies all constraints. Constraint propagation methods are used to identify such solutions (if they exist). Some constraint programming solvers also allow objective functions to be specified, and after feasible solutions are identified they seek those with better objective function values.
For many important problems, a natural integer programming formulation can be an excellent model and useful for finding optimal or near-optimal solutions. In other cases, the generality provided by constraint programming modeling may be a better choice and may identify high-quality solutions faster than an equivalent IP model. Knowing when to choose which toolkit for particular problem is an engineering skill and the right choice may change over time as both fields continue to evolve.
-
1$\begingroup$ How about modifying your description of IP (and maybe of CP too) and turning it into a tag wiki? (You might not be able to yet -- there is a pending edit to the tag description and those seem to be backlogged at the moment.) $\endgroup$ Jun 3, 2019 at 13:35
-
1$\begingroup$ I'm not sure what you mean. Others should feel free to modify my descriptions as needed. $\endgroup$– alereraJun 3, 2019 at 13:38
-
3$\begingroup$ A tag wiki is the medium-length description of a tag that appears when you click on a tag and then click on "learn more". OR.SE doesn't have any yet AFAIK, but here is the calculus tag wiki on math.SE. I'm not saying your description of IP has problems; on the contrary I'm suggesting you should turn it into a tag wiki so it becomes (the basis for) "our" definition of IP. $\endgroup$ Jun 3, 2019 at 13:40
-
2
$\begingroup$
$\endgroup$
There were times when the IP and CP communities started to learn about the existence of the other, and initially, people tried to build a list of vocabulary to translate one concept into another. You can still find these attempts like in these lecture notes by Bockmayr/Reinert. Examples are "node preprocessing" (in IP) vs. "domain propagation" etc.
$\begingroup$
$\endgroup$
In practice and without being exhaustive,
Linear Programming solves a linear combination of constraint with, but not only) a linear objective expression. As integer combinatorial problem, it use the simplex current optimal and dual deductions: That is the deduction are very strong but costly (cpu and memory) and heuristic decision are quite systematic. when working, it is a top quality techniques. When problems are strongly disjunctive (highly non linear) it may gives poor results.
Constraint Programming use both arithmetical and logical algebra. That is handle highly disjunctive (non linear) constraints. Deductions are made by constraint propagation, a relatively quick method but not as strong as with simplex. It is compensate by more effort in decisions heuristics techniques. It is known to work very well for highly disjunctive problem as scheduling with a large time horizon.
