Triangular Factorization and Generalized Upper Bounding Techniques

We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used f...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1977-01, Vol.25 (1), p.89-99
Main Authors: Kallio, Markku, Porteus, Evan L
Format: Article
Language:English
Subjects:
Factorization
Linear programming
Mathematical procedures
Research universities
Simplex method
Staircases
Studies
Citations: 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-c306t-9b463b8a900308cd8cb59709ea1f5d59ce97bb71279a195ff0e78870a940e0083
cites
container_end_page 99
container_issue 1
container_start_page 89
container_title Operations research
container_volume 25
creator Kallio, Markku
Porteus, Evan L
description We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.
doi_str_mv 10.1287/opre.25.1.89
format article
fullrecord <record><control><sourceid>jstor_infor</sourceid><recordid>TN_cdi_jstor_primary_169550</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>169550</jstor_id><sourcerecordid>169550</sourcerecordid><originalsourceid>FETCH-LOGICAL-c306t-9b463b8a900308cd8cb59709ea1f5d59ce97bb71279a195ff0e78870a940e0083</originalsourceid><addsrcrecordid>eNqFkL1PwzAQxS0EEqWwsbFEICZIOCdxbI-0ooBUiaWV2CwncVpXrRPsRIj-9TgKHxNiuuH97r27h9A5hgjHjN7VjVVRTCIcMX6ARpjEWUjSLDlEI4AEwiRLX4_RiXMbAOAkIyM0WVgtzarbShvMZNHWVu9lq2sTSFMGj8ooK7d6r8pg2TTKBpO6M6U2q2ChirXRb51yp-ioklunzr7mGC1nD4vpUzh_eXye3s_DIoGsDXnuL8mZ5P0prChZkRNOgSuJK1ISXihO85zimHKJOakqUJQxCpKnoABYMkaXg29j6z63FZu6s8ZHihhzTFL_noeu_oJw4oNpllLw1O1AFbZ2zqpKNFbvpP0QGERfpeirFDERWDDu8YsB3zhf0C-bcUJ6s5tB1aaq7c7953U90Gu9Wr9rr3yv9Zj74T4BpwSLTg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1303076470</pqid></control><display><type>article</type><title>Triangular Factorization and Generalized Upper Bounding Techniques</title><source>Informs</source><source>JSTOR Archival Journals and Primary Sources Collection</source><source>BSC - Ebsco (Business Source Ultimate)</source><creator>Kallio, Markku ; Porteus, Evan L</creator><creatorcontrib>Kallio, Markku ; Porteus, Evan L</creatorcontrib><description>We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.</description><identifier>ISSN: 0030-364X</identifier><identifier>EISSN: 1526-5463</identifier><identifier>DOI: 10.1287/opre.25.1.89</identifier><identifier>CODEN: OPREAI</identifier><language>eng</language><publisher>Baltimore, Md: INFORMS</publisher><subject>Factorization ; Linear programming ; Mathematical procedures ; Research universities ; Simplex method ; Staircases ; Studies</subject><ispartof>Operations research, 1977-01, Vol.25 (1), p.89-99</ispartof><rights>Copyright 1977 The Operations Research Society of America</rights><rights>Copyright Institute for Operations Research and the Management Sciences JAN./FEB. 1977</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c306t-9b463b8a900308cd8cb59709ea1f5d59ce97bb71279a195ff0e78870a940e0083</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/169550$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://pubsonline.informs.org/doi/full/10.1287/opre.25.1.89$$EHTML$$P50$$Ginforms$$H</linktohtml><link.rule.ids>314,780,784,3692,27924,27925,58238,58471,62616</link.rule.ids></links><search><creatorcontrib>Kallio, Markku</creatorcontrib><creatorcontrib>Porteus, Evan L</creatorcontrib><title>Triangular Factorization and Generalized Upper Bounding Techniques</title><title>Operations research</title><description>We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.</description><subject>Factorization</subject><subject>Linear programming</subject><subject>Mathematical procedures</subject><subject>Research universities</subject><subject>Simplex method</subject><subject>Staircases</subject><subject>Studies</subject><issn>0030-364X</issn><issn>1526-5463</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1977</creationdate><recordtype>article</recordtype><recordid>eNqFkL1PwzAQxS0EEqWwsbFEICZIOCdxbI-0ooBUiaWV2CwncVpXrRPsRIj-9TgKHxNiuuH97r27h9A5hgjHjN7VjVVRTCIcMX6ARpjEWUjSLDlEI4AEwiRLX4_RiXMbAOAkIyM0WVgtzarbShvMZNHWVu9lq2sTSFMGj8ooK7d6r8pg2TTKBpO6M6U2q2ChirXRb51yp-ioklunzr7mGC1nD4vpUzh_eXye3s_DIoGsDXnuL8mZ5P0prChZkRNOgSuJK1ISXihO85zimHKJOakqUJQxCpKnoABYMkaXg29j6z63FZu6s8ZHihhzTFL_noeu_oJw4oNpllLw1O1AFbZ2zqpKNFbvpP0QGERfpeirFDERWDDu8YsB3zhf0C-bcUJ6s5tB1aaq7c7953U90Gu9Wr9rr3yv9Zj74T4BpwSLTg</recordid><startdate>19770101</startdate><enddate>19770101</enddate><creator>Kallio, Markku</creator><creator>Porteus, Evan L</creator><general>INFORMS</general><general>Operations Research Society of America</general><general>Institute for Operations Research and the Management Sciences</general><scope>AAYXX</scope><scope>CITATION</scope><scope>HJHVS</scope><scope>IBDFT</scope><scope>K30</scope><scope>PAAUG</scope><scope>PAWHS</scope><scope>PAWZZ</scope><scope>PAXOH</scope><scope>PBHAV</scope><scope>PBQSW</scope><scope>PBYQZ</scope><scope>PCIWU</scope><scope>PCMID</scope><scope>PCZJX</scope><scope>PDGRG</scope><scope>PDWWI</scope><scope>PETMR</scope><scope>PFVGT</scope><scope>PGXDX</scope><scope>PIHIL</scope><scope>PISVA</scope><scope>PJCTQ</scope><scope>PJTMS</scope><scope>PLCHJ</scope><scope>PMHAD</scope><scope>PNQDJ</scope><scope>POUND</scope><scope>PPLAD</scope><scope>PQAPC</scope><scope>PQCAN</scope><scope>PQCMW</scope><scope>PQEME</scope><scope>PQHKH</scope><scope>PQMID</scope><scope>PQNCT</scope><scope>PQNET</scope><scope>PQSCT</scope><scope>PQSET</scope><scope>PSVJG</scope><scope>PVMQY</scope><scope>PZGFC</scope><scope>JQ2</scope><scope>K9.</scope></search><sort><creationdate>19770101</creationdate><title>Triangular Factorization and Generalized Upper Bounding Techniques</title><author>Kallio, Markku ; Porteus, Evan L</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c306t-9b463b8a900308cd8cb59709ea1f5d59ce97bb71279a195ff0e78870a940e0083</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1977</creationdate><topic>Factorization</topic><topic>Linear programming</topic><topic>Mathematical procedures</topic><topic>Research universities</topic><topic>Simplex method</topic><topic>Staircases</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kallio, Markku</creatorcontrib><creatorcontrib>Porteus, Evan L</creatorcontrib><collection>CrossRef</collection><collection>Periodicals Index Online Segment 19</collection><collection>Periodicals Index Online Segment 27</collection><collection>Periodicals Index Online</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - West</collection><collection>Primary Sources Access (Plan D) - International</collection><collection>Primary Sources Access &amp; Build (Plan A) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Midwest</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Northeast</collection><collection>Primary Sources Access (Plan D) - Southeast</collection><collection>Primary Sources Access (Plan D) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Southeast</collection><collection>Primary Sources Access (Plan D) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - UK / I</collection><collection>Primary Sources Access (Plan D) - Canada</collection><collection>Primary Sources Access (Plan D) - EMEALA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - International</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - International</collection><collection>Primary Sources Access (Plan D) - West</collection><collection>Periodicals Index Online Segments 1-50</collection><collection>Primary Sources Access (Plan D) - APAC</collection><collection>Primary Sources Access (Plan D) - Midwest</collection><collection>Primary Sources Access (Plan D) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Canada</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - EMEALA</collection><collection>Primary Sources Access &amp; Build (Plan A) - APAC</collection><collection>Primary Sources Access &amp; Build (Plan A) - Canada</collection><collection>Primary Sources Access &amp; Build (Plan A) - West</collection><collection>Primary Sources Access &amp; Build (Plan A) - EMEALA</collection><collection>Primary Sources Access (Plan D) - Northeast</collection><collection>Primary Sources Access &amp; Build (Plan A) - Midwest</collection><collection>Primary Sources Access &amp; Build (Plan A) - North Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - Northeast</collection><collection>Primary Sources Access &amp; Build (Plan A) - South Central</collection><collection>Primary Sources Access &amp; Build (Plan A) - Southeast</collection><collection>Primary Sources Access (Plan D) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - APAC</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - MEA</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Health &amp; Medical Complete (Alumni)</collection><jtitle>Operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kallio, Markku</au><au>Porteus, Evan L</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Triangular Factorization and Generalized Upper Bounding Techniques</atitle><jtitle>Operations research</jtitle><date>1977-01-01</date><risdate>1977</risdate><volume>25</volume><issue>1</issue><spage>89</spage><epage>99</epage><pages>89-99</pages><issn>0030-364X</issn><eissn>1526-5463</eissn><coden>OPREAI</coden><abstract>We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.</abstract><cop>Baltimore, Md</cop><pub>INFORMS</pub><doi>10.1287/opre.25.1.89</doi><tpages>11</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0030-364X
ispartof Operations research, 1977-01, Vol.25 (1), p.89-99
issn 0030-364X
1526-5463
language eng
recordid cdi_jstor_primary_169550
source Informs; JSTOR Archival Journals and Primary Sources Collection; BSC - Ebsco (Business Source Ultimate)
subjects Factorization
Linear programming
Mathematical procedures
Research universities
Simplex method
Staircases
Studies
title Triangular Factorization and Generalized Upper Bounding Techniques
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T21%3A13%3A12IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_infor&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Triangular%20Factorization%20and%20Generalized%20Upper%20Bounding%20Techniques&rft.jtitle=Operations%20research&rft.au=Kallio,%20Markku&rft.date=1977-01-01&rft.volume=25&rft.issue=1&rft.spage=89&rft.epage=99&rft.pages=89-99&rft.issn=0030-364X&rft.eissn=1526-5463&rft.coden=OPREAI&rft_id=info:doi/10.1287/opre.25.1.89&rft_dat=%3Cjstor_infor%3E169550%3C/jstor_infor%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c306t-9b463b8a900308cd8cb59709ea1f5d59ce97bb71279a195ff0e78870a940e0083%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1303076470&rft_id=info:pmid/&rft_jstor_id=169550&rfr_iscdi=true