{"entities":{"Q792216":{"pageid":794064,"ns":120,"title":"Item:Q792216","lastrevid":64414161,"modified":"2026-04-11T19:42:53Z","type":"item","id":"Q792216","labels":{"en":{"language":"en","value":"An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3852790"}},"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":"Q792216$80D0BD17-B869-4A8F-B381-D4DF5964F96E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97b6bb252d66f9fb11c13f0008f225fb5cf5269e","datavalue":{"value":{"text":"An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792216$6006015C-32DF-4FE6-B28B-E54A554B9944","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"636f3bead17e40e6aa7102c64e7b172153db037f","datavalue":{"value":"0536.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$AE319583-B62B-4626-AFC4-14CCF6A6F39D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df3e801fa88098293aa540790e5a12393b246740","datavalue":{"value":"10.1016/0377-2217(84)90015-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$D4DC3CAA-5779-4B26-A066-8C0EEE765875","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bba0dc06d9e863feee266304b6624ac54f793c4","datavalue":{"value":{"entity-type":"item","numeric-id":168083,"id":"Q168083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$23A7B477-B53C-45F5-8186-26500550058A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebc81156bfa770990eb6930939f0807d36373a6b","datavalue":{"value":{"entity-type":"item","numeric-id":1072450,"id":"Q1072450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$CE99707E-DDFC-4F8C-B0C2-D544C5884142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"528213fff139b1cbbc9f99c29c0de7561f9e3846","datavalue":{"value":{"entity-type":"item","numeric-id":917440,"id":"Q917440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$678E399D-A924-4410-8D08-9FA7B2077678","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$AB1DC6BA-82B7-442E-A582-EB8907E538D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q792216$61568378-0A2C-4D6D-9EB3-9AD434B6DFB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d1906449f7468d22d830926088e21178d530a88","datavalue":{"value":"To improve an algorithm by \\textit{B. Gavish} and \\textit{E. Shlifer} [ibid. 3, 122-134 (1979; Zbl 0392.90055)] for a class of transportation scheduling problems, \\textit{G. P. White} [ibid. 9, 190-193 (1982; Zbl 0473.90054)] proposes the use of an alternative subproblem as a relaxation within a branch and bound framework. White's subproblem replaces an assignment problem relaxation used in Gavish and Shlifer's paper [loc. cit.] with a bipartite weighted matching problem, observing that the latter is susceptible to a 'Hungarian-type' of algorithm due to \\textit{E. Lawler} [''Combinatorial optimization: Networks and matroids'' (1976; Zbl 0413.90040)].    The purpose of this note is to show that the bipartite weighted matching problem, applying a special case of a result of \\textit{A. Charnes, F. Glover} and \\textit{D. Klingman} [Nav. Res. Logist. Q. 18, 277-281 (1971; Zbl 0226.90025)], is equivalent to a 'quasi-transportation' problem - i.e., a transportation problem in which exactly one origin and one destination have a non-unit supply and demand. Empirical studies of \\textit{F. Glover} and \\textit{D. Klingman} [Techn. Rep. 212, Army Office Res., Research Triangle, Durham, NC, USA (1980)] have shown that the quasi- transportation problem can be solved very efficiently by a primal simplex type of code that exploits an alternating path basis structure due to \\textit{R. S. Barr, F. Glover} and \\textit{D. Klingman} [Eur. J. Oper. Res. 2, 137-144 (1978; Zbl 0376.90068)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$96669BAA-B8EF-4A19-80FC-FF45D7D76C22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$64ADB997-C010-4A64-8860-3E8B61143051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$F0A97ED6-32C7-4A27-AC5E-72B9E369B2AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39b31deb7f98ba3c9137cd4e501f527eb0ba266e","datavalue":{"value":"3852790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$2DC0CAA1-EE90-4C67-A831-BE9FCC5A4C69","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecd6c5582a59225376bc67598010edecc5c1ce3b","datavalue":{"value":"primal simplex algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$02171986-3EBF-4764-988D-05BD31B4AEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffbc80d430c4d75e9464b6e0605061c19ccd9763","datavalue":{"value":"transportation scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$A5290FB8-5244-441A-AC76-D646C354952C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9675bb37dbeeee484cb314a4abd71e5ae4600c0","datavalue":{"value":"relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$486F67CE-C97B-4182-933F-8F6955BD29D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a4614b01642c290f3ce90938761d9224e5f556d","datavalue":{"value":"bipartite weighted matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$AB5F155B-793E-4526-9F3E-F68193FDE96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d38b13b4f2fa958681454c068577449684e42dc","datavalue":{"value":"alternating path basis structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q792216$29E49571-2F17-4B17-9327-6C21DACC2EE1","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":"Q792216$64F007E0-AA05-495A-86FF-A73F0D9EE7D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1a0fdbfbc1f563de73ae14f9cd2246082fb1310","datavalue":{"value":"https://doi.org/10.1016/0377-2217(84)90015-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q792216$7CF183AE-F617-47BB-B1B1-846F8BB39D37","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"91a1b2f457f7b969702dd7e5d1f5c2edb2d45afe","datavalue":{"value":"W2037942733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792216$5D74C837-4285-4273-A820-28DA6DFEA365","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b0c4699b2a6f74d1b2d31837e5f0bdbe084b33c","datavalue":{"value":{"entity-type":"item","numeric-id":5633828,"id":"Q5633828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$CA8A7378-F338-4720-ADA2-0DA7820C0433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b8d1f1dec187949c55d24425e38fee6023c1bf","datavalue":{"value":{"entity-type":"item","numeric-id":4159200,"id":"Q4159200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$6DDBA827-BAEC-4B7A-A699-3E04CA7B69FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea6be8db4fad5918990043b1c3988ec8fe334a45","datavalue":{"value":{"entity-type":"item","numeric-id":1245652,"id":"Q1245652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$F7E1C767-CB9A-443F-906D-8652A1A19A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb3f0318f4c2281498883fe698492a41d5ac577d","datavalue":{"value":{"entity-type":"item","numeric-id":4152359,"id":"Q4152359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$FD0C17ED-4365-4352-B834-2EDAC9C6B31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"379eb08edcdf199e39da047e7f4ccd5515e392d3","datavalue":{"value":{"entity-type":"item","numeric-id":1251987,"id":"Q1251987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$5C3F97BA-2BA4-47A8-92D5-196591EBE0EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"825b05e2e03806f0ee57627c2cb39822bbd252de","datavalue":{"value":{"entity-type":"item","numeric-id":4101626,"id":"Q4101626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$0C856131-3E23-49B4-9C43-C58AA9438258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$FF2188E2-EB5C-45B3-BD00-71A7B465C8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731e99376e8702c5d355c7d2ba0ddb139c20b787","datavalue":{"value":{"entity-type":"item","numeric-id":3899825,"id":"Q3899825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$62CF2FF8-AE6A-428A-9D1E-3DE45E74D4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$1D9BAB3E-9BCF-4D10-A1A0-0937C68738BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84b636253a1b1cf690746f21730d0dba0fc33c4","datavalue":{"value":{"entity-type":"item","numeric-id":4158842,"id":"Q4158842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$E610BA10-8120-4AFC-B11C-9A9102215185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dac9b199f6347c77c269f40bf9ba3cb885fa7bc0","datavalue":{"value":{"entity-type":"item","numeric-id":1159133,"id":"Q1159133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792216$088D34FB-F015-4F9D-BFF3-9E938F9BA34B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bd2ce30fc142dbcb5ce7f136ee8033d4d1bfbaa","datavalue":{"value":{"entity-type":"item","numeric-id":3815858,"id":"Q3815858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"540666f8e2931ad036a562b15021e4610ef85507","datavalue":{"value":{"amount":"+0.7384005784988403","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":"Q792216$BCA8ED5B-5C15-43CE-90B1-01E7FF6231BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f863a111275a852edd033a295267195080b59493","datavalue":{"value":{"entity-type":"item","numeric-id":3014721,"id":"Q3014721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb10fcc3fee3a04affb0821d857287f7295d9855","datavalue":{"value":{"amount":"+0.7378315329551697","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":"Q792216$DFA8B219-5450-445A-B7C4-424EE4EDF17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef980df4b9f24258afd8626415ceb4a6ad3bbd68","datavalue":{"value":{"entity-type":"item","numeric-id":808992,"id":"Q808992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92996d773a03b80b871c090d38b5382fe1514c86","datavalue":{"value":{"amount":"+0.737551748752594","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":"Q792216$972B0746-26D4-4D06-A871-93CAC045D8C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbd716bb375c0ea4ee82ed6876b869a6afd73799","datavalue":{"value":{"entity-type":"item","numeric-id":1083031,"id":"Q1083031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01961e5885b705a978f7da953429d3370ae3e196","datavalue":{"value":{"amount":"+0.734571635723114","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":"Q792216$E9006131-C943-4EA9-986E-598AD9124060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02c779a2a30a540c27eb6c0a32ffbd685c768858","datavalue":{"value":{"entity-type":"item","numeric-id":3790928,"id":"Q3790928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4efda70a8e74dce706d664e32f16cf914bd0e439","datavalue":{"value":{"amount":"+0.7317792177200317","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":"Q792216$D14B5183-F601-4BE6-BF1E-C9216D74A4B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_equivalent_subproblem_relaxation_for_improving_the_solution_of_a_class_of_transportation_scheduling_problems"}}}}}