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

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

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15http://dbpedia.org/resource/File:
n14http://portal.acm.org/
n11http://www.math.ca/cjm/v6/
n24https://global.dbpedia.org/id/
n17http://www.cs.uu.nl/research/techreps/repo/CS-1996/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-fahttp://fa.dbpedia.org/resource/
n18http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-nlhttp://nl.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Protein_design
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Approximation_algorithm
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Relaxation_(approximation)
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Cutting-plane_method
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Vertex_cover
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Integer_programming
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Interval_scheduling
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:List_of_named_matrices
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:List_of_numerical_analysis_topics
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Conditional_random_field
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Maximum_disjoint_set
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Frankl–Rödl_graph
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Branch_and_cut
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Branch_and_price
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Möbius_ladder
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Configuration_linear_program
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Feedback_arc_set
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Maximum_satisfiability_problem
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Linear_programming
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Linear_programming_decoding
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Linear_programming_relaxation
rdf:type
yago:Abstraction100002137 yago:PsychologicalFeature100023100 yago:Act100030358 yago:YagoPermanentlyLocatedEntity yago:Algorithm105847438 yago:WikicatAlgorithms yago:Event100029378 yago:Procedure101023820 yago:Rule105846932 yago:Activity100407535
rdfs:label
线性规划的松弛 LP-relaxatie LP-Relaxation Linear programming relaxation Relaxation continue
rdfs:comment
Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem derganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird. So ersetzt man z. B. Nebenbedingungen der Gestalt des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann. Die Methode wurde von Shmuel Agmon im Jahr 1954 beschrieben. En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Lors d'une optimisation linéaire en nombres entiers, la relaxation continue s'avère à la fois efficace et facile à mettre en œuvre. * Portail de l'analyse * Portail de l'informatique théorique In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form . The relaxation of the original integer program instead uses a collection of linear constraints In de wiskunde is LP-relaxatie de verandering van een lineaire- programmeringsprobleem met geheeltallige beperkingen door de eis van geheeltalligheid van de variabelen te laten vallen. Het toegelaten gebied kan hierdoor groter worden, waardoor het mogelijk gemakkelijker opgelost kan worden. Er moet dan later wel gecontroleerd worden of de verkregen optimale oplossing aan de oorspronkelijke eisen van geheeltalligheid voldoet, wat waarschijnlijk niet het geval zal zijn. Wel zal de gevonden oplossing gebruikt kunnen worden als een benaderende oplossing voor het oorspronkelijke geheeltallige probleem. 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。
foaf:depiction
n18:IP_polytope_with_LP_relaxation.svg
dct:subject
dbc:Relaxation_(approximation) dbc:Polyhedral_combinatorics dbc:Combinatorial_optimization dbc:Linear_programming
dbo:wikiPageID
6368430
dbo:wikiPageRevisionID
1032189211
dbo:wikiPageWikiLink
dbr:Approximation_algorithm dbr:Polyhedral_combinatorics dbc:Linear_programming dbr:Harmonic_number dbr:Convex_polytope dbr:NP-hard dbr:Convex_hull dbr:Set_(mathematics) dbr:Set_cover_problem dbr:Cutting-plane_method dbr:Facet_(mathematics) dbr:Graph_coloring dbr:Relaxation_technique_(mathematics) n15:IP_polytope_with_LP_relaxation.svg dbr:Fractional_coloring dbr:Polynomial_time dbr:Greedy_algorithm dbc:Polyhedral_combinatorics dbc:Relaxation_(approximation) dbr:Traveling_salesman_problem dbr:Indicator_variable dbr:Approximation_ratio dbr:Branch_and_cut dbr:Branch_and_bound dbr:Method_of_conditional_probabilities dbr:Mixed_integer_linear_programming dbr:Randomized_algorithm dbc:Combinatorial_optimization dbr:Linear_program dbr:Bulletin_of_the_American_Mathematical_Society dbr:Totally_unimodular dbr:Randomized_rounding dbr:0–1_integer_program dbr:Union_(set_theory)
dbo:wikiPageExternalLink
n11:p393 n11:p382 n14:citation.cfm%3Fid=313689 n17:1996-27.pdf
owl:sameAs
dbpedia-nl:LP-relaxatie yago-res:Linear_programming_relaxation dbpedia-fa:آزادسازی_در_برنامه‌ریزی_خطی wikidata:Q1512771 freebase:m.0g2s8y n24:WVWR dbpedia-zh:线性规划的松弛 dbpedia-fr:Relaxation_continue dbpedia-de:LP-Relaxation
dbp:wikiPageUsesTemplate
dbt:''a'',_''b''%7D,_%7B''b'',_''c''%7D,_%7B''a'',_''c'' dbt:Harvtxt dbt:Harv dbt:Citation
dbo:thumbnail
n18:IP_polytope_with_LP_relaxation.svg?width=300
dbo:abstract
In de wiskunde is LP-relaxatie de verandering van een lineaire- programmeringsprobleem met geheeltallige beperkingen door de eis van geheeltalligheid van de variabelen te laten vallen. Het toegelaten gebied kan hierdoor groter worden, waardoor het mogelijk gemakkelijker opgelost kan worden. Er moet dan later wel gecontroleerd worden of de verkregen optimale oplossing aan de oorspronkelijke eisen van geheeltalligheid voldoet, wat waarschijnlijk niet het geval zal zijn. Wel zal de gevonden oplossing gebruikt kunnen worden als een benaderende oplossing voor het oorspronkelijke geheeltallige probleem. Men vervangt bijvoorbeeld nevenvoorwaarden van de vorm in het oorspronkelijke geheeltallige programmeringsprobleem door de 'gerelaxeerde' beperkingen . De methode is beschreven door in 1954. Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem derganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird. So ersetzt man z. B. Nebenbedingungen der Gestalt des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen Das Problem („Programm“) lässt sich in der relaxierten Form mit Hilfe der linearen Optimierung lösen. Die so entstandene reelle Lösung erfüllt nur in Ausnahmefällen die Ganzzahligkeitsbedingungen des ursprünglichen Problems, mit ihrer Hilfe können jedoch Schlüsse über die Lösung des ursprünglichen Problems gezogen werden. Die Lösung des relaxierten Problems kann auch als Näherungslösung für einen Algorithmus zur ganzzahligen Optimierung verwendet werden. Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann. Die Methode wurde von Shmuel Agmon im Jahr 1954 beschrieben. Von einer Relaxation im Kontext eines Optimierungsproblems (z. B. Maximierung einer Zielfunktion) wird allgemein dann gesprochen, wenn die Menge zulässiger Lösungen vergrößert wird. Hierdurch wird der maximale Zielfunktionswert nicht verkleinert. En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode. Lors d'une optimisation linéaire en nombres entiers, la relaxation continue s'avère à la fois efficace et facile à mettre en œuvre. Dans un problème de minimisation, la relaxation continue fournit une borne inférieure de la solution du problème initial discret. En effet, la minimisation continue se fait sur un ensemble contenant l'ensemble des points admissibles du problème discret. Le ratio entre la solution optimale de la relaxation et du problème initial est appelé integrality gap. * Portail de l'analyse * Portail de l'informatique théorique In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form . The relaxation of the original integer program instead uses a collection of linear constraints The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program. 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。
prov:wasDerivedFrom
wikipedia-en:Linear_programming_relaxation?oldid=1032189211&ns=0
dbo:wikiPageLength
17161
foaf:isPrimaryTopicOf
wikipedia-en:Linear_programming_relaxation
Subject Item
dbr:Balanced_matrix
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Discrete_Mathematics_(journal)
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Fractional_coloring
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Graver_basis
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Knapsack_problem
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Penny_Haxell
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Set_cover_problem
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:In_Pursuit_of_the_Traveling_Salesman
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Stable_matching_polytope
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:Randomized_rounding
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
Subject Item
dbr:LP-relaxation
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
dbo:wikiPageRedirects
dbr:Linear_programming_relaxation
Subject Item
dbr:LP_relaxation
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
dbo:wikiPageRedirects
dbr:Linear_programming_relaxation
Subject Item
dbr:Integrality_gap
dbo:wikiPageWikiLink
dbr:Linear_programming_relaxation
dbo:wikiPageRedirects
dbr:Linear_programming_relaxation
Subject Item
wikipedia-en:Linear_programming_relaxation
foaf:primaryTopic
dbr:Linear_programming_relaxation