An exact algorithm for bilevel 0-1 knapsack problems
type: Item
instance of: scholarly article
title: An exact algorithm for bilevel 0-1 knapsack problems
zbMATH Open document ID: 1264.90149
DOI: 10.1155/2012/504713
author: Raïd Mansi
author: Cláudio Alves
author: Saïd Hanafi
author: José Valério de Carvalho
published in: Mathematical Problems in Engineering
publication date: 2013-06-11T00:00:00Z
review text: Summary: We propose a new exact method for solving bilevel 0-1 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 must 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-1 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 report on computational experiments which are compared with the results achieved with other state-of-the-art approaches. The results attest the performance of our approach.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 6173340
describes a project that uses: Knapsack
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/504713
OpenAlex ID: W2041998819
cites work: Mathematical Programs with Optimization Problems in the Constraints
cites work: Q4332850
cites work: Foundations of bilevel programming
cites work: Bilevel programming: a survey
cites work: Bilevel programming with knapsack constraints
cites work: Q4434989
cites work: A dynamic programming algorithm for the bilevel Knapsack problem
cites work: The Mixed Integer Linear Bilevel Programming Problem
cites work: One-level reformulation of the bilevel Knapsack problem using dynamic programming
cites work: Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints
cites work: A trust region algorithm for nonlinear bilevel programming
cites work: On a stochastic bilevel programming problem
cites work: Q3989989
cites work: Weak via strong Stackelberg problem: New results
cites work: Q3993418
cites work: Pivot and Complement–A Heuristic for 0-1 Programming
cites work: Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
cites work: Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
cites work: Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
Wikidata QID: Q58911904
Recommended article: On exact solution approaches for bilevel quadratic 0-1 knapsack problem
Recommended article: Exact algorithm for bi-objective 0-1 knapsack problem
Recommended article: An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
Recommended article: An exact algorithm for 0-1 polynomial Knapsack problems
Recommended article: An exact algorithm for the 0-1 collapsing knapsack problem
Recommended article: Approximation algorithms for a bi-level knapsack problem
Recommended article: Approximation Algorithms for a Bi-level Knapsack Problem
Recommended article: A Complexity and Approximability Study of the Bilevel Knapsack Problem
Recommended article: Exact solution approach for a class of nonlinear bilevel knapsack problems
Recommended article: An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable
description: scientific article; zbMATH DE number 6173340