MAiNGO
Modeling in MAiNGO

Modeling with ALE

A convenient way of modeling with MAiNGO is to use ALE, which provides a framework for writing logical-algebraic expressions. The input can be written as .txt files in ALE syntax. An exemplary problem.txt file can be found in examples/01_BasicExample/problem.txt. An example for how MAiNGO can be used to read such as file can be found in examples/mainAleParser.cpp.

The ALE syntax uses data types to decide which expressions can appear in which context. All data types are constructed from the basic types real, index, and boolean and potentially derived types such as set and tensor. Every expression has one of the following types:

  • scalars of the basic data types (e.g., real scalar)
  • tensors of the basic data types up to a maximum dimension (default: 3) (e.g., index matrix)
  • sets of scalars or tensors of the basic data types (e.g., real vector set)

In the context of modeling in MAiNGO, optimization variables are real scalars or tensors, while the objective function is a real scalar. Furthermore, constraints are boolean scalars, which result from comparison operations (inequalities and equalities) on real scalars. Finally, indexes are used to dereference tensors and sets can be used in expressions that expand over all their elements.

File Structure

The input file is structured into sections, which are initiated with an appropriate keyword (e.g., definitions) followed by a colon (:). Within each section, there may be zero, one, or more statements, which are each terminated by a semicolon (;). At any point in the input file, the pound symbol (#) may be used to initiate an end-of-line comment, meaning that all input between the pound symbol and the end of the current line is ignored. Finally, whitespace characters have no meaning except that they serve to separate keywords.

Parameter, Variable, and Expression Symbols

Symbols are named entities that refer to fixed values, variables, or expressions of a particular type. The names used are allowed to contain letters, numbers, and underscores and must start with a letter. All symbols must be defined in a definitions section of an input file which is initiated by

definitions:

A single input file may have arbitrarily many definitions sections that may be empty or contain arbitrarily many definitions. However, since symbols can only be used once they have been defined, it is advisable to collect all definitions in a single definitions section at the beginning of the input file.

All definitions begin with a declarator indicating the desired data type (e.g., real, index, or boolean) and are terminated with a semicolon.

Parameter Symbol Definitions

The following are valid definitions of different scalar parameters (fixed values), which are assigned using the definition operator (:=) operator:

real a := 12.5e-2; # defines a scalar real parameter named "a" with value 12.5e-2
index i := 2; # defines a scalar index parameter named "i" with value 2
boolean b := true; # defines a scalar boolean parameter named "b" with value true

For the definition of a tensor parameter its length in each dimension must be provided in square brackets after the declarator. Furthermore, vector values are written in parentheses as a comma-separated list of entries. Similarly, tensor values are written in terms of their subvectors (i.e., matrices are vectors of vectors, and so on). The following are valid definitions of different tensor parameters:

real[3] rv := (1.3, 2.4, 3.5); # defines a real vector parameter of length 3
index[2,2] im := ((1, 2), (3, 4)); # defines a 2x2 index matrix parameter

For convenience, tensors can also be initialized with a scalar:

real[3,3] rm := 0; # defines a 3x3 real matrix parameter filled with zeros

Particular entries of tensors or values of scalars can later be changed using the assignment operator (<-). A colon (:) can be used to indicate an assignment for all values of a particular index:

i <- 1; # assigns the value 1 to i
rm[1,2] <- 5.2; # assigns the value 5.2 to entry [1,2] of rm
rm[2,:] <- 2.2; # assigns the value 2.2 to entries [2,1], [2,2], [2,3] of rm

In the context of assignments, it is important to note that all expressions provided for modeling are evaluated late, meaning that only the final value of a parameter symbol has any impact on the model.

For the definition of sets, the declarator is composed of the keyword set and the desired element type in braces. Therein, tensor-valued elements are denoted using the same notation as above with a colon instead of the tensor lengths. Similarly, set values are denoted as comma-separated lists in braces. Contiguous index set values can be denoted in short-hand as shown below. The following are valid definitions of different set parameters:

set{index} i_set := {1, 3, 5}; # defines an index set parameter containing 1, 3, and 5
set{index} j_set := {1 .. 5}; # defines an index set parameter containing 1 through 5
set{real[:]} v_set := {(1.3, 2.4), (3.5, 4.6)}; # defines real vector set containing two vectors

Variable Symbol Definitions

Variable symbols can be defined using largely the same syntax as parameters with the difference that variables are not assigned values but bound intervals using the in operator. Furthermore, variables can only be real scalars or tensors. The following are valid definitions of different scalar and tensor variables:

real x; # defines an unbounded real scalar variable
real[3] y in [(1, 2, 3), (2.5, 1e2, 5.4)]; # defines a bounded real vector variable
real[2,2] z in [0, ((20, 10), (23, 15))]; # defines a bounded real matrix variable with all lower bounds being zero

Note in the above example that one or both bounds of a tensor variable may be provided as a single scalar.

Integral variables can be defined by replacing the real declarator by either binary or integer. In the case of a binary variable, no bounds can be assigned ass they are implicit. The following are valid definitions of different binary and integer variables:

binary bx; # defines a binary scalar variable
integer[3] iy in [(1, 2, 3), (2, 10, 5)]; # defines a bounded integer vector variable

Similar to the assignment of parameter values, the lower bound, upper bound, and initial point of a variable symbol can be assigned using the assignment operator (<-) and the appropriate suffix for the variable name (lb, ub, or init):

x.lb <- -1; # assigns the lower bound of x to be -1
x.ub <- 3; # assigns the upper bound of x to be 3
x.init <- 2; # assigns the initial point of x to be 2
z.lb[1,1] <- 2; # assigns the lower bound of entry [1,1] of z to be 2

Expression Symbol Definitions

Expression symbols are similar to parameter symbols with the difference that they do not hold a basic value but rather an arbitrary expression of the appropriate type. In contrast to parameter symbols, expression symbols can only be real, index, or boolean scalars. The syntax for defining expression symbols is identical to the one for parameter symbols with the difference an expression is assigned instead of a constant. For further information on what constitutes a valid expression, refer to Expressions. The following are valid definitions of different scalar expressions:

real re := exp(x) - 4*x; # defines a real expression
index ie := 2*i + 1; # defines an index expression

Note that upon evaluating the input, expression symbols are substituted by their expression and don't become optimization variables. As such, they can be used to write reduced-space formulations in a procedural way.

Further Section Headings

Beyond the definitions section, there are several sections for defining expressions such as the objective function. While the examples provided here should be self-explanatory, a more detailed discussion of possible expressions is provided in Expressions.

Objective section

The objective function to be minimized must be defined in an objective section of an input file which is initiated by

objective:

Each objective section may only contain a single real scalar expression with an optional description in quotes (" ") and terminated by a semicolon (;):

sin(x^2) "the objective function";

If multiple objective sections are present in a file, the last defined objective function will be used.

Outputs Ssection

Optionally, additional outputs can be defined in an outputs section of an input file which is initiated by

outputs:

Each outputs section may contain arbitrarily many scalar real expressions, each with an optional description in quotes (" ") and terminated by a semicolon (;):

2 * sin(x^2) "twice the objective function";

Upon completion of an optimization, the additional outputs will be evaluated at the optimal solution and reported.

Constraints Section

Constraints must be defined in a constraints section of an input file which is initiated by

constraints:

Each constraints section may contain arbitrarily many boolean scalar expressions, each with an optional description in quotes (" ") and terminated by a semicolon (;). MAiNGO will only accept constraints that either result from a weak inequality, an equality, or a set-based expansion over a weak inequality or an equality (see Scalar Boolean Expressions). Note that this restriction does not preclude the use of general boolean expressions in the context of indicator sets (see Set Expressions)

x <= y[1] "a simple inequality";
y[3] = 4 "a simple equality";
forall k in {1, 2} : y[k] <= y[k + 1] "a set-based inequality";

Relaxation-only Constraints Section

Relaxation-only constraints (see Modeling Tips and Tricks) must be defined in a relaxation only constraints section of an input file which is initiated by

relaxation only constraints:

These constraints must satisfy the same conditions as regular constraints and are denoted in the same way (see Constraints Section).

Squashing Constraint Section

Squashing constraints (see Modeling Tips and Tricks) must be defined in a squashing constraints section of an input file which is initiated by

squashing constraints:

These constraints must satisfy the same conditions as regular constraints and are denoted in the same way (see Constraints Section). Furthermore, they must result from a weak inequality or a set-based expansion over a weak inequality.

Example Input File

The following are the contents of a valid input file

definitions:
binary x;
real y in [-2,2];
real a := 20;
real p1 := 0.2;
real p2 := 3.14159265358979323846; # ~ PI
real temp1 := -p1 * sqrt( (x^2 + y^2) / 2 ); # This is neither an optimization variable nor an equality constraint
real temp2 := (cos(p2*x) + cos(p2*y)) / 2; # This is neither an optimization variable nor an equality constraint
x.init <- 0;
y.init <- 1;
constraints:
x <= 1;
pow(x,2) + sqr(y) = 1 "circle equality";
relaxation only constraints:
y - 1 <= 0;
y + x = 1;
outputs:
temp1 "Result of temp1";
objective: # Always minimizing
-a * exp(temp1) - exp(temp2) + a + exp(1);

Expressions

The ALE syntax for denoting expressions is similar to other established modeling languages and should be mostly intuitive. In the following, the different expression types and the allowed operators are discussed:

Scalar Real Expressions

The basic building blocks of real scalar expressions are constants, symbol names, and entries of real tensors. Constants can be any real number written in floating-point or scientific notation as shown above in the definition of symbols. Entries of tensors are accessed by bracket notation as shown above for the assignment of tensor entries. Operators are defined for addition (+), subtraction (-), multiplication (*), division (/), and exponentiation (^). Parentheses are used to enforce precedence and to denote arguments to functions. For a complete list of implemented functions beyond the standard functions (exp(), log(), sin(), asin(), etc.), refer to doc/implementedFunctions/Implemented_functions.pdf. The following are valid real expressions:

x + sin(y[1])
3 ^ (2 * z[1,1])

For convenience, ALE provides the following set-based expressions that expand over a set of any given type:

sum(k in {1 .. 3} : rv[k])
sum(v in v_set : v[1])
min(r in {1.2, 10.0, -1.5} : r)
max(k in {1 .. 3} : rv[k])

Note however, that the min and max function can also be used without set expansion:

min(y[2], 3e-2, 5.3, x)
max(rm[1,1], rm[2,2])

Scalar Index Expressions

Similar to real expressions, the basic building blocks of index expressions are constants, symbol names, and entries of real tensors. However, index expressions and therefore also constants and the values of symbols can only take whole values. By the same token, only the operators for addition (+), subtraction (-), and multiplication (*) are defined for indexes. Parentheses are used to enforce precedence.

Scalar Boolean Expressions

The basic building blocks of boolean expressions are constants, symbol names, and entries of real tensors. Furthermore, boolean expressions result from the comparison operators (<, <=, =, >=, >). Boolean expressions and therefore also constants and the values of symbols can only be true or false. Operators are defined for conjunction (&), disjunction (|), and negation (!). Parentheses are used to enforce precedence. The following are valid boolean expressions:

b & false
x * y[1] <= 2

Furthermore, ALE provides a set-based conjunction similar to the set-based real expressions:

forall k in {1, 2} : y[k] <= y[k + 1]
forall r in {1.2, 10.0, -1.5} : x >= r

Set Expressions

The basic building blocks of set expressions are constants and symbol names. These basic sets can be refined by employing an indicator set, which only contains those elements that satisfy a logical condition:

{r in {1.2, 2.3, 3.4} : r <= 3} # only contains 1.2 and 2.3

Modeling via C++ or Python

Another way of modeling with MAiNGO is to directly work with the C++ or Python APIs. The Python API really just consists of Python bindings (enabled by pybind11) that make the C++ API usable from Python. Thus, the following description applies equally to both APIs, although the Doxygen documentation of the classes and functions refers to the C++ version.

An example for calling MAiNGO via the C++ API can be found in examples/mainCppApi.cpp. For communicating an optimization problem to MAiNGO, you need to implement a specialization of the MAiNGOmodel class. An example for such a specialization can be found in examples/01_BasicExample/problem.h. An example for the use of MAiNGO and implementation of an optimization problem in Python can be found in examples/01_BasicExample/examplePythonInterface.py.

Your specialization of the MAiNGOmodel class needs to implement at least the following functions:

  • get_variables: Here you need to specify the optimization variables, which are defined by their lower and upper bounds. This is done by creating and returning a vector of OptimizationVariable objects. Typically, a variable at least needs to be given Bounds (the only exception are binary variables). Optionally, each optimization variable can be given flags to determine whether they are continuous, integer, or binary (cf. VT) and a branching priority which has to be at least 0. The default branching priority is 1 and a branching priority N means that MAiNGO will branch log_2(n+1) more often on the corresponding variable than on a variable with branching priority 1. Branching priority 0 means that MAiNGO will never branch on the variable. A variable can also be given a name. However, this name is used only in the output. Unfortunately, it currently cannot be used when implementing the functions in the evaluate function (cf. below). Therefore, variable names also need not be unique. If no name is given, the variable will be called x<i>, where <i> is a running index.

  • evaluate: this function is called by MAiNGO to construt the directed acyclic graph of the objective function and constraints. The results of the evaluation of f, g, and h have to be written to the objective, eq, and ineq members of the EvaluationContainer returned by the evaluate function. The evaluate function takes a vector of mc::FFVar objects as input. These correspond to the optimization variables defined in the get_variables function. However, for technical reasons, they are not the same objects. In particular, the optimization variable corresponding to an mc::FFVar variable in the argument vector of the evaluate function can only be identified by their positions in the corresponding vectors. See, e.g., examples/01_BasicExample/problem.h or examples/01_BasicExample/examplePythonInterface.py. The results of all calculations done with these mc::FVar objects are also of this type. Other data types (e.g., double) must only be used for constant parameters. When working in Python, you need typically not worry about the types.

Additionally, you may do the following in your specialization of MAiNGOmodel:

  • Specify an initial point that is used for the first local search in multistart during pre-processing using get_initial_point.

Modeling Tips and Tricks

Within the evaluate function, you can do almost any type of computation (including calling other functions / libraries), as long as they are implemented with mc::FFVar. However, it is not allowed to use loops with a number of iteration not known a priori (such as, e.g., solving a nonlinear equation system), and to use conditional statements that depend on variables (and the resulting code will not compile, since comparison operations are not defined for mc::FFVar). For a list of intrinsic functions supported by MAiNGO, refer to the documentation in doc/implementedFunctions/Implemented_functions.pdf.

If your model does contain equations that would require iterative solution, you need to leave appropriate optimization variables and equations to the optimizer instead (cf. Bongartz & Mitsos 2017a).

Using conditional statements that depend on variables is not possible directly. This could results in non-smooth or discontinuous functions, and computing valid relaxations always requires information on the entire domain. Such statements can however be reformulated, either through the use of implemented non-smooth functions like the maximum of two functions, or using the methods for relaxation of discontinuous functions introduced by Wechsung & Barton 2015. As an alternative, one can also resort to mixed integer formulations.

For the constraints, it is important to manually scale all constraints for the relevant terms to be of the order of one, since constraint tolerances are only implemented as absolute values.

You can also specify constraints that are to be used only in the relaxation, not in the original problem (cf. Sahinidis & Tawarmalani 2005). To this end, the EvaluationContainer returned by the evaluate function contains the vectors ineqRelaxationOnly and eqRelaxationOnly. This can be useful when adding redundant constraints that would complicate the local solution of the original problem but might tighten the relaxations. Note that adding incorrect relaxation-only constraints may lead to false infeasibility claims or other spurious behavior of the optimization process.

You may add OutputVariables to the output vector in the EvaluationContainer. This can be used to compute and return information that is not needed during the optimization but that you are interested in at the optimal solution.

If you are using the squash_node function, it is neccessary to introduce appropriate squash inequalities to maintain correctness of the optimization problem. For more information refer to doc/implementedFunctions/Implemented_functions.pdf.

Parsing GAMS Files

We also provide a tool for parsing GAMS convert files to ALE problem.txt or MAiNGO problem.h files. For detailed description please refer to utilities/MAiNGO_Reader_Writer/ and the documentation found therein.