Glossary

Basis: when solving an LP problem with the Simplex algorithm, the basis provides the complete information about which variables and constraints are active in a given solution. It can therefore be used to save and quickly restore the status of the solution algorithm at a given point.

Binary model file (BIM file): a compiled version of the .mos model file that is portable across all platforms for which Mosel is available. It does not include any data read from external files. These must still be provided in separate files, thus making it possible to run the same BIM file with different data sets.

Bound: equality or inequality constraint on a single decision variable. When working with Xpress Optimizer through Mosel, bounds may be changed without having to reload the problem.

Branch-and-Bound: solution method for MIP problems consisting of an enumeration of the feasible values of the discrete variables (branching) coupled with LP techniques (providing bounding information). Typically represented in the form of a Branch-and-Bound tree where every node stands for the solution of an LP problem, and the connections between these nodes are the bound changes or added constraints. Such enumerative methods may lead to a computational explosion, even for relatively small problem instances, so that it is not always realistic to solve MIP problems to optimality.

Branch-and-Cut: solution algorithm for MIP problems similar to Branch-and-Bound. At some or all nodes of the search tree violated cuts are added to the problem to tighten the LP relaxation.

Builder Component Library (BCL): model builder library for developing a model directly in a programming language. BCL allows users to formulate their models with objects (decision variables, constraints, index sets) similar to those of a dedicated modeling language.

Constraint: relation between decision variables. Constraint types include equality constraints (operator = in Mosel), inequality constraints (operators >= and <= in Mosel), and integrality conditions. Bounds are special cases of inequality or equality constraints.

Constraint Programming (CP): a problem solving technology for constraint satisfaction and optimization problems expressed by the means of decision variables and constraints (including but not limited to algebraic relations); the solving process uses constraint propagation (deducing information from the current state of variables and constraints) in association with tree search methods.

Cut: also called valid inequality; additional constraint in MIP problems that is not required to characterize the set of integer solutions, but must be satisfied by all feasible solutions. Cuts tighten the LP relaxation by drawing the LP solution space closer to the convex hull of the MIP solution space.

Decision variable (or variable for short): unknown that needs to be assigned a value by the solution algorithm. The basic variable type is a continuous variable (a variable taking values from a continuous domain between a given lower and upper bound). Discrete variable types include binary variables (also called indicator variables; variables that may only take the values 0 or 1); integer variables (taking values in an integer range between given lower and upper bounds); semi-continuous variables (either 0 or values from a continuous interval between a given limit and upper bound); semi-continuous integer variables (either 0 or integer values between a given limit and upper bound); partial integer variables (integer-valued from the lower bound to a given limit and continuous beyond this limit value)

Declaration: the declaration of an object states its form and type and usually precedes the definition of its contents. With Mosel, the declaration of basic types and linear constraints is optional, but decision variables must always be declared; subroutines must be declared if they are used in a model prior to their definition.

Dense array: arrays in Mosel can be either dense or sparse. By default arrays in Mosel are dense, that is, every possible index tuple is associated to a cell in the array. A dense array is fixed if its index sets are constant or have been finalized to make them static; non-fixed arrays can increase dynamically with the contents assigned to them, however it is generally more efficient to finalize their index sets as early as possible, this also allows Mosel to check for `out of range' errors that cannot be detected if the sets are dynamic.

Dynamic set, dynamic array: sets and arrays in Mosel can be marked explicitly as dynamic. Dynamic sets cannot be finalized to make them static; dynamic arrays and hashmap arrays are two forms of (sparse) arrays for storing and efficiently enumerating sparse data tables. Non-fixed dense arrays are sometimes referred to as implicitly dynamic arrays, particularly for earlier versions of Mosel.

Heuristic: algorithm for finding feasible solution(s) to a problem. Some heuristics guarantee a bound on the solution quality but usually no proof of optimality is possible.

Index set: set used for indexing an array. Using string indices may help to make the output produced by Mosel more easily understandable.

Interactive Visual Environment (IVE): development environment for Mosel that provides, amongst many other tools, graphical displays of solution information.

Linear Programming (LP) problem: a Mathematical Programming problem where all constraints and the objective function are linear expressions of the decision variables, and the variables have continuous domains—i.e., they can take on any, usually non-negative, real values. A well-understood case for which efficient algorithms (Simplex, interior point) are known.

Loop: Loops group actions that need to be repeated a certain number of times, either for all values of some index or counter (forall in Mosel) or depending on whether a condition is fulfilled or not (while, repeat until in Mosel).

LP relaxation: in a MIP problem, the LP relaxation is obtained by dropping the integrality conditions on the decision variables.

Mathematical Programming problem (or problem for short): a set of decision variables, constraints over these variables and an objective function to be maximized or minimized.

Matrix: the matrix representation of Mathematical Programming problems with linear constraints is a table where the columns are the variables and the rows represent the constraints. The table entries are the coefficients of the variables in the constraints, usually stored in sparse format, that is, only the non-zero entries are given.

Mixed Integer Programming (MIP) problem: a Mathematical Programming problem where constraints and objective function are linear just as in LP and variables may have either discrete or continuous domains. To solve this type of problems, LP techniques are coupled with an enumeration (known as Branch-and-Bound).

Modeling language: a high-level language (such as the Mosel language) that allows the user to state Mathematical Programming problems in a form close to their algebraic representation. Carries out automatically the transformation to the representation required by the solver(s).

Model: algebraic representation of a problem; also employed to denote the implementation with a modeling tool such as Mosel or the object-oriented solver APIs.

Module: also called dynamic shared object (DSO); dynamic library written in the C programming language that observes the conventions set out by the Mosel Native Interface. Modules enable users to extend the Mosel language with new features (e.g. to implement problem-specific data handling, or connections to external solvers or solution algorithms). Modules of the Xpress distribution include access to Xpress Solver (Xpress Optimizer for LP, MIP, QP, Xpress NonLinear for NLP, and Xpress Kalis for CP), data handling facilities (e.g. via ODBC) and access to system functions, graphing capabilities, distributed and remote computing functionality via the Mosel Distributed Framework, and also interfaces to statistics packages such as R or Matlab.

Mosel: modeling and solving environment comprising the Mosel language (a modeling and programming language), the Mosel libraries (for embedding Mosel models into applications), and the Mosel Native Interface (opening up the Mosel language to external additions in the form of modules).

Mosel Native Interface (NI): a subroutine library giving access to Mosel models during their execution; defines also the conventions to be observed by Mosel modules. The NI enables users to extend the Mosel language with new features.

Newton-Barrier algorithm: also interior point algorithm; solution algorithm for LP and QP problems that proceeds from some initial interior point in the set of feasible solutions towards an optimal solution without touching the border of the feasible set.

Non-linear Programming (NLP) problem: a Mathematical Programming problem with non-linear constraints or objective function. Frequently heuristic or approximation methods are employed to find good (locally optimal) solutions. Methods provided by Xpress for solving problems of this type include Successive Linear Programming (SLP) and interior point methods. Global optimization of non-convex non-linear programming problems can be performed using Xpress Global.

Objective function: an expression of decision variables to be minimized or maximized (in this manual only linear or quadratic expressions are considered).

Optimization: finding a feasible solution to a problem that minimizes or maximizes a given objective function.

Optimizer: the Xpress solver for LP, MIP, QP, MIQCQP, and MISOCP. Available in the form of a library or a standalone program.

Overloading: subroutines that are defined in several versions for different types or numbers of arguments; operators that are defined for different operand types or combinations of operand types.

Parameter: depending on the context this term has several slightly different meanings: the settings of model parameters (in Mosel) may be changed at run-time, for instance to define different input data sets; problem parameters (in the Optimizer usually called problem attributes) provide access to information about a problem (e.g. solution status) and are typically read-only; algorithm control parameters are used to control algorithmic settings (choice of the solution algorithm, tolerances, etc.).

Problem instance: a Mathematical Programming problem complete with a specific data set.

Quadratic Programming (QP) problem: differs from LP problems in that there are quadratic terms in the objective function (the constraints remain linear). The decision variables may be continuous or discrete, in the latter case we speak of Mixed Integer Quadratic Programming (MIQP). In Quadratically Constrained Quadratic Programming (QCQP) problems the constraints also contain quadratic terms.

Range set: (in Mosel) a set of consecutive integers.

Right hand side (RHS): constant term of a (linear) constraint; a standard format (used, for example, in the matrix representation) is to write all terms involving decision variables on the left of the operator sign and the constant term on its right side.

Second Order Cone Programming (SOCP) problem: a convex optimization problem with a special form of non-linear constraints (the objective remains linear) that can be solved by interior point methods. The decision variables may be continuous or discrete, in the latter case we speak of Mixed Integer Second Order Cone Programming (MISOCP).

Selection statement: statement to express a selection between different actions to be taken in a program. In Mosel these are if/then/elif/then/else/end-if and case.

Simplex algorithm: solution algorithm for LP problems. The idea of the Simplex algorithm is moving from vertex to vertex of the polytope (`simplex') that represents the set of feasible solutions for an LP problem, to improve the objective function value.

Solution: this term may be used with two different meanings: it may denote an assignment of values to all decision variables that satisfies all constraints (feasible solution). In optimization problems where the best possible solution is sought—i.e., a solution minimizing or maximizing a given objective function, the term solution usually is equivalent to optimal solution.

Solver: software used to solve (usually optimize) a problem. With Xpress we use Xpress Solver (comprising Xpress Optimizer, Xpress NonLinear, Xpress Global, and Xpress Kalis).

Sparse array: arrays in Mosel can be either dense or sparse. Sparse arrays are created empty and may grow on demand as their entries are created or get assigned values. Mosel has two types of sparse arrays: dynamic arrays require less memory and are faster for linear enumeration, hashmap arrays are faster for random access.

Status information: Mosel and the Optimizer define different parameters providing status information, such as the LP or MIP status that tell the user among others whether the problem has been solved correctly and a solution is available.

Subroutine: substructures allowing programs to be broken down into smaller subtasks that are easier to understand and to work with. In Mosel, subroutines may be employed in the form of procedures or functions. Procedures are called as a program statement, they have no return value, functions must be called in an expression that uses their return value.

Successive Linear Programming (SLP): method for solving NLP problems via a sequence of LP problems.

Workbench: development environment for Mosel and Python that provides, amongst many other tools, functionality for deploying and debugging Xpress Insight apps.