An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane
type: Item
instance of: scholarly article
title: An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane
zbMATH Open document ID: 1120.90033
author: Pei Wang Gao
published in: Applied Mathematics and Computation
publication date: 2007-03-12T00:00:00Z
review text: Previous algorithms for solving the general integer linear programming problem often involve the solution of linear programs and have significant memory requirement in the heuristic search process. This paper considers practical algorithms for solving the integer programming problem. The value ranges of the variables in the convex polyhedron of the feasible region of the linear programming relaxation problem intercepted by the objective function hyperplane are established. An efficient heuristic algorithm is presented for finding an optimal solution or showing that there is no feasible solution to the integer programming problem on the objective function hyperplane. The algorithm does not need to solve any linear programming subproblems. The memory requirements of the algorithm change linearly with the size of the problem. Computational results on some numerical problems show that the proposed algorithm is more efficient than the stopped simplex method of Thompson and the all-integer method of Gomory.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 5132918
zbMATH Keywords: linear programming
zbMATH Keywords: integer linear programming
zbMATH Keywords: simplex method
zbMATH Keywords: bound-and-stopped algorithm
MaRDI profile type: Publication
full work available at URL: j.amc.2006.06.100
OpenAlex ID: W2002374099
cites work: Letter to the Editor—A Note on the Branch-and-Bound Principle
cites work: Gomory cuts revisited
cites work: Cutting planes for integer programs with general integer variables
cites work: Q3844775
cites work: The Accelerated Bound-and-Scan Algorithm for Integer Programming
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: Lagrangean Decomposition In Integer Linear Programming: A New Scheme
cites work: Parametric formulation of the general integer linear programming problem
cites work: A computational study of an objective hyperplane search heuristic for the general integer linear programming problem
cites work: An Automatic Method of Solving Discrete Programming Problems
cites work: Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems
cites work: Q5730600
cites work: DNA solution of integer linear programming
DOI: 10.1016/J.AMC.2006.06.100
description: scientific article; zbMATH DE number 5132918