In this post I present how Groovy meta-programming features can be leveraged to implement a Linear Programming (hereafter called LP) DSL, called Groptim. Internally, Groptim uses the Apache Commons Mathematics Library and its Simplex implementation (see org.apache.commons.math3.optim.linear.SimplexSolver) to solve the LP instances.
Every LP instance can be written in the LP canonical form, which defines all the constrains to be "less than or equals to" and all the variables non-negative:
Some flexibility beyond the canonical form is offered:
Let's see how an LP instance looks like in Groptim:
The first line obviously creates an object of the main Groptim class, which is LPSolver.groovy. To define a maximization problem we write lp.max (for minimization write lp.min).
Immediately after the max (or min), we have to define the Objective Function (hereafter OF). in brackets {} (the space between max and the brackets is optional). In this case the OF is 15*x0 + 10*x1 + 7. Notice that we write 7.c to denote the constant number 7. This is needed as every term of the OF (and itself as a whole) has to be evaluated as an Expression object by Groovy. We will dive into implementation details in the next paragraph. Notice that constants are not needed in the OF. Finding a vector x that maximizes (or minimizes) 15*x0 + 10*x1 + 7 is equivalent with finding a vector x that maximizes (resp. minimizes) 15*x0 + 10*x1. This is why the canonical LP form does not allow for constants in the OF. For Groptim a constant in the OF is optional.
After the objective function block, the keyword 'subjectTo' has to follow to denote that the block that follows defines the constraints. Instead of 'subjectTo', one can write 'subject() to', but not 'subject to'. Looking at the constraints, the first two are straightforward, but the 3rd and 4rth are the result of canonizing the non-canonical constraint x0 + x1 = 4. This is equivalent with x0 + x1 <= 4 and x0 + x1 >= 4 that should both be satisfied. The first is canonical, the second can be easily canonized by multiplying -1 both sides of the inequality and therefore changing '>' with '<': -x0 - x1 <= -4.
That's it, this is valid Groovy code. After the subjectTo block you can access the lp fields to read the solution of the LP instance, e.g.:
which means that the OF is maximized at (x0, x1) = (2, 2) and its maximum value is 57.
Notice that any string (except for Groovy reserved keywords) can be used for variable names, e.g. instead of x0, x1, x2, one can write x, y, or myvar. Also coefficients can be arbitrary real numbers and standard arithmetic rules apply, e.g.
Source code, Dependencies, License
Groptim is an open source project licensed under Apache License, Version 2.0.
The code is hosted by github under the groptim repository.
Gradle is used for building and dependency management.
The only compile time dependency is the Apache Commons Mathematics Library, while testing is done with Spock.
Usage for Groovy Developers
Plenty of examples on how to use Groptim from Groovy code can be found at LPSolverSpec.groovy. In this paragraph, I pick some representative examples to present the flexibility and the limitations of the syntax.Every LP instance can be written in the LP canonical form, which defines all the constrains to be "less than or equals to" and all the variables non-negative:
Some flexibility beyond the canonical form is offered:
- you can define min instead of max to minimize the objective function;
- constants are allowed in the objective function;
- variables are allowed to be negative (if you want one to be strictly non-negative, you need to make this explicit with a constraint).
Let's see how an LP instance looks like in Groptim:
The first line obviously creates an object of the main Groptim class, which is LPSolver.groovy. To define a maximization problem we write lp.max (for minimization write lp.min).
Immediately after the max (or min), we have to define the Objective Function (hereafter OF). in brackets {} (the space between max and the brackets is optional). In this case the OF is 15*x0 + 10*x1 + 7. Notice that we write 7.c to denote the constant number 7. This is needed as every term of the OF (and itself as a whole) has to be evaluated as an Expression object by Groovy. We will dive into implementation details in the next paragraph. Notice that constants are not needed in the OF. Finding a vector x that maximizes (or minimizes) 15*x0 + 10*x1 + 7 is equivalent with finding a vector x that maximizes (resp. minimizes) 15*x0 + 10*x1. This is why the canonical LP form does not allow for constants in the OF. For Groptim a constant in the OF is optional.
After the objective function block, the keyword 'subjectTo' has to follow to denote that the block that follows defines the constraints. Instead of 'subjectTo', one can write 'subject() to', but not 'subject to'. Looking at the constraints, the first two are straightforward, but the 3rd and 4rth are the result of canonizing the non-canonical constraint x0 + x1 = 4. This is equivalent with x0 + x1 <= 4 and x0 + x1 >= 4 that should both be satisfied. The first is canonical, the second can be easily canonized by multiplying -1 both sides of the inequality and therefore changing '>' with '<': -x0 - x1 <= -4.
That's it, this is valid Groovy code. After the subjectTo block you can access the lp fields to read the solution of the LP instance, e.g.:
which means that the OF is maximized at (x0, x1) = (2, 2) and its maximum value is 57.
Notice that any string (except for Groovy reserved keywords) can be used for variable names, e.g. instead of x0, x1, x2, one can write x, y, or myvar. Also coefficients can be arbitrary real numbers and standard arithmetic rules apply, e.g.
- 0*x1 is equivalent with 0.c
- 1.7*x0 - x1 is equivalent with 1.7*x0 + -x1
Also, non-linear OF, or constraints are not allowed in LP, therefore Groptim throws an IllegalStateException if you write a something like x0*x1 or (2*x0 + 5.c)*(4*x1-3.c).
Usage for Everyone
One of the many reasons why Groovy is "groovy", is that it can be used as a scripting language. In the script/ directory I have included the groptim script along with two input LP files written in Groptim:
Notice that the lp object is not needed in this case. I will explain in the following paragraph how the script silently injects it. You can run groptim script to solve the LP instances described in these files and get the solution printed in your console as:
To allow this magic to happen, you need to install Groovy and have the groovy command in your path. Notice that groptim script has 2 dependencies (managed by Grape), apache math ('org.apache.commons:commons-math3:3.5') and Groptim itself ('org.ytheohar:groptim:1.0'). Both will be fetched from the maven central repository. When groptim script runs it will have Ivy copy these artifacts under your .groovy/grapes/ directory.
How it works
The objective function as well as both the left and right part of each constraint is evaluated as an Expression or more precisely as one of its subclasses, i.e. NumberExpression, LPVar or BinaryExpression. Take for instance 15*x0 + 10*x1 + 7.c:
- x0 is evaluated as an LPVar
- 15*x0 as a BinaryExpression
- x1 as an LPVar
- 10*x1 as a BinaryExpression
- 7.c as a NumberExpression
- 15*x0 + 10*x1 as a BinaryExpression
- 15*x0 + 10*x1 + 7.c as a BinaryExpression
Number.metaClass.getC { new NumberExpression(delegate) }
Then, we can append any number with .c and Groovy will evaluate this by delegating to the method getC, e.g. 7.c is equivalent with 7.getC() which in turn is evaluated into new NumberExpression(7).
The evaluation of x0 and x1 (steps 1, 3) as LPVar objects is more interesting. This is a good point to introduce the LPSolver class which implements the core of the Groptim DSL:
The max method takes as argument the OF block, which is evaluated in a closure by Groovy and passes that closure to optimize method. This changes the delegate object from the object that owns the closure (i.e. the one it was defined in) to this (i.e. LPSolver instance). Then it calls the closure, which triggers the above evaluation of the OF block into a BinaryExpression.
On the first occurrence of x0 in the OF block, Groovy will search for a field x0 in the delegate object (which is an LPSolver instance). It will not find any, so it will call the propertyMissing method on the delegate object. The implementation of this method first looks if a variable with the name 'x0' has been registered before and if not it registers it. It is important to understand that if I had not set the delegate to be this in the optimize method, then Groovy would have called the propertyMissing method on the object that owns the LPSolver instance, possible throwing a MethodMissingException. This would be client's class, e.g. it wiould be LPSolverSpec, when we run a test.
Both LPVar and NumberExpression define a negative() method, to which Groovy delegates the symbol '-', e.g. -x0 (strictly no space between '-' and x0) is equivalent with x0.negative() and -7.c to 7.getC().negative().
A number multiplied with an LPVar is evaluated (steps 2 and 4) as a BinaryExpression. To do this, I had to add the multiply method into the Number.metaclass (see LPSolver constructor). This makes 15*x0 equivalent with 15.multiply(x0) which evaluates in a BinaryExpression.
Groovy delegates the symbol '+','-' (when there is one or more spaces between '-' and a variable, e.g. x0) and '*' to plus, minus and multiply method respectively (steps 6, 7). It should be no surprise to you that Expression class defines all of them, to make possible the composition of Expressions (BinaryExpressions to be more precise) from other Expressions:
Finally, Groovy delegates all the comparison operators ('<','>','<=','>=') to the compareTo method, e.g. x0 + x1 <= 4.c is equivalent with (x0 + x1).compareTo(4.c) <= 0. Notice that the compareTo implementation creates a new constraint and registers it in the solver object. This poses a limitation for Groptim as any comparison operator will be delegated to the same method and there is no way to know which comparison operator triggered this call. Therefore, any constraint is considered as '<=' constraint from Groptim and this is the reason why Groptim strictly follows the canonical LP form for constraints.
It should be stressed that Groovy delegates the '==' operator into the equals method (e.g. x0 == 2.c is equivalent with x0.equals(2.c)), except if the delegate's class implements the Comparable interface, in which case it delegates to compareTo (e.g. x0 == 2.c is equivalent with x0.compareTo(2.c) == 0). Therefore, Groptim will consider a '==' constraint as an '<=' constraint too.
More precisely, if the delegate class implements the Comparable interface, the '==' operator is not directly delegated to the compareTo method. Take for instance, the constraint x0 == 2.c. If neither x0 (LPVar instance) is of a subtype of 2.c (NumberExpression instance) or 2.c is of a subtype of x0, then Groovy will not call compareTo at all, as it can conclude that the two objects are not equal. This check is done in the Groovy SDK class org.codehaus.groovy.runtime.typehandling.DefaultTypeTransformation and its compareToWithEqualityCheck method:
Due to this reason, I defined both LPVar and BinaryExpression as subclasses of NumberExpression. Otherwise, compareTo would not be called for '==' constraints and I would loose them, since constraint objects are created in the compareTo method.
Another interesting point is the return type of the optimize (and therefore max and min) method. It is a map that maps the String 'subject' to the closure { it -> ['to': { Closure cTo-> subjectTo(cTo)}]} and the String 'subjectTo' to the closure { it -> subjectTo(it)}. As you may have realized, this allows for the two alternative Groptim syntaxes for constraints, i.e. 'subject() to {}' and 'subjectTo {}' respectively.
When you write 'subjectTo {}', effectively you ask for the value that 'subjectTo' maps to. This value is a closure that takes as argument another closure denoted by it (represents the constraints block) and passes that to the subjectTo method. Pure fun! Isn't it?
The case that you write 'subject() to {}' is a little more interesting (more fun). In this case, you effectively ask for the value that the String 'subject' maps to, which is a closure. By writing () you call this closure which returns the map ['to': { Closure cTo-> subjectTo(cTo)}]. Obviously, this maps the String 'to' to another closure {Closure cTo-> subjectTo(cTo)}. This closure is returned when you write 'to'. In turn this takes as argument another closure (denoted by cTo) which represents the constraints block. This is called command chain. In Groovy, when you call a method with arguments, the () can be omitted (e.g. 'subjectTo {}' is equivalent with subjectTo({})), but when the method has no arguments, () is mandatory. This is why you can not write 'subject to {}'.
The evaluation of x0 and x1 (steps 1, 3) as LPVar objects is more interesting. This is a good point to introduce the LPSolver class which implements the core of the Groptim DSL:
The max method takes as argument the OF block, which is evaluated in a closure by Groovy and passes that closure to optimize method. This changes the delegate object from the object that owns the closure (i.e. the one it was defined in) to this (i.e. LPSolver instance). Then it calls the closure, which triggers the above evaluation of the OF block into a BinaryExpression.
On the first occurrence of x0 in the OF block, Groovy will search for a field x0 in the delegate object (which is an LPSolver instance). It will not find any, so it will call the propertyMissing method on the delegate object. The implementation of this method first looks if a variable with the name 'x0' has been registered before and if not it registers it. It is important to understand that if I had not set the delegate to be this in the optimize method, then Groovy would have called the propertyMissing method on the object that owns the LPSolver instance, possible throwing a MethodMissingException. This would be client's class, e.g. it wiould be LPSolverSpec, when we run a test.
Both LPVar and NumberExpression define a negative() method, to which Groovy delegates the symbol '-', e.g. -x0 (strictly no space between '-' and x0) is equivalent with x0.negative() and -7.c to 7.getC().negative().
A number multiplied with an LPVar is evaluated (steps 2 and 4) as a BinaryExpression. To do this, I had to add the multiply method into the Number.metaclass (see LPSolver constructor). This makes 15*x0 equivalent with 15.multiply(x0) which evaluates in a BinaryExpression.
Groovy delegates the symbol '+','-' (when there is one or more spaces between '-' and a variable, e.g. x0) and '*' to plus, minus and multiply method respectively (steps 6, 7). It should be no surprise to you that Expression class defines all of them, to make possible the composition of Expressions (BinaryExpressions to be more precise) from other Expressions:
Finally, Groovy delegates all the comparison operators ('<','>','<=','>=') to the compareTo method, e.g. x0 + x1 <= 4.c is equivalent with (x0 + x1).compareTo(4.c) <= 0. Notice that the compareTo implementation creates a new constraint and registers it in the solver object. This poses a limitation for Groptim as any comparison operator will be delegated to the same method and there is no way to know which comparison operator triggered this call. Therefore, any constraint is considered as '<=' constraint from Groptim and this is the reason why Groptim strictly follows the canonical LP form for constraints.
It should be stressed that Groovy delegates the '==' operator into the equals method (e.g. x0 == 2.c is equivalent with x0.equals(2.c)), except if the delegate's class implements the Comparable interface, in which case it delegates to compareTo (e.g. x0 == 2.c is equivalent with x0.compareTo(2.c) == 0). Therefore, Groptim will consider a '==' constraint as an '<=' constraint too.
More precisely, if the delegate class implements the Comparable interface, the '==' operator is not directly delegated to the compareTo method. Take for instance, the constraint x0 == 2.c. If neither x0 (LPVar instance) is of a subtype of 2.c (NumberExpression instance) or 2.c is of a subtype of x0, then Groovy will not call compareTo at all, as it can conclude that the two objects are not equal. This check is done in the Groovy SDK class org.codehaus.groovy.runtime.typehandling.DefaultTypeTransformation and its compareToWithEqualityCheck method:
Due to this reason, I defined both LPVar and BinaryExpression as subclasses of NumberExpression. Otherwise, compareTo would not be called for '==' constraints and I would loose them, since constraint objects are created in the compareTo method.
Another interesting point is the return type of the optimize (and therefore max and min) method. It is a map that maps the String 'subject' to the closure { it -> ['to': { Closure cTo-> subjectTo(cTo)}]} and the String 'subjectTo' to the closure { it -> subjectTo(it)}. As you may have realized, this allows for the two alternative Groptim syntaxes for constraints, i.e. 'subject() to {}' and 'subjectTo {}' respectively.
When you write 'subjectTo {}', effectively you ask for the value that 'subjectTo' maps to. This value is a closure that takes as argument another closure denoted by it (represents the constraints block) and passes that to the subjectTo method. Pure fun! Isn't it?
The case that you write 'subject() to {}' is a little more interesting (more fun). In this case, you effectively ask for the value that the String 'subject' maps to, which is a closure. By writing () you call this closure which returns the map ['to': { Closure cTo-> subjectTo(cTo)}]. Obviously, this maps the String 'to' to another closure {Closure cTo-> subjectTo(cTo)}. This closure is returned when you write 'to'. In turn this takes as argument another closure (denoted by cTo) which represents the constraints block. This is called command chain. In Groovy, when you call a method with arguments, the () can be omitted (e.g. 'subjectTo {}' is equivalent with subjectTo({})), but when the method has no arguments, () is mandatory. This is why you can not write 'subject to {}'.
Reducing Boilerplate when Running as a Script
Groovy offers a GroovyShell class with which you can run Groovy code as if it was a script. One can initialize a GroovyShell object with a Binding object, which implements what is mostly known as 'Environment' in programming languages, e.g. a set of bindings in key-value pairs. I used this mechanism to inject the LPSolver object to any input file, so that the groptim script user does not need to create the LPSolver object. Take a look at the groptim script code:
Whenever an input file writes max (min), this is delegated to lp.max (lp.min) method. This is achieved by binding the max (min) keyword with a method reference to the max (min) method of the lp object. By calling the evaluate method on the GroovyShell object you can then evaluate Groovy code, that can either be contained in a file passed as argument (as in this case) or directly passed as an argument in the form of a String.
No comments:
Post a Comment