About: Total dual integrality

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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.

Property Value
dbo: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)
dbo:wikiPageID
  • 37974931 (xsd:integer)
dbo:wikiPageLength
  • 2451 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1024303441 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dct:subject
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)
rdfs:label
  • Total dual integrality (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License