No label defined (Q4216092)

Constraint solvers usually only allow implicit constraints which are combined by conjunctions. In practical applications however explicit alternatives combined by disjunctions are common. They can be solved by backtracking only at the cost of large running times. This work develops algorithms for the transformation into conjunctive constraints. First the key idea of transforming implicit constraints given by equalities and inequalities in disjunctive form into conjunctive constraints using switching-variables (Schaltvariable) is exemplified. In the next chapter explicit alternatives are tackled. Using logic programming complete enumeration and backtracking is a common method. This one is contrasted with three methods based on the above transformation applied to alternatives of binary variables. So the author shows first how to transform general numerical alternatives into alternatives of binary variables. Each alternative can be described by an inequality or an equality, in the second case a grouping of alternatives may precede. Transforming them into conjunctive form gives the three algorithms. The author provides prolog programs to carry through simulations of the algorithms. The comparison of running times suggest exponential running times for complete enumeration and polynomial ones in the other cases, with grouping being the fastest.