{"entities":{"Q2277139":{"pageid":2287882,"ns":120,"title":"Item:Q2277139","lastrevid":49482397,"modified":"2026-01-07T06:01:38Z","type":"item","id":"Q2277139","labels":{"en":{"language":"en","value":"The basic algorithm for pseudo-Boolean programming revisited"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4195698"}},"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":"Q2277139$A63790EC-E1AA-4A13-A999-F780F709B22F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d814eb134ef2f20e85b075a8ce8d2754827cd30","datavalue":{"value":{"text":"The basic algorithm for pseudo-Boolean programming revisited","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277139$DF7A5F45-ECF1-42FB-B583-0AEBBA1F0712","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18cd0262737d0c74f1ab907e7cc284c2a5234731","datavalue":{"value":"0724.90040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$11BAAF14-6B5E-4B3E-97D7-4AE8F5B1F9CD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"829b04d5c74454f4e631fe185332e130d1af4e7b","datavalue":{"value":"10.1016/0166-218X(90)90142-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$6DADF6BE-FC85-45EE-8ADD-2F400D264390","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bf47db66b00e4c421ce1e7ba44bc0c7e860c19b","datavalue":{"value":{"entity-type":"item","numeric-id":190032,"id":"Q190032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$999B1C25-5A2C-416D-AEA3-F951D567526D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d014b1a5c53d4583e103a493ca5a114390d7213","datavalue":{"value":{"entity-type":"item","numeric-id":185380,"id":"Q185380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$25B91A60-F131-4CA0-8C18-E9D118C3CF9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"689f0097808e0ebdfd3bc5250e1c6d60df9ca6cc","datavalue":{"value":{"entity-type":"item","numeric-id":1278721,"id":"Q1278721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$F1E6D714-8175-4984-9834-4EC7509AD744","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$83A5AC0E-8A92-4F5F-80A0-570DFA175FF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2277139$C3B941F2-5D19-48A2-9F12-39B1B7BE3AEF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e770555d0b0038cae8c77304de8ee353a91a19d","datavalue":{"value":"A pseudo-Boolean function is a real-valued function of 0-1 variables, which can be expressed (nonuniquely) as a polynomial in its variables and their complements. The basic algorithm for pseudo-Boolean programming due to \\textit{P. L. Hammer} and \\textit{S. Rudeanu} [see their book ``Boolean methods in Operations Research and related areas'' (1968; Zbl 0155.280)] recursively eliminates variables so that at each iteration a function is produced depending on one variable less, but having the same optimal value as the previous one.    In this paper it is shown that the basic algorithm has linear-time complexity when applied to function associated in a natural way with graphs of bounded tree-width. A new approach to the elimination of a variable based on a branch-and-bound scheme is also proposed, which allows shortcuts in Boolean manipulations. The paper is concluded by some computational results obtained with a FORTRAN 77 program for problems with up to 200 variables.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277139$BC2BF8F1-C26A-467D-846C-C7AC5097CDCA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$D2E3ADCF-E838-4694-881C-0939B88735F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$CE4ECA68-C1B5-4D2A-BABE-8E6186FEF2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$8E81CC0B-1653-4A7E-9F22-F058D6F895FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"52de7d4bf5a27d5ad252804eec58396bb3e40c44","datavalue":{"value":"90C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$87DA88DD-22B1-43F8-B7F2-A523E10EB634","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18fcfa5551efb123432dbe2f3017f1dfc1a8e7af","datavalue":{"value":"4195698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277139$35EF0A34-6B43-4263-ADEE-7FD0F0875177","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e29b4b59e9d37d0ea68642bf2bdd61b279dd40c7","datavalue":{"value":"pseudo-Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277139$C8A55011-3F56-45C4-A341-E90216477EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f0bac228d83f8ca67eefa654554559e747d24ad","datavalue":{"value":"linear-time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277139$F0282BE6-7E2F-4540-96B6-8F661CEB7F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277139$8490A5C4-A1B4-47F0-BB33-01A9BA25FBB9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$90AE8489-81A3-421D-B7CD-3FB9FF8987F6","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":"Q2277139$6B5DCB70-1DE8-4CDC-97CB-4DA68966BE39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$CD129831-A824-4919-A573-1B059A3C8F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$95E1F801-37A0-4F24-8503-6BEE5BB81BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$C715DAD6-26CA-4853-A799-CEF99E1F214B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bbafc7ca60b695ec572adad0752159531ff1382","datavalue":{"value":{"entity-type":"item","numeric-id":3216430,"id":"Q3216430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$018B7D85-4113-40C2-9F64-9C3919E0E035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ceaa2a97c35856d0db00dda4acf15ea31b6101c","datavalue":{"value":{"entity-type":"item","numeric-id":3216431,"id":"Q3216431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$9D11E61B-55F7-43E1-8784-61170149E5E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cfb8880da1dc0f0814b2cc36ba3b7a47b067129","datavalue":{"value":{"entity-type":"item","numeric-id":1079494,"id":"Q1079494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$17E98106-56B0-4E1A-BCD2-13627B73F299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$118C4899-3BB4-478C-BB72-71653561E781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"487c3b72cf5317ad59f2588afc0b3ef4297b1153","datavalue":{"value":{"entity-type":"item","numeric-id":1104751,"id":"Q1104751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$A91BEC3F-54F6-45BC-84DD-DE90B4E7EE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3a349112008990fff36a0cb39ed0606dd9478b8","datavalue":{"value":{"entity-type":"item","numeric-id":3893670,"id":"Q3893670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$879F315B-F8CA-453C-B710-925595D53E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9ddefc8c6dd536bfffbdf83e93f2bb6c7a5d63","datavalue":{"value":{"entity-type":"item","numeric-id":5339894,"id":"Q5339894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$261065E2-1CCB-45BC-8CC0-AFDB129CC6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59d96307b007676d87a7e633dcb786c2042f820c","datavalue":{"value":{"entity-type":"item","numeric-id":5596842,"id":"Q5596842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$84A4FFB3-55F6-4F0A-95C2-34B2B57EDB96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ec5477ed81b4bd9beebf6ad8b16c4546d8f0c7","datavalue":{"value":{"entity-type":"item","numeric-id":5538300,"id":"Q5538300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$B5BDC2B3-4184-4CE7-8896-3D7F221EA4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89c5c7de880ce0f25d1e29cac58149e9143c9c22","datavalue":{"value":{"entity-type":"item","numeric-id":4062940,"id":"Q4062940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$2CE83BF6-64CE-4647-9045-8B794709FAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31074369c209dfc74a6f46f2b4314f30e1ac87d1","datavalue":{"value":{"entity-type":"item","numeric-id":1079493,"id":"Q1079493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$65AC4A88-3712-477B-B015-0B1AC446F7A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$63411DC6-DF83-4CAC-B457-D553695EFF32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$BE77D38E-C50B-45C1-B2E6-2DACE71BA618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21dba65f6864a064525a7b91461ba0cc8e468cbb","datavalue":{"value":{"entity-type":"item","numeric-id":5656593,"id":"Q5656593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$5B2B1A30-F304-445C-823F-12B6EDAB7F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92df622ddeadfd312e1fc9de6113c9adbf992909","datavalue":{"value":{"entity-type":"item","numeric-id":5661709,"id":"Q5661709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277139$82028F59-503D-45E1-B063-EF9B623FE2A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1ba346f5a07e5d9ce14fcf90eab38f888cfbc18","datavalue":{"value":{"entity-type":"item","numeric-id":1341991,"id":"Q1341991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"917a4ef8d47f48dfddfac655541fce63931b0b33","datavalue":{"value":{"amount":"+0.8238153457641602","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":"Q2277139$AAE36036-0050-4671-A64A-40F38EEAA203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecf00aea67a7fb260b01c8b51a10a77cbc9c3da0","datavalue":{"value":{"entity-type":"item","numeric-id":3996042,"id":"Q3996042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8af781be22859989ed7b28fcfa6a1f5ca4248b96","datavalue":{"value":{"amount":"+0.8139556646347046","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":"Q2277139$998FF7B0-81DF-4550-9473-059BD1BFB34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a79ee6bee1c0898a87f31785182964e7b3dc70e","datavalue":{"value":{"entity-type":"item","numeric-id":3221886,"id":"Q3221886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68e4bae9bc3266732f26626eb3130d554062f69a","datavalue":{"value":{"amount":"+0.7805505394935608","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":"Q2277139$AA4A98E1-3177-4E0F-8632-0E208A22CBBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1943dd40a37bc0260bc9eb89bc6414b2abe05b1d","datavalue":{"value":{"entity-type":"item","numeric-id":5341344,"id":"Q5341344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc4155c090413fef9c193dfc98e66ef0d84cf70c","datavalue":{"value":{"amount":"+0.765638530254364","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":"Q2277139$237C80E8-AFD1-4A35-9660-2254B2ADEA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dec4c857bcb23ae3ab76b94e7a98b8013247522","datavalue":{"value":{"entity-type":"item","numeric-id":3682509,"id":"Q3682509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ddec11a05db8e6b452411a84418f44792f931ec","datavalue":{"value":{"amount":"+0.7648459672927856","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":"Q2277139$16E2073B-2F92-477E-823B-120CFE59025A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277139","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277139"}}}}}