All Pages

From Glossary

Jump to: navigation, search

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.

See also variable ordering heuristic.

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.

See also value ordering heuristic.

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:

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


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.

Personal tools