0:02
So welcome to the reference material for the course.
So this material is designed to give you a different viewpoint
on the technical components of a MiniZinc model.
So the main material on the courses are problem based and
will introduce the concepts as they need them.
But here we're trying to give you a summary of the concepts all in one place.
And in this first project material,
we'll just go through the basic components of a MiniZinc model.
So the basic things we need to understand to build a model are firstly types, and
the kinds of variables we can have, which parameters and decision variables.
Then how are we going to build our basic parenthetic expressions and
then convert those into constraints.
And finally how are they going to put that all together in the structure of a model.
0:53
So the types available in MiniZinc are rather restricted,
the main one because we're doing discreet optimization is integers.
And we'll often use a range, a fixed range, so
1..n indicates a set of integers from 1 to n, and indeed l..u is just a way
of writing the number set of integers from l, starting at l going up to u.
And we also have floating point numbers which are of the type float but
we can also have ranges of float numbers.
So 1.0..f is the range of all floating point numbers in between 1.0 and
whatever value we've given to the floating point parameter f.
We have booleans, so this is true-false things, and
they appear in many discrete optimization problems.
And strings, so strings are really only made available in MiniZinc in order
to have some output so that you can see the result of your model.
Other important types are arrays and sets but
we'll talk about those in later chapters.
So variables are critical for modeling a problem, so
they are the key thing that goes into a constraint model,
variables and constraints.
There are two distinct types of variables in MiniZinc, they're parameters and
decision variables.
And parameters are those which basically reflect fixed information,
so they're going to be given to us in terms of input to the problem.
They're really the information that describes what the problem is or
what are the parameters of problems.
So what we'll typically try to do is build a model which can run from
many different inputs for many different values for its parameters.
And then decision variables are the decisions we
have to make to solve the problem.
And so they're the key thing that in fact we've got to be careful
we are not going to be responsible for giving values to those decision variables,
that's what's going to be the job of the solver.
And if you want they're the output of our model,
a set of decisions which solve constraints.
2:51
So parameters are very much like variables in a standard programming
language except that they can only be assigned a value once.
They're not like in a procedural language where you can think of a parameter or
a variable as a storage place which I can put different values into at
different times.
A parameter will only take one value point in time.
And a parameter is declared in this form.
So we have this par keyword, which is optional.
Then the type of the parameter, then colon, then the name of the parameter.
And then optionally we can have this equals to some expression.
And then we finish off that declaration with a semicolon.
And in MiniZinc the semicolon is a statement terminator, so
it brings to the end each of the statements of the model.
3:36
So type can be any of the types that we've talked about and
other types that we haven't talked about yet.
varname is the name of the parameter.
And the par is optional, right, and is typically omitted, we won't ever really
use par but it's nice to think of it there because it shows the correspondence
between pars and vars, which is decision variables which we'll see later.
Now the optional expression can give a value to the parameter, so
you can just give a value to the parameter straight away or
you can later on give it value.
So decision variables are our other kind of variables and
there you've got to think of them like variables in mathematics.
They get declared with a type and this var keyword, and
they're what the solver's going to compute.
And they're, again, only going to take one value,
that's the value that the solver's going to compute for them.
So what the solver's trying to do is find a value for
all of those decision variables that satisfies all the constraints.
4:29
And the declaration is very much the same as the parameter declaration, except for
you're going to have this var keyword in front of the type, and
then everything else is the same.
And typically a decision variable is not equated to an expression,
it can make sense to equate a decision variable to an expression
which includes other decision variables,
which means it's really just if you want a macro for some named expression.
5:01
So the next important component of a model is an assignment.
An assignment just is this varname equals expression.
What it is is going to give a value to the variable varname, and
that could be a parameter or it could be a decision variable.
So when it's giving a or
it can define an expression which it equates to a decision variable.
And so we've got some examples down here.
So here I've declared an integer m and then I've equated it to 3 times n,
where presumably n must be another parameter that I've
previously given a value to so that I can work out the value of m.
Here's a declaration of a decision variable d which is a variable which you
can make an integer value, and here I've equated d to the absolute value of
x- y and presumably one of x- y is a variable, at least one.
And so what we're really doing is saying okay, d is just a name for
the expression of the absolute difference between x and y, so
I can use that elsewhere throughout my model.
And down here I have a declaration.
Whoops.
And then after that an assignment, then I can put them together.
And really, that's what we've seen when we were showing you the format for
declarations of parameters and variables, is we can have this equality basing this
assignment part directly afterwards and it's just the same as if I had written
these two statements here and just wrote them as one together.
6:25
So variables have an instantiation which basically determines whether
they're parameters or decision variables,
and the type or instantiation is called the type instance.
Sometimes you'll see error messages come out of MiniZinc which are termed in,
talk about type-insts, so that's why it's important to know what a type-inst is.
But basically it's just a combination of the instantiation type which is var or
par, and the type.
So we have var int, some are var 0 to 3, we could have a par float, or par bool.
And again, usually we omit the par, so when I talk about the type-inst float I'm
really talking about par floats, a float with a fixed value.
7:05
Now it's important to put comments in the model just like it is important to put
comments in any kind of program, there's two ways you can do that in MiniZinc.
You can have a percentage character and
then everything after that in the line is considered as a comment and
won't be really seen by the MiniZinc compiler.
And you can also use this C style comments where you have a slash star to open
the comment and the star slash to close the comment,
and then anything between those will be ignored.
And it's just like in programming,
we should have a header comment describing the model at the top of the file.
You should describe each parameter when you put in into the model.
You should describe each decision variable when put it in the model.
And you should describe each constraint.
So really, comments are very worthwhile to have in your model.
You will not use so many of them during the course in some sense,
because when we're showing you things on slides, we have to keep it concise.
All right strings are really, as I said, only provided for output and
the output item basically takes an output keyword, and
then a list of strings, and again terminated with a semicolon.
8:19
So what are strings, so strings,
literals are just like those in C they're enclosed in double quotes.
They can't extend across more than one line, so
if you need to build a big string, big thick string,
then you need to break it into lines and then concatenate the strings together.
You can use backslash to get special characters, for
example /n would give you a new line, /t would give you a tab, so
we use the same special characters as you've seen.
And there's some important built in functions for building strings.
So show(v) takes an expression v and converts that into a string,
so basically takes the value of that expression v and converts it into a string
and that expression could be complex, could be an array, could be a set.
There's another useful thing which is this backlash open braces and
then v close brace, so this is a thing we can put inside a string which will
replace that expression with this result of showing v, so basically
it's a way of putting a show inside, building a string inside another string.
9:41
So the key things that we're going to deal in a discrete optimization model
are mathematical arithmetic expressions.
And so MiniZinc provides very standard arithmetic operators,
so the obvious ones multiplication, division, addition, and subtraction.
And for integers multiplication this is integer division, and
modulo is addition and subtraction.
And integer and float literals are like those in C, so they're very [INAUDIBLE].
You can automatically coerce, MiniZinc will automatically coerce from integers
to floats, so if you use an integer in a place where it requires a float,
it will actually coerce it for you.
But you can also use the builtin int2float coercion to map an integer into a float.
And there are lots of builtin arithmetic functions,
you can look through the MiniZinc documentation to find them all.
There are things like absolute values and sine, cos, or tan,
all kinds of arithmetic functions, the standard familiar ones.
All right, the basic arithmetic constraints, and remember what we're
aiming to do with that arithmetic expressions is build constraints.
10:51
These relational operators so equality, disequality,
greater than, less than, better than or equal to, and less than or equal to.
And the constraint is just written with this constraint keyword and
then constraint-expression.
And so we have some simple examples,
here's to find a constraint where x is less than or equal to y.
Here's a more complicated one where I'm saying that x + 2 times y- the absolute
value of z is not allowed to be = 0.
And again, each of these expressions is terminated by a semicolon.
And so now we are ready to finish, we've seen all of the basic items that can be in
a model and a MiniZinc model is just a sequence of these items.
And really the order of the items doesn't matter, you'll see that we'll have a style
where we tend to put the parameter declarations first,
then the variable declarations, then the constraints, then the objective,
then the output, but they can be in any order.
And so the kinds of items you can have are inclusion items,
so this allows you to include a file, it's just as if the file was read
into your model at that point and that file name is given as a string literal.
There's the output item which we've discussed before,
which takes a list of string expressions and we'll print them out.
But of course we'll have variable ways, and shows, and things like that, and
it'll be typically printing out the value of the decision that we've made.
We'll have variable declarations, which could be for parameter or
decision variable.
Variable assignments which are typically your parameters but can also be made for
decision variables and constraints.
Or a constraint and then a boolean expression, so
we'll see later on we can go beyond those basic relations.
And lastly there has to be a solve item and this tells you what the solver should
do, and it's going to be one of these three things.
It's going to solve satisfy,
which means just look for any solution that satisfies these constraints.
Or it could be solve maximize and then arithmetic expressions say find me
a solution which maximizes the value of this arithmetic expression, or
similarly solve minimize.
12:54
Other items which we'll see later on in the course are predicate, function, and
test items that these allow us to encapsulate
commonly used constraints with their names so they can be used multiple times.
And annotation items which we won't see in this course,
which is a way of extending the language of communication with the solver,
so I can tell more things to the solver by building new kind of [INAUDIBLE].
So we didn't really talk about par identifiers so what these parameter names
and variable names and also names, function names should be.
But basically they start with a letter, they're followed by other letters and
underscores or digits as the characters that can make up an identifier.
You can also use the underscore itself just alone as a name of an anonymous
decision variable.
So sometimes this is useful so if you want to build up an array,
you want to put in some fixed values and some unknown values,
you can use an anonymous decision variable underscore.