An improved enumeration for pure 0-1 programs

DOI10.1080/02331939108843664MaRDI QIDQ3978584zbMATH OpenOpenAlexFDO

Authors Jürgen Sommerschuh

Publication date 25 June 1992

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939108843664

zbMATH Keywords

branch and boundenumerationLP relaxation

Mathematics Subject Classification ID

Numerical methods of relaxation type (49M20) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05) Boolean programming (90C09) Integer programming (90C10)

Review text

The paper presents a contribution to the enumeration method for solving pure 0-1 linear programming problems. The approach is based on LP relaxation and a subsequent branch and bound scheme. It employs a reduction idea for the variables not fixed yet. To achieve this, it uses information obtainable from the optimal simplex tableau belonging to the current node of the branch and bound tree. Some numerical experiences are also presented that suggest an improvement in performance over a previous algorithm of the author.

Recommendations

• scientific article; zbMATH DE number 3585214
• Implicit Enumeration for the Pure Integer 0/1 Minimax Programming Problem
• scientific article; zbMATH DE number 1094193
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Solving \(0/1\) integer programs with enumeration cutting planes

Cites work

• An algorithm for the 0/1 Knapsack problem
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• Reduction Algorithm for Zero-One Single Knapsack Problems
• Some computational results on real 0-1 knapsack problems
• Technical Note—An Improved Branch-and-Bound Method for Integer Programming
• Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben
• Verzweigungsstrategien in branch and bound-algorithmen für gemischt-ganzzahlige lineare 0-1-optimierungsanfgaben

Cited in

(4)

• Octane: A New Heuristic for Pure 0–1 Programs
• scientific article; zbMATH DE number 3585214 (Why is no real title available?)
• Implicit Enumeration for the Pure Integer 0/1 Minimax Programming Problem
• A Refinement of the μ-measure for Stack Programs

This page was built for publication: An improved enumeration for pure 0-1 programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978584)