An Algorithm for Large Zero-One Knapsack Problems
From MaRDI portal
Publication:3896840
DOI10.1287/opre.28.5.1130zbMath0449.90064OpenAlexW2017316844MaRDI QIDQ3896840
Publication date: 1980
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.28.5.1130
algorithmcomputational experiencerandomly generated test problemshard knapsack problemsbinary search-type procedurelarge zero-one knapsack problemsproblem coresimple heuristic
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Boolean programming (90C09)
Related Items
Sensitivity Analysis to Perturbations of the Weight of a Subset of Items: The Single Knapsack Case Study, Dantzig-Wolfe reformulations for binary quadratic problems, Optimal experimental design for combinatorial problems, An efficient heuristic method for the simple assembly line balancing problem, Optimal algorithms for some inverse uncapacitated facility location problems on networks, An experimental study of random knapsack problems, A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances, A new class of hard problem instances for the 0-1 knapsack problem, Exact algorithms for the 0-1 time-bomb knapsack problem, Hybrid approaches for the two-scenario max-min knapsack problem, Optimal approaches for upgrading selective obnoxious \(p\)-median location problems on tree networks, The cardinality constrained inverse center location problems on tree networks with edge length augmentation, The replenishment problem with multiple articles and an order threshold, A polynomial algorithm for a continuous bilevel knapsack problem, Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, A minimal algorithm for the Bounded Knapsack Problem, A novel reformulation for the single-sink fixed-charge transportation problem, The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights, Integer knapsack problems with profit functions of the same value range, The max-sum inverse median location problem on trees with budget constraint, A Dynamic Programming Heuristic for the Quadratic Knapsack Problem, Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem, Computational aspects of the inverse single facility location problem on trees under \(l_k\)-norm, On Bilevel Optimization with Inexact Follower, Two-row and two-column mixed-integer presolve using hashing-based pairing methods, Designing a minimal spanning tree network subject to a budget constraint, Solving a class of multiplicative programs with 0-1 knapsack constraints, Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben, Multivariate composite distributions for coefficients in synthetic optimization problems, Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem, Algorithms for solving the single-sink fixed-charge transportation problem, An optimization algorithm for a penalized knapsack problem, Two-machine open shop problem with controllable processing times, A best first search exact algorithm for the multiple-choice multidimensional knapsack problem, Core problems in bi-criteria \(\{0,1\}\)-knapsack problems, AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints, Solving TSP through the Integration of OR and CP Techniques, An O(n) algorithm for the multiple-choice knapsack linear program, Some polynomially solvable cases of the inverse ordered 1-median problem on trees, Verzweigungsstrategien in branch and bound-algorithmen für gemischt-ganzzahlige lineare 0-1-optimierungsanfgaben, Budgeting with bounded multiple-choice constraints., Evolution of new algorithms for the binary knapsack problem, An exact algorithm for the knapsack sharing problem, On the complexity of the continuous unbounded knapsack problem with uncertain coefficients, An efficient algorithm for the collapsing knapsack problem, Unnamed Item, A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric, A linear-time algorithm for solving continuous maximin knapsack problems, Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis, An exact algorithm for the subset sum problem, A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem, Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems, Linear Time Optimal Approaches for Max-Profit Inverse 1-Median Location Problems, Random knapsack in expected polynomial time, Shop scheduling problems with pliable jobs, A model for the inverse 1-median problem on trees under uncertain costs, An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core, A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem, CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem, Presolve Reductions in Mixed Integer Programming, The continuous knapsack problem with capacities, An algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions, Scheduling divisible loads with time and cost constraints, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Heuristic methods and applications: A categorized survey, Exact Solution Methods for the k-Item Quadratic Knapsack Problem, Inverse 1-median problem on trees under mixed rectilinear and Chebyshev norms, Combinatorial algorithms for the uniform-cost inverse 1-center problem on weighted trees, The multiobjective multidimensional knapsack problem: a survey and a new approach, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Approximation algorithms for fractional knapsack problems, A reduction dynamic programming algorithm for the bi-objective integer knapsack problem, An exact algorithm for the 0-1 collapsing knapsack problem, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Some computational results on real 0-1 knapsack problems, The inverse connected \(p\)-median problem on block graphs under various cost functions, Exact methods for the knapsack problem and its generalizations, An integer programming model for the allocation of databases in a distributed computer system, Inverse 1-median problem on block graphs with variable vertex weights, The reduced cost branch and bound algorithm for mixed integer programming, Efficient algorithms for the capacitated concentrator location problem, Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem, Comment on 'Some computational results on real 0-1 knapsack problems', The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation, A surrogate heuristic for set covering problems, A new enumeration scheme for the knapsack problem, A simulated annealing approach to the multiconstraint zero-one knapsack problem, Robust efficiency measures for linear knapsack problem variants, Constructive dual methods for discrete programming, Exact approaches for the knapsack problem with setups, On the product knapsack problem, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, Simple but efficient approaches for the collapsing knapsack problem, An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks, Continuous location of an assembly station, An improved direct descent algorithm for binary knapsack problems, A simple linear time algorithm for scheduling with step-improving processing times, Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem, The knapsack problem with generalized upper bounds, Uniqueness of integer solution of linear equations, An exact algorithm for large multiple knapsack problems, Pre-emptive scheduling problems with controllable processing times, An approximation algorithm for solving unconstrained two-dimensional knapsack problems, Some thoughts on combinatorial optimisation, A minimal algorithm for the multiple-choice knapsack problem, The bottleneck generalized assignment problem, Avoiding anomalies in the \(MT2\) algorithm by Martello and Toth, An expanding-core algorithm for the exact \(0-1\) knapsack problem, On minimal realisations of dynamical structure functions, Upgrading \(p\)-median problem on a path, A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems, Inverse median location problems with variable coordinates, Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem, Heuristics and their design: A survey, Kernel search: a new heuristic framework for portfolio selection, An algorithm for the solution of the 0-1 knapsack problem, An exact algorithm for large unbounded knapsack problems, Inverse 1-median problem on trees under weighted Hamming distance, The multidimensional 0-1 knapsack problem: an overview., On search over rationals, Exact and heuristic solution approaches for the mixed integer setup knapsack problem, An appraisal of computational complexity for operations researchers, Capacitated assortment and price optimization for customers with disjoint consideration sets, Qos-aware service evaluation and selection, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics, Reverse 2-median problem on trees, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem, Mathematical models and decomposition methods for the multiple knapsack problem, An incomplete \(m\)-exchange algorithm for solving the large-scale multi-scenario knapsack problem, Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems, Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem, Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem, Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem, Measuring instance difficulty for combinatorial optimization problems, A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem, A column generation method for the multiple-choice multi-dimensional knapsack problem, Kernel search: a general heuristic for the multi-dimensional knapsack problem, Dynamic generalized assignment problems with stochastic demands and multiple agent-task relationships, Where are the hard knapsack problems?, A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over, Efficient heuristic algorithms for path-based hardware/software partitioning, Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study, Undesirable facility location with minimal covering objectives, Formulating and solving production planning problems, Solving dense subset-sum problems by using analytical number theory, On a cardinality constrained linear programming knapsack problem, Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem, 0-1 reformulations of the multicommodity capacitated network design problem, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, Real-time task reallocation in fault-tolerant distributed computer systems, A fast algorithm for strongly correlated knapsack problems, New trends in exact algorithms for the \(0-1\) knapsack problem, An exact method for the two-echelon, single-source, capacitated facility location problem, New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems, A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem, Knapsack problems with setups, Inverse 1-center location problems with edge length augmentation on trees, An effective heuristic for large-scale capacitated facility location problems, Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, A heuristic algorithm for the multidimensional zero-one knapsack problem, A fast algorithm for the linear multiple-choice knapsack problem, Zero-one integer programs with few contraints - lower bounding theory, The stochastic linear continuous type knapsack problem: A generalized P model, Zero-one integer programs with few constraints - Efficient branch and bound algorithms, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual
