# All Pages

### From Glossary

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 , where , and is in
smooth. Further, suppose we can partition the variables, ,
such that is m-dimensional with nonsingular at
. Then, there exists for which there is an
*implicit function*, , on the neighborhood,
such that
for all .
Further, is smooth with
.

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 , such that for all feasible .

Inactive constraint |

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

Incidence matrix |

A matrix, say , that represents the incidence of edges or arcs to nodes in a graph or network. In the undirected case, is binary valued: if edge has endpoints and , then and for . In the directed case, the entry indicates the tail: if the arc is directed from to , and .

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, , an *independent set* (also called a *stable set*) is a subgraph induced by a subset of vertices, , plus all edges with both endpoints in , 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, for , the weight of an independent set, , is the sum of the weights in . 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 , since
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 . Such functions are usually denoted or and are evaluated as

Inequality |

A relation of the form or
. Such constraints are typical
of mathematical programs.
With equality allowed, these are called *weak inequalities*;
*strict inequalities* are and .

- Here are particular inequalities in this glossary:
- Cauchy-Schwarz
- Hadamard
- Hölder
- Jensen
- Kantorovich
- Minkowski
- Triangle

Also see variational inequality.

Inequality of degree k |

An inequality, usually linear, with 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:

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

Both sets consist of two the points and .

Integer polyhedron |

The convex hull of the feasible region of a linear integer program: .

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 , is , where and 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 be the inventory at the beginning of period , with given. Then, the inventory equation is:

where is the level of production (or somehow acquired),
and is the level of sales (or somehow consumed). Typically, ,
but if it is called a *loss factor*, and if 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: . Let be a basis from , and we ask for for which this basis is optimal. This has a simple solution. Let and partition and conformally, so and Then, the set of for which the associated basic solution is optimal is the following cone:

A more difficult inverse problem is when there is some target value for the parameters. We might, for example, fix and seek to minimize subject to , where is a target value for .

The problem can be combinatorial. We might want to minimize for some norm where '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 directly, such as simple bounds.

The general inverse problem may thus be stated:

where is the target, is some norm, is a non-empty, closed set, which generally does not contain , and is the feasible region for , given .

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:

where is the perimeter. For positive and and multiplier , Lagrange's multiplier conditions requires and , so , which means the solution is the square.

Isoquant |

Same as Contour.

Isotonic function |

An order preserving function , i.e. for any and in

Categories: MIP/CO | Nonlinear Programming | Constraint Programming | Linear Programming | MIP/CO | Linear Programming | MIP/CO | Common Problems | MIP/CO | Linear Algebra & Geometry | Nonlinear Programming | Linear Programming | MIP/CO | MIP/CO | Nonlinear Programming | MIP/CO | MIP/CO | MIP/CO | MIP/CO | Linear Programming | Linear Programming | Linear Programming | Linear Programming | Linear Programming | Linear Programming | Linear Algebra & Geometry | Linear Programming