{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:46:43Z","timestamp":1774946803814,"version":"3.50.1"},"reference-count":21,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2012,2,14]],"date-time":"2012-02-14T00:00:00Z","timestamp":1329177600000},"content-version":"vor","delay-in-days":44,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Portuguese Science and Technology Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Problems in Engineering"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We propose a new exact method for solving bilevel 0\u20101 knapsack problems. A bilevel problem models a hierarchical decision process that involves two decision makers called the leader and the follower. In these processes, the leader takes his decision by considering explicitly the reaction of the follower. From an optimization standpoint, these are problems in which a subset of the variables\nmust be the optimal solution of another (parametric) optimization problem. These problems have various applications in the field of transportation and revenue management, for example. Our approach relies on different components. We describe a polynomial time procedure to solve the linear relaxation of the bilevel 0\u20101 knapsack problem. Using the information provided by the solutions generated by this procedure, we compute a feasible solution (and hence a lower bound) for the problem. This bound is used together with an upper bound to reduce the size of the original problem. The optimal integer solution of the original problem is computed using dynamic programming. We\nreport on computational experiments which are compared with the results achieved with other state\u2010of\u2010the\u2010art approaches. The results attest the performance of our approach.<\/jats:p>","DOI":"10.1155\/2012\/504713","type":"journal-article","created":{"date-parts":[[2012,2,14]],"date-time":"2012-02-14T21:01:51Z","timestamp":1329253311000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["An Exact Algorithm for Bilevel 0\u20101 Knapsack Problems"],"prefix":"10.1155","volume":"2012","author":[{"given":"Raid","family":"Mansi","sequence":"first","affiliation":[]},{"given":"Cl\u00e1udio","family":"Alves","sequence":"additional","affiliation":[]},{"given":"J. M.","family":"Val\u00e9rio de Carvalho","sequence":"additional","affiliation":[]},{"given":"Sa\u00efd","family":"Hanafi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2012,2,14]]},"reference":[{"key":"e_1_2_7_1_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.1.37"},{"key":"e_1_2_7_2_2","volume-title":"The Theory of the Market Economy","author":"Stackelberg H.","year":"1952"},{"key":"e_1_2_7_3_2","volume-title":"Nondifferentiable and Two-Level Mathematical Programming","author":"Shimizu K.","year":"1996"},{"key":"e_1_2_7_4_2","volume-title":"Foundations of Bilevel Programming","author":"Dempe S.","year":"2002"},{"key":"e_1_2_7_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10288\u2010005\u20100071\u20100"},{"key":"e_1_2_7_6_2","first-page":"93","article-title":"Bilevel programming with knapsack constraints","volume":"8","author":"Dempe S.","year":"2000","journal-title":"Central European Journal of Operations Research"},{"key":"e_1_2_7_7_2","first-page":"44","article-title":"The bilevel optimization problem with multiple-choice knapsack problem in lower level","volume":"10","author":"Plyasunov A.","year":"2003","journal-title":"Discrete Analysis and Research Operations"},{"key":"e_1_2_7_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2009.01.007"},{"key":"e_1_2_7_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.38.5.911"},{"key":"e_1_2_7_10_2","unstructured":"BrotcorneL. HanafiS. andMansiR. One-level reformulation of the bilevel knapsack problem using dynamic programming 2011 Universit\u00e9 de Valenciennes et du Hainaut-Cambr\u00e9sis France."},{"key":"e_1_2_7_11_2","doi-asserted-by":"publisher","DOI":"10.1080\/0233193031000149894"},{"key":"e_1_2_7_12_2","doi-asserted-by":"crossref","DOI":"10.1007\/0-306-48332-7_31","volume-title":"Bilevel Programming: Applications","author":"Marcotte O.","year":"2001"},{"key":"e_1_2_7_13_2","doi-asserted-by":"crossref","unstructured":"KosuchS. Le BodicP. LeungJ. andLisserA. On a stochastic bilevel programming problem with knapsack constraints Proceedings of the International Network Optimization Conference 2009 https:\/\/doi.org\/10.1007\/BF02591863.","DOI":"10.1007\/BF02591863"},{"key":"e_1_2_7_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199204)39:3<419::AID-NAV3220390310>3.0.CO;2-C"},{"key":"e_1_2_7_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00121269"},{"key":"e_1_2_7_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/21.101139"},{"key":"e_1_2_7_17_2","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello S.","year":"1990"},{"key":"e_1_2_7_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.1.86"},{"key":"e_1_2_7_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.09.016"},{"key":"e_1_2_7_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591863"},{"key":"e_1_2_7_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.45.3.414"}],"container-title":["Mathematical Problems in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/mpe\/2012\/504713.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/mpe\/2012\/504713.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2012\/504713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T05:41:55Z","timestamp":1718170915000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2012\/504713"}},"subtitle":[],"editor":[{"given":"Piermarco","family":"Cannarsa","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1155\/2012\/504713"],"URL":"https:\/\/doi.org\/10.1155\/2012\/504713","archive":["Portico"],"relation":{},"ISSN":["1024-123X","1563-5147"],"issn-type":[{"value":"1024-123X","type":"print"},{"value":"1563-5147","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-08-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"504713"}}