Defining Constraint Satisfaction Problems (CSP)

Formally a CSP is defined by

  • a set of variables V1, V2, … Vn, and
  • a set of constraints, C1, C2, … Cm.

Each variable Vi has a non-empty domain Di of possible values. Each constraint Cj involves some subset of the variables and specifies the allowable combinations of values for that subset. A state of the problem is defined by an assignment of values to some or all of the variables. A solution to a CSP is an assignment that satisfies all the constraints. If a CSP requires a solution that maximizes or minimizes an objective function it is called “constraint optimization problem”.  A special module that solves a problem by finding one or several solutions or proving that there are no solutions is usually called “Solver”. I will devote a separate post(s) to Solvers, but here I will talk only about Problem Definition.

A problem may be considered as a placeholder and a factory for all variables and constraints. From a standardization perspective we suggest the following naming convention:

  • start all methods that create and add constrained variables with the word “variable
  • start all methods that create and post constrains with the word “constraint”.

In particular, the JSR-331 specifies a standard interface Problem with several variable-methods. For example, if p is an instance of the class Problem, you may write

Var digit = p.variable(“X”,0,9);

It will create a new constrained integer variable with the name “X” and domain [0;9]. This variable will be “added” to the problem that means that you may get this variable by its name using the method p.getVar(“X”) . The domain of a variable may be also defined not as an interval [min;max] but as an array of integers, e.g.

int[] domain = {0,1,2,3,4,5,6,7,8,9};
Var digit = p.variable(“X”,domain);

For efficiency reasons, if you know that your domain has many “holes” between its min and max, you may specify a type of your domain like in this example:

Var var = p.variable(”A”,1,1000,DomainType.DOMAIN_SPARSE);

Along with the most popular integer variables(defined by the interface Var) a Problem may include real variables (VarReal), boolean variables (VarBool), and set variables (VarSet). For example, you may create and add a real variable like this:

Var tempVar = p.variableReal(“R”,0.0,105.5);

Because JSR-331 enforces a strict naming convention for implementation packages, a user may also use directly constructors for the implementation classes like in this example:

Var digit = new javax.constraints.impl.Var(p,“X”,0,9);
p.add(digit);

That’s all about creation of constrained variables. I will describe suggested standardized ways for constraint creation in the next post.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s