Portal de Periódicos da CAPES

Dealing with the Product Constraint

2022; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-031-08011-1_18

1611-3349

Steve Malalel, Victor Jung, Jean-Charles Régin, Marie Pelleau,

Constraint Satisfaction and Optimization

The product constraint ensures that the product of some variables will be greater than a given value, that is $$\varPi _{i=1}^{n} x_i \ge w$$ . With the emergence of stochastic problems, this constraint appears more and more frequently in practice. The variables are most often probability variables that represent the probability that an event will occur and the minimum bound is the minimum probability that must be satisfied. This is often done to guarantee a certain level of security or a certain quality of service. To deal with this constraint, it is tempting as proposed by many authors to take the logarithm of the sum and the bound in order to transform the product into a sum. In this article we show that this idea creates many problems and forbids an exact calculation. We propose and compare different representations allowing to compute the set of solutions of this problem exactly or up to a certain precision. We also give an efficient method to represent that constraint by a Multi-valued Decision Diagram (MDD) in order to combine this constraint with some others MDDs.