# Valid inequality

An inequality constraint added to a relaxation that is redundant in the original mathematical program. An example is a linear form, $LaTeX: a x \le 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:

$LaTeX: \mbox{F}(s) = \mbox{Opt}\{ r_{x, s} + a \sum_{s'} \mbox{P}(x, s, s')*\mbox{F}(s')\},$

where $LaTeX: a$ is a discount rate. The successive approximation becomes the DP forward equation. If $LaTeX: \textstyle 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.

# Value ordering heuristic

The value ordering heuristic is part of the search strategy and specifies in what order values are assigned to a variables during tree search. For instance, a simple value ordering is to pick the smallest value first and step-wise increase it. More complex, dynamic variable orderings evaluate information about the current node in the search tree to heuristically choose a promising value.

# 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: $LaTeX: \textstyle d^* \in \arg\max\{\nabla f(x)*d: ||d|| = 1\},$ where $LaTeX: \textstyle ||d||$ is the vector norm (or metric) defined by the quadratic form, $LaTeX: \textstyle d'Hd.$ With $LaTeX: H$ symmetric and positive definite, the constraint $LaTeX: \textstyle 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 $LaTeX: H,$ as in the DFP update, to capture the curvature of the objective function, $LaTeX: f,$ we have a family of ascent algorithms. Besides DFP, if one chooses $LaTeX: H=I,$ we have Cauchy's steepest ascent. If $LaTeX: f$ is concave and one chooses $LaTeX: H$ equal to the negative of the inverse hessian, we have the modified Newton's method.

# Variable ordering heuristic

The variable ordering heuristic is part of the search strategy and specifies in what order variables are branched on during tree search. For instance, a popular, simple heuristic is to pick the variable with the smallest domain first following the fail first principle.

A variable ordering heuristic is more commonly called a branching rule in branch-and-bound search.

# Variable upper bound

(VUB). A constraint of the form: $LaTeX: x_i \le x_j$

# Variational calculus

An approach to solving a class of optimization problems that seek a functional $LaTeX: (y)$ to make some integral function $LaTeX: (J)$ an extreme. Given $LaTeX: \textstyle F : \Omega \times \mathbb{R} \times \mathbb{R}^n \rightarrow \mathbb{R}$ is smooth, then the classical unconstrained problem is to find $LaTeX: \textstyle y \in C^1$ to minimize (or maximize) the following function:

$LaTeX: \mbox{J}(y) = \int\limits_{x_0}^{x_1}\mbox{F}(x,y(x),\nabla y(x))\, dx.$

An example is a min arc length, where $LaTeX: \textstyle \mbox{F} = \sqrt{1+y'^2}.$ Using the Euler-Lagrange equation, the solution is $LaTeX: \textstyle y(x) = ax + b,$ where $LaTeX: \textstyle a$ and $LaTeX: \textstyle b$ are determined by boundary conditions: $LaTeX: \textstyle y(x_0) = y_0 \mbox{ and } y(x_1) = y_1.$

If constraints take the form $LaTeX: \textstyle \mbox{G}(x, y, y') = 0,$ this is called the problem of Lagrange; other forms are possible.

# Variational inequality

$LaTeX: \textstyle \mbox{Let F:X} \to \mathbb{R}^n.$ The variational inequality problem is to find $LaTeX: \textstyle x \in \mbox{X}$ such that $LaTeX: \textstyle \mbox{F}(x)(y-x) \ge 0 \mbox{ for all } y \in \mbox{X.}$ This includes the complementarity problem.

# Vector space

A set closed under addition and scalar multiplication. One example is $LaTeX: \textstyle \mathbb{R}^n,$ where addition is the usual coordinate-wise addition, and scalar multiplication is $LaTeX: \textstyle t(x_1,\dots,x_n) = (tx_1,\dots,tx_n).$ Another vector space is the set of all $LaTeX: \textstyle m \mbox{x} n$ matrices. If $LaTeX: A$ and $LaTeX: B$ are two matrices (of the same size), so is $LaTeX: A+B.$ Also, $LaTeX: tA$ is a matrix for any scalar, $LaTeX: \textstyle t \in \mathbb{R.}$ Another vector space is the set of all functions with domain $LaTeX: X$ and range in $LaTeX: \textstyle \mbox{R}^n.$ If $LaTeX: \textstyle f \mbox{ and } g$ are two such functions, so are $LaTeX: \textstyle f+g \mbox{ and } tf \mbox{ for all } t \in \mbox{R.}$ Note that a vector space must have a zero since we can set $LaTeX: 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 traveling salseman problem, 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, $LaTeX: \textstyle G = \left [ V, E \right ],$ a vertex cover is a subset of $LaTeX: V,$ say $LaTeX: C,$ such that for each edge $LaTeX: \textstyle (u,v) \in E,$ at least one of $LaTeX: u$ and $LaTeX: v$ is in $LaTeX: C.$ Given weights, $LaTeX: \{w(v)\}$ for $LaTeX: v \in V,$ the weight of a vertex cover is the sum of weights of the nodes in $LaTeX: 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.