{"entities":{"Q2277361":{"pageid":2288104,"ns":120,"title":"Item:Q2277361","lastrevid":49490533,"modified":"2026-01-07T07:17:05Z","type":"item","id":"Q2277361","labels":{"en":{"language":"en","value":"Unconstrained 0-1 optimization and Lagrangean relaxation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4197748"}},"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":"Q2277361$04F82A77-AD54-4CD1-9367-9B75EA62A397","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2de73c0f7da6018d7cf422763a01ca45b350d99b","datavalue":{"value":{"text":"Unconstrained 0-1 optimization and Lagrangean relaxation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277361$9FD3E116-572C-40F5-8CFE-703497991D90","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"baa624df6b8ce18adb706458121113db84e3f460","datavalue":{"value":"0725.90067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277361$70787930-FEAD-4E92-9251-7AD2B7C827B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c72e1e5da7110918c597dc8112f38c4d5e2f2a8","datavalue":{"value":"10.1016/0166-218X(90)90139-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277361$BE3D02FB-36A2-4807-A877-0A04935D380F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"174c18e133ed0db3f91324f8994a685843553e56","datavalue":{"value":{"entity-type":"item","numeric-id":2277360,"id":"Q2277360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$618A9929-FE35-4887-8855-A429C45B64C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1f1c6a8167c7f3e97dc242c6c4f58c64741e146","datavalue":{"value":{"entity-type":"item","numeric-id":176416,"id":"Q176416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$776780F5-5195-4A36-B871-3FDA079F91F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b55f657605a88430f5c1fce5fb12d3be88e6ac54","datavalue":{"value":{"entity-type":"item","numeric-id":1190603,"id":"Q1190603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$C66C2DFB-629D-4A04-AC11-AB55A54324D9","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":"Q2277361$DCB4969C-2195-4A4A-9E46-2BCAB0BACAA7","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":"Q2277361$FE1D1CC1-42E1-4AC4-B3BA-7DB01346D7C1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f275f4b62ddfe02b66220244285ce69d224ff9d","datavalue":{"value":"The unconstrained 0-1 polynomial programming problem (PPP), (P1) is considered. An equivalent problem with nonnegative coefficients of the terms of degree 2 and more is used:  \\[  (P2)\\quad Z_{P_ 2}=\\max \\{f(x,\\bar x)| x\\in \\{0,1\\}^ n,\\quad \\bar x\\in \\{0,1\\}^{\\{I_ c\\}}=  \\]   \\[  \\sum^{n}_{i=1}\\ell_ ix_ i+\\sum_{k\\in P}d_ k\\prod_{i\\in Q(k)}x_ i+\\sum_{k\\in N}c_ k\\bar x_{T(k)}\\prod_{i\\in R(k)}x_ i,  \\]  (here \\(\\bar x_ i=1-x_ i)\\). A linear function \\(p(x)\\), a roof for (P2), is constructed as an upper bounding function of \\(f(x,\\bar x)\\). Let R be the set of all roofs, then the dual roof is defined as  \\[  W(R)=\\min_{p(x)\\in R}\\{\\max_{x\\in \\{0,1\\}^ n}p(x)\\}  \\]  and this value may be calculated by solving the LP problem  \\[  Z_{LP}=\\max [\\sum^{n}_{i=1}\\ell_ ix_ i+\\sum_{k\\in P}d_ xt_ k+\\sum_{k\\in N}c_ kw_ k]  \\]  subject to linear constraints. W(R) is an upper bound on \\(Z_{P_ 1}\\) with the so-called roof duality gap  \\[  W(R)-Z_{P_ 1}=\\min_{p(x)\\in R}\\{\\max_{x\\in \\{0,1\\}^ n}p(x)\\}-\\max_{x\\in \\{0,1\\}^ n}\\{\\min_{p(x)\\in R}p(x)\\}.  \\]  The problem (P3) is built from (P2) by substitution \\(y_ i=\\bar x_ i\\). A Lagrangean dual function LD(\\(\\pi\\)) is constructed for problem \\((P3)\\quad Z_{LD}=\\min_{(\\pi)} LD(\\pi).\\)    One of the results is the following Theorem 1. \\(W(R)=Z_{LD}.\\)    It is shown that checking the existence of a roof duality gap is equivalent to the checking of the consistency of a 0-1 quadratic posiform. The results of the paper are illustrated on an example of a 0-1 cubic programming problem with 4 variables.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$264B7D16-E5DD-4843-A4B3-C542D775077E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277361$C0DC6FD1-34A9-4383-BBC5-14A5E9E98DC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9b8bdcc402eb9c0bf759f6a88223cbae1a32275","datavalue":{"value":"4197748","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277361$352BEDAC-278E-4870-9D89-FC90491C5FFA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9aa437bbd3dbe6249a1c18556e84bd41e9c855e0","datavalue":{"value":"polynomial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$E9B711DF-F2D4-4D90-912B-80B6EAA9635D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"468a9760790c50a8f14ee210166e4f56f71c3ca9","datavalue":{"value":"Lagrangean relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$5BC699EE-D665-4F6B-ACD7-F64FC5AF3784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"848fd803f55f1147fbbc23e195681232f0621c7c","datavalue":{"value":"unconstrained 0-1 polynomial programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$B8D90A9D-D075-4EED-AB77-A1E43F40D862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2a7f4c85e8a6d53447c2ee4179d20f6d0173222","datavalue":{"value":"equivalent problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$3C4FB737-2163-4496-985C-87D82545F8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a59dabd2b02de88ff84ab1501a4ca274905c6af","datavalue":{"value":"roof duality gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277361$DA2B19CC-B195-4C5B-B502-AA2054ECA215","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3ba912c6c747366fcbf58ca77660b129d8633c6","datavalue":{"value":{"entity-type":"item","numeric-id":1014034,"id":"Q1014034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$A991CDA6-ACF5-4E57-AE94-19569A8ABE68","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":"Q2277361$FDDF650D-1B4C-4B26-8B17-23AE6C995FC4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"02996930b92064b47da397ea259d50ecc0b5dc61","datavalue":{"value":{"entity-type":"item","numeric-id":1314325,"id":"Q1314325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$FFBF28F0-32D2-417E-BF76-9F200100C0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$27781BC0-927F-4233-84DB-DE4B30CEE6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b04d40c31014fccd7a519094c8ec2ae4634b6ea7","datavalue":{"value":{"entity-type":"item","numeric-id":5181541,"id":"Q5181541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$879CEB76-1638-4134-9897-9662427B5189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1e239dce14973bc963cb9871e26501ddc153e9","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$F1534D1B-8CE5-4F54-86DF-0080C3312E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38eb1f17892f3ce6224c0b99096dc54a9b9bb175","datavalue":{"value":{"entity-type":"item","numeric-id":1174434,"id":"Q1174434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$85F33391-C51F-4B93-8D44-3444E96D58ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc9afe9f6377e82be989526d04e8a4fd443ec08","datavalue":{"value":{"entity-type":"item","numeric-id":3770279,"id":"Q3770279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$E8F5CD16-7DF8-4063-BFF5-8EEB5AD7EE6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d2ff8ca55c71a00eb97ded234e95c181b7889c","datavalue":{"value":{"entity-type":"item","numeric-id":5603745,"id":"Q5603745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277361$CE7BE537-02F2-492F-90D2-DB91581F44C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dc247f7e2b0ed6f364fb37fb087e424f3337cfd","datavalue":{"value":{"entity-type":"item","numeric-id":1314325,"id":"Q1314325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d16886c3605ab23afa68aba65d8f5e074bd19e","datavalue":{"value":{"amount":"+0.8486936092376709","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":"Q2277361$96C76CE9-D8FB-49C9-A515-8B29F8E9BEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82bef91bd5fa80231940b8fb35adb8fb151e9269","datavalue":{"value":{"entity-type":"item","numeric-id":3786282,"id":"Q3786282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d16886c3605ab23afa68aba65d8f5e074bd19e","datavalue":{"value":{"amount":"+0.8486936092376709","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":"Q2277361$9A35BBF2-1D4B-4CA6-9D6B-7B5241B3C59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bae348e9499b80fc4c703cbdce82aa171eded6d0","datavalue":{"value":{"entity-type":"item","numeric-id":3770279,"id":"Q3770279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39401c5f45de0021596f3cc3bae7ba7377403dd0","datavalue":{"value":{"amount":"+0.8415256142616272","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":"Q2277361$031EC293-1F55-4425-94C1-8F61AD4849E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"207bbacaa7f9c01cc9c1e81f528c52726bf98916","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0dddc0955faa40f314a90ee8c8b244ac60fa21c","datavalue":{"value":{"amount":"+0.8147398233413696","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":"Q2277361$9B81C5DB-DD86-4AC8-B493-D1A809A68EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ad1c07f0a808727d6e1c1a59151a86483cf1369","datavalue":{"value":{"entity-type":"item","numeric-id":4729611,"id":"Q4729611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1a72da77619e97dbf1e1f6b7960074771510c29","datavalue":{"value":{"amount":"+0.8084216713905334","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":"Q2277361$85C243B6-6455-42FC-94F3-52D78B7C4BCE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277361","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277361"}}}}}