A minimal algorithm for the multiple-choice knapsack problem

DOI10.1016/0377-2217(95)00015-IzbMath0904.90143OpenAlexW2086168649WikidataQ58826519 ScholiaQ58826519MaRDI QIDQ1388832

Publication date: 11 June 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00015-i

zbMATH Keywords

partitioning dynamic programming reduction knapsack problem multiple-choice knapsack problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Dynamic programming (90C39) Boolean programming (90C09)

Related Items (56)

Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation ⋮ An experimental study of random knapsack problems ⋮ Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ Integer optimization with penalized fractional values: the knapsack case ⋮ Matroid and knapsack center problems ⋮ Admission control in computer networks with uncertain parameters ⋮ The linking set problem: a polynomial special case of the multiple-choice knapsack problem ⋮ A comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0–1 knapsack problem using the integer programming option of CPLEX^® ⋮ A generalization of column generation to accelerate convergence ⋮ A branch-cut-and-price algorithm for the piecewise linear transportation problem ⋮ A versatile algorithm for assembly line balancing ⋮ Robust efficiency measures for linear knapsack problem variants ⋮ A cross entropy algorithm for the Knapsack problem with setups ⋮ A genetic algorithm for the retail shelf space allocation problem with virtual segments ⋮ Hybrid approaches for the two-scenario max-min knapsack problem ⋮ The one dimensional Compartmentalised Knapsack problem: a case study ⋮ An integrated cutting stock and sequencing problem ⋮ Simple but efficient approaches for the collapsing knapsack problem ⋮ A stochastic approach to handle resource constraints as knapsack problems in ensemble pruning ⋮ A minimal algorithm for the multiple-choice knapsack problem ⋮ An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem ⋮ A minimal algorithm for the Bounded Knapsack Problem ⋮ On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization ⋮ An improved binary search algorithm for the Multiple-Choice Knapsack Problem ⋮ Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm ⋮ Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach ⋮ Optimal bandwidth allocation for bandwidth adaptation in wireless multimedia networks. ⋮ A QoS-aware composition method supporting cross-platform service invocation in cloud environment ⋮ Improved lower bounds for the capacitated lot sizing problem with setup times. ⋮ Optimal sequential inspection policies ⋮ The inverse \(\{0,1\}\)-knapsack problem: theory, algorithms and computational experiments ⋮ A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints ⋮ Qos-aware service evaluation and selection ⋮ A DYNAMIC PROGRAMMING HEURISTIC FOR RETAIL SHELF SPACE ALLOCATION PROBLEM ⋮ A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive APL2 code ⋮ A best first search exact algorithm for the multiple-choice multidimensional knapsack problem ⋮ SALSA: combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing ⋮ Budgeting with bounded multiple-choice constraints. ⋮ Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems ⋮ A Decentralized Heuristic for Multiple-Choice Combinatorial Optimization Problems ⋮ A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem ⋮ Efficient heuristic algorithms for path-based hardware/software partitioning ⋮ A two-stage vehicle routing model for large-scale bioterrorism emergencies ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem ⋮ On the importance of variability when managing metrology capacity ⋮ Single Commodity Stochastic Network Design Under Probabilistic Constraint with Discrete Random Variables ⋮ Random knapsack in expected polynomial time ⋮ A 0-1 knapsack model for evaluating the possible electoral college performance in two-party US presidential elections ⋮ Algorithmic aspects for power-efficient hardware/software partitioning ⋮ An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core ⋮ A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem ⋮ Knapsack problems with setups ⋮ Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core ⋮ Solving the selective multi-category parallel-servicing problem

Uses Software

Cites Work

This page was built for publication: A minimal algorithm for the multiple-choice knapsack problem