Loading…
A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space
Consider a set, A of n points in m-dimensional space. The convex hull of these points is a polytope, P , in R m . The frame, F , of these points in the set of extreme points of teh polytope P with F ⊆ A . The problem of identifying the frame plays a central role in optimization theory (redundancy in...
Saved in:
| Published in: | European journal of operational research 1996-07, Vol.92 (2), p.352-367 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3 |
| container_end_page | 367 |
| container_issue | 2 |
| container_start_page | 352 |
| container_title | European journal of operational research |
| container_volume | 92 |
| creator | Dulá, J.H. Helgason, R.V. |
| description | Consider a set,
A
of
n points in
m-dimensional space. The convex hull of these points is a polytope,
P
, in
R
m
. The
frame,
F
, of these points in the set of extreme points of teh polytope
P
with
F ⊆
A
. The problem of identifying the frame plays a central role in optimization theory (redundancy in linear programming and stochastic programming), economics (data envelopment analysis), computational geometry (facial decomposition of polytopes) and statistics (Gastwirth estimators). The standard approach for finding the elements of
F
consists of solving linear programs with
m rows and
n − 1 columns; one for each element of
A
, differing only in the right-hand side vectors. Although enhancements to reduce the total number of linear programs which must ultimately be solved as well as to reduce the number of columns in the technology matrix are known, the utility of this approach is severely limited by its laboriousness and computational demands. We introduce a new procedure also based on solving linear programs but with an important and distinguishing difference. The linear programs begin small and grow larger, but never have more columns than the number of extreme points of
P
. Experimental results indicate that the time to find the frame using the new procedure is between about one-third and two-thirds that of an enhanced implementation of the established method currently in use. |
| doi_str_mv | 10.1016/0377-2217(94)00366-1 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_204139325</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>0377221794003661</els_id><sourcerecordid>10056903</sourcerecordid><originalsourceid>FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3</originalsourceid><addsrcrecordid>eNp9UU2PFCEQJUYTx9V_4IF40kMrXw30xWSzWb-yiRc9EwaqHSbd0AI96_x76R2zR0keBa9eVYoHQq8peU8JlR8IV6pjjKq3g3hHCJeyo0_QjmrFOqkleYp2j5Ln6EUpR0II7Wm_Q_fXOMI9XnJy4NcMeEwZBw-xhvEc4i9cD43LdgacxoeLS_EEf_BhnaaNsngMMdSNnyZwNaS40UsKsRYcIp7XqQYfZoil5eyEy2IdvETPRjsVePUvXqGfn25_3Hzp7r5__npzfdc5IUXtBPXCOq1A-733jmrvBB0tkyBBc-Ucs2Tveq-0oFRb4bRsQucdgz0fleVX6M2lb3vh7xVKNce05jZGMYwIygfO-iYSF5HLqZQMo1lymG0-G0rM5rDZ7DObfWYQ5sFhQ1vZt0tZhgXcYw20dUwZijkZbgfWtnMDHQbZQmjYqKWB9-0klTnUuTX7eGkGzY1TgGyKCxDbr4TcbDU-hf9P8xdpwJ4w</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>204139325</pqid></control><display><type>article</type><title>A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Dulá, J.H. ; Helgason, R.V.</creator><creatorcontrib>Dulá, J.H. ; Helgason, R.V.</creatorcontrib><description>Consider a set,
A
of
n points in
m-dimensional space. The convex hull of these points is a polytope,
P
, in
R
m
. The
frame,
F
, of these points in the set of extreme points of teh polytope
P
with
F ⊆
A
. The problem of identifying the frame plays a central role in optimization theory (redundancy in linear programming and stochastic programming), economics (data envelopment analysis), computational geometry (facial decomposition of polytopes) and statistics (Gastwirth estimators). The standard approach for finding the elements of
F
consists of solving linear programs with
m rows and
n − 1 columns; one for each element of
A
, differing only in the right-hand side vectors. Although enhancements to reduce the total number of linear programs which must ultimately be solved as well as to reduce the number of columns in the technology matrix are known, the utility of this approach is severely limited by its laboriousness and computational demands. We introduce a new procedure also based on solving linear programs but with an important and distinguishing difference. The linear programs begin small and grow larger, but never have more columns than the number of extreme points of
P
. Experimental results indicate that the time to find the frame using the new procedure is between about one-third and two-thirds that of an enhanced implementation of the established method currently in use.</description><identifier>ISSN: 0377-2217</identifier><identifier>EISSN: 1872-6860</identifier><identifier>DOI: 10.1016/0377-2217(94)00366-1</identifier><identifier>CODEN: EJORDT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Convex hull problem ; Data envelopment analysis ; Frame ; Linear programming ; Operations research ; Problem solving ; Redundancy ; Studies</subject><ispartof>European journal of operational research, 1996-07, Vol.92 (2), p.352-367</ispartof><rights>1996</rights><rights>Copyright Elsevier Sequoia S.A. Jul 19, 1996</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3</citedby><cites>FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,777,781,27905,27906</link.rule.ids><backlink>$$Uhttp://econpapers.repec.org/article/eeeejores/v_3a92_3ay_3a1996_3ai_3a2_3ap_3a352-367.htm$$DView record in RePEc$$Hfree_for_read</backlink></links><search><creatorcontrib>Dulá, J.H.</creatorcontrib><creatorcontrib>Helgason, R.V.</creatorcontrib><title>A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space</title><title>European journal of operational research</title><description>Consider a set,
A
of
n points in
m-dimensional space. The convex hull of these points is a polytope,
P
, in
R
m
. The
frame,
F
, of these points in the set of extreme points of teh polytope
P
with
F ⊆
A
. The problem of identifying the frame plays a central role in optimization theory (redundancy in linear programming and stochastic programming), economics (data envelopment analysis), computational geometry (facial decomposition of polytopes) and statistics (Gastwirth estimators). The standard approach for finding the elements of
F
consists of solving linear programs with
m rows and
n − 1 columns; one for each element of
A
, differing only in the right-hand side vectors. Although enhancements to reduce the total number of linear programs which must ultimately be solved as well as to reduce the number of columns in the technology matrix are known, the utility of this approach is severely limited by its laboriousness and computational demands. We introduce a new procedure also based on solving linear programs but with an important and distinguishing difference. The linear programs begin small and grow larger, but never have more columns than the number of extreme points of
P
. Experimental results indicate that the time to find the frame using the new procedure is between about one-third and two-thirds that of an enhanced implementation of the established method currently in use.</description><subject>Convex hull problem</subject><subject>Data envelopment analysis</subject><subject>Frame</subject><subject>Linear programming</subject><subject>Operations research</subject><subject>Problem solving</subject><subject>Redundancy</subject><subject>Studies</subject><issn>0377-2217</issn><issn>1872-6860</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1996</creationdate><recordtype>article</recordtype><recordid>eNp9UU2PFCEQJUYTx9V_4IF40kMrXw30xWSzWb-yiRc9EwaqHSbd0AI96_x76R2zR0keBa9eVYoHQq8peU8JlR8IV6pjjKq3g3hHCJeyo0_QjmrFOqkleYp2j5Ln6EUpR0II7Wm_Q_fXOMI9XnJy4NcMeEwZBw-xhvEc4i9cD43LdgacxoeLS_EEf_BhnaaNsngMMdSNnyZwNaS40UsKsRYcIp7XqQYfZoil5eyEy2IdvETPRjsVePUvXqGfn25_3Hzp7r5__npzfdc5IUXtBPXCOq1A-733jmrvBB0tkyBBc-Ucs2Tveq-0oFRb4bRsQucdgz0fleVX6M2lb3vh7xVKNce05jZGMYwIygfO-iYSF5HLqZQMo1lymG0-G0rM5rDZ7DObfWYQ5sFhQ1vZt0tZhgXcYw20dUwZijkZbgfWtnMDHQbZQmjYqKWB9-0klTnUuTX7eGkGzY1TgGyKCxDbr4TcbDU-hf9P8xdpwJ4w</recordid><startdate>19960719</startdate><enddate>19960719</enddate><creator>Dulá, J.H.</creator><creator>Helgason, R.V.</creator><general>Elsevier B.V</general><general>Elsevier</general><general>Elsevier Sequoia S.A</general><scope>DKI</scope><scope>X2L</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19960719</creationdate><title>A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space</title><author>Dulá, J.H. ; Helgason, R.V.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1996</creationdate><topic>Convex hull problem</topic><topic>Data envelopment analysis</topic><topic>Frame</topic><topic>Linear programming</topic><topic>Operations research</topic><topic>Problem solving</topic><topic>Redundancy</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Dulá, J.H.</creatorcontrib><creatorcontrib>Helgason, R.V.</creatorcontrib><collection>RePEc IDEAS</collection><collection>RePEc</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>European journal of operational research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Dulá, J.H.</au><au>Helgason, R.V.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space</atitle><jtitle>European journal of operational research</jtitle><date>1996-07-19</date><risdate>1996</risdate><volume>92</volume><issue>2</issue><spage>352</spage><epage>367</epage><pages>352-367</pages><issn>0377-2217</issn><eissn>1872-6860</eissn><coden>EJORDT</coden><abstract>Consider a set,
A
of
n points in
m-dimensional space. The convex hull of these points is a polytope,
P
, in
R
m
. The
frame,
F
, of these points in the set of extreme points of teh polytope
P
with
F ⊆
A
. The problem of identifying the frame plays a central role in optimization theory (redundancy in linear programming and stochastic programming), economics (data envelopment analysis), computational geometry (facial decomposition of polytopes) and statistics (Gastwirth estimators). The standard approach for finding the elements of
F
consists of solving linear programs with
m rows and
n − 1 columns; one for each element of
A
, differing only in the right-hand side vectors. Although enhancements to reduce the total number of linear programs which must ultimately be solved as well as to reduce the number of columns in the technology matrix are known, the utility of this approach is severely limited by its laboriousness and computational demands. We introduce a new procedure also based on solving linear programs but with an important and distinguishing difference. The linear programs begin small and grow larger, but never have more columns than the number of extreme points of
P
. Experimental results indicate that the time to find the frame using the new procedure is between about one-third and two-thirds that of an enhanced implementation of the established method currently in use.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/0377-2217(94)00366-1</doi><tpages>16</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0377-2217 |
| ispartof | European journal of operational research, 1996-07, Vol.92 (2), p.352-367 |
| issn | 0377-2217 1872-6860 |
| language | eng |
| recordid | cdi_proquest_journals_204139325 |
| source | ScienceDirect Freedom Collection 2022-2024 |
| subjects | Convex hull problem Data envelopment analysis Frame Linear programming Operations research Problem solving Redundancy Studies |
| title | A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-20T13%3A58%3A56IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20new%20procedure%20for%20identifying%20the%20frame%20of%20the%20convex%20hull%20of%20a%20finite%20collection%20of%20points%20in%20multidimensional%20space&rft.jtitle=European%20journal%20of%20operational%20research&rft.au=Dul%C3%A1,%20J.H.&rft.date=1996-07-19&rft.volume=92&rft.issue=2&rft.spage=352&rft.epage=367&rft.pages=352-367&rft.issn=0377-2217&rft.eissn=1872-6860&rft.coden=EJORDT&rft_id=info:doi/10.1016/0377-2217(94)00366-1&rft_dat=%3Cproquest_cross%3E10056903%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c464t-41d4ac87e8dbddc18dc41fa26e6e837cc2a0bc5d784118a4c86dbdcdc2eb3f7a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=204139325&rft_id=info:pmid/&rfr_iscdi=true |