Zero-one integer programs with few constraints - Efficient branch and bound algorithms
type: Item
instance of: scholarly article
title: Zero-one integer programs with few constraints - Efficient branch and bound algorithms
zbMATH Open document ID: 0588.90060
DOI: 10.1016/0377-2217(85)90113-4
author: Bezalel Gavish
author: Hasan Pirkul
published in: European Journal of Operational Research
publication date: 1985-01-01T00:00:00Z
review text: The 0-1 integer programming problem and its special case, the 0-1 knapsack problem are frequently encountered in modeling various design and decision making processes. This paper is a follow-up paper to an earlier paper of the authors [ibid. 21, 213-224 (1985; Zbl 0569.90057)] and deals with the development of an effective solution procedure for 0-1 integer programs with few constraints. Detailed computational experiments are carried out and different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with previously developed optimal algorithms. It is suggested that this procedure may also be used as a heuristic method for large problems by early termination of the tree search. This scheme is tested and found to be very effective.
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3945877
zbMATH Keywords: surrogate relaxation
zbMATH Keywords: 0-1 knapsack problem
zbMATH Keywords: few constraints
zbMATH Keywords: computational experiments
zbMATH Keywords: branch and bound procedure
describes a project that uses: SCICONIC
MaRDI profile type: Publication
full work available at URL: 0377-2217(85)90113-4
OpenAlex ID: W2029446116
cites work: An Algorithm for Large Zero-One Knapsack Problems
cites work: Zero-one integer programs with few contraints - lower bounding theory
cites work: New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
cites work: An upper bound for the zero-one knapsack problem and a branch and bound algorithm
cites work: A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
description: scientific article; zbMATH DE number 3945877