All Pages

From Glossary

Jump to: navigation, search

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.


Infeasible

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.

Inventory control problem

See production scheduling 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.


Isoquant

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


Views
Personal tools