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$
$(Chi, D, C) tag{CSP}$
[diophantine equation over finite domains]For example downside, allow us to outline the CSP for fixing a specific instance of a diophantine equation $x^3+y^2z^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^2z^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 pythonconstraint. 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.
$x$  $y$  $z$ 

$3$  $3$  $6$ 
$2$  $1$  $3$ 
If we plug in these values to $x^3+y^2z^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$
$(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$
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 pythonconstraint
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.
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

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