Linear programming relaxation (original) (raw)
在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。
| Property | Value |
|---|---|
| dbo:abstract | 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. (de) 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. (en) 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 (fr) 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. (nl) 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/IP_polytope_with_LP_relaxation.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.uu.nl/research/techreps/repo/CS-1996/1996-27.pdf http://www.math.ca/cjm/v6/p382 http://www.math.ca/cjm/v6/p393 http://portal.acm.org/citation.cfm%3Fid=313689 |
| dbo:wikiPageID | 6368430 (xsd:integer) |
| dbo:wikiPageLength | 17161 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032189211 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Method_of_conditional_probabilities dbr:Totally_unimodular dbr:Branch_and_bound dbr:Approximation_algorithm dbr:Cutting-plane_method dbr:0–1_integer_program dbc:Combinatorial_optimization dbr:Graph_coloring dbr:Branch_and_cut dbr:NP-hard dbr:Convex_hull dbr:Convex_polytope dbc:Relaxation_(approximation) dbc:Polyhedral_combinatorics dbr:Fractional_coloring dbr:Harmonic_number dbc:Linear_programming dbr:Bulletin_of_the_American_Mathematical_Society dbr:Polyhedral_combinatorics dbr:Greedy_algorithm dbr:Polynomial_time dbr:Approximation_ratio dbr:Facet_(mathematics) dbr:Randomized_algorithm dbr:Set_(mathematics) dbr:Set_cover_problem dbr:Union_(set_theory) dbr:Randomized_rounding dbr:Mixed_integer_linear_programming dbr:Linear_program dbr:Traveling_salesman_problem dbr:Indicator_variable dbr:Relaxation_technique_(mathematics) dbr:File:IP_polytope_with_LP_relaxation.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:''a'',_''b''},_{''b'',_''c''},_{''a'',_''c'' |
| dct:subject | dbc:Combinatorial_optimization dbc:Relaxation_(approximation) dbc:Polyhedral_combinatorics dbc:Linear_programming |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | 在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。 (zh) 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. (de) 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 (en) 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 (fr) 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. (nl) |
| rdfs:label | LP-Relaxation (de) Relaxation continue (fr) Linear programming relaxation (en) LP-relaxatie (nl) 线性规划的松弛 (zh) |
| owl:sameAs | freebase:Linear programming relaxation yago-res:Linear programming relaxation wikidata:Linear programming relaxation dbpedia-de:Linear programming relaxation dbpedia-fa:Linear programming relaxation dbpedia-fr:Linear programming relaxation dbpedia-nl:Linear programming relaxation dbpedia-zh:Linear programming relaxation https://global.dbpedia.org/id/WVWR |
| prov:wasDerivedFrom | wikipedia-en:Linear_programming_relaxation?oldid=1032189211&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/IP_polytope_with_LP_relaxation.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Linear_programming_relaxation |
| is dbo:wikiPageRedirects of | dbr:LP-relaxation dbr:LP_relaxation dbr:Integrality_gap |
| is dbo:wikiPageWikiLink of | dbr:Protein_design dbr:Approximation_algorithm dbr:Relaxation_(approximation) dbr:Cutting-plane_method dbr:Vertex_cover dbr:Integer_programming dbr:Interval_scheduling dbr:List_of_named_matrices dbr:List_of_numerical_analysis_topics dbr:Conditional_random_field dbr:Maximum_disjoint_set dbr:Frankl–Rödl_graph dbr:Branch_and_cut dbr:Branch_and_price dbr:Möbius_ladder dbr:Configuration_linear_program dbr:Feedback_arc_set dbr:Maximum_satisfiability_problem dbr:Linear_programming dbr:Linear_programming_decoding dbr:Balanced_matrix dbr:Discrete_Mathematics_(journal) dbr:Fractional_coloring dbr:Graver_basis dbr:Knapsack_problem dbr:Penny_Haxell dbr:Set_cover_problem dbr:In_Pursuit_of_the_Traveling_Salesman dbr:Stable_matching_polytope dbr:Randomized_rounding dbr:LP-relaxation dbr:LP_relaxation dbr:Integrality_gap |
| is foaf:primaryTopic of | wikipedia-en:Linear_programming_relaxation |
