0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Commented Aug 16, 2023 at 5:03
  • $\begingroup$ 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 $\endgroup$
    – sascha
    Commented Aug 17, 2023 at 1:53
  • 1
    $\begingroup$ 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) $\endgroup$
    – sascha
    Commented Aug 17, 2023 at 1:54
  • 1
    $\begingroup$ CP-SAT is a very good ILP solver. So even with purely linear model, it is worth using. $\endgroup$
    – Laurent Perron
    Commented Aug 17, 2023 at 14:19

1 Answer 1

Reset to default
3
$\begingroup$

For the CP-SAT solver, the rule of thumb is the following:

  • if you need to check if a variable ==/!= value, then you should use an array of Boolean variables instead
  • the start, end, size of interval variables must be integer variables
  • index of element constraint, variables in a constraint like all_different, table, automaton: they will all be expanded to Boolean variables as the constraints will also be expanded to Boolean and enforced linear constraints.

So for quantities, sums, time: use IntVar For assignment: use BoolVars.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.