{"entities":{"Q1174842":{"pageid":1185591,"ns":120,"title":"Item:Q1174842","lastrevid":70047828,"modified":"2026-04-13T12:05:10Z","type":"item","id":"Q1174842","labels":{"en":{"language":"en","value":"An optimal-basis identification technique for interior-point linear programming algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 9513"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$261DF742-E017-4044-8B16-96B80A1F4077","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61429fde6376e83de599db88f775a95982620a2d","datavalue":{"value":{"text":"An optimal-basis identification technique for interior-point linear programming algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174842$9F9E2EC2-B665-48F1-9526-3BFFD21CA302","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"123329847bb876a3f4d02a9ad580ac1acfb9aa0b","datavalue":{"value":"0737.65052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$6C25AD44-07F2-46ED-BEB9-3C315C88AD59","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"02934f642648b9023be022a72813dc62dff0d3af","datavalue":{"value":"10.1016/0024-3795(91)90281-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$7920A879-07E9-408C-B697-FA0C8EC3883C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7666952584a8ff6efd0842588cf64b1071ec0d33","datavalue":{"value":{"entity-type":"item","numeric-id":520188,"id":"Q520188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$A1D248D1-7F60-41CF-A9B2-E8F926B21B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c569ac5f3b2dec61f8c32df80bd77a482bd61ef4","datavalue":{"value":{"entity-type":"item","numeric-id":1297862,"id":"Q1297862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$E9673C6B-74A3-4897-B691-EB4C6FEB432B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$66B21A9E-A7BA-4452-BEA8-F1362FFAF9F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1174842$9C74C7B2-055E-4E68-8948-8F936FCB08BC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f663d374e2ead10e8236a7ea490ea5e6de055b74","datavalue":{"value":"This paper is concerned with a method for identifying an optimal basis for linear programming problems in the setting of interior-point methods. Theoretically an interior-point algorithm with integer data can be terminated when the iterate is sufficiently close to an optimal solution and then is rounded to the nearby optimal solution.   A reliable technique for identifying optimal basic and nonbasic variables in the early stage of an interior-point iterative process is developed, so that either an early termination or a reduction in problem size can be obtained and the efficiency of interior-point methods can be improved. To each iterate \\(x^ k\\) generated by an interior-point algorithm, an indicator vector \\(q^ k\\) is associated. The vector \\(q^ k\\) has the property that if \\(x^ k\\) converges to a nondegenerate vertex \\(x^*\\), then \\(q^ k\\) converges to the \\(0-1\\) vector \\(\\hbox{sign}(x^*)\\). The convergence of \\(q^ k\\) is quadratically faster than that of \\(x^ k\\) in the sense that \\(\\| q^ k-q^*\\|=O(\\| x^ k-x^*\\|^ 2)\\).   This clear-cut separation and rapid convergence allows one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. Under suitable assumptions, this method can be extended to handle certain types of degeneracy.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174842$66C2D6F7-A836-43DA-91C8-52D9B8596B13","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$55257CC6-7170-4F49-879A-87626C3F4BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$4B9D9C8B-D346-4B14-9119-3706E730B252","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46c0ce59c28f11ed0feeca0461fca16ece51b610","datavalue":{"value":"9513","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$C05CA0F6-5389-4E8E-A483-2D1119D76C5C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6cb9fd9fc202b3d1144fad25d898e0501add4bc","datavalue":{"value":"optimal basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174842$8FB96373-BA17-41C3-A735-F6ED00FCD81A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174842$A65F31EC-D3E2-41DD-88C3-2CD54A7C4B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3db49cf982077bb5fd20c5a1253284bdc42ab42b","datavalue":{"value":"interior-point methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174842$2E2BC6B7-0C98-4CCC-A781-5AA799BEA166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ee0109af41ad406ecd743518061baaa9e5e3ff","datavalue":{"value":"convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174842$8F525258-4227-46A7-9B47-5E870C93AC07","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a075ab23da9dc44ed4d008dc8701efc81a0b03c","datavalue":{"value":{"entity-type":"item","numeric-id":425327,"id":"Q425327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$7141A78D-EF3C-4CC6-AA3E-7CA0CF177C2F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$A85E753C-56D6-48A2-B7D8-0F8FA4B00D36","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7bc2e01a25612f93d1577e4f6e02544a598bc603","datavalue":{"value":"Q114852068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174842$91AE2008-CBB6-44A9-B895-2B218D674B7A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f010c61a9c8e0b102af07c8aa50cfec862982a96","datavalue":{"value":{"entity-type":"item","numeric-id":1824551,"id":"Q1824551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$157DF43F-ADE7-4254-AB85-36FC8BEB62E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caf60e5f4990c7a0cd6e5dba9aa6644993544836","datavalue":{"value":{"entity-type":"item","numeric-id":911987,"id":"Q911987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$503B891B-52E3-435C-8BA2-CAF4CAC4FC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c633d9447e5d986230e2957316f8249514ca99d","datavalue":{"value":{"entity-type":"item","numeric-id":3030578,"id":"Q3030578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$0BC44957-A92F-46A6-BBDD-B316CDC50DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d4a4f4dd932bd775f3d25a9110ed67c05d2f39a","datavalue":{"value":{"entity-type":"item","numeric-id":1094330,"id":"Q1094330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$1FB28C64-81D4-4ED7-BAD9-D9B657A23BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6d1ec9843c65861c97c28bde17d5f7b4cd3ee00","datavalue":{"value":{"entity-type":"item","numeric-id":5583564,"id":"Q5583564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$C1A85A82-BA41-4D87-8043-FCD3A78E0EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66828504eeffda82e9ae408bb909d11a3036a9d5","datavalue":{"value":{"entity-type":"item","numeric-id":3975042,"id":"Q3975042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$DF0D691D-E2EB-4C00-97D3-FAD99FA28774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$B6C1C660-4374-4513-AFCD-FA5745300342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"943374b6c837e7f0bc930cf423d337e38053cf8e","datavalue":{"value":{"entity-type":"item","numeric-id":1113799,"id":"Q1113799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$7481A25C-634D-4033-96BB-FC78E71C372B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02a7afaa43720bcf86b29d1d0d8112e49edf9bd","datavalue":{"value":{"entity-type":"item","numeric-id":3491304,"id":"Q3491304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$2702096D-60B5-4F6F-B06B-B8FA4D94A67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f914d518973935babf8343eb8de19f4a46a36a","datavalue":{"value":{"entity-type":"item","numeric-id":1092808,"id":"Q1092808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$720582F8-3007-49AA-A66B-F58016B7BAD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fcd1ee8ac759d0b53271ab98fbce055d727d780","datavalue":{"value":{"entity-type":"item","numeric-id":5652137,"id":"Q5652137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$4EF71BDA-2394-4096-8AB7-EDB41DFFCE13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5847947913b451f28c5d9e5a81afcdb6bf47a6f7","datavalue":{"value":{"entity-type":"item","numeric-id":3818123,"id":"Q3818123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$B91088BF-3324-432C-83D9-3E641E997AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b365497a35d2bc4f523f5dc7d8ba065391e6222","datavalue":{"value":{"entity-type":"item","numeric-id":1090601,"id":"Q1090601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$6444F4AC-009D-4BAF-97F4-9AFB1C1335D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab237fd832a455377a602e00fd5500bf0ebec557","datavalue":{"value":{"entity-type":"item","numeric-id":3664841,"id":"Q3664841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$792F1540-4071-4863-BD63-8A06D677AB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a975d39735d0d10d92ac745a75752a43e0af022","datavalue":{"value":{"entity-type":"item","numeric-id":581231,"id":"Q581231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$3CCE94C1-4340-4E8F-879E-A24E5C85357D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c1a5fe61529ded0932202d29677b531990fe53","datavalue":{"value":{"entity-type":"item","numeric-id":3780756,"id":"Q3780756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$869A5BE1-354D-4994-B2FB-6FAC5314014F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbe1f73eb871a15c847e3e052d2720d071111f42","datavalue":{"value":{"entity-type":"item","numeric-id":1813834,"id":"Q1813834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174842$2D20056F-6550-4833-A040-4909BA770A7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88e5fe36625908ac8c2221047d1e9f2fd557f3af","datavalue":{"value":{"entity-type":"item","numeric-id":4427366,"id":"Q4427366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edc8ffad627db26c7a28c7dc8c9ef9fccac032c3","datavalue":{"value":{"amount":"+0.8519974946975708","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174842$40A2EFAC-9CDD-4B20-9512-10428F1131E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a325776b324a253cf247837610f4685582267d78","datavalue":{"value":{"entity-type":"item","numeric-id":1915926,"id":"Q1915926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b628b9bd9f37cfc2dca0f0acac8ced561415e0f4","datavalue":{"value":{"amount":"+0.8274715542793274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174842$929B73F9-9C60-412A-9343-B559FA828D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8668ce9fc941c3960fce37addb25deaa303bce0","datavalue":{"value":{"entity-type":"item","numeric-id":1342078,"id":"Q1342078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e0af8ea5994ba1330c3dd86aa426d3007844abc","datavalue":{"value":{"amount":"+0.8198122382164001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174842$27E78A77-4833-40EC-A18A-006958238B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fba30de7ad568fa3a46e8211c8dd3f2363205f28","datavalue":{"value":{"entity-type":"item","numeric-id":3484625,"id":"Q3484625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"607f48421f3dcc2e30f183f909566f6030c8eb85","datavalue":{"value":{"amount":"+0.8116955161094666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174842$F48704C9-0CC8-4E23-B5C1-DE54973ADAA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce6248ef42e93c00743f5cf9837f336f764052f2","datavalue":{"value":{"entity-type":"item","numeric-id":1319020,"id":"Q1319020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cfdddb8a9f13db18dceb107768639a0ef4d1741","datavalue":{"value":{"amount":"+0.8095172047615051","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174842$AF2666D9-591E-434C-8705-2F4AAB8FE3B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal-basis identification technique for interior-point linear programming algorithms","badges":[]}}}}}