This HTML5 document contains 20 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n9	https://global.dbpedia.org/id/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
prov	http://www.w3.org/ns/prov#
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Total_dual_integrality

rdfs:label

Total dual integrality

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.

dcterms:subject

dbc:Linear_programming

dbo:wikiPageID

37974931

dbo:wikiPageRevisionID

1024303441

dbo:wikiPageWikiLink

dbr:Integral_polyhedron dbr:Linear_programming dbr:Simplex_algorithm dbc:Linear_programming dbr:Integer_programming dbr:Mathematical_optimization dbr:Unimodular_matrix

owl:sameAs

freebase:m.0pb607d n9:4wN41 wikidata:Q7828108

dbp:wikiPageUsesTemplate

dbt:Reflist

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.

prov:wasDerivedFrom

wikipedia-en:Total_dual_integrality?oldid=1024303441&ns=0

dbo:wikiPageLength

2451

foaf:isPrimaryTopicOf

wikipedia-en:Total_dual_integrality