Glossary

This glossary includes terms and definitions for IBM® ILOG® CPLEX® Optimization Studio.

The following cross-references are used in this glossary:

See refers you from a term to a preferred synonym, or from an acronym or abbreviation to the defined full form.
See also refers you to a related or contrasting term.

To view glossaries for other IBM products, go to www.ibm.com/software/globalization/terminology (opens in new window).

A

activity

A time interval in a scheduling problem. Typical examples include the filling or emptying of capacity resources such as tanks or inventories, or the use of physical resources such as trucks, machines, or people.

argument

An independent variable or any value of an independent variable. Examples of arguments are a search key and a number identifying the location of an item in a table.
A value passed to or returned from a function or procedure at run time.

array

A structure that contains an ordered collection of elements of the same data type in which each element can be referenced by its index value or ordinal position in the collection. See also matrix.

B

backtracking

In constraint programming, the activity of abandoning one line of search (usually after a failure), returning to a given state in the system, and restoring variables to their previous values in that state so that another alternative can be explored in the search for a solution.

barrier algorithm

An algorithm for solving linear programming problems. It exploits both the primal and dual forms of a problem to find a sequence of primal and dual solutions. It measures the feasibility of solutions as it works, and it stops when it finds complementary primal and dual feasible solutions.

basis

A collection of variables that is determined during an iteration of the simplex algorithm and that represents a feasible solution. The basis of a problem may change with each iteration as preferred decision variables enter the basis or variables that are less valuable leave the basis.

bound

A limit on the value that a variable can assume. See also lower bound, upper bound.

bound strengthening

The tightening of bounds on a variable in one of two ways: range, by changing one of the bounds; value, by reducing the domain of the variable to only one possible value. See also lower bound, upper bound.

branch and cut

An algorithm that searches the tree of all possible solutions, branching on decision variables and cutting off those branches that do not lead toward a better solution than the one currently known.

breakpoint

A point where some property of a function changes, such as its slope, for example.
A marked point in a process or programmatic flow that causes that flow to pause when the point is reached, typically to allow debugging or monitoring.

C

cardinality: The number of elements in a set.
ceiling: The smallest integer that is greater than the floating-point number under consideration. For example, the ceiling of 3.5 is 4.
choice point: A point that is set automatically by CP Optimizer as it executes a goal during the search for a solution. At the choice point, the engine records the current state of constraints, variables, and domains, along with other goals not yet executed. If execution of the goal leads to failure, CP Optimizer backtracks to the choice point, restores the state recorded, and tries one of the stored goals.
Cholesky factoring: A technique that is used to factor a matrix into the product of a lower triangular matrix and its conjugate transpose.
complete: A property of a search algorithm such that, when it returns failure in a search, it has proved that no solution exists satisfying the constraints that governed the search, and when it returns success, it is capable of finding all the possible solutions satisfying the constraints of the problem.
complex: In data processing or software engineering, pertaining to an application that may have many components, such as a graphic user interface, a client-server architecture, an engine, a database connection, an output device, input facilities, and so forth.
complexity: A measurement of how many more computing resources the solution of a problem requires as the problem grows in number of variables. Complexity is expressed in notation known informally as Big O notation or more formally as Omega notation.
conflict: In an infeasible model, a set of constraints that cannot all be true at the same time. See also relaxation.
constraint: A condition that must be satisfied by the solution of a problem. A constraint may be arithmetic, requiring that a solution satisfy certain numeric properties, or symbolic, requiring that a solution meet other properties, such as membership of a collection, uniqueness, or cardinality.
constraint programming (CP): A nondeterministic method of computer programming that is based on logic and symbolic reasoning to solve intractable problems. It offers a technique for solving combinatorial problems based on applying constraint propagation on the domains of decision variables. Commercially, it offers a means of representing business rules as constraints, goals, wishes, preferences, strategies, and criteria. See also mathematical programming.
constraint propagation: A process that dynamically reduces the domain of each variable in a problem. Modifications in the domain of one constrained variable may have implications for the domains of other constrained variables. Constraint propagation involves transmitting these implications and carrying out their effects.
convergence: In an algorithm, the process of repeated iterations moving closer and closer to an optimal feasible solution, as opposed to sometimes moving closer and sometimes moving further away.
convex: Pertaining to a set of points in which every possible line between any two points in the set contains only points that are also in the set. See also convex hull.
convex hull: The minimal set of points that is both convex and fully contains the original set of points. See also convex.
cost function: A function in the simplex algorithm that associates a price or cost with a variable as variables move into or out of the basis. See also pseudocost.
CP: See constraint programming.
crash: A heuristic capable of generating a starting point for an algorithm.
crossover: The change from the barrier algorithm to the primal or dual simplex algorithm.
crush: The process of compressing a problem to make it manageable at intermediate steps in an algorithm. See also uncrush.
cumulative function: A function that is used to model a quantity that varies over time and whose value depends on other decision variables of the problem. For example, a given capacity or physical resource can be modeled with a cumul function, and the cumulated contribution of intervals (activities) on the resource is represented by a function of time. cumulFunction is a CP keyword but is accepted as a CPLEX identifier.
cut: A way of eliminating part of the search space without losing any feasible or optimal solutions.

D

Data Definition Language (DDL): A language for describing data and its relationships in a database. See also relational database management system.
data element: An entity in an OPL model that represents input data as well as the result of declarative calculations. See also variable.
DDL: See Data Definition Language.
decision expression: A syntax that is used to express a combination of decision variables in a more compact way. See also decision variable.
decision variable: An unknown in a model, which is a placeholder for the solution of the problem in the model. See also decision expression, variable.
declarative: Pertaining to a statement, model, or application that assumes no particular order. That is, the result does not depend on the order of statements, or parts of the model, or components of the application.
discrete: Pertaining to an element that is cleanly separated from another element; they are not connected. For example, integers are discrete: between any two consecutive integers, there is some distance.
dive strategy: An approach taken by CPLEX in probing child nodes below the current level in the tree before deciding which node to follow during branch and cut.
domain: The set of potential values that a variable can assume.
domain reduction: The removal from the domain of a variable of values that do not satisfy the constraints on the variable (and thus cannot be part of a solution).
dual problem: A mathematical programming (MP) problem which is converted from the primal MP problem and in which each feasible solution yields a bound on the optimal solution of the primal.

E

engine: An algorithmic component that is used to solve optimization problems.
external data: Data that is initialized outside of the model file, in a separate.dat file. See also internal data.

F

factor

In mathematics, to determine the prime numbers to multiply in order to produce the original number.
To determine the most basic relevant elements of a problem. For example, a typical activity in designing the model of a problem is to factor the problem, and then to remove or reduce the repeated factors to eliminate symmetries or redundance in the model.

feasible

In operations research, pertaining to a solution that represents an assignment of values to decision variables that satisfies the constraints of the problem, even if it does not satisfy the objective function of the problem. A feasible solution is thus a state in which values of decision variables respect all the constraints, but for which optimality is not necessarily satisfied. See also objective function, optimal solution, solution.

feasOpt algorithm

An algorithm with facilities to help repair an infeasible model using bound and constraint relaxations determined by user preferences.

floating-point

Pertaining to a method of encoding binary numbers and decimal numbers within the limits of finite precision available on computers.

floor

The greatest integer that is less than or equal to the floating-point number under consideration. For example, the floor of 3.5 is 3.

G

gap: The relative difference between the integer solution found and the proven best possible objective solution value.
generic array: An array whose elements are initialized by external data and which is useful in performing some simple transformations.
generic set: A conjunction of expressions of the form p in S : condition where p is a parameter (or a tuple of parameters), S is a range, a string, or a finite set, and condition is an expression. These expressions are also used in forall statements and aggregate operators. They are often useful to transform a data structure, such as the data stored in a file, into a data structure more appropriate for stating the model effectively.
GLB: See greatest lower bound.
goal: The means by which an engine implements a search algorithm. See also search strategy.
greatest lower bound (GLB): On a decision variable, the largest number that is less than the variable. Greatest lower bounds are important in mathematical programming and constraint programming in the context of setting bounds on variables as tightly as possible. See also least upper bound, lower bound.
ground: Pertaining to an expression that does not contain decision variables, since the variables have no value at their stage of the computation and are subject to almost no restrictions. Breakpoints and slopes in a piecewise linear function must always be ground.

I

incumbent solution: The current best solution, which allows CPLEX to prune from the search tree all subproblems for which the value of the objective function is no better.
integer: A positive or negative whole number, or zero.
integer programming (IP): A form of mathematical programming in which the model of a problem includes the additional stipulation that the domain of all the variables is restricted to integers.
intensity: A measure of usage or utility over an interval length.
internal data: Data that is initialized within the model file along with its declaration. See also external data.
interval size: A measure of the total work capacity of an interval.
interval variable: A decision variable that represents an period of time and is characterized by a start value, an end value, a size, and an intensity.
intractable: Pertaining to a problem that is very large in size or complex.
IP: See integer programming.

L

least upper bound (LUB): The smallest number that is greater than the variable. Least upper bounds are important in math programming (MP) and constraint programming (CP) in the context of setting bounds on variables as tightly as possible. See also greatest lower bound, upper bound.
linear: Pertaining to a function that can be represented by an equation for which the variables are only first degree (that is, none of the variables is multiplied by any other variable, and none of the variables is raised to a higher power, such as squared or cubed) and where the coefficients of the variables are constant numeric values (that is, integers or floating-point numbers).
linearization: The activity of converting logical, symbolic, quadratic, or other nonlinear constraints into a linear representation that can be solved by math programming (MP) methods.
linear programming (LP): A technique for the optimization of a linear function subject to linear constraints over decision variables. In LP, the model of a problem is expressed through numeric variables combined with linear constraints and governed by a linear objective function and by bounds on the variables.
local memory: The amount of memory consumed by a step. It is measured by comparing memory usage snapshots at the beginning and after the end of a step. See also peak memory.
lower bound: A limit that indicates the least value that a variable can assume. In operations research, a lower bound may or may not be in the domain of a variable. When a lower bound is in the domain of the variable, the variable may assume precisely that value, but no less. When a lower bound is not in the domain of the variable, the variable may assume values strictly greater than the lower bound, but not precisely the lower bound itself. See also bound, bound strengthening, greatest lower bound, minimum, upper bound.
LP: See linear programming.
LUB: See least upper bound.

M

makespan: The total duration of a schedule, between the start of the first activity and the end of the last activity.
Markowitz threshold: A value that is associated with the Markowitz criterion for pivoting, which can be of use in a sparse matrix. The threshold condition requires that a selected pivot be a given multiple of the maximum value within its row. This condition is a guard against numerical instability which can result from choosing an extremely small pivot.
master model: One of two models used in model decomposition as applied in column generation techniques. See also model decomposition, submodel.
mathematical programming (MP): A set of optimization techniques that were developed in operations research to solve intractable problems. See also constraint programming.
matrix: A data structure used to represent the coefficients of the variables in a set of linear functions that serve as the constraints in a problem. There is no limit on the number of dimensions of a matrix, but in practice most matrices are only two-dimensional. That is, they consist of one array, the elements of which are arrays themselves. See also array.
maximum: In constraint programming, the greatest value in the domain of a variable.
minimum: In constraint programming, the least value in the domain of a variable. See also lower bound.
model: A group of data items and decision variables that are subject to constraints. A model can contain an objective function to minimize or maximize and a search procedure to guide the algorithm solving the problem.
model decomposition: The process of breaking down one complex model into several models and defining a sequence to solve those other models so as to lead to a solution that is also a solution to the original model. See also master model, multimodel architecture, submodel.
MP: See mathematical programming.
multimodel architecture: An approach to big problems whereby a large model is decomposed into a main model and submodels. The results of each solved submodel are aggregated and returned to the main model to produce a global result. See also model decomposition.

N

network simplex

A version of the simplex algorithm that takes into account the network structure in a network problem.

NLP

See nonlinear programming.

node

A choice point in a binary search tree.

nondeterminism

The capability of a solving engine to search for a solution by exploring many alternative possibilities without the developer knowing beforehand which of those possibilities will necessarily succeed. An engine manages the implementation of nondeterminism through choice points, restored states, reversible variables, backtracking, and so forth.

nonlinear

In operations research, pertaining to functions that can be represented by polynomial or quadratic equations.
In constraint programming, pertaining to a function that is not linear. That is, it may be a quadratic polynomial, or it may be logical and symbolic in ways that cannot be easily or efficiently represented by linear equations. For example, the trigonometric functions, such as sine, cosine, tangent, and so forth, are considered nonlinear in this context.

nonlinear programming (NLP)

A technique for solving an optimization problem for which the model may contain a nonlinear objective and nonlinear constraints. Typically, the decision variables are continuous (not discrete).

O

objective function: In operations research, an expression to optimize (that is, either to minimize or to maximize) while satisfying other constraints of the problem. See also feasible.
optimal solution: In operations research, a solution to a problem that optimizes the objective function (whether linear or quadratic) and satisfies all the other constraints of the problem. See also feasible.
optimization: The discipline of attacking intractable problems and reducing them to manageable proportions.

P

peak memory: The maximal memory used to process an OPL problem. See also local memory.
perturbation: The process of changing a parameter value or function slightly to see whether the change eliminates numerical difficulties that may have stalled the algorithm. Changes are limited to some neighborhood of the initial values.
piecewise linear function: A nonlinear function that can be represented by a sequence of segments of linear functions.
pivot: An element in the tableau representation of a linear problem that is used in an iteration of the simplex algorithm and held constant while certain other elements in the table are set to zero. This makes it possible to determine whether a variable should enter the basis.
positive semidefinite matrix: A matrix that represents a problem with quadratic terms. If the quadratic term gives rise to a matrix that is positive semidefinite, CPLEX can solve the problem (all other aspects of the problem being feasible).
precision: A value that a user defines to indicate how much tolerance a computation involving floating-point arithmetic should allow, that is, how exact it should be.
pricing: A means of measuring which variable should enter, or which should leave, a basis. Pricing is a tactic in the simplex method by which each variable is evaluated for its potential to improve the value of the objective function.
primal problem: In operations research, particularly in the discipline of mathematical programming (MP), a standard way of stating a linear programming (LP) problem as a maximization of an objective function subject to a matrix of linear constraints over variables with bounds. Every feasible solution of the primal problem yields a bound on the optimal solution of the dual. If the primal problem has an optimal solution, then so does the dual.
primitive type: A predefined basic data type without any substructure, such as an integer or a string.
probing: A technique that examines the logical implications of fixing each binary variable to 0 or 1. It is performed after preprocessing and before the solution of the root relaxation.
programming variable: A location in memory that can contain a value or a reference, depending on its type.
program unit: A group of statements that is considered as a whole. Typically an OPL script file loaded by the application is treated as a program unit.
project: The association of a model and a set of data files.
pseudocost: A cost for binary (0-1) variables. A pseudocost offers the same facilities in branch and bound or branch and cut for binary variables as cost does for continuous variables. See also cost function.

Q

QP: See quadratic programming.
quadratic: Pertaining to a function that can be represented by an equation in N variables where the variables are only first or second degree (that is, one variable may be multiplied by another variable, and any of the variables may be squared) and where the coefficients of the variables are constant numeric values (that is, integers or floating-point numbers).
quadratic programming (QP): A technique for solving an optimization problem for which the model contains a quadratic objective.

R

RDBMS: See relational database management system.
reduced cost: The amount by which an objective function coefficient must improve (increase for maximization, decrease for minimization) before the value of a corresponding variable is positive in the optimal solution.
relational database management system (RDBMS): A collection of hardware and software that organizes and provides access to a relational database. See also Data Definition Language.
relaxation: In operations research, a loosening of constraints, usually to find a solution that may not be the optimal feasible solution of the original problem but a solution that is good enough in some sense. For example, in a mathematical programming problem expressed as integer variables, to allow floating-point solutions that are sufficiently close to integer solutions. See also conflict.
resource: A person, piece of equipment, or material that is used to perform an activity.
run configuration: A method of handling model, data, and settings files within a project. A run configuration is a variation of a given project for execution and testing purposes. It combines a model file and one or more data files that differ, regarding contents and/or settings, from the original model and data of the project, while addressing the same mathematical problem.

S

scripting log

A standard output device comprising lines of text written by the programs executing.

script variable

A memory area in which values can be stored and read inside IBM ILOG Script statements (main , execute , and prepare blocks). See also variable.

search failure

A demonstration that no solution exists under current conditions.

search space

A space that consists of the Cartesian product of the domains of the constrained variables of the problem. See also search strategy, solution space.

search strategy

A methodical and systematic way of exploring the search space. This is materialized as a data structure that is associated with an object, field, or value of a field. It controls the order in which decisions are made by a search engine. See also goal, search space.

sequence

A decision variable that represents a total order over a set of interval variables.

series

In mathematics, the sum of a sequence.

set

A collection of unique, unordered elements. No element appears more than once in a set, and by default, there is no reproducible order for the elements of a set.
An ordered list of unique elements.

sifting

An algorithm developed to use the characteristics of models that have a large ratio of the number of columns to the number of rows.

simplex method

An algorithm for solving linear programming problems by testing adjacent vertices of the feasible set in a sequence such that at each new vertex the objective function is either unchanged or improved.

slack basis

A basis that contains all the slack variables.

slack variable

A variable that is introduced into the standard formulation of a problem so that a constraint can be expressed as a strict equality instead of a “less than or equal to” OR “greater than or equal to” inequality.

slicing

A mathematical technique for processing a sparse matrix. It consists of creating pairs of values that identify cells of interest, as opposed to empty cells. The pairs of values can be used to set up processing loops. In OPL, the process of defining constraints with nested iterations on filtering conditions.

solution

In operations research, an assignment of values to variables that satisfies the constraints of the problem. If, in addition to satisfying the constraints, the assignment of values to variables also optimizes an objective function, then the solution is an optimal solution.
In constraint programming, an assignment of values to variables that satisfies all the constraints of the problem, including any objective function. See also feasible.

solution space

A subset of the search space of a problem. It consists of only those tuples (of the Cartesian product of the domains of the variables) that satisfy the constraints. See also search space.

SOS

See special ordered set.

sparsity

The fraction of zeros in a matrix. If matrix A is m by n , and A(i, j) != 0 for k of its elements, its sparsity is k/mn . Large linear programs tend to be very sparse, increasing as the dimensions get large.

specialized constraint

A set of arithmetic or logical constraints that expresses complicated relations between variables, for example, relations that would require a large number of arithmetic constraints. Specialized constraints enter into such considerations as counting values, maintaining load weights, and other critical activities. In most of the cases, a specialized constraint achieves more domain reduction than the equivalent set of basic constraints, and in all cases it performs domain reduction more efficiently.

special ordered set (SOS)

A set of variables in a math programming (MP) problem that must sum to one.

state

A record taken at each choice point during the search for a solution. The record includes information on all constrained variables, their current values, their domains, and constraints upon them.

state function

A function that is used to describe the state of a feature of the problem as a non-negative integer. For example the various operating temperatures of an oven can be described as a state function.

stepwise linear function

A special case of the piecewise linear function where all slopes are equal to zero. The primary use of a stepwise linear function is in scheduling, typically used to model the efficiency of a resource over time. In all uses with scheduling, the domain and image of the function are limited to integers.

submodel

One of two models used in model decomposition as applied, for example, in column generation techniques. See also master model, model decomposition.

subproblem

Any subset of variables in the original problem.

T

tree: A data structure whose elements are linked in a hierarchical fashion.
tuple: A data structure that contains a given number of elements in a given order. In a relational database, a tuple represents a row or record of a table in the database.

U

unbounded

Pertaining to a variable for which one or both of its bounds is infinite.
Pertaining to a model for which the objective function can be optimized without limit.

uncrush

The process of putting a solution back in terms of the original formulation of a problem so that a customer can recognize it. See also crush.

upper bound

A limit that indicates the greatest value that a variable can assume. In operations research, an upper bound may or may not be in the domain of a variable. When an upper bound is in the domain of the variable, the variable may assume precisely that value, but no greater. When an upper bound is not in the domain of the variable, the variable may assume values strictly less than the upper bound, but not precisely the upper bound itself. See also bound, bound strengthening, least upper bound, lower bound.

V

variable

A representation of a changeable value.
An entity that represents an unknown quantity that is determined as a result of solving the mathematical program containing the variable. In this context, a variable may be governed by one or more formal constraints. See also data element, decision variable, script variable.

view

A pane or window within the IDE frame. A view can be an editor or navigator or can provide an alternate way to visualize and work with a project. A view has its own menu and may have its own toolbar.

W

working set: A set that groups or filters elements for display in views or for operations on a set of elements. In the search facility, working sets can be used to restrict the set of elements that are searched.
workspace: A directory on disk that contains all project files, as well as information such as preferences.