SBTB 2015: Germán Ferrari, Embedded DSL to manipulate Mathprog Mixed Integer Programming
Recording: SBTB 2015: Germán Ferrari, Embedded DSL to manipulate Mathprog Mixed Integer Programming
really introduce myself my name is Carmen Ferrari I'm a master's student at the basic science program of the University of the Republic in uruguay and i am at teaching our research assistant at the operational research department at the same university the objective of this talk is to show you an embedded domain-specific language to work with math pro models inside Scala and the techniques I used in coded syntax what I hope you were out of this presentation it's an idea of how Scala can be used on called a moderately complex language using the implicit infrastructure and type classes I will start by introducing math pro and the kind of problems that can be expressed by it then I will show some samples of the EDS all and the scholar features use and I will finish talking a bit about the implementation of the encoding of one of the operators so new math pro must pro stands for mathematical programming which despite the name has nothing to do with computer priming so mathematical programming is another name for mathematical optimization so here in this context a program cover first to some plan or schedule that we want to optimize so math pro it's a modeling language for mathematical programming problems from some in a typical workflow we can have something like this we have some optimization problem some problem for which we want to find the best solution to then we write a pure mathematical model then we write it in some language that can be understood by the computer and here is where we can use math pro and then we run computation experiment using different data instances and by computational experiment I mean running some program that knows how to solve these kind of problems and these programs are called solvers because of that so for example the new linear bracket is a free software package that you can that support that includes one of such solvers and support that you use a mac pro pro pro model to specify your problem the kind of problems that can be expressed by Mac Pro are all linear I'm gonna have either integer or real variables and these problems are called mixed integer programming because the yellow they allow integer and real variables to mix so this is how it looks a generic mixed integer musician meet integer parameter optimization problem written in math pro here what we are saying is that we want to find x and y that minimize some function f while satisfying some constraints g x and y are called the decision variables they model the decisions that we want to optimize the function f is called the objective function and it's a measure that we will be using to say that one decision is better than the other and they constraint g are equations or in equation that our decisions must satisfy so in this case we have an equation and both the double check d function and the constraint must be linear that is they can only be composed by assumes of multiplication of variables and constants so this is the full model here we are adding the Declaration of the parameters the seeds and the variables here we have the declaration of the variables X here is an integer variable and has a lower bound of 0 and Y is a real variable because all the variables are real by default and also has a lower bound of 0 this is the Declaration of the parameters we have some simple parameters and other parameters that are indexed by some sets and this is the declaration of the sets that we are using to index the other declaration here we are using the assignation attribute to specify directly in the model the value that we want to use in this case we are using what multiple calls and arithmetic set with this range of numbers if we go if we don't do that we have to specify these values later along with the other parameters theta so ok we are going to embed much bro nice color so the first question that you probably have is why we want to do why do we want to do that so this is an incomplete list of things that I want to do with the Scala I want to parramatta generate the constraints I want to be able to transform my models and create new ones for example by splitting some variables and I want to develop alternative resolution algorithm using all the information that not much bro has and working at the high level of abstraction so in order to embed must probe in Scala we basically need to do two things we need to represent its syntax in Scala and we need to define some semantics so we can use the e dsl for country negs else than writing the model for example we can generate not pro and use that to call the solver so we are going to do a deep embedding of the language so for the representation of the model we are going to use an encoding of the abstract syntax tree of montreux math pro using case classes and sealed trades and to mimic the math processing text we're going to use some methods as a smart constructors for some parts of the AST and other functions that will allows us to combine some trees and create new ones so this is the first example of the idea so here we have the declaration part of the model we saw earlier on the left we have the mud pro version and on the right we have the skull adsl dsl version we have three basic smart constructors for the sets the parameters and variables for certain parameters we are using the same word as must probe of but for variables because bar is a reserved word we are using X bar and these smart constructors return the abstract syntax tree that represents these parameters for example of these declarations this is the ast of the sea parameter here we can see that it can get pretty be even from simple terms so one thing that we can see here is how we define their arithmetic sets we can use the same addition as scholar ranges in this case we are not creating a range because M and an L are not numbers they are parameters so this is creating an abstract syntax tree that represents this arithmetic set another thing that we can see here is that we can use its caliber arts to represent the simple cases of indexing and for more complex complex cases we can use specific syntax that the eds L provides here we have the Declaration of the variables to say that one variable is an integer variable we just call an integer method and this will create a new variable with the integer attribute added in the same way to specify the lower bound of a variable we just write greater than or equal some value and this will create a new declaration of the variable with this lower bound attribute out so every time we call these methods and operators we are creating new values we never modify anything and this is some proposed so everything in de dsl can be mutable ok this is the objective function and constraint part we have two more smart constructors for the objective function we can use minimize we can also use maximize and for the constraint we are using an abbreviation of subject to we are using st so one thing that we can t see here is that we we are using multiple parameter list to separate the name and indexing from the expression in both the objective function and the constraints this allows us to use barks for simple cases of indexing and also helps it look more similar to most pro we are also using multiple parameter list in this summation for separate for the separation of the indexing and expression being added here we have examples of addition multiplication and summation and to reference the individual parameters variable sources we just apply them to some indexing value and this is similar to how we skylar with the race or lists and to the final constraint the constraint we just used the less than or equals operator we can also use the greater than or equals operator or triple equals and if either the expression on the left of the expression the right our linear expressions then we will be creating a constraint and must probe linear expressions are expressions that involve sets involved sorry involved variables ok and here the st smart constructor is receiving a constraint and is creating a new one adding the name and indexing specified so now I'm going to talk a bit about the implementation of the syntax most of the implementation of the syntax so many of the syntactic construct that we want to implement require a broad and possible open number of over loadings we also want to be able to use them using an object-oriented style we want to say some value dot method arguments or value operator arguments so this will lead us to use type classes and object-oriented forwarders and this in turn will lead us to use implicit prioritization so I will try to show and motivate these by an example so I wish of the implementation of the greater than or equals operator so here we are using greater than or equals to define the lower bound of a parameter the param smart constructor returns some data type paramus that that is part of the AST and because we want to treat the AST as just data we don't want to add any syntax related method to it so we are going to add this method using implicit conversion and we need to handle many over loadings for example we can use a skull and numeric type to specify the lower bound or another parameter or we can use the greater than or equals operator with variables or to compare to numerical expressions and create logical expressions or expression or to compare two linear expressions and create a constraint one thing that is important here is that the result type depends on the types of both arguments so one thing that we can do here is to use an implicit class to use to add this operator that this generic on both the types of the left argument and the right argument and the result type so this class is foolish generic has a type parameter a which represents the left argument and defines a method with two type parameters that represent the right argument under assault type but because this class is foolish generic we can have here the different implementation of the operator because we need the concrete types to do that so instead what we do is to ask for some implicit instance of a trait that represents our operator so here we have this straight gde up with which has three type parameters and defines a metal gde which will have the implementation of the greater than or equals operator for this combination of types so this straight here is working as a tech class once we have this instance we can forward implementation of the greater than or equals symbolic operator to the shitty email method in this instance so now with this machinery we can have the greater than or equals operator on every combination of types for which we have an instance of this type class so we are changing our problem to define the right instances and its priority one thing that is worth mentioning here is that we are asking for the implicit instance at the met at the method level so scala can use both the type types of the left and right arguments to do the implicit search of this instance this is what allows to have implementations that depends on both types so the problem is now to define the right instances so I will show the most relevant ones I will show only the type because the implementation is not really important here so this is the instance that allows to use the greater than or equals operator to define the lower bound of a parameter it is an epc def not an implicit bulb because we want to have a type parameter and is creating an instance of our trade that our type class that has a parameter as a left argument some generic a as a in principle as a right argument and will be returning a new parameter and for this generic a we are asking for the existence of an implicit function that can convert this a to an American expression so this is kyle is called a be bound and this is putting in fact a constraint on all the possible types that can be used here so it's generic as long as you have the simplest conversion so with this we can use greater than 2 or equals to define the lower bound using a any numerical expression but also any other type that can be seen as a numerical expression so this is the instance for the variable variables it's pretty similar to the instance for parameter in this case we're asking for a variable as a right a left argument this is the instance that allow us to compare two numerical expressions and create a logical expression in this case we have to type parameters we are creating an instance instance of the type class that these generic on the Left argument and the right argument and create a logical expression but again we are using do bounce to constraint the possible types that can be used here so with this we can compare any two types and create a logical expression as long as there is an increased conversion from such types to a numerical expression um this is the instance for the linear expression it's pretty much pretty much the same as the numerical expressions this is what allows to use the greater than or equals operator to create a constraint in this case we are asking that the view bounds be two linear expression and we are creating the constraint so with this we are satisfying all the requirements that we have regarding the overloading the way you want to use the operators but we have still one problem the problem is that these instances are ambiguous as defined so for example the instance for the numerical expressions and the instance for parameters are in conflict because the parameters can be implicitly compared to numerical expressions to allow to write things like parm Picchu greater than or equals B 1 so the parameters can be used as the left argument or using any of the two instances and the instance for the numerical expression is in conflict with the instance of the linear expressions because every numerical expression is a linear expression so they free really satisfy the blue bound of the numerical expressions so when we have this kind of problem in Scala one thing that we can do is to try to use implicit prioritization in Scala the implicit that you define the PC instances that you define in a trade from which you are extending have a lower priority than the instances that you define Detroit itself so if you write something like this the instances for the parameters and variables we have the same priority but they will have a higher priority than the instance for the numerical expression which will have a higher priority than the instance for the linear expressions and with this we can solve all our ambiguity problems ok and I'm about to end this is these are things that I'm working on or I want to work on future I want to have new semantics for example to talk directly to the solvers API so i don't have to generate math probe to solve the problems i want to add more study controls so i can check for example they at compile time that the rit of the expressions i'm using to index other declarations have the right size and i'm working to support other problems beyond mix integer programming for example i'm working in supporting multistage stochastic priming problems with discrete scenarios these problems have a fairly standard encoding us mixing to serve ramen problems but you need to add some constraints to keep consistency and also specifying the data it's painful because you need to specify your values for every combination of the stages and scenarios so all these problems can be alleviated using the embedding we can generate the constraint or we can provide a more specific API to specify these values for this stochastic parameters on a final note i just want to mention that all the cool percent here comes from a project in which i am sparing menteng with working with math pro in scala the high level this project is called an fit and this is it have a repository if you want to check it out um that's it thank you now if you have any questions no yes yes it's a bad thing the targets of the females were not just another set of type classes yes because am i AST i have concrete types I did numerical expression it's not that it can be maybe some improvement I can use maybe some numerical expression data type class or something like that these parameter Isis in the type at this moment the ASD if has not type parameters at all I have any numeric type and I have I know I have some hot Birds for topple to touch two tuples are for from least to set littler literals are there are a lot of complicity around but the implicit are open you can add / loadings if you wanted so oh okay for the question was I don't know if I get it the question is if this will work with nested linear expression what for example yes okay you can you can have a list of yes okay but you can if you your variables or something herbs specific you have them in a least you can do a fold over that list and you can be creating I don't know if that is what you mean but you can accumulate that I'm creating a bigger model on every yes you can use yes ah yes ok I know it what you mean yes we can we can only use edition with linear expressions to keep the linearity if you try to multiply two linear expression you will have a compile error because there is no type class instance for the multiplication operator D but yes you don't have any problem with the nesting I'm not sure I maybe we can talk later I'm not sure I understand your question ok yes yes I consider that my major concern was like having the AST like don't touching the HD because i have the HD from a previous iteration i right a rod my arm of probe parser scala i want you to keep it shut treated just as just data but maybe I could have create a parallel here G her key and yes yes yes if you have if you define your methods directly on your types you can solve these problems by giving you giving the right over loadings but this won't be open to more hua loadings so I don't know because for example you have some expressions in which you say that this value and this value and this value are in some set expression and maybe you want to give some overloading so you can use a topic and not a list are things inside Adam I know I want it to be open so the problem you have is that you have this ambiguity and you have to use these be bound because you want to keep the type you need to you need to be balanced because you need the discolor see that he can use the implicit conversion on your type it don't need to convert privilege to another type so with the b1 you're chaining increased conversion some way yes yes I'm doing that but I I haven't like maybe one of you guys can help me with that now I'm trying yes but yes it's one of the thing things I want to work on yes true so for your office classes you have yes yes okay that's nice nice configuration yes that it's not really an open type because you it is determined by the other two types okay thank you this i I didn't thought about it but I think it's a great thing yes yes okay thank you