Total dual integrality

Last updated August 29, 2020

In mathematical optimization, total dual integrality is a sufficient condition for the integrality of a polyhedron. Thus, the optimization of a linear objective over the integral points of such a polyhedron can be done using techniques from linear programming.

A linear system $Ax\leq b$ , where $A$ and $b$ are rational, is called totally dual integral (TDI) if for any $c\in \mathbb {Z} ^{n}$ such that there is a feasible, bounded solution to the linear program

{\begin{aligned}&&\max c^{\mathrm {T} }x\\&&Ax\leq b,\end{aligned}}

there is an integer optimal dual solution.^[1]^[2]^[3]

Edmonds and Giles^[2] showed that if a polyhedron $P$ is the solution set of a TDI system $Ax\leq b$ , where $b$ has all integer entries, then every vertex of $P$ is integer-valued. Thus, if a linear program as above is solved by the simplex algorithm, the optimal solution returned will be integer. Further, Giles and Pulleyblank^[1] showed that if $P$ is a polytope whose vertices are all integer valued, then $P$ is the solution set of some TDI system $Ax\leq b$ , where $b$ is integer valued.

Note that TDI is a weaker sufficient condition for integrality than total unimodularity.^[4]

Related Research Articles

In mathematics, an equation is a statement that asserts the equality of two expressions. The word equation and its cognates in other languages may have subtly different meanings; for example, in French an équation is defined as containing one or more variables, while in English any equality is an equation.

Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

In mathematics, a unimodular matrixM is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse. Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The unimodular matrices of order n form a group, which is denoted $.$

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common.

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

In linear algebra, a convex cone is a subset of a vector space over an ordered field that is closed under linear combinations with positive coefficients.

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

A second-order cone program (SOCP) is a convex optimization problem of the form

The dual of a given linear program (LP) is another LP that is derived from the original LP in the following schematic way:

In mathematics a linear inequality is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality:. It shows the data which is not equal in graph form.

In mathematical optimization, the fundamental theorem of linear programming states, in a weak formulation, that the maxima and minima of a linear function over a convex polygonal region occur at the region's corners. Further, if an extreme value occurs at two corners, then it must also occur everywhere on the line segment between them.

Within computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly . Many such problems do admit fast approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.

In applied mathematics, Graver bases enable iterative solutions of linear and various nonlinear integer programming problems in polynomial time. They were introduced by Jack E. Graver. Their connection to the theory of Gröbner bases was discussed by Bernd Sturmfels. The algorithmic theory of Graver bases and its application to integer programming is described by Shmuel Onn.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of item to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

References

1 2 Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear Algebra and its Applications. 25: 191–196. doi: 10.1016/0024-3795(79)90018-1 .
1 2 Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.
↑ Schrijver, A. (1981). "On Total Dual Integrality". Linear Algebra and its Applications. 38: 27–32. doi: 10.1016/0024-3795(81)90005-7 .
↑ Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[gilesPulleyblank-1] 1 2 Giles, F.R.; W.R. Pulleyblank (1979). "Total Dual Integrality and Integer Polyhedra". Linear Algebra and its Applications. 25: 191–196. doi: 10.1016/0024-3795(79)90018-1 .

[EdmondsGiles-2] 1 2 Edmonds, J.; R. Giles (1977). "A min-max relation for submodular functions on graphs". Annals of Discrete Mathematics. 1: 185–204.

[3] Schrijver, A. (1981). "On Total Dual Integrality". Linear Algebra and its Applications. 38: 27–32. doi: 10.1016/0024-3795(81)90005-7 .

[4] Chekuri, C. "Combinatorial Optimization Lecture Notes" (PDF).