A multi-criteria approach to approximate solution of multiple-choice knapsack problem (Q721960): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Normalize DOI.
 
(7 intermediate revisions by 7 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s10589-018-9988-z / rank
Normal rank
 
Property / describes a project that uses
 
Property / describes a project that uses: Knapsack / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2964091621 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1712.06723 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls / rank
 
Normal rank
Property / cites work
 
Property / cites work: A ``reduce and solve'' approach for the multiple-choice multidimensional knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A column generation method for the multiple-choice multi-dimensional knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A fast algorithm for the linear multiple-choice knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact methods for the knapsack problem and its generalizations / rank
 
Normal rank
Property / cites work
 
Property / cites work: A branch and bound algorithm for solving the multiple-choice knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: An O(n) algorithm for the multiple-choice knapsack linear program / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multicriteria Optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hard multidimensional multiple choice knapsack problems, an empirical study / rank
 
Normal rank
Property / cites work
 
Property / cites work: Heuristic algorithms for the multiple-choice multidimensional knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: New trends in exact algorithms for the \(0-1\) knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constrained optimization using multiple objective programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3993418 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nonlinear multiobjective optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: The 0-1 knapsack problem with multiple choice constraints / rank
 
Normal rank
Property / cites work
 
Property / cites work: A minimal algorithm for the multiple-choice knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Avoiding anomalies in the \(MT2\) algorithm by Martello and Toth / rank
 
Normal rank
Property / cites work
 
Property / cites work: Budgeting with bounded multiple-choice constraints. / rank
 
Normal rank
Property / cites work
 
Property / cites work: A best first search exact algorithm for the multiple-choice multidimensional knapsack problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Multiple-Choice Knapsack Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: An O(n) algorithm for the linear multiple choice knapsack problem and related problems / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S10589-018-9988-Z / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 02:03, 10 December 2024

scientific article
Language Label Description Also known as
English
A multi-criteria approach to approximate solution of multiple-choice knapsack problem
scientific article

    Statements

    A multi-criteria approach to approximate solution of multiple-choice knapsack problem (English)
    0 references
    0 references
    0 references
    0 references
    20 July 2018
    0 references
    Given sets \(N_{1},\dots, N_{k}\) of items with cardinalities \(|N_{i}|=n_{i}\) for \(i=1,\dots,k\), profits \(p_{ij} \geq 0\) and costs \(c_{ij} \geq 0\) for \(i=1,\dots,k\), \(j=1,\dots, n_{i}\), the multiple choice knapsack problem (MCKP) consists in choosing exactly one item from each set \(N_{i}\) so that the total cost does not exceed a given bound \(b \geq 0\) and the total profit is maximized. The authors present a method to find approximate solutions to the MCKP which consists in transforming the MCKP into a bi-objective optimization problem (BP), a linear scalarization of which, (BS(\(\lambda\))), allowing to be solved explicitly by a closed-form formula. The method is tested on large-scale, uncorrelated and weakly-correlated problem instances, and the results show that the optimal value of the MCKP is approximated by an accuracy comparable to that of the greedy algorithm.
    0 references
    knapsack
    0 references
    multi-objective optimization
    0 references
    multiple-choice knapsack
    0 references
    linear scalarization
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references