Valid inequality. An inequality constraint added to a relaxation that is redundant in the original mathematical program. An example is a linear form, ax <= b, used as a cutting plane in the LP relaxation of an integer program. Another is a linear form that is a facet of the integer polyhedron.

Value iteration. This is an algorithm for infinite horizon [stochastic] dynamic programs that proceeds by successive approximation to satisfy the fundamental equation:

where a is a discount rate. The successive approximation becomes the DP forward equation. If 0 < a < 1, this is a fixed point, and Banach's theorem yields convergence because then `Opt' is a contraction map. Even when there is no discounting, policy iteration can apply.

Variable metric method. Originally referred to the Davidon-Fletcher-Powell (DFP) method, this is a family of methods that choose the direction vector in unconstrained optimization by the subproblem: d* in argmax{grad_f(x)d: ||d||=1}, where ||d|| is the vector norm (or metric) defined by the quadratic form, d'Hd. With H symmetric and positive definite, the constraint d'Hd = 1 restricts d by being on a "circle" -- points that are "equidistant" from a stationary point, called the "center" (the origin in this case). By varying H, as in the DFP update, to capture the curvature of the objective function, f, we have a family of ascent algorithms. Besides DFP, if one chooses H=I, we have Cauchy's steepest ascent. If f is concave and one chooses H equal to the negative of the inverse hessian, we have the modified Newton's method.

Variable upper bound (VUB). A constraint of the form: x_i <= x_j.

Variational calculus. An approach to solving a class of optimization problems that seek a functional (y) to make some integral function (J) an extreme. Given F is in C^1, the classical unconstrained problem is to find y in C^1 to minimize (or maximize) the following function:

                         _x1 
                        | 
                J(y) =  | F(x,y,y') dx. 
                        |   
                       _|x0 

If constraints take the form G(x, y, y') = 0, this is called the problem of Lagrange; other forms are possible.

Variational inequality. Let F:X-->R^n. The variational inequality problem is to find x in X such that F(x)(y-x) >= 0 for all y in X. This includes the complementarity problem.

Vector space. A set closed under addition and scalar multiplication. One example is R^n, where addition is the usual coordinate-wise addition, and scalar multiplication is t(x1,...,xn) = (tx1,...,txn). Another vector space is the set of all mxn matrices. If A and B are two matrices (of the same size), so is A+B. Also, tA is a matrix for any scalar, t in R. Another vector space is the set of all functions with domain X and range in R^n. If f and g are two such functions, so are f+g and tf for all t in R. Note that a vector space must have a zero since we can set t=0.

Vehicle routing problem (VRP). Find optimal delivery routes from one or more depots to a set of geographically scattered points (e.g., population centers). A simple case is finding a route for snow removal, garbage collection, or street sweeping (without complications, this is akin to a shortest path problem). In its most complex form, the VRP is a generalization of the TSP, as it can include additional time and capacity constraints, precedence constraints, plus more.

Vertex. An extreme point of a polyhedron or a node in a graph or network.

Vertex cover. Given a graph, G=[V,E], a vertex cover is a subset of V, say C, such that for each edge (u,v) in E, at least one of u and v is in C. Given weights, {w(v)} for v in V, the weight of a vertex cover is the sum of weights of the nodes in C. The minimum weight vertex cover problem is to find a vertex cover whose weight is minimum. (Also see the covering problem and the maximum weight independent set problem.

Vertex Enumeration. The problem of enumerating all vertices (extreme points) of a polytope.