MAiNGO
Modeling in MAiNGO

Modeling with ALE

The most convenient way of modeling with MAiNGO is to use ALE (https://git.rwth-aachen.de/avt.svt/public/libale.git), 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 exampleAleParser/problem.txt.

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 Advanced Modeling) 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 Advanced Modeling) 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++

Another way of modeling with MAiNGO is to directly work with the C++ API. If you are not interested in the development of an own Model class simply use the exemplary C++ implementation, that can be found in exampleCppApi/problem.h and proceed with the next subsection.

For communicating an optimization problem to MAiNGO, you need to implement a specialization of the MAiNGOmodel class. 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 adding an appropriate OptimizationVariable object to the variables vector. Optionally, each optimization variable can be given flags to determine whether they are continuous 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.

  • 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. In the implementation of the evaluate function, you need to consider the following points:
    • All variables need to be of type mc::FFVar. In problem.h in the example folder, we use a typedef to call it Var instead and save some typing. Other data types (e.g., double) must only be used for constant parameters.

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.

Advanced Modeling

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. 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. 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, J. Global Optim 69 (2017) 761).

Using conditional statements that give non-smooth or discontinuous functions is not possible directly, since 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 et al., J. Global Optim. 63 (2015) 1. 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, J. Global Optim. 32 (2005) 259). 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 in order 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.