Efficient Filtering for the Resource-Cost AllDifferent Constraint

摘要

High energy consuming industries are increasingly concerned about the energy prices when optimizing their production schedule. This is by far due to today politics promoting the use of renewable energies. A consequence of renewable energies is the high fluctuation of the prices. Today one can forecast accurately the energy prices for the next few hours and up to one day in advance. In this work, we consider a family of problems where a set of items, each requiring a possibly different amount of energy, must be produced at different time slots. The goal is to schedule them such that the overall energy bill is minimized. In Constraint Programming, one can model this cost in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. In the latter case, the cost of an edge linking a variable (i.e., an item) to a value (i.e., a time slot) is the product of the item consumption with the energy price of the time slot. Unfortunately, both approaches have limitations. Modeling with a sum of element constraints does not take into account the fact that the items must all be assigned to different time slots. The MinimumAssignment incorporates the AllDifferent constraint, but the algorithm has a quite high time complexity of O(n~3), where n is the number of items. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint [1] and an associated scalable filtering algorithm, running in 0{n.m), where m is the maximum domain size. Its purpose is to compute the total cost by dealing with the fact that all assignments must be different in a scalable manner. The constraint ResourceCostAllDifferent(X, C, P, T) ensures that ^{ AllDifferent(X) T = Σ_(i=1)~｜x｜ C(X_i)*P(X_i) where X is a sequence of integer variables; C is a sequence of X integer constants; P is a sequence of H integer constants (H ≥｜X｜); and T is an integer variable that is the total resource cost. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones.