Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

DOI10.1007/BF02591863zbMath0571.90065MaRDI QIDQ3688105

Hasan Pirkul, Bezalel Gavish

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

computational experimentsbranch and boundrelaxationssolution proceduremultiple resource constraintsmulticonstraint 0-1 knapsack problemsurrogate bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Boolean programming (90C09)

Related Items

An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem ⋮ Tabu search for nonlinear and parametric optimization (with links to genetic algorithms) ⋮ An integer programming model for the allocation of databases in a distributed computer system ⋮ On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming ⋮ Dynamic tabu list management using the reverse elimination method ⋮ Part type selection problem in flexible manufacturing systems: Tabu search algorithms ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ A surrogate heuristic for set covering problems ⋮ Optimization by ghost image processes in neural networks ⋮ Surrogate Constraints in Integer Programming ⋮ An improved enumeration for pure 0-1 programs ⋮ Heuristics for the multi-resource generalized assignment problem ⋮ Une approche hybride pour le sac à dos multidimensionnel en variables 0–1 ⋮ A simulated annealing approach to the multiconstraint zero-one knapsack problem ⋮ Surrogate duality in a branch-and-bound procedure for integer programming ⋮ An improved typology of cutting and packing problems ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ MineReduce: an approach based on data mining for problem size reduction ⋮ An algorithm to perform a complete right-hand-side parametrical analysis for a 0-1-integer linear programming problem ⋮ Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach ⋮ Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ Lagrangean decomposition: A model yielding stronger lagrangean bounds ⋮ Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem ⋮ Capacity allocation problem with random demands for the rail container carrier ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ A fuzzy genetic algorithm based on binary encoding for solving multidimensional knapsack problems ⋮ An exact algorithm for bilevel 0-1 knapsack problems ⋮ Intelligent water drops algorithm ⋮ Modeling multiple plant sourcing decisions ⋮ A surrogate and Lagrangian approach to constrained network problems ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben ⋮ Solving the Knapsack problem with imprecise weight coefficients using genetic algorithms ⋮ Essential particle swarm optimization queen with tabu search for MKP resolution ⋮ A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles ⋮ A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem ⋮ Bringing order into the neighborhoods: Relaxation guided variable neighborhood search ⋮ Configuration of fully replicated distributed database system over wide area networks ⋮ A survey of algorithms for the generalized assignment problem ⋮ Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem ⋮ Analysis of maximum total return in the continuous knapsack problem with fuzzy object weights ⋮ A multi-level search strategy for the 0-1 multidimensional knapsack problem ⋮ NeuroGenetic approach for combinatorial optimization: an exploratory analysis ⋮ An efficient algorithm to allocate shelf space ⋮ Very large-scale neighborhood search for the \(K\)-constraint multiple knapsack problem ⋮ Improved results on the 0--1 multidimensional knapsack problem ⋮ A tabu search algorithm for the routing and capacity assignment problem in computer networks ⋮ Using fuzzy numbers in knapsack problems ⋮ Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ A trust branching path heuristic for zero-one programming ⋮ CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem ⋮ Future paths for integer programming and links to artificial intelligence ⋮ Piecewise convex maximization approach to multiknapsack ⋮ A contraction for the multiparametric integer linear programming problem ⋮ Heuristics for the 0-1 multidimensional knapsack problem ⋮ An algorithm for the multiparametric 0--1-integer linear programming problem relative to the objective function ⋮ Addressing capacity uncertainty in resource-constrained assignment problems ⋮ An algorithm for the multiparametric 0-1-integer linear programming problem relative to the constraint matrix ⋮ An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem ⋮ An algorithm to perform a complete parametric analysis relative to the constraint matrix for a 0-1-integer linear program ⋮ A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems ⋮ An efficient tabu search approach for the 0-1 multidimensional knapsack problem ⋮ On generalized surrogate duality in mixed-integer nonlinear programming ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects ⋮ An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual

Uses Software

• SCICONIC

Cites Work

• Unnamed Item
• Unnamed Item
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Zero-one programming with many variables and few constraints
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• Some relationships between lagrangian and surrogate duality in integer programming
• A Dual-Based Procedure for Uncapacitated Facility Location
• New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
• Pivot and Complement–A Heuristic for 0-1 Programming
• An Algorithm for Large Zero-One Knapsack Problems
• Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
• Calculating surrogate constraints
• Topological design of centralized computer networks—formulations and algorithms
• Reduction Algorithm for Zero-One Single Knapsack Problems
• The knapsack problem: A survey
• Surrogate Constraint Duality in Mathematical Programming
• Computing Partitions with Applications to the Knapsack Problem
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Computational results with a branch-and-bound algorithm for the general knapsack problem
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Validation of subgradient optimization
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• The Theory and Computation of Knapsack Functions
• An Enumeration Algorithm for Knapsack Problems
• Quasi-Convex Programming
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Surrogate Mathematical Programming
• The Generalized Penalty-Function/Surrogate Model