{"entities":{"Q431007":{"pageid":432774,"ns":120,"title":"Item:Q431007","lastrevid":61779204,"modified":"2026-04-11T01:35:53Z","type":"item","id":"Q431007","labels":{"en":{"language":"en","value":"Clique-based facets for the precedence constrained knapsack problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6050443"}},"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":"Q431007$01D99855-2B70-4D8A-9AA7-7C0CA16D2EC5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5472de2ebea4ec7c988f6b807a138c90f603e321","datavalue":{"value":{"text":"Clique-based facets for the precedence constrained knapsack problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q431007$B48AC04F-CDAC-4E2A-B85D-ADD4FE8F3060","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcc559ca1358d98d23420984b4b4bd51c0c330c8","datavalue":{"value":"1259.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$B0B15AC8-0A31-4DB2-B709-4486E0856186","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfc1a42b1f9d24440a42c90ff9174cfa6f7025e0","datavalue":{"value":{"entity-type":"item","numeric-id":291040,"id":"Q291040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$DAD66D98-1DC4-48CD-9876-88CFAAE87F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebb4ed8b23fbd201877a5d16268eb43147460039","datavalue":{"value":{"entity-type":"item","numeric-id":313787,"id":"Q313787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$7A6011F5-BE68-4AF4-8550-AAEF94725EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf4ee87e4a93cafce20ee98d10018665c5783ac3","datavalue":{"value":{"entity-type":"item","numeric-id":431006,"id":"Q431006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$3C16C62E-D407-410B-9529-24595BC7E57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbb62d8ac4be3a4d6741a8dc2d332d1cbbd3e02f","datavalue":{"value":{"entity-type":"item","numeric-id":195976,"id":"Q195976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$3B317A86-FA5E-400D-9B29-1E8386722C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc2276bfead9878d5e4eb68cfdff70ba5ff83ab0","datavalue":{"value":{"entity-type":"item","numeric-id":296967,"id":"Q296967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$2985763F-02DE-49B1-977A-97C1016C36EE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$1B981970-B02C-48BE-AAC1-547A12C57858","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f03a3c04b271440e0460d17b6cd1c270f9267efc","datavalue":{"value":{"time":"+2012-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q431007$EB89E7DD-58FB-4DD7-A038-8627736B44E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c4918eec39b09154b70b1a9151b7f0c1a4f81fb","datavalue":{"value":"The authors present a novel approach for determining facets of the precedence constrained knapsack problem (PCKP) based on clique inequalities. The PCKP is an NP-hard combinatorial optimization problem that finds many interesting applications especially in manufacturing and mining. The main idea is to investigate clique inequalities derived from a directed graph representing pairwise conflict relationships between the integer variables and derive necessary and sufficient conditions under which they represent the convex hull of the associated PCKP polyhedron. There is presented as well a comparison between the previous defined covers and cliques in the conflict graph. In the last part of the paper, there are described applications of the clique-based inequalities in the case of some PCKP examples, showing their relative strengthening effect on the LP relaxation. Computational results are reported in the case of two classes of instances, demonstrating benefits of using the clique constraints to realistic problems, with respect to the reduction of the solution times.","type":"string"},"datatype":"string"},"type":"statement","id":"Q431007$8152129F-D9FD-4C7B-896D-EFE7BFD06FC1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$2A092E4F-572E-49DC-9BF9-6A1D988D9CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$711C769A-E4AA-464D-9F50-E56AB9E94463","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97bf01e669d7b28417edae6bef8de62ba7c3ba02","datavalue":{"value":"6050443","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$F04BB34F-5790-4717-A8C5-25BDC1B61EBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe4d98d70ae07ac7be3c8a22e834366cf96c34c6","datavalue":{"value":"precedence constrained knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q431007$3C5EA8A1-9250-4FBD-8228-4227D8505ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a43f04ca8a2b4ead5e76c37b9db7ad43d82fbcae","datavalue":{"value":"clique inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q431007$F6114F8A-72DE-4264-9EA4-2F0B13B61F03","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b2e2936f14ed4ac57a25cb265a3d2d00acb32d2f","datavalue":{"value":{"entity-type":"item","numeric-id":455035,"id":"Q455035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$0CD6E299-5B18-4FB0-A533-B03156375C32","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6663be921a3fe3b244879abf2c0c98e00d21e962","datavalue":{"value":{"entity-type":"item","numeric-id":13835,"id":"Q13835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$4326A31E-8111-43C2-857D-95348AA70EDC","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":"Q431007$E674114C-BAA0-4428-9C1E-0B35BDF7ACF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"acb2ec5238c9876f26f7d948904ab39c154d8838","datavalue":{"value":"https://doi.org/10.1007/s10107-010-0438-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q431007$2F1F057D-7B1E-45D8-AB3C-6B0C0D443A39","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"48e732f33d1828a1253cbf47be7eb7cd7db259a5","datavalue":{"value":"W2141422661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$0D1A38C4-9BB5-448C-A45A-B7AB72B9FD66","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9c7ea1f06f038807a755d5bb32d9bea726cb1a5f","datavalue":{"value":"Q59139576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$A81FE096-D374-4D58-BC02-6BDF46F8C3FB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d98efefe2d5cc57c83d83dae7ca6a97f020ce9bc","datavalue":{"value":{"entity-type":"item","numeric-id":2471271,"id":"Q2471271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$CB5A1781-84C2-4928-8D59-34FD576B39EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd53d6e9478c4bb1c7a40fd9e4a8dadfd6988d8","datavalue":{"value":{"entity-type":"item","numeric-id":4197624,"id":"Q4197624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$B9C022D9-834A-4071-A44D-B250A473C655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a3ea2948746b546c1f6ec54192a0e5c04578bc7","datavalue":{"value":{"entity-type":"item","numeric-id":5391869,"id":"Q5391869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$3C9676F1-2CC0-41D1-A307-E8F3ABBC8959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b6908292f21eb50bdb8ce223c32e180f10d78a7","datavalue":{"value":{"entity-type":"item","numeric-id":2270449,"id":"Q2270449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$9C5E9A53-1D88-4A59-8BBE-EB9BB2478403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa0180fc07b01b5b3a63dd32f85d22b496fa0f3","datavalue":{"value":{"entity-type":"item","numeric-id":3145799,"id":"Q3145799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$7A51F2CC-1B0D-4535-90F4-8250479DB87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4e5079d5f962cdf5112b41bb7b5876f93b90e3c","datavalue":{"value":{"entity-type":"item","numeric-id":1208480,"id":"Q1208480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$5D2D2315-208A-4EF0-B16B-9AE22EA582CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2abf8f5c68768ee2261f0896da2b063b3182f8","datavalue":{"value":{"entity-type":"item","numeric-id":1407258,"id":"Q1407258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$65FAEB2E-91CC-411A-BFB0-4AC130D818BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$BFAAADF1-67C7-4D9D-AE8D-1B5547106972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dde7402857e95cc177da46dc7bdabb069f4737e1","datavalue":{"value":{"entity-type":"item","numeric-id":4190413,"id":"Q4190413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$9AAB8963-6E6E-4CAB-9C27-1EFB065535E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d702c846b4aacb92193180293a1a5b223f5025cc","datavalue":{"value":{"entity-type":"item","numeric-id":4744041,"id":"Q4744041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$0855EC58-F5F5-4681-8A1B-62FFE651E376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1e8c199d0a3738b5df7039fa423628b9c9f24f","datavalue":{"value":{"entity-type":"item","numeric-id":4040221,"id":"Q4040221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$A70E9E07-4C0E-471E-98BB-524558643BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29da6733cc7c8beeed2c44e6454d84db57e6c5a5","datavalue":{"value":{"entity-type":"item","numeric-id":674439,"id":"Q674439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$8654045B-965A-48F3-B80B-D0EDABCC6E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b2cb54d7312c0b765fdd460be5bf57c3284b2cc","datavalue":{"value":{"entity-type":"item","numeric-id":1806031,"id":"Q1806031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431007$7A7AF159-0F13-402F-BF6B-82BE3103D77E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1533a598517635c48f5d04214856379af06a2e46","datavalue":{"value":"10.1007/S10107-010-0438-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431007$5B7B28C3-ED96-43A7-9F94-BCFBF31F65A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e03b849650c39a28d601d0d2d4716e8575ef0d","datavalue":{"value":{"entity-type":"item","numeric-id":1208480,"id":"Q1208480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eac1bf46eb9327d0bbf9d17f4b30c65876f12d1c","datavalue":{"value":{"amount":"+0.8418008089065552","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":"Q431007$89DC90CD-8BDE-41B2-B3FE-D39A45072F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a081a89890e7445d6c229c6c522be1910841b80d","datavalue":{"value":{"entity-type":"item","numeric-id":2408089,"id":"Q2408089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6bde133b01f53d96783bc22a828351e1149ab8","datavalue":{"value":{"amount":"+0.8387776613235474","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":"Q431007$3118F933-19D0-4CDB-9D95-D9BBD9ED0FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eab6cfff7dc72a0957a2df64ee38b82dfe5ab18","datavalue":{"value":{"entity-type":"item","numeric-id":1806031,"id":"Q1806031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e3cf583ca94e036201c25cdbffac7f2e130e154","datavalue":{"value":{"amount":"+0.8263871669769287","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":"Q431007$9D293CA1-5B3A-4EB1-AFA3-3C8BC55DAE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76cae6210843204e419e6bfdc26e0791eaa683ad","datavalue":{"value":{"entity-type":"item","numeric-id":674439,"id":"Q674439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1dd445786433a5075d2b0962d80b32fedcb59f6","datavalue":{"value":{"amount":"+0.8174838423728943","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":"Q431007$CE8ABC65-674A-4CEE-AFCF-9EE4626A0448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c085eca97458a30a9ec3386d7402f1cf60d61bdc","datavalue":{"value":{"entity-type":"item","numeric-id":2371351,"id":"Q2371351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fa49a6fe5c928675b45763d6462b6c0948cf4e7","datavalue":{"value":{"amount":"+0.8112414479255676","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":"Q431007$E5D87387-799B-4F50-8477-1562BB7F45BB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Clique-based facets for the precedence constrained knapsack problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Clique-based_facets_for_the_precedence_constrained_knapsack_problem"}}}}}