This HTML5 document contains 32 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/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-kohttp://ko.dbpedia.org/resource/
n15http://g.co/kg/m/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n13http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n18http://ma-graph.org/entity/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Branch_and_cut
rdfs:label
Branch and cut
rdfs:comment
Branch and cut est une méthode d'optimisation combinatoire pour résoudre des problèmes d'optimisation linéaire en nombres entiers. Cette méthode utilise la méthode de séparation et évaluation et la méthode des plans sécants.
owl:sameAs
dbr:Branch_and_cut wikidata:Q498566 dbpedia-fa:شاخه_و_برش n15:090g6v dbpedia-de:Branch-and-Cut n18:50797617 dbpedia-zh:分支切割法 dbpedia-ko:분기_절단법
dbo:wikiPageID
4154430
dbo:wikiPageRevisionID
167672179
dbo:wikiPageWikiLink
dbpedia-fr:Algorithme_du_simplexe dbpedia-fr:Méthode_des_plans_sécants dbpedia-fr:Optimisation_combinatoire dbpedia-fr:Relaxation_continue category-fr:Algorithmique dbpedia-fr:Optimisation_linéaire dbpedia-fr:Optimisation_linéaire_en_nombres_entiers dbpedia-fr:Partie_entière_et_partie_fractionnaire dbpedia-fr:Séparation_et_évaluation category-fr:Optimisation_combinatoire
dbo:wikiPageLength
2020
dct:subject
category-fr:Algorithmique category-fr:Optimisation_combinatoire
prop-fr:wikiPageUsesTemplate
n13:Références n13:Ébauche n13:Portail n13:Langue_du_titre
prov:wasDerivedFrom
wikipedia-fr:Branch_and_cut?oldid=167672179&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:Branch_and_cut
dbo:abstract
Branch and cut est une méthode d'optimisation combinatoire pour résoudre des problèmes d'optimisation linéaire en nombres entiers. Cette méthode utilise la méthode de séparation et évaluation et la méthode des plans sécants. Le principe est de résoudre la relaxation continue du programme linéaire en nombres entiers à l'aide de l'algorithme du simplexe. Lorsqu'une solution optimale est trouvée, et que l'une des variables qu'on souhaite entières a une valeur non entière, on utilise un algorithme de plan sécant pour trouver une contrainte linéaire satisfaite par toutes les valeurs entières de la solution mais violée par la valeur fractionnaire. Si une telle contrainte est trouvée, alors elle est ajoutée au programme linéaire de sorte que la résolution de ce programme donne une solution avec moins de valeurs non entières. On répète ce procédé jusqu'à ce qu'une solution entière soit trouvée (qui est alors optimale) ou jusqu'à ce qu'aucun plan sécant ne puisse être trouvé. À ce moment, la partie séparation et évaluation de l'algorithme commence. Le problème est scindé en deux sous-problèmes, l'un en rajoutant la contrainte que la variable est supérieure ou égale à la partie entière par excès de la solution intermédiaire, et l'autre en rajoutant la contrainte que la variable est inférieure ou égale à sa partie entière usuelle (par défaut). Ces deux nouveaux programmes linéaires sont résolus avec l'algorithme du simplexe et on itère la procédure présentée précédemment.