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


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

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.

# 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

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

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