{"entities":{"Q1174841":{"pageid":1185590,"ns":120,"title":"Item:Q1174841","lastrevid":47038885,"modified":"2025-12-31T11:34:36Z","type":"item","id":"Q1174841","labels":{"en":{"language":"en","value":"On finding a vertex solution using interior point methods"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 9512"}},"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":"Q1174841$B7117E08-23F0-417F-9D8A-A3F55E694E65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9166ee65bf566c5b19d2a0585e4529a1828556c3","datavalue":{"value":{"text":"On finding a vertex solution using interior point methods","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174841$989189DC-542A-46AA-8BAF-23361F75A288","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fcf2e18c46dc8bb83699dc803486068608eb5480","datavalue":{"value":"0737.65050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$D5295651-2D3A-4310-8524-A48320D4B209","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c98fa54f798a33ff361e696f26f4644814d4f933","datavalue":{"value":"10.1016/0024-3795(91)90277-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$139071F8-FE25-46A9-984A-A10D0B8468BA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cc3cbe474fb83a006cca698eaea2c0246a45088","datavalue":{"value":{"entity-type":"item","numeric-id":173876,"id":"Q173876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$758BF72C-4BAB-41A8-B8A4-A030466DA97B","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":"Q1174841$D56DC635-D482-48E5-8EB0-078D583ECF80","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":"Q1174841$9A57AE30-04A0-4E26-A9BD-69BB394E8ACF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4c7921418ef1f8b3f9a98ab4d2abb2b5f3668e4","datavalue":{"value":"An approach is proposed to generate a vertex solution while using a primal-dual interior-point method to solve linear programs \\(\\min\\{z=c^ Tx\\mid Ax=b, x\\geq 0\\}\\). Let \\(z^*\\) denote the optimal objective value of the linear program, and \\(v^*\\) be a vertex solution of the linear program satisfying \\(c^ Tv^*-z^*\\leq\\varepsilon\\). The problem of finding the vertex solution \\(v^*\\) can be solved within the framework of implementations of interior-point methods. When the choice of \\(\\varepsilon\\) is properly small the vertex solution \\(v^*\\) is the optimal solution of the linear program. The known practical approaches to finding a vertex from an interior solution perform computations similar to those in the simplex method. However there are potential disadvantages in using such approach to find a vertex solution.   In the paper, an approach is proposed. The approach makes a controlled random perturbation to the cost vector to improve the likelihood that the perturbed linear program has unique solution. The size of the perturbation is controlled so that the objective value at the optimal solution of the perturbed problem is within the specified tolerance of \\(z^*\\). A method to identify the active constraints at the vertex to which the solutions are converging is given. The basic method is further refined to save computational effort.   The proposed approach is tested by using a variation of the primal-dual interior-point method on problems from the NETLIB test set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$60F62C10-4E63-406B-ADC4-F2D50D4895AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$7647209F-F9FF-404B-A3F7-0687E1D8E3FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$AC711846-902E-4FA4-9668-D681C0E55F8D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9169454b0b4b7354c4c1619ce180fc42b9bf111","datavalue":{"value":"9512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$E8FE65F7-EEF5-4A83-88E0-6F1183BB3660","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$8430F8B9-C806-4FAF-A60E-C4DA7B2538F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b771ac3fadce615f3d4de5d62ddacbd611c7d83","datavalue":{"value":"vertex solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$528C980D-E46C-4275-8EF9-8540D4421F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83bb74df2a23c8b01a2fbc6ce66df04582f9c3ab","datavalue":{"value":"primal-dual interior-point method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$78553608-30AB-4D3D-8EEC-62EBF7170191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6a9e644a062c5b7767e4219356e03dc48d7fb21","datavalue":{"value":"simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$DE48E3D1-DDCC-4A67-991A-E7F250BC8423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4786765fe67f2b8e1aadc1ee98851fde21f021e6","datavalue":{"value":"controlled random perturbation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$FFAE7173-F89E-497E-84AC-CCC67248F72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d22a6f3cb091cae71935fec20f153594bb672fb1","datavalue":{"value":"perturbed linear program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174841$BC9FF8D2-F184-4607-A1E3-82D18EAA2814","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":"Q1174841$DFA5132F-41F9-4777-A510-5FCFD1CC3898","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ab3966d5d6e8667fc001b632fbfdec3e474c4efe","datavalue":{"value":{"entity-type":"item","numeric-id":23426,"id":"Q23426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$657EABC7-7B68-4680-BB22-54A677F8B4F2","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":"Q1174841$5302EE4C-62F2-4B87-940A-29065AAE9518","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"103fd76ed1bf53637b1dbe565674d785fb871fba","datavalue":{"value":"https://doi.org/10.1016/0024-3795(91)90277-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1174841$CD9AF309-6F77-4200-9946-4D71DCBCED89","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71c529ca4294bffa6a1aad3ffdcdf9a494d94119","datavalue":{"value":"W2078519610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174841$6E67319C-B9B2-41A3-ADC4-FE489CE1829E","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":"Q1174841$14B871D5-2C31-444A-9220-177DC833DCCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9ea1480294b8a9cf75a645c717b410a9893810","datavalue":{"value":{"entity-type":"item","numeric-id":4025908,"id":"Q4025908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$72234DDB-711F-4536-A2BE-EDC9E406A197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4ed6006cba17f406781b62d8980af79fac4266","datavalue":{"value":{"entity-type":"item","numeric-id":3026741,"id":"Q3026741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$02B90A9F-0692-4610-8B7B-0C61B72C0AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6903b57642fba4124efaf8cf6666f0a30f9eec18","datavalue":{"value":{"entity-type":"item","numeric-id":4730699,"id":"Q4730699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$5EAE6C1F-04F5-4B04-89E3-53713AEB79C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5595433e1d739ff967385f6abe4497bd290d31a7","datavalue":{"value":{"entity-type":"item","numeric-id":808184,"id":"Q808184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$5E2EB2B4-D86B-4B16-AA57-06FF66B80472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb5c2529d59e4977f3b021ebdb2e3f9a59cb983","datavalue":{"value":{"entity-type":"item","numeric-id":4020667,"id":"Q4020667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$379315A4-337D-443B-9F89-4E927CC0EBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7df5ffd2d7d6a2272297144e67233a0999193c60","datavalue":{"value":{"entity-type":"item","numeric-id":4019974,"id":"Q4019974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$D33DF715-F9FA-4688-B7F3-EEE3E49C7568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fef1b6cfa6a5c0862474be12c7c10e54c72fba8","datavalue":{"value":{"entity-type":"item","numeric-id":4030782,"id":"Q4030782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$CADEE893-7949-4A2B-8055-EC3083509FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75a4548fa6b30113fcc44826e06826d2994e381","datavalue":{"value":{"entity-type":"item","numeric-id":4015447,"id":"Q4015447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$362C16D0-4F92-4701-8E3A-6C26A80CAB91","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":"Q1174841$DE7C5A44-FA7D-427F-B51B-6F0B3F33D754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ef74802c806b26873ffc203fcfaccbf9407d58","datavalue":{"value":{"entity-type":"item","numeric-id":4040780,"id":"Q4040780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$613CE1FB-0D1D-4EF2-B445-FEF3FD3DB07C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$B44218FE-3ECA-4B94-89A6-5EEEE3F001BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25bf2bb184be25cded7bca2812c614443b4c501f","datavalue":{"value":{"entity-type":"item","numeric-id":3907424,"id":"Q3907424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$61ED0A5C-34A1-4692-9AC8-A38321774F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0adf5f7dfe0857ece90a4c1f7f7f04c79135132","datavalue":{"value":{"entity-type":"item","numeric-id":1321176,"id":"Q1321176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174841$6ABC81BF-D9F8-41A4-80A3-871C9EF8EAE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"077689e799efebd128e3023108736f33152f5cf2","datavalue":{"value":{"entity-type":"item","numeric-id":3139571,"id":"Q3139571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35bc57f6fa2968a6e34b770a896722a8dfbb1490","datavalue":{"value":{"amount":"+0.7554894089698792","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":"Q1174841$111B8662-CD73-4211-BA68-EDB730AAD973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f1244cdabc719120abafb77fd39935a6c8b81d7","datavalue":{"value":{"entity-type":"item","numeric-id":1321229,"id":"Q1321229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71d93108c6f54416069ce5bef788889249a9cfdc","datavalue":{"value":{"amount":"+0.7547568678855896","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":"Q1174841$60765DF6-A46D-457D-8E20-88E06377E153","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":"46736f4543fd583fda08b6f8ee9f42ae0165714d","datavalue":{"value":{"amount":"+0.7531924247741699","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":"Q1174841$FB3271CB-0963-472F-858A-BB79EE4F691D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55105119bee55acbc2c89eeac9125f68d6019c07","datavalue":{"value":{"entity-type":"item","numeric-id":2366606,"id":"Q2366606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a7eb7a0f49b69d1a674f21a26c71cd6c81b0221","datavalue":{"value":{"amount":"+0.7524332404136658","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":"Q1174841$CC3E6E67-3BB0-4682-BEEB-C81464622865","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":"d984d5d8da0ed74a0551c807330cec20ec9b81d9","datavalue":{"value":{"amount":"+0.7514668107032776","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":"Q1174841$45C377EB-4C58-477F-BA7E-5F5F59E490AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1174841","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1174841"}}}}}