scientific article; zbMATH DE number 3906236
The following problem P is considered: (1.1) \(\sum_{j\in I}c_ jx_ j\to \max\), (1.2) \(\sum_{j\in I}a_ jx_ j\leq b\), (1.3) \(\sum_{j\in G_ i}x_ j=1\) \((i=1,...,q)\), (1.4) \(x_ j\leq 1\) (j\(\in K)\), (1.5) \(x_ j\geq 0\) (j\(\in I)\), (1.6) \(x_ j\leq U_ j\) (j\(\in R)\), (1.7) \(x_ j\) integer (j\(\in G\cup K)\), where \(I=\{1,...,n\}\), \(\cup^{q}_{i=1}G_ i=G\subseteq I\), \(K\subseteq I\), \(R\subseteq I\), the sets \(G_ i\) \((i=1,...,q)\), K and R are mutually exclusive. The paper presents some important properties of optimal solutions to problem P and to its linear relaxation LP, gives a solution method for the problem LP and for the approximate solution of problem P, and a procedure for an a priori analysis to reduce the dimension. As conclusion a computationally efficient multistage solution procedure is outlined: (1.) Problem P is solved for an approximate solution, which gives a lower bound to the optimal value of the criterion. (2.) Problem LP is solved (analytically). (3.) The procedure for the a priori analysis of problem P is applied. This includes solution of LP (\(| G|\) times) under additional assumption \(x_ j=\alpha\), where \(j\in G\), \(\alpha\in \{0,1\}\) and for each j the value of \(\alpha\) is defined from the solution of step 2. As a result the optimal values of a part of the binary variables are determined and the dimension of problem P is reduced. (4.) The reduced problem P is solved by means of a dynamic programming algorithm.
- Exact methods for the knapsack problem and its generalizations
- Extending Dantzig's bound to the bounded multiple-class binary knapsack problem
- Global optimization and multi knapsack: a percolation algorithm.
- On the product knapsack problem
- Mathematical models and decomposition methods for the multiple knapsack problem
- Knapsack problems with dependencies through non-additive measures and Choquet integral
- Some new results on multi-dimension Knapsack problem
- A dynamic programming approach to the multiple-choice multi-period, knapsack problem and the recursive APL2 code
- scientific article; zbMATH DE number 4191398 (Why is no real title available?)
- Piecewise convex maximization approach to multiknapsack
- scientific article; zbMATH DE number 3984973 (Why is no real title available?)
- scientific article; zbMATH DE number 4005978 (Why is no real title available?)
- Decentralized decision‐making involving multiple criteria: a multiple knapsack formulation
- STRUCTURE OF OPTIMAL SOLUTIONS OF A KNAPSACK PROBLEM SUBJECT TO A GIVEN TOTAL NUMBER OF VARIABLES USED
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- The knapsack problem with disjoint multiple-choice constraints
- A multi-period renewal equipment problem
- scientific article; zbMATH DE number 2010048 (Why is no real title available?)
- The multiple-choice multi-period knapsack problem
- On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint
- Method for solving the Backpack Problem with an additional restriction on the number of items types
- Multiple criteria dynamic programming and multiple knapsack problem
- Algorithm for solving the knapsack problem with certain properties of Pareto layers
- A multi-criteria approach to approximate solution of multiple-choice knapsack problem
- The linking set problem: a polynomial special case of the multiple-choice knapsack problem
- A solution procedure for general knapsack problems with a few constraints
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683899)