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. Most commonly an optimization problem of the form

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 N={1, ..., n} be a finite set, and let M={S1, ..., Sm} be a collection of subsets of N. (N,M) is an independence system if Si in M implies every subset of Si is in M. Elements of M are called independent sets, and the remaining subsets of N are called dependent sets. An independent set, say Si, is maximal if Si\/{k} is not in M for any k in N\Si. The max-cardinality independent set of any subset of N, say T, is given by:

A matroid is an independence system (N, M) in which for any subset of N, say T, every independent set in T that is maximal in T has cardinality 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.

Max flow problem. In a network, [V, A], there are two special nodes in V: a source (s) and a sink (t). The problem is to maximize the flow from s to 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. Further details are in the supplement, Ford-Fulkerson Max Flow Labeling Algorithm.

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

maximize v:  0 <= x(i, j) <= U(i, j) for (i, j) in A;

Sum_j{x(i, j)} - Sum_j{x(j, i)} = 0   for i in V \ {s,t};

Sum_j{x(s, j)} - Sum_j{x(j, s)} = v;

Sum_j{x(t, j)} - Sum_j{x(j, t)} = -v.

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

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 Duality Theorem of Linear Programming.

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:

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 n variables, we define the subset of items taken (for any solution) as J={j: x_j=1}. Then, we define J as maximal if no item can be added without violating the limit     i.e., a_k > b     sum_j in J a_j   for all k not in 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 e-maximum is within e of being a maximum: f(x) >= f* - e, where f* is the supremum and e > 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:

Then, the objective is to maximize 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 (some hyphenate as meta-heuristic). 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:

• Ant Colony Optimization
• Genetic Algorithms
• Memetic Algorithms
• Neural Networks
• Particle Swarm Optimization
• Scatter Search
• Simulated Annealing
• Tabu Search
• Target Analysis

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. Using standard form (except no equality constraints), define

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

Metric. A function, d, on pairs from a set S such that for each x, y, z in S:

1. d(x, y) >= 0;
2. d(x, y) = 0 <==> x=y;
3. d(x, y) + d(y, z) >= d(x, z).

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 x be an optimal solution, {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

2x₁ + x₂ >= 1

More generally, suppose ax >= b is a valid inequality, and we consider (a',b') such that a' <= ta and b' >= tb for some t > 0 such that (a',b') not= t(a,b). If a'x >= b' is a valid inequality, it dominates the original one because

{x in Rⁿ⁺: a'x >= b'} is a subset of {x in Rⁿ⁺: ax >= b}.

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:

Minimax Theorem. Proven by von Neumann in 1928, this is a cornerstone of duality (and of game theory). It states that there exists x in S_m and y in S_n such that x'Ay is a saddlepoint of the bilinear form:

Let F:X*Y-->R be such that X and Y are non-empty, convex, compact sets, F(.,y) is convex on X for each y in Y, and F(x,.) is concave on Y for each x in X. Then, there exists a saddlepoint, (x*,y*) in X*Y:

Min{Max F(x,y): y in Y}: x in X} = Max{Min F(x,y): x in X}: y in Y} = F(x*,y*).

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

Minkowski's inequality. ||x + y||_p <= ||x||_p + ||y||_p, where ||.||_p denotes the L_p norm and p >= 1. Equality holds if, and only if, x = ay for some scalar, a.

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

Mixed-integer program (MIP). 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.

Modified Newton method. The Newton method is designed to find the root of a function, say grad_f(x)=0, by the algorithm map A(x) = x - [H_f(x)^–1]grad_f(x). This need not converge, so a modification is to use line search, resulting in the algorithm map:

where s* is in argmax{f(x - s[H_f(x)^–1]grad_f(x)): s >= 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.

MODLER. Modeling by Object Driven Linear Elemental Relations

Monoid. A set, M, defined on rational vectors, such that: (1) 0 is in M, and (2) if v, w are in M, then v+w is in 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: f(x') >= f(x) whenever x' >= x (it is strictly increasing if f(x') > f(x) for x' not= x). A non-increasing, or anatonic, function satisfies: f(x') <= f(x) whenever x' >= x (it is strictly decreasing if f(x') < f(x) for x' not= x). This extends to a vector function, where range(f) is in Rⁿ:   (f(x)-f(y))^t (x-y) >= 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.

MOSEK. A collection of mathematical programming software solvers.

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

MPL. Mathematical Programming Language.

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 Myth LP-5 for one of the complexities.

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

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

min f(x, y):  x in X,  y in Y,  h(x, y)=0,  g(x, y)=0,  y in argmax{F(x, y):  y in S(x)},

Multiple objectives. 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): x* is feasible, and there does not exist another feasible point, x, such that f(x) >= f(x*) and f_i(x) > f_i(x*) for some i, where 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 w'f(x), where w > 0.
2. lexicographic: F_1 = Max{f_1(x)} and for i > 1, F_i = Max{f_i(x): f_k(x)=F_k for k=1, ..., i-1}. This results in x* for which 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.

Multi-stage decision process. See dynamic programming and the recourse model in stochastic programming.

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.)