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 , where and are rational, is called totally dual integral (TDI) if for any such that there is a feasible, bounded solution to the linear program there is an integer optimal dual solution. Note that TDI is a weaker sufficient condition for integrality than total unimodularity.
Attributes | Values |
---|
rdfs:label
| - Total dual integrality (en)
|
rdfs:comment
| - 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 , where and are rational, is called totally dual integral (TDI) if for any such that there is a feasible, bounded solution to the linear program there is an integer optimal dual solution. Note that TDI is a weaker sufficient condition for integrality than total unimodularity. (en)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - 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 , where and are rational, is called totally dual integral (TDI) if for any such that there is a feasible, bounded solution to the linear program there is an integer optimal dual solution. Edmonds and Giles showed that if a polyhedron is the solution set of a TDI system , where has all integer entries, then every vertex of 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 showed that if is a polytope whose vertices are all integer valued, then is the solution set of some TDI system , where is integer valued. Note that TDI is a weaker sufficient condition for integrality than total unimodularity. (en)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |