Constraint Programming – Marek Narozniak’s Homepage

Pc programming is greater than having a machine blindly following bunch of guidelines below the type of laptop program. There are numerous paradigms of programming and constraint logic programming (Jaffar & Lassez, 1987) is a type of nondeterministic programming (Floyd, 1967). Underneath constraint program, your “program” is a mannequin involving constraints, which is to be processed by a solver trying to find answer or a set of options to the mannequin.

The constraint satisfaction downside includes a set of variables $Chi$, their respective domains $D$ and a set of constraints $C$ that should be glad, placing all of it collectively offers the next construction.

$(Chi, D, C) tag{CSP}$

For example downside, allow us to outline the CSP for fixing a specific instance of a diophantine equation $x^3+y^2-z^2=0$

$start{aligned} P &= (Chi, D, C), Chi &= {x, y, z}, D &= {x in [1 dots 10], y in [1 dots 10], z in [1 dots 10]}, C &= {x^3+y^2-z^2=0} finish{aligned}$

Best approach to get began, a minimum of for me, can be to make use of a easy constraint programming library for Python python-constraint. Allow us to begin by creating empty mannequin, outline variables and their finite domains.

from constraint import Drawback
downside = Drawback()
downside.addVariable('x', vary(1, 10))
downside.addVariable('y', vary(1, 10))
downside.addVariable('z', vary(1, 10))

Outline customized constraint that checks if the diophantine equation is glad.

def constraintCheck(x, y, z):
    if x**3 + y**2 - z**2 == 0:
        return True
    return False
downside.addConstraint(constraintCheck, ['x', 'y', 'z'])

Course of the mannequin and get all of the options and print them out.

options = downside.getSolutions()
for answer in options:
    print(answer)
    x = answer['x']
    y = answer['y']
    z = answer['z']
    # you are able to do one thing with the values of x, y, z right here

This gives us with the next output.

If we plug in these values to $x^3+y^2-z^2=0$

What about optimization issues? What differs constraint satisfaction downside from constraint optimization downside can be the target perform and a criterion. The target perform is a mathematical perform accepting project of values to variables $Chi$ withing their respective domains $D$ and returns a quantity. The criterion is both minimization both maximization, since these are equal as much as an indication allow us to simply assume any further we we have now minimization by default. If we incorporate these ideas the constraint satisfaction downside will turn into the constraint optimization downside and what differs them is there’s some type of measure of high quality of answer and never all options are equal, some are most well-liked over others.

$(Chi, D, C, textual content{min} f(Chi)) tag{COP}$

We’ve got a pleasant instance of downside we may use to outline and resolve an instance constraint optimization downside, we have now our Pokémon Facilities and Pokémon Gyms downside from Vertex Covers and Independent Sets in game level design and we even have a quantum adiabatic answer to match from Quantum Adiabatic Optimization. In the event you haven’t learn these tutorials I extremely advocate you test them now to know what the issue is about, and in case you are already accustomed to it, allow us to proceed with a mannequin.

$start{aligned} P &= (Chi, D, C, textual content{min} f(Chi)), Chi &= {x_text{Pallet City}, x_text{Viridian Metropolis}, dots x_text{Cinnabar Island}}, D &= {x in {textual content{heart}, textual content{health club}} vert x in Chi}, C &= {vert{x_a, x_b} cap {textual content{health club}}vert leq 1vert (x_a, x_b) in E(G)}, f(Chi) &= sum_{x_a in Chi} vert{x_a} cap {textual content{heart}}vert finish{aligned}$

Variables $Chi$ are cities from Kanto area map from unique Pokémon video games, their domains $D$ encompass two values – they are often both Pokémon Facilities both Pokémon Gyms, lastly the constraints implement the situation of the unbiased set and we use the the target perform to attenuate the overal variety of Pokémon facilities, successfully fixing the minimal vertex cowl downside.

As with the earlier instance, we begin by defining empty mannequin.

G = (V, E)
V = listing(V)
E = listing(E)
downside = Drawback()

To outline the variables and their domains we observe our definition – each city in Kanto can have both a Pokémon Facilities both Pokémon Gyms.

for city in V:
    varname = city.decrease().substitute(' ', '_')
    downside.addVariable(varname, ['center', 'gym'])

Just one particular constraint is required for every fringe of the graph (or every route), it’s the unbiased set constraint – there may be no two Pokémon Gyms subsequent to one another.

for pair in listing(E):
    dest_i, dest_j = tuple(pair)
    dest_i = dest_i.decrease().substitute(' ', '_')
    dest_j = dest_j.decrease().substitute(' ', '_')
    downside.addConstraint(lambda x, y: True if not x == y == 'health club' else False, [dest_i, dest_j])

We course of the mannequin and get the all of the CSP options

options = downside.getSolutions()

Now the tough half, the python-constraint library doesn’t assist constraint optimization issues, so we should perform a little hack to get the COP options – we will filter out the options that fulfill the standards. To make issues a bit extra enjoyable, we are going to implement each goal perform, the minimal vertex cowl and most unbiased set standards simply to test in the event that they match (they have to).

best_mis = []
best_mis_size = 0
best_mvc = []
best_mvc_size = len(V) + 1
# get COP answer
for answer in options:
    values = listing(answer.values())
    nb_gyms = values.depend('health club')
    nb_centers = values.depend('heart')
    # MVC criterion
    if nb_centers < best_mvc_size:
        best_mvc = [solution]
        best_mvc_size = nb_centers
    elif nb_gyms == best_mvc_size:
        best_mvc.append(answer)
    # MIS criterion
    if nb_gyms > best_mis_size:
        best_mis = [solution]
        best_mis_size = nb_gyms
    elif nb_centers == best_mis_size:
        best_mis.append(answer)

Allow us to this Python trick to test if lists of dictionaries are deeply equal.

See Also

The top of cash

assert [i for i in best_mis if i not in best_mvc] == []

In the event that they don’t match that may crash… And it didn’t (you’ll have to belief me or run by your self).

Allow us to proceed the custom and visualize the options in retrograming fashion!

Completely matches the quantum answer from Quantum Adiabatic Optimization… And any further allow us to use COP answer because the reference, it’s a lot smarter approach to get options than brute pressure we utilized in Vertex Covers and Independent Sets in game level design. Even when we hacked round to get the COP criterion processed, which isn’t very reminiscence environment friendly, it nonetheless ought to be higher. For bigger fashions I extremely advocate to make use of library that already incorporates COP standards of their search algorithm.

I feel that may be it, I made a decision to maintain it transient this time. As common, in case you discover errors or typos, or simply wish to talk about, be happy to tweet me!

For the entire supply code please seek the advice of the gist repository

1. Jaffar, J., & Lassez, J.-L. (1987). Constraint Logic Programming. In Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Rules of Programming Languages, POPL ’87 (pp. 111–119). New York, NY, USA: Affiliation for Computing Equipment.

   10.1145/41625.41635