All Pages

From Glossary

Jump to: navigation, search

MAX CSP

A constraint satisfaction problem where some constraints may be violated, and the quality of the solution is measured by the number of satisfied constraints (i.e., the optimal solution will have the maximum of satisfied constraints).


MIMI

Manager for Interactive Modeling Interfaces - A modeling system that integrates mathematical programming, database management and artificial intelligence.


MINOS

Modular In-core Nonlinear Optimization System - An optimization system, available from Stanford Optimization Lab.


MODLER

Modeling by Object Driven Linear Elemental Relations


MOSEK

A software package for solving large-scale sparse linear, conic and convex optimization problems.


MPL

Mathematical Programming Language.MPL.


Main Page

Mathematical Programming Glossary©

This glossary contains terms specific to mathematical programming and related disciplines like economics, computer science, and mathematics. A thread of terms is constructed by following other terms that are defined within those already displayed. Terms can be removed from a thread by clicking button.png. A new thread is initiated by following the title of one of the thread's terms.

The following are of general interest (you should read them if this is your first time here).

Please remember this is a glossary, not a survey, so no attempt is made to cite credits.

Manpower planning problem

This has many variations, but typically focuses on either short-term problems, like scheduling workers, or on longterm problems, like recruiting. There are workers of different categories, some relate to each other by level (e.g., copilot and pilot), others do not. For longterm manpower planning, inventory balance equations  are typically used to represent changes in the number of employees in each category over time, including new hires and various forms of departures. For the short-term scheduling, a simple model is the shortest path  through a network. Often, more complicated combinatorial programs are required.


Marginal price

The rate at which the optimal objective value changes with respect to a perturbation of a right-hand side, like a supply, demand or capacity limit. When it exists, the marginal price is often equal to a most pessimistic dual price (e.g., consumer's marginal price is the greatest dual price, which reflects what another unit of demand would cost to satisfy).


Markov decision process

A stochastic dynamic program, whereby for each policy the resulting state variables comprise a Markov process (a stochastic process with the property that the conditional probability of a transition to any state depends only on the current state, and not on previous states).


Matching problem

Given a graph, a matching is a subgraph with the property that no two edges are incident to the same node. Subject to certain restrictions, the problem is to find a feasible matching that optimizes some objective, such as minimizing the total cost of the edges in the matching. A perfect matching is when each node is incident with exactly one edge.

The assignment problem is a classical perfect matching, whereby the graph is bipartite (nodes are two sets: people and jobs), and the matching must have all nodes (every person must do a job, and every job must be done). Then, the matching corresponds precisely to an assignment since each job node is incident with exactly one person node in the matching. Further, the cost of each such matching is precisely the total cost of the corresponding assignment, so this min-cost matching problem is the same as the assignment problem.

Another type of matching problem, called maximum cardinality matching, is to find a matching with the greatest number of nodes, and this is also solvable in polynomial time. However, minimum weight – maximum cardinality is NP-complete.


Mathematical program

Commonly an optimization problem of the form

LaTeX: \max \{ f(x) : x \in X,\, g(x) \le 0, \, h(x) = 0\},

where LaTeX: X is a subset of LaTeX: \mathbb{R}^n and is the domain of LaTeX: f, LaTeX: g and LaTeX: h, which map into real spaces. The function LaTeX: f is called the objective function, which is typically real-valued. If not, then LaTeX: f maps into LaTeX: \mathbb{R}^p with LaTeX: p \ge 2, and the problem is a multiple objective problem. The feasible region is the collection of LaTeX: x that simultaneously satisfy LaTeX: x in LaTeX: X, LaTeX: g(x) \le 0, and LaTeX: h(x) = 0, which are the program's constraints.


Matrix norm

See norm.

Matroid

This is an abstraction of independence that includes vectors in linear algebra and circuits in graphs. First, we need some preliminary definitions. Let LaTeX: N = \{1, \ldots, n\} be a finite set, and let LaTeX: M = \{S_1, \ldots, S_m\} be a collection of subsets of LaTeX: N. LaTeX: (N,M) is an independence system if LaTeX: S_i in LaTeX: M implies every subset of LaTeX: S_i is in LaTeX: M. Elements of LaTeX: M are called independent sets, and the remaining subsets of LaTeX: N are called dependent sets. An independent set, say LaTeX: S_i, is maximal if LaTeX: S_i \cup \{k\} is not in LaTeX: M for any LaTeX: k \in N\backslash S_i. The max-cardinality independent set of any subset of LaTeX: N, say LaTeX: T, is given by:

LaTeX: m(T) = \max \{ |S_i|: S_i \in M, \, S_i \subseteq T\}.

A matroid is an independence system LaTeX: (N, M) in which for any subset of LaTeX: N, say LaTeX: T, every independent set in LaTeX: T that is maximal in LaTeX: T has cardinality LaTeX: m(T). The definition essentially means that maximal and maximum are the same. In other words, a system is a matroid if, and only if, a greedy algorithm yields a globally optimal solution to the associated max weight problem. An example is the spanning tree.


MaxMin

(or maximin). The objective is, itself, the value of another mathematical program:

LaTeX: f(x) = \inf \{ f(x, y): y \in Y(x),\, g(x, y) \ge 0,\, h(x, y) = 0\}.

Then, the objective is to maximize f(x) (on some feasible region).


Max flow-min cut theorem

The maximum flow through a (single commodity) capacitated network from a specified node, called the source, to another node, called the sink, equals the value of the minimum cutset. Originally proven directly from principles of networks, this was discovered to be a special case of the [[LP|]]uality Theorem of Linear Programming.

Max flow problem

In a network, LaTeX: [V, A], there are two special nodes in LaTeX: V: a source LaTeX: (s) and a sink LaTeX: (t). The problem is to maximize the flow from LaTeX: s to LaTeX: t subject to conservation of flow constraints at each node and flow bounds on each arc. The max flow labeling algorithm provides a constructive proof of the Max flow - Min cut theorem.

This can also be obtained from the duality of the following linear program:

maximize LaTeX: v:

LaTeX: 0 \le x_{ij} \le U_{ij} for LaTeX: (i, j) \in A;

LaTeX: \sum_j x_{ij} - \sum_j x_{ji} = 0 for LaTeX: i \in V \backslash \{s,t\};

LaTeX: \sum_j x_{sj} - \sum_j x_{js} = v;

LaTeX: \sum_j x_{tj} - \sum_j x_{jt} = -v.

LaTeX: U are upper bounds (capacities) on arc flows, and each sum is for LaTeX: j such that the indicated arc is in LaTeX: A.


Maximal

In a partially ordered set, a maximal element is one for which no element follows it in the ordering. This is not to be confused with maximum. For example, consider the following knapsack problem:

LaTeX: \max \{ 5x + y: (x, y) in \mathbb{Z}^2, \, x \ge 0, \, y \ge 0,  3x + 2y \le 3\}.

The maximum value is LaTeX: 5, with LaTeX: (x, y) = (1, 0). Define the partial ordering to be the ordinary greater-than-or-equal-to, so that LaTeX: (x',y') > (x, y) means LaTeX: x' \ge x, LaTeX: y' \ge y, and either LaTeX: x' > x or LaTeX: y' > y. In words, LaTeX: (x', y') > (x, y) means we can put at least one more item into the knapsack, in which case we would increase our return. When we cannot do so, LaTeX: (x, y) is a maximal element. In particular, LaTeX: (0,1) is a maximal element, and its value is LaTeX: 1, which is not the maximum.

Another definition pertains to a subset with respect to some property such that no proper superset has that property. In the 0-1 knapsack problem with LaTeX: n variables, we define the subset of items taken (for any solution) as LaTeX: J=\{j: x_j=1\}. Then, we define LaTeX: J as maximal if no item can be added without violating the limit, i.e., LaTeX: \textstyle a_k > b - \sum_{j\in J} a_j for all LaTeX: k not in LaTeX: J.


Maximand

The objective function in a mathematical program whose sense of optimization is to maximize.

Maximum

(pl. maxima). A feasible point at which the supremum is achieved. (See Weierstrass' Theorem.) An LaTeX: \varepsilon-maximum is within LaTeX: \varepsilon of being a maximum: LaTeX: \textstyle f(x) \ge f^* - \varepsilon, where LaTeX: f^* is the supremum and LaTeX: \varepsilon > 0.


Maximum principle

Necessary conditions for a solution to the (constrained) problem of variational calculus, given in terms of nonlinear differential equations. Generally credited to Pontryagin (1962), it was derived as an extension of the Euler-Lagrange conditions for variational calculus, and later was derived from dynamic programming.


Maxmin

(or maximin). The objective is, itself, the value of another mathematical program:

LaTeX: f(x) = \inf \{f(x, y): y \in Y(x),\, g(x, y) \ge 0, \, h(x, y) = 0\}.

Then, the objective is to maximize LaTeX: f(x) (on some feasible region).


Memetic algorithm

This a population-based approach for heuristic search in optimization problems. It uses the crossover operation of genetic algorithms, but combines it with local search heuristics. Implementations are typically parallel with an MIMD architecture.


Metaheuristic

This is a general framework for heuristics in solving hard problems. The idea of ``meta is that of level. An analogy is the use of a meta-language to explain a language. For computer languages, we use symbols, like brackets, in the meta-language to denote properties of the language being described, such as parameters that are optional. Examples of metaheuristics

are:

Besides parameters that define specific algorithms with each framework, these metaheuristics also require some concept of representation, which is problem dependent. Also see GRASP.

Method of centers

This is an interior method defined for a mathematical program without equality constraints with a nonempty strict interior. Considering LaTeX: \max \{ f(x) : x \in X, \, g(x) \le 0 \}, define

LaTeX: G(w, x) = \min \{f(w)-f(x), -g_1(w), \ldots,-g_m(w)\}

Observe that LaTeX: G(w, x) > 0 if, and only if, LaTeX: f(w) > f(x) and LaTeX: g_i(w) < 0 for all LaTeX: i. Then, the algorithm map is LaTeX: \arg\max \{G(w,x): w \in \mathbb{R}^n\}.


Metric

A nonnegative, real-valued function, LaTeX: d, on pairs from a set LaTeX: S such that for each LaTeX: x, LaTeX: y, and LaTeX: z in LaTeX: S:

  1. LaTeX: d(x, y) \ge 0;
  2. LaTeX: d(x, y) = 0 \Rightarrow x=y;
  3. LaTeX: d(x, y) + d(y, z) \ge d(x, z).

The function is also called a distance; the pair LaTeX: (S, d) is a metric space. Condition (3) is called the Triangle inequality. A space is metrizable if a metric can be defined. A metric is induced by a norm if one exists: LaTeX: d(x,y) = \| x - y \|. See Hausdorff metric.


Min-conflicts heuristic

The min-conflicts heuristic is a local search or heuristic repair method (see heuristic search) for solving CSPs. This heuristic randomly selects a variable in the scope of a violated constraint and assigns it to the value in its domain that minimizes the number of violated constraints. If there are more than one such value, it chooses randomly among them.


Minimal

In a partially ordered set, a minimal element is one that does not follow another in the ordering. This is not to be confused with minimum.

Another definition pertains to a subset with respect to some property such that no proper subset has that property. In the 0-1 knapsack problem the set of items not taken is minimal with respect to the greedy algorithm of adding the most valuable item, if it fits, until there are no more items than can fit. This does not necessarily produce a maximum objective value, but the converse is certainly true:  in order that LaTeX: x be an optimal solution, LaTeX: \{j: x_j=0\} must be minimal with respect to adding items that fit. See maximal for analogy and numerical example.


Minimal inequality

In integer programming, a valid inequality is minimal if it not dominated by any valid inequality. Originally, this was limited to not being able to decrease any coefficient and remain valid. For example, suppose LaTeX: 2x_1 + x_2 \ge 1 is a valid inequality. Then, if we decrease the first coefficient to obtain LaTeX: x_1 + x_2 = 1, either this is not valid or it dominates the former, rendering it non-minimal.

More generally, suppose LaTeX: a^Tx \ge b is a valid inequality, and we consider LaTeX: (a',b') such that LaTeX: a' \le t a and LaTeX: b' \ge t b for some positive LaTeX: t such that LaTeX: (a',b') \neq t (a,b). If LaTeX: (a')^T x \ge b' is a valid inequality, it dominates the original one because

\{ x \in \mathbb{R}^n : x \ge 0, \, (a')^T x \ge b \} \subseteq \{ x \in \mathbb{R}^n : x \ge 0, \, a^T x \ge 0 \}.

For example, LaTeX: 4x_1 + 2x_2 \ge 3 dominates LaTeX: 2x_1 + x_2 \ge 1 (use LaTeX: t = 2), so if this is valid, LaTeX: 2x_1 + x_2 \ge 1 cannot be minimal. Every facet-defining inequality is minimal, but not conversely.


Minimand

The objective function in a mathematical program whose sense of optimization is to minimize.

Minimax

The objective is, itself, the value of another mathematical program:

LaTeX: 
f(x) = \sup \{f(x, y): y \in Y(x),\, g(x, y) \ge 0, \, h(x, y) = 0\}.

Then, the objective is to minimize LaTeX: f(x) (on some feasible region).


Minimax theorem

Proven by von Neumann in 1928, this is a cornerstone of duality (and of game theory). It states that there exists LaTeX: x \in S_m and LaTeX: y \in S_n such that LaTeX: x^T A y is a saddlepoint of the bilinear form:

LaTeX: \min \left\{ \max \{ u^T A v: v \in S_n\}: u \in S_m \right} = 
\max \left\{ \min \{ u^T A v: u \in S_m\}: v \in S_n \right\} = x^TAy.

This extends to the following.

Let LaTeX: F:X\timesY\rightarrow \mathbb{R} be such that LaTeX: X and LaTeX: Y are non-empty, convex, compact sets, LaTeX: F(.,y) is convex on LaTeX: X for each LaTeX: y \in Y, and LaTeX: F(x,.) is concave on LaTeX: Y for each LaTeX: x \in X. Then, there exists a saddlepoint, LaTeX: (x^*,y^*) \in X\times Y such that

LaTeX: \min \left\{ \max \{F(x,y): y \in Y\}: x \in X\right\} 
= \max \left\{ \min \{F(x,y): x \in X\}: y \in Y\right\} = F(x^*,y^*).


Minimum

(pl. minima). A feasible point at which the infimum is achieved. (See Weierstrass' Theorem.) An LaTeX: \varepsilon-minimum is within e of being a minimum: LaTeX: f(x) \le f^* + \varepsilon, where LaTeX: f^* is the infimum and LaTeX: \varepsilon > 0.


Minkowski inequality

The Minkowski inequality is

LaTeX: \|x + y\|_p \le \|x\|_p + \|y\|_p,

where LaTeX: \|\cdot \|_p denotes the LaTeX: L_p norm and LaTeX: p \ge 1. Equality holds if, and only if, LaTeX: x = \alpha y for some scalar, LaTeX: \alpha.


Mixed-integer program

A mixed-integer program (MIP) is a mathematical program in which some of the variables are required to be integer-valued. Historically, this term implied the mathematical program was otherwise linear, so older papers (and some recent ones) mean this, but most now refer to the following:

MILP: Mixed integer linear program
MINLP: Mixed integer nonlinear program
MIQP: Mixed integer quadratic program
Also see combinatorial program.


Modified Newton method

The Newton method is designed to find the root of a function, say LaTeX: \nabla f(x)=0, by the algorithm map LaTeX: A(x) = x - \nabla^2 f(x)^{-1} \nabla f(x). This need not converge, so a modification is to use line search, resulting in the algorithm map:

LaTeX: A(x) = x - s*\nabla^2 f(x)^{-1} \nabla f(x),

where LaTeX: s^* \in \arg\max \{f(x - s\nabla^2 f(x)^{-1} \nabla f(x)): s \ge 0\}. More generally, we could have another step size rule; as long as it is chosen to converge, the modified algorithm is sometimes called the damped Newton method.


Monoid

A set, LaTeX: M, defined on rational vectors, such that: (1) LaTeX: 0 \in M, and (2) if LaTeX: v, LaTeX: w are in LaTeX: M, then LaTeX: v+w is in LaTeX: M. The monoid is integral if it contains only integer vectors. One can think of a monoid as a discrete analogue of a convex cone.


Monotonic function

A function that either never decreases or never increases. A non-decreasing, or isotonic, function satisfies: LaTeX: f(x') \ge f(x) whenever LaTeX: x' \ge x (it is strictly increasing if LaTeX: f(x') > f(x) for LaTeX: x' > x). A non-increasing, or anatonic, function satisfies: LaTeX: f(x') \le f(x) whenever LaTeX: x' \ge x (it is strictly decreasing if LaTeX: f(x') < f(x) for LaTeX: x'> x). This extends to a vector function, where LaTeX: \mbox{range}(f) is in LaTeX: \mathbb{R}^n: LaTeX: (f(x)-f(x))^T (x-y) \ge 0.


Monte Carlo optimization

A class of algorithms that seek a maximum by sampling, using a pseudo-random number generator. One example is simulated annealing.


Moore-Penrose inverse

See generalized inverse.


More for less paradox

This was originally introduced in the context of linear network flows:

It is possible to send more flow from supply to demand nodes at lower cost, even if all arc costs are positive.

See Myths and Counter Examples in Mathematical Prgramming for a non-network example.


Mosel

A modelling and solving environment and language, which was designed to fit with Xpress-MP.

Multi-commodity flow

A network flow problem in which more than one commodity share arc capacities. This applies to communication networks as well as to shipments of different grains on barges of limited capacities. It is more complicated than the single-commodity flow, generally NP-complete (except for some special cases). See [1] for one of the complexities.


Multi-stage decision process

See dynamic programming and the recourse model in stochastic programming.


Multilevel program

The "level" refers to sets of variables. A bilevel program has two sets:

LaTeX: \min \{ f(x, y): x \in X,\, y \in Y, \, h(x, y)=0, \, g(x, y)=0\}.

A reason for identifying levels is to apply a decomposition principle for algorithm design. One example is the bilinear program. Another is when one set of variables is constrained to be a solution to an inner optimization problem:

LaTeX: \min \{ f(x, y): x \in X,\, y \in Y,\, h(x, y)=0,\, g(x, y)=0,\, 
y \in \arg\max \{F(x, y): y \in S(x)\} \},

where LaTeX: S(x) is some subset of LaTeX: Y.


Multiple objectives

Headline text

The problem has more than one objective function. Since these do not lie in a totally ordered set, a solution is often defined as an efficient point (sometimes called a Pareto optimum): LaTeX: x^* is feasible, and there does not exist another feasible point, LaTeX: x, such that LaTeX: f(x) \ge f(x^*) and LaTeX: f_i(x) > f_i(x^*) for some LaTeX: i, where LaTeX: i indexes the objective functions, and we assume we are maximizing. This reduces to the usual definition of an optimum when there is only one objective.

There have been two principle approaches to solving a multiple objective mathematical program (MOMP):

  1. weighted sum: Maximize LaTeX: w^T f(x), where LaTeX: w > 0.
  2. lexicographically: LaTeX: F_1 = \max \{f_1(x)\} and for LaTeX: i > 1, LaTeX: F_i = \max \{f_i(x): f_k(x) = F_k \mbox{ for } k=1, \ldots, i-1\}. This results in LaTeX: x^* for which LaTeX: f(x^*) is lexicographically greater than (or equal to) any feasible solution. (Note: the order is fixed in advance.)

Both methods yield an efficient point (if one exists). Under certain assumptions, both methods can be used to generate the set of all efficient points, called the efficient frontier. (Care must be exercised in doing so, however; for example, see MOP Myth #2 for issues that arise when varying the weights of the objectives.)


Mutation operation

See genetic algorithm.


Myopic optimization

Given any partial solution, assign another value that improves the objective the most. (Algorithms that produce solutions based on myopic optimization are called greedy algorithms.)


Views
Personal tools