On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
Identifieur interne : 000964 ( Istex/Corpus ); précédent : 000963; suivant : 000965On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
Auteurs : Reiner Horst ; Jakob De Vries ; Nguyen V. ThoaiSource :
- Operations Research Letters [ 0167-6377 ] ; 1988.
Abstract
Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope P created from a given polytope P (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.
Url:
DOI: 10.1016/0167-6377(88)90071-5
Links to Exploration step
ISTEX:A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title><author><name sortKey="Horst, Reiner" sort="Horst, Reiner" uniqKey="Horst R" first="Reiner" last="Horst">Reiner Horst</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</mods:affiliation></affiliation></author><author><name sortKey="De Vries, Jakob" sort="De Vries, Jakob" uniqKey="De Vries J" first="Jakob" last="De Vries">Jakob De Vries</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</mods:affiliation></affiliation></author><author><name sortKey="Thoai, Nguyen V" sort="Thoai, Nguyen V" uniqKey="Thoai N" first="Nguyen V" last="Thoai">Nguyen V. Thoai</name><affiliation><mods:affiliation>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94</idno><date when="1988" year="1988">1988</date><idno type="doi">10.1016/0167-6377(88)90071-5</idno><idno type="url">https://api.istex.fr/document/A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000964</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000964</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title><author><name sortKey="Horst, Reiner" sort="Horst, Reiner" uniqKey="Horst R" first="Reiner" last="Horst">Reiner Horst</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</mods:affiliation></affiliation></author><author><name sortKey="De Vries, Jakob" sort="De Vries, Jakob" uniqKey="De Vries J" first="Jakob" last="De Vries">Jakob De Vries</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</mods:affiliation></affiliation></author><author><name sortKey="Thoai, Nguyen V" sort="Thoai, Nguyen V" uniqKey="Thoai N" first="Nguyen V" last="Thoai">Nguyen V. Thoai</name><affiliation><mods:affiliation>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Operations Research Letters</title><title level="j" type="abbrev">OPERES</title><idno type="ISSN">0167-6377</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1988">1988</date><biblScope unit="volume">7</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="85">85</biblScope><biblScope unit="page" to="90">90</biblScope></imprint><idno type="ISSN">0167-6377</idno></series><idno type="istex">A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94</idno><idno type="DOI">10.1016/0167-6377(88)90071-5</idno><idno type="PII">0167-6377(88)90071-5</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-6377</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope P created from a given polytope P (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>Reiner Horst</name><affiliations><json:string>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</json:string></affiliations></json:item><json:item><name>Jakob de Vries</name><affiliations><json:string>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</json:string></affiliations></json:item><json:item><name>Nguyen V Thoai</name><affiliations><json:string>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>mathematical programming</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>global optimization</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>cutting planes</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>redundant constraints</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>polytopes</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope P created from a given polytope P (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.</abstract><qualityIndicators><score>3.913</score><pdfVersion>1.2</pdfVersion><pdfPageSize>576 x 792 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>5</keywordCount><abstractCharCount>681</abstractCharCount><pdfWordCount>2593</pdfWordCount><pdfCharCount>13771</pdfCharCount><pdfPageCount>6</pdfPageCount><abstractWordCount>110</abstractWordCount></qualityIndicators><title>On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title><pii><json:string>0167-6377(88)90071-5</json:string></pii><refBibs><json:item><author><json:item><name>B.C Eaves</name></json:item><json:item><name>W.I Zangwill</name></json:item></author><host><volume>9</volume><pages><last>542</last><first>529</first></pages><author></author><title>SIAM J. Control</title></host><title>Generalized cutting plane algorithms</title></json:item><json:item><author><json:item><name>J Falk</name></json:item><json:item><name>K.R Hoffman</name></json:item></author><host><volume>1</volume><pages><last>259</last><first>251</first></pages><author></author><title>Math. Oper. Res.</title></host><title>A successive underestimation method for concave minimization problems</title></json:item><json:item><author><json:item><name>K.R Hoffman</name></json:item></author><host><volume>20</volume><pages><last>32</last><first>22</first></pages><author></author><title>Math. Programming</title></host><title>A method for globally minimizing concave functions over convex sets</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>T.H Matheis</name></json:item><json:item><name>D.S Rubin</name></json:item></author><host><volume>5</volume><pages><last>184</last><first>167</first></pages><author></author><title>Math. Oper. Res.</title></host><title>A survey and comparison of methods for finding all vertices of convex polyhedral sets</title></json:item><json:item><author><json:item><name>T.V Thieu</name></json:item><json:item><name>B.T Tam</name></json:item><json:item><name>V.T Ban</name></json:item></author><host><volume>8</volume><pages><last>40</last><first>21</first></pages><author></author><title>Acta Mathematica Vietnamica</title></host><title>An outer approximation method for flobally minimizing a concave function over a compact convex set</title></json:item><json:item><author><json:item><name>H Tuy</name></json:item></author><host><volume>8</volume><pages><last>34</last><first>3</first></pages><author></author><title>Acta Mathematica Vietnamica</title></host><title>On outer approximation methods for solving concave minimization problems</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>7</volume><pii><json:string>S0167-6377(00)X0150-2</json:string></pii><pages><last>90</last><first>85</first></pages><issn><json:string>0167-6377</json:string></issn><issue>2</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Operations Research Letters</title><publicationDate>1988</publicationDate></host><publicationDate>1988</publicationDate><copyrightDate>1988</copyrightDate><doi><json:string>10.1016/0167-6377(88)90071-5</json:string></doi><id>A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94</id><score>1.4457582</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1988</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title><author xml:id="author-1"><persName><forename type="first">Reiner</forename><surname>Horst</surname></persName><affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Jakob</forename><surname>de Vries</surname></persName><affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</affiliation></author><author xml:id="author-3"><persName><forename type="first">Nguyen V</forename><surname>Thoai</surname></persName><note type="biography">On leave at University of Trier as a fellow of the Alexander von Humboldt foundation.</note><affiliation>On leave at University of Trier as a fellow of the Alexander von Humboldt foundation.</affiliation><affiliation>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</affiliation></author></analytic><monogr><title level="j">Operations Research Letters</title><title level="j" type="abbrev">OPERES</title><idno type="pISSN">0167-6377</idno><idno type="PII">S0167-6377(00)X0150-2</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1988"></date><biblScope unit="volume">7</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="85">85</biblScope><biblScope unit="page" to="90">90</biblScope></imprint></monogr><idno type="istex">A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94</idno><idno type="DOI">10.1016/0167-6377(88)90071-5</idno><idno type="PII">0167-6377(88)90071-5</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1988</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope P created from a given polytope P (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>mathematical programming</term></item><item><term>global optimization</term></item><item><term>cutting planes</term></item><item><term>redundant constraints</term></item><item><term>polytopes</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1988-01-14">Modified</change><change when="1988">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>OPERES</jid><aid>88900715</aid><ce:pii>0167-6377(88)90071-5</ce:pii><ce:doi>10.1016/0167-6377(88)90071-5</ce:doi><ce:copyright type="unknown" year="1988"></ce:copyright></item-info><head><ce:title>On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</ce:title><ce:author-group><ce:author><ce:given-name>Reiner</ce:given-name><ce:surname>Horst</ce:surname></ce:author><ce:author><ce:given-name>Jakob</ce:given-name><ce:surname>de Vries</ce:surname></ce:author><ce:affiliation><ce:textfn>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</ce:textfn></ce:affiliation></ce:author-group><ce:author-group><ce:author><ce:given-name>Nguyen V</ce:given-name><ce:surname>Thoai</ce:surname><ce:cross-ref refid="FN1"><ce:sup>∗</ce:sup></ce:cross-ref></ce:author><ce:affiliation><ce:textfn>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</ce:textfn></ce:affiliation><ce:footnote id="FN1"><ce:label>∗</ce:label><ce:note-para>On leave at University of Trier as a fellow of the Alexander von Humboldt foundation.</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="11" month="6" year="1987"></ce:date-received><ce:date-revised day="14" month="1" year="1988"></ce:date-revised><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope <math altimg="si1.gif"><ovl type="bar">P</ovl></math> created from a given polytope <ce:italic>P</ce:italic> (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>mathematical programming</ce:text></ce:keyword><ce:keyword><ce:text>global optimization</ce:text></ce:keyword><ce:keyword><ce:text>cutting planes</ce:text></ce:keyword><ce:keyword><ce:text>redundant constraints</ce:text></ce:keyword><ce:keyword><ce:text>polytopes</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>On finding new vertices and redundant constraints in cutting plane algorithms for global optimization</title></titleInfo><name type="personal"><namePart type="given">Reiner</namePart><namePart type="family">Horst</namePart><affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Jakob</namePart><namePart type="family">de Vries</namePart><affiliation>Universität Trier, Fachbereich IV - Mathematik, Postfach 3825 D - 5500 Trier, Fed. Rep. Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Nguyen V</namePart><namePart type="family">Thoai</namePart><affiliation>Institute of Mathematics, PO Box 631, Hanoi, Vietnam</affiliation><description>On leave at University of Trier as a fellow of the Alexander von Humboldt foundation.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1988</dateIssued><dateModified encoding="w3cdtf">1988-01-14</dateModified><copyrightDate encoding="w3cdtf">1988</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Cutting plane algorithms belong to the basic tools for solving certain classes of global multiextremal optimization problems such as the global minimization of a concave function on a compact, convex set. The computationally most expensive part of these algorithms consists in the calculation of all new vertices of the polytope P created from a given polytope P (with known vertex set) by a cut. We first present a new procedure for solving this subproblem that allows to handle degeneracy and give a theoretical and numerical comparison with existing approaches. Then we show how redundant constraints can be eliminated by a criterion based on the known vertex set of a polytope.</abstract><subject><genre>Keywords</genre><topic>mathematical programming</topic><topic>global optimization</topic><topic>cutting planes</topic><topic>redundant constraints</topic><topic>polytopes</topic></subject><relatedItem type="host"><titleInfo><title>Operations Research Letters</title></titleInfo><titleInfo type="abbreviated"><title>OPERES</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">198804</dateIssued></originInfo><identifier type="ISSN">0167-6377</identifier><identifier type="PII">S0167-6377(00)X0150-2</identifier><part><date>198804</date><detail type="volume"><number>7</number><caption>vol.</caption></detail><detail type="issue"><number>2</number><caption>no.</caption></detail><extent unit="issue pages"><start>61</start><end>102</end></extent><extent unit="pages"><start>85</start><end>90</end></extent></part></relatedItem><identifier type="istex">A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94</identifier><identifier type="DOI">10.1016/0167-6377(88)90071-5</identifier><identifier type="PII">0167-6377(88)90071-5</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000964 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000964 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:A5664C1BAFBEB551B6312DD4773CCD0B3E7D4C94
|texte= On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
}}
| This area was generated with Dilib version V0.6.31. |  |