About: dbpedia-fr:Branch_and_cut     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : fr.dbpedia.org associated with source document(s)

AttributesValues
rdfs:label
  • Branch and cut (fr)
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. (fr)
sameAs
Wikipage page ID
Wikipage revision ID
dbo:wikiPageWikiLink
page length (characters) of wiki page
dct:subject
prop-fr:wikiPageUsesTemplate
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
has 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. (fr)
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of
Faceted Search & Find service v1.16.111 as of Oct 19 2022


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 10 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software