{"entities":{"Q870164":{"pageid":872012,"ns":120,"title":"Item:Q870164","lastrevid":65003352,"modified":"2026-04-11T23:40:13Z","type":"item","id":"Q870164","labels":{"en":{"language":"en","value":"An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5132918"}},"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":"Q870164$1D429E87-3EB9-476E-B12B-770DAA98174D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33b8c96bd853f133a733b5919485fa938e31c303","datavalue":{"value":{"text":"An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q870164$1A5708A5-C0B6-4BA3-A89D-76CB9493EA53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a68a5848004becb51d3bfed1888595d69828a783","datavalue":{"value":"1120.90033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$EC130E3F-CB06-40CC-885E-835DF17B52CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eed6c9e55e7b534f06e6bb0d901f08f3f0516b85","datavalue":{"value":{"entity-type":"item","numeric-id":870163,"id":"Q870163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$CA04600B-5D57-4BD1-8ED1-FA0D2FB54C94","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"add6fb6b993c46c88f8cbd1c0026e2e785c9381d","datavalue":{"value":{"entity-type":"item","numeric-id":70476,"id":"Q70476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$0CF2DC15-2529-433A-86DD-2B4FC5698CBF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39eed756ef4774638f5dc70a5b404d4f34900328","datavalue":{"value":{"time":"+2007-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q870164$9A483B56-A762-4900-8DDF-AFB8A356C948","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b33957051007e9d94ce6d23c6a7cf8497ea5a323","datavalue":{"value":"Previous algorithms for solving the general integer linear programming problem often involve the solution of linear programs and have significant memory requirement in the heuristic search process. This paper considers practical algorithms for solving the integer programming problem. The value ranges of the variables in the convex polyhedron of the feasible region of the linear programming relaxation problem intercepted by the objective function hyperplane are established. An efficient heuristic algorithm is presented for finding an optimal solution or showing that there is no feasible solution to the integer programming problem on the objective function hyperplane. The algorithm does not need to solve any linear programming subproblems. The memory requirements of the algorithm change linearly with the size of the problem. Computational results on some numerical problems show that the proposed algorithm is more efficient than the stopped simplex method of Thompson and the all-integer method of Gomory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q870164$EB21DBAF-BEE3-4F3B-8DEE-9F25D6AE52E2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$9DD9D793-0C8A-434D-9016-77111211D9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$080E3955-172A-4FBD-8B82-701222962D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$E16E0C6B-8B55-4763-98E1-A52F8F8B2B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$92C6F117-74C1-4BE3-8FEA-4CFFD082E2C0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0896f2753492a4eeecd32fbe88df6bdc55037d32","datavalue":{"value":"5132918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$B6A5A25E-55CD-4860-A333-26AEDC8856DF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q870164$33E265EE-FD9A-45E0-85EC-139BDF1F7A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e87618aee6343e13e99830120698ef319daa4c9","datavalue":{"value":"integer linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q870164$559F67BE-2D95-427E-BFA6-5ABDC6738381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6a9e644a062c5b7767e4219356e03dc48d7fb21","datavalue":{"value":"simplex method","type":"string"},"datatype":"string"},"type":"statement","id":"Q870164$6DB710A2-AB25-4B27-B7B2-809F0408E216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f425c824fdf09c6d45c0a5d30889a982e077a719","datavalue":{"value":"bound-and-stopped algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q870164$DB876596-B4E3-4F7A-BCC2-5B67E5A10642","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":"Q870164$E9153950-7DAD-4903-8D6C-2D05B2BB878F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"73f4a9aefeda2c7cb4a6738690d0e2ccfeb30293","datavalue":{"value":"https://doi.org/10.1016/j.amc.2006.06.100","type":"string"},"datatype":"url"},"type":"statement","id":"Q870164$8645868B-2CFC-494A-862A-81E3C6267AA5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd00cbbecb32c5beb38b3a2b116babdc7fcb9173","datavalue":{"value":"W2002374099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$6A492253-C895-45E5-8F47-5B213831A4FD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"80bb199555bb7c046b8c35e5422681a1df8cc770","datavalue":{"value":{"entity-type":"item","numeric-id":5580091,"id":"Q5580091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$620B1C70-16BE-4873-946C-D60F3B68E587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a4639797cf5fbc0d34c85e044a1e3bb9473a201","datavalue":{"value":{"entity-type":"item","numeric-id":2564234,"id":"Q2564234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$4C786675-343E-4C2A-A371-46D2F6226A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ccce28bc6c4880fffb7fe52c69b4ac0eabeb12a","datavalue":{"value":{"entity-type":"item","numeric-id":1290616,"id":"Q1290616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$E20D144E-D295-4A9E-B32F-AF982CB4F7E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$53ACF704-0C0C-46B3-B9A5-92A3DC983677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d63f710260bc2300f4e56c57bb6c00c833be47b6","datavalue":{"value":{"entity-type":"item","numeric-id":4081004,"id":"Q4081004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$F36D1AA3-B8F4-4ABF-81A2-836299FE2FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4960d97c11c0cd0f282650fb582b7cd310577033","datavalue":{"value":{"entity-type":"item","numeric-id":3256638,"id":"Q3256638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$A6DFACFB-700B-47E5-B059-5F9BAEFBB928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"899fbafa300a5814f11e5bb8d430764d35c71536","datavalue":{"value":{"entity-type":"item","numeric-id":4009106,"id":"Q4009106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$9AC2D39C-1DE5-4B02-9761-F7762188D6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a4400402d200de3ae471fd9b208efe80de2dee","datavalue":{"value":{"entity-type":"item","numeric-id":1919968,"id":"Q1919968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$C652BFCF-4FF4-4777-93D3-3134C3C5A0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bfa737142dda3b79a31ddaa85ef1721545c5c2","datavalue":{"value":{"entity-type":"item","numeric-id":1368436,"id":"Q1368436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$4D8CA056-F832-45FD-911E-FB7C8312A65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab40a8239685dbf77c7e24c55373bc52bb4d07ab","datavalue":{"value":{"entity-type":"item","numeric-id":3284268,"id":"Q3284268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$2DB4765E-026E-4D06-8ECB-0473D4AF8531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dece8ff15c2e0290beebaeb82d2681b378a65b06","datavalue":{"value":{"entity-type":"item","numeric-id":1278590,"id":"Q1278590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$678E4410-3E6B-4A2A-B73F-F11AA55F6621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b519dd5c48a8212730fc16766e8b007aee08779","datavalue":{"value":{"entity-type":"item","numeric-id":5730600,"id":"Q5730600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$F624B967-388F-4C51-9370-C1989A8447A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77da6d96467cfe6971f7a5d7a0870fca93340eb","datavalue":{"value":{"entity-type":"item","numeric-id":2572046,"id":"Q2572046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870164$9A071965-E4D6-45C7-ACE4-FBBBADEBF41E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e2eba2b8fe467e42803ddf98a114f1e0db190a8","datavalue":{"value":"10.1016/J.AMC.2006.06.100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870164$86180BC0-4670-41A6-940E-5C87FBE54F6F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e424b5c92abd8d89d2b761d6bc1f8d720a33ac47","datavalue":{"value":{"entity-type":"item","numeric-id":1368436,"id":"Q1368436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"517a3b888fdc9c7a84d0006ad370a98e104d3336","datavalue":{"value":{"amount":"+0.8355358242988586","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":"Q870164$CC551794-F542-46FE-9935-5526DBEC55E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f838aff8dbfb7b43a76081f433df5088357c837d","datavalue":{"value":{"entity-type":"item","numeric-id":3014687,"id":"Q3014687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c34431b268625afc80829762ba5bd5c772640f71","datavalue":{"value":{"amount":"+0.8034542798995972","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":"Q870164$67380AC1-6A86-4017-9E39-F1F7CF0C3C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b85422831e3e327a0095ac13ad23aa99b74c0fb7","datavalue":{"value":{"entity-type":"item","numeric-id":1291694,"id":"Q1291694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"377c1310f8226e459665b54ce82dcf5c11e31df3","datavalue":{"value":{"amount":"+0.7927055358886719","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":"Q870164$4816EC31-1181-4EEE-8161-80E0CA5B7704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5aac70271c178a4647e22e5b9de2848fb34f9be7","datavalue":{"value":{"entity-type":"item","numeric-id":3650775,"id":"Q3650775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a880633071364bdaeb4675868bace987f101cd82","datavalue":{"value":{"amount":"+0.7888477444648743","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":"Q870164$34B5575A-968F-4D41-8854-10FFA6482637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b22ded6280fd448db446f3c2f90ca52002409c2e","datavalue":{"value":{"entity-type":"item","numeric-id":5192531,"id":"Q5192531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46e8c24f9d8f78fb6f0e7e850c34db94a01d25af","datavalue":{"value":{"amount":"+0.7849295735359192","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":"Q870164$28C9A542-47CB-4756-B731-93D0A7ADED40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_bound-and-stopped_algorithm_for_integer_linear_programs_on_the_objective_function_hyperplane"}}}}}