A revised bound improvement sequence algorithm

DOI10.1016/0377-2217(88)90426-2MaRDI QIDQ1102193zbMATH OpenOpenAlexFDO

Authors Paulo Barcia, Søren Holm

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0377-2217(88)90426-2

zbMATH Keywords

Bound Improvement Sequence Algorithmcomputational improvementcomputational resultsfixed pointsLagrange multipliers

Mathematics Subject Classification ID

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

Review text

We present a generalization and a computational improvement of the Bound Improvement Sequence Algorithm. The main computational burden of this algorithm consists in determining whether there exists a feasible point on the objective hyperplane, when the algorithm encounters a fixed point. By generalizing the algorithm, such that the objective function and constraints are treated alike, the number of fixed points that are required can be reduced. The computational results that we report allow us to conclude that the number of fixed points can generally be reduced for loosely constrained problems. For this class of problems the new algorithm appears to be more efficient than a standard MIP code such as FMPS.

Recommendations

• The bound improving sequence algorithm
• An interval branch and bound algorithm for bound constrained optimization problems
• Principles and Practice of Constraint Programming – CP 2004
• Publication:4504439
• A branch-and-bound algorithm for solving fixed charge problems

Cites work

• Constructive dual methods for discrete programming
• Heuristic algorithms for the multiple knapsack problem
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3793779 (Why is no real title available?)
• The bound improving sequence algorithm

Cited in

(6)

• The bound improving sequence algorithm
• A survey of algorithms for the generalized assignment problem
• A bound-improving approach to discrete programming problems
• The multidimensional 0-1 knapsack problem: an overview.
• Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
• Improved Lagrangean decomposition: An application to the generalized assignment problem

This page was built for publication: A revised bound improvement sequence algorithm

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