Implicit enumeration

Applied to integer programming, this is a systematic evaluation of all possible solutions without explicitly evaluating all of them. For example, suppose a feasible solution is at hand with objective value 100. Now suppose we solve a relaxation, such as fixing some of the variables and solving the resulting linear program, and we obtain a value of only 90. If we seek a maximum, we can ignore all possible solutions having the fixed values in the relaxation since they must all have an objective value of at most 90. This is often said to be equivalent to branch and bound; however, the early versions of these methods were related, but different. The early branch and bound was a best-first (even breadth-first) heuristic search   strategy. Early implicit enumeration schemes were depth-first.

Implicit function theorem

Suppose $LaTeX: h:R^n \rightarrow R^m$, where $LaTeX: n > m$, and $LaTeX: h$ is in smooth. Further, suppose we can partition the variables, $LaTeX: x = (y, z)$, such that $LaTeX: y$ is m-dimensional with $LaTeX: \nabla_y h(x)$ nonsingular at $LaTeX: x^* = (y^*, z^*)$. Then, there exists $LaTeX: \varepsilon > 0$ for which there is an implicit function, $LaTeX: f$, on the neighborhood, $LaTeX: N_{\varepsilon}(z*) = \{z: \|z-z*\| < e\}$ such that $LaTeX: h(f(z), z)=0$ for all $LaTeX: z \in N_{\varepsilon}(z*)$. Further, $LaTeX: f$ is smooth with $LaTeX: \nabla_z f(z^*) = -\left( \nabla_y h(x^*) \right)^{-1} \nabla_z h(z^*)$.

Implied constraint

An implied constraint is a redundant constraint that (typically) improves propagation if it is added to a constraint model.

Implied equality

Implied equality. An inequality constraint, say $LaTeX: g(x) \le 0$, such that $LaTeX: g(x)=0$ for all feasible $LaTeX: x$.

Inactive constraint

A constraint that is not active (at a point).

Incidence matrix

A matrix, say $LaTeX: M$, that represents the incidence of edges or arcs to nodes in a graph or network. In the undirected case, $LaTeX: M$ is binary valued: if edge $LaTeX: k$ has endpoints $LaTeX: i$ and $LaTeX: j$, then $LaTeX: M_{ik} = M_{jk} = 1$ and $LaTeX: M_{rk} = 0$ for $LaTeX: r \neq i,j$. In the directed case, the entry $LaTeX: -1$ indicates the tail: if the arc is directed from $LaTeX: i$ to $LaTeX: j$, $LaTeX: M_{ik} =-1$ and $LaTeX: M_{jk} = 1$.

Inconsistent

A system of inequalities and/or equations for which there is no feasible solution.

Incumbent solution

The current best solution found during an algorithmic search procedure. Typically in (mixed) integer programming this refers to the best known feasible solution in the branching tree.

Independent set

Given a graph, $LaTeX: G=(V,E)$, an independent set (also called a stable set) is a subgraph induced by a subset of vertices, $LaTeX: S$, plus all edges with both endpoints in $LaTeX: S$, such that no two nodes in the subgraph are adjacent. A maximal independent set is one such that adding any node causes the subgraph to violate independence -- the added node is adjacent to some node already in the set. Given weights, $LaTeX: w(v)$ for $LaTeX: v \in V$, the weight of an independent set, $LaTeX: S$, is the sum of the weights in $LaTeX: S$. The maximum independent set problem is to find an independent set of maximum weight. This is equivalent to finding a minimum weight vertex cover, say $LaTeX: C$, since $LaTeX: V\backslash C$ is an independent set. (One can also refer to an independent set of arcs (or edges) as a subgraph with no two arcs (or edges) adjacent.)

Indicator function

A function indicating membership in a set, say $LaTeX: A$. Such functions are usually denoted $LaTeX: \chi_A$ or $LaTeX: 1_A$ and are evaluated as

$LaTeX: \chi_A (x) = 1_A = \left\{ \begin{array}{cl} 1, & x \in A \\ 0, & x \not\in A. \end{array} \right.$

Inequality

A relation of the form $LaTeX: g(x) \le 0$ or $LaTeX: g(x) \ge 0$. Such constraints are typical of mathematical programs. With equality allowed, these are called weak inequalities; strict inequalities are $LaTeX: g(x) < 0$ and $LaTeX: g(x) > 0$.

Also see variational inequality.

Inequality of degree k

An inequality, usually linear, with $LaTeX: k$ variables. This arises in integer programming, where the variables are binary. In particular, an inequality of degree 2 can represent a precedence constraint, and it has special computational advantages in the node packing problem.

Not feasible.

Inference dual

See it in the list of particular duals.

Infimum

(abbr. Inf). The greatest lower bound on a (real-valued) function over (a subset of) its domain. If f is unbounded from below, Inf{f} = -infinity, and if the domain is empty, Inf{f} = infinity. Otherwise, suppose L is any lower bound: f(x) >= L for all x in X. L is a greatest lower bound if, for any e > 0, there exists x in the domain for which f(x) <= L+e. (That is, we can get arbitrarily close to L in the range of f.) Note that the infimum is always defined, and its range is in the extended reals. The infimum is the minimum, if it is attained by some point in its domain.

Infinite program

An infinite [dimensional] program is a mathematical program with an infinite number of variables and constraints (also see semi-infinite program). Generally, this is approached as an abstract program.

Inner approximation

This solves a mathematical program by a sequence of approximations whose feasible regions are contained in the original feasible region. One example is the use of a barrier penalty method. Another example is polyhedral annexation.

Integer equivalent aggregation

Integer equivalent aggregation is a reduction of a system of linear algebraic equations with non-negative integer solutions to a single equation, which is a linear combination of the equations of the system and has the same set of non-negative integer solutions. For example, consider the system:

$LaTeX: S = \{ (x,y,z) \in \{0,1\}^3 : x + y = 1 , y + z = 1\}.$
.

By simply adding the equations, we have the equivalent description:

$LaTeX: S = \{(x,y,z) \in {0,1}^3: x + 2y + z = 2\}$.

Both sets consist of two the points $LaTeX: (0,1,0)$ and $LaTeX: (1,0,1)$.

Integer polyhedron

The convex hull of the feasible region of a linear integer program: $LaTeX: \{x \in \mathbb{Z}^n+ : Ax \ge b\}$.

Integer program

Abbreviated IP. The variables are required to be integer-valued. Historically, this term implied the mathematical program was otherwise linear, so one often qualifies a nonlinear integer program vs. a linear IP. Also see mixed integer program and combinatorial program.

Integer rounding

Rounding a non-integer solution to an integer neighbor. This will generally not yield an optimal solution to an integer program -- see Myths and Counterexamples in Mathematical Programming.

Interior penalty function

Same as barrier function.

Interior point method

A family of algorithms that stays in the strict interior of the feasible region, possibly through the use of a barrier function. The term grew from Karmarkar's algorithm to solve a linear program. In that case, the resulting solution (if it exists) is strictly complementary, which defines the (unique) optimal partition.

Interior solution

An optimal solution to a mathematical program that is in the relative interior of its set of optimal solutions. This arises in interior point methods, and relates to the strict complementarity of the solution.

Interpolation

An estimate of a value between two others. In LP, an interpolation estimate of the optimal objective value, say $LaTeX: z(\alpha b+(1-\alpha)b')$, is $LaTeX: \alpha z(b) +(1-\alpha)z(b')$, where $LaTeX: b$ and $LaTeX: b'$ are right-hand side vectors.

Intersection cut

See convexity cut.

Inventory balance equation

The constraint that says that the amount of inventory in the next time period must equal the current inventory plus what is produced or purchased minus what is lost or sold. Let $LaTeX: y(t)$ be the inventory at the beginning of period $LaTeX: t$, with $LaTeX: y(0)$ given. Then, the inventory equation is:

$LaTeX: y(t+1) = ay(t) + P(t) - S(t),$

where $LaTeX: P(t)$ is the level of production (or somehow acquired), and $LaTeX: S(t)$ is the level of sales (or somehow consumed). Typically, $LaTeX: a=1$, but if $LaTeX: a < 1,$ it is called a loss factor, and if $LaTeX: a > 1,$ it is called a gain factor.

The language used is for the inventory control in the production scheduling problem, but this has become a standard system of equations that appears in many mathematical programs. Thus, the meaning of the variables can be substantially different. One example is the

steel beam assortment problem.

Inverse problem

Given a point in the decision space, find parameter values that render it optimal. For example, suppose we have the LP: $LaTeX: \min \{c^T x : Ax = b, \,x \ge 0\}$. Let $LaTeX: B$ be a basis from $LaTeX: A$, and we ask for $LaTeX: (b, c)$ for which this basis is optimal. This has a simple solution. Let $LaTeX: A = [B \, N]$ and partition $LaTeX: c$ and $LaTeX: x$ conformally, so $LaTeX: Ax = Bx_B + Nx_N$ and $LaTeX: c^Tx = c^T_Bx_B + c^T_Nx_N$ Then, the set of $LaTeX: (b, c)$ for which the associated basic solution is optimal is the following cone:

$LaTeX: K_B = \{ (b, c) : B^{-1}b \ge 0, \, c_B B^{-1}N \le c_N\}.$

A more difficult inverse problem is when there is some target value for the parameters. We might, for example, fix $LaTeX: b$ and seek to minimize $LaTeX: \|c - c^*\|^2$ subject to $LaTeX: (b, c) \in K_B$, where $LaTeX: c^*$ is a target value for $LaTeX: c$.

The problem can be combinatorial. We might want to minimize $LaTeX: \|c - c^*\|$ for some norm where $LaTeX: c$'s are costs on the arcs or edges of a network. The solution at hand might be a spanning tree or a TSP tour. We might also impose constraints on $LaTeX: c$ directly, such as simple bounds.

The general inverse problem may thus be stated:

$LaTeX: \min \{ \|p - p^* \| : p \in P, \, p \in \arg\min \{ f(x; p): x \in F(p)\},$

where $LaTeX: p^*$ is the target, $LaTeX: ||\cdot||$ is some norm, $LaTeX: P$ is a non-empty, closed set, which generally does not contain $LaTeX: p^*$, and $LaTeX: F(p)$ is the feasible region for $LaTeX: x$, given $LaTeX: p$.

There are variations, such as when only a partial solution is given. An example is a partial TSP tour or some partial scheduling of jobs, and we ask for cost values for which there is an optimal

solution that contains these subsets.

Involutionary property

Of a transformation, it means something is its own inverse. In linear programming, the dual of the dual is the primal.

Irreducible infeasible subsystem

Abbreviated IIS. A subsystem of inequalities and equations such that the subsystem is inconsistent and every proper subsystem is consistent.

Irredundant

A system of constraints is irredundant if it contains no redundant constraint.

Isoperimetric problem

Among all closed plane curves with a given perimeter find one that maximizes the area. This is also known as Queen Dido's problem and serves as a classical problem for variational calculus. Its significance in mathematical programming is that it led to Lagrange's multiplier theorem. Restricting shapes to rectangles, the problem is:

$LaTeX: \max \{xy : x+y=p, \, x \ge 0, \, y \ge 0\},$

where $LaTeX: 2p$ is the perimeter. For positive $LaTeX: x$ and $LaTeX: y$ and multiplier $LaTeX: u$, Lagrange's multiplier conditions requires $LaTeX: y-u=0$ and $LaTeX: x-u=0$, so $LaTeX: x=y$, which means the solution is the square.

Same as Contour.

Isotonic function

An order preserving function $LaTeX: f: X \rightarrow \mathbb{R}^m$, i.e. for any $LaTeX: x$ and $LaTeX: y$ in $LaTeX: X$

$LaTeX: x > y \Rightarrow f(x) > f(y) \; \mbox{ and } \; x < y \Rightarrow f(x) < f(y).$