Operations research, mathematical programming

Start here

• ConceptConstrained optimisation

  Constrained optimisation looks for the maximum or minimum of an objective function $f$ of several variables over the set of points that satisfy given constraints. Typical constraints are equations $g_i(x) = c_i$ and inequalities $h_j(x) \ge d_j$.

• ConceptLinear programming

  Linear programming is the optimization of a linear function over the set of solutions of finitely many linear inequalities. The feasible set is a convex polyhedron. When an optimum exists, it is attained on a face, and at a vertex when the polyhedron has vertices. Each linear program has a dual program. If one of the two has an optimal solution, so does the other, with the same optimal value; this is tied to Farkas' lemma. Linear programs are solved in practice by the simplex algorithm and by interior point methods. The ellipsoid method and interior point methods solve them in polynomial time.

• LemmaFarkas' lemma

  Let $A$ be a real $m \times n$ matrix and let $b \in \R^m$. For vectors, write $v \ge 0$ when every coordinate of $v$ is nonnegative, and let $A^T$ be the transpose of $A$. Then exactly one of the following two systems has a solution:

• ConceptFourier–Motzkin elimination

  Fourier–Motzkin elimination removes one variable from a system of linear inequalities, as Gaussian elimination does for equations. The new system has a solution exactly when the old one has, and its solutions are the projections of the old solutions. Repeating it decides whether a system of linear inequalities is solvable. It gives short proofs of Farkas' lemma and of the fact that projections of polyhedra are polyhedra. The number of inequalities can grow very fast, so it is mainly a theoretical tool.

• ConceptSimplex algorithm

  The simplex algorithm, introduced by George Dantzig, solves linear programs. It walks from vertex to adjacent vertex of the feasible polyhedron along edges, never decreasing the objective, until no neighbouring vertex is better. In practice it is fast. But for the usual pivot rules there are inputs, such as the Klee–Minty cubes, on which it takes exponentially many steps. The question of how few steps suffice in the worst case is linked to the diameter of polytope graphs and to the Hirsch conjecture.

• ConceptTotally unimodular matrix

  A totally unimodular matrix is an integer matrix in which every square submatrix has determinant $0$, $1$ or $-1$. In particular every entry is $0$, $1$ or $-1$. A linear program whose constraint matrix is totally unimodular and whose right-hand side is integral has integral vertices. This explains why many problems on graphs, such as bipartite matching and network flows, can be solved exactly by linear programming.