# Using binary variable or integer variable in Constraint Programming (CP)?

I am trying to solve an assignment problem by Constraint Programming (CP). Let us consider a task assignment problem that have $$|M|$$ tasks and $$|N|$$ machines, each task has different processing time required on each machine, and each machine has a maximum capacity (number of tasks can be processed). The objective is to assign each task to a single machine with respect to the precedence requirements, such that the overall processing time can be minimized.

To model the assignment decisions, we can use $$|M||N|$$ binary variables (represent whether a task is assigned to a machine) or $$|M|$$ integer variables (each has a domain of $$[1, |N|]$$, represent the machine that each task is assigned to). I am little experienced with CP, but I have read material that says less variable, and more constraints can be beneficial for solving CP. So, I suspect that using integer variables is better.

My questions are:

- How the choice of variable type (binary / integer) impacts the algorithm efficiency?

- Will CP solvers (e.g. OR-Tools) convert integer variables into binary ones automatically, such that there is no difference between binary variables and integer variables?

This question is related to How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation? and Does exchanging integer variables by binary variables strengthen a MIP?, which are in the context of Mathematical Programming, rather than CP.

• As far as I know, and at least for the scheduling problems, the main benefit of the $CP$ is by using the interval and sequence variables in contrast to the $MIP$ formulation. I am not sure if by defining the binary or integer variables directly, the performance may have a considerable difference. Aug 16 at 5:03
• Imho it depends a bit on your Solver-API and your modelling-approach. In most cases i would expect n*m optional interval-variables and all APIs i know will need boolean-vars to enable/disable those intervals. On the other hand, there is nothing more efficient to express the "select a single machine" than an int-var (and a sum=1 on bools can be rather inefficient). Usually this means you will have both, bool and int and channel/link those to get the best of both worlds. See Gecode API. This applies to more classic CP Aug 17 at 1:53
• Some solvers might deviate a lot from classic CP and things might change significantly. ILOG CP probably has high-lvl constraints and or-tools cp-sat is based on lazy-clause generation. In both cases, it's more important to identify a fitting modelling-approach (cp-sat examples: flex-jss + gate-sched) before focusing on the assignment subproblem. Both solvers know about scheduling-structures and i would highly recommend those. or-tools will indeed use booleans internally eventually, even for int-vars, but not for the reasons you expect. It's a necessity for LCG conflict-analysis (explanations) Aug 17 at 1:54
• CP-SAT is a very good ILP solver. So even with purely linear model, it is worth using. Aug 17 at 14:19