EN FR
EN FR




Section: New Results

Constraints with costs (modelling and filtering)

Participants : Thierry Petit, Nicolas Beldiceanu.

  1. Distribution of costs We presented a new cardinality constraint dedicated to sequences of totally ordered cost. This constraint is useful to impose a precise (fair) distribution of the values taken by the cost variables in a given sequence, for instance in a bin packing with safety rules or in cumulative scheduling with overloads of resource. We came up with a generalized arc-consistency filtering algorithm, whose time complexity is linear in the sum of the number of variables and the number of values in the union of their domains.

    The corresponding paper the Ordered Distribute Constraint was published in the International Journal on Artificial Intelligence Tools  [15] .

  2. The objective sum constraint. Constraint toolkits generally provide a sum constraint whose propagation is poor to solve optimization problems. Therefore, solving real-world problems requires to develop ad-hoc techniques for handling sums, based on the particular properties of each problem. We proposed a generic technique which improves the standard sum constraint by exploiting the propagation of a set of constraints defined on the variables involved in a sum.

    The corresponding paper The Objective Sum Constraint was published in the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011 ) [25] .

  3. the increasing sum constraint Given a sequence of variables X of length n, we consider the increasing sum constraint, which imposes the variables of X to be sorted in non strictly order, and that the sum of the variables of X is equal to s. We propose an linear time bound-consistency algorithm for increasing sum. This work is related to problems with variable symmetries, when some of the symmetric variables are involved in sum constraints.

    The paper A Theta(n) Bound-Consistency Algorithm for the Increasing Sum Constraint was published at the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011 ), [24] .

These works were all done in collaboration with J.-C. Régin (Univ. Nice ).