Integer Programming Algorithms: A Framework and State-of-the-Art Survey
Management SciencePublished 1 May 1972
Arthur M. Geoffrion, Roy E. Marsten
Citations353
SJR quartileQ1
SJR score5.72
SNIP2.88
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A unifying framework is developed to facilitate the understanding of most known computational approaches to integer programming, and a number of currently operational algorithms are related to this framework.
Abstract
A unifying framework is developed to facilitate the understanding of most known computational approaches to integer programming. A number of currently operational algorithms are related to this framework, and prospects for future progress are assessed.
Keywords
Computer ScienceMathematics
An Automatic Method for Solving Discrete Programming Problems
1,997 Citations2009A. H. Land, Alison Doig
Operations ResearchBranch-and-Bound Methods: A Survey
1,982 Citations1966Eugene L. Lawler, Derek Wood
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees
1,443 Citations1970Michael Held, Richard M. Karp
It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.
IEEE Transactions on Systems Man and CyberneticsOptimization Theory of Large Systems
1,237 Citations1971Leon S. Lasdon, Daniel Tabak
Operations ResearchAn Algorithm for the Traveling Salesman Problem
1,049 Citations1963John D. C. Little, Katta G. Murty +2 more
A “branch and bound” algorithm is presented for solving the traveling salesman problem, where the set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching.
International series in management science/operations research/International series in operations research & management scienceMulticommodity Distribution System Design by Benders Decomposition * † ‡
983 Citations2010Arthur M. Geoffrion, G. W. Graves§
Operations ResearchAn Additive Algorithm for Solving Linear Programs with Zero-One Variables
705 Citations1965Egon Balas
The Computer JournalA tree-search algorithm for mixed integer programming problems
638 Citations1965R. J. Dakin
Management ScienceInteger Programming: Methods, Uses, Computations
621 Citations1965Michel Balinski
This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems, as well as some special purpose algorithms for use on highly structured problems.
Ökonometrie und UnternehmensforschungBoolean Methods in Operations Research and Related Areas
520 Citations1968Peter L. Hammer, Sergiu Rudeanu
Linear Algebra and its ApplicationsSome polyhedra related to combinatorial problems
392 Citations1969Ralph E. Gomory
Operations ResearchBranch-and-Bound Methods: General Formulation and Properties
331 Citations1970L. G. Mitten
Discrete programming, which includes integer programming and combinatorial optimization problems, is discussed and Fibonacci search is presented as an example of a nonfinite branch-and-bound procedure employing an optimal convergence rule.
Operations ResearchA Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
328 Citations1965Fred Glover
The algorithm of this paper is based upon an underlying tree-search structure upon which a series of tests is superimposed to exclude large portions of the tree of all possible 0-1 solutions from examination, resulting in an algorithm that appears to be quite efficient in relation to other algorithms currently available for solving the0-1 integer programming problem.
Mathematical ProgrammingExperiments in mixed-integer linear programming
300 Citations1971M. Benichou, J. M. Gauthier +4 more
The heuristic rules for generating the tree, which are the main features of the method, are presented and numerous parameters allow the user for adjusting the search strategy to a given problem.
Mathematical ProgrammingSome continuous functions related to corner polyhedra
245 Citations1972Ralph E. Gomory, Ellis L. Johnson
It is shown how faces previously generated and those given here can be used to give valid inequalities for any integer program.
Operations ResearchAn Improved Implicit Enumeration Approach for Integer Programming
231 Citations1969Arthur M. Geoffrion
This paper synthesizes the Balasian implicit enumeration approach to integer linear programming with the approach typified by Land and Doig and by Roy, Bertier, and Nghiem and suggests that use of the imbedded linear program in the prescribed way may mitigate solution-time dependence on the number of variables from an exponential to a low-order polynomial increase.
SIAM ReviewInteger Programming by Implicit Enumeration and Balas’ Method
221 Citations1967Arthur M. Geoffrion
The present reformulation of the essentials of Balas' algorithm for the zero-one integer linear programming problem is based upon the idea of 'elementary tree search' that has been used by Glover as the basis for his multiphase-dual algorithm.
Proceedings of the National Academy of SciencesON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
199 Citations1965Ralph E. Gomory
Naval Research Logistics QuarterlyA branch‐bound algorithm for the capacitated facilities location problem
185 Citations1969Peter Davis, T. L. Ray
Management ScienceAn Algorithm for the Solution of Mixed Integer Programming Problems
140 Citations1966Norman J. Driebeek
An algorithm is presented for the solution of mixed integer programming problems which contain a large number of continuous variables in addition to a few variables that are restricted to discrete values.
Management ScienceOptimum Seeking with Branch and Bound
110 Citations1966Norman Agin
A generalized description of branch and bound algorithms to demonstrate the wide applicability to combinatorial problems in general is provided.
Operations ResearchDirect Search Algorithms for Zero-One and Mixed-Integer Programming
110 Citations1967C. E. Lemke, Kurt Spielberg
A method of solution for the mixed integer-programming problem is proposed, based on an exhaustive search of the integer variables, coupled with an efficient use of the product form of the basis matrix inverse, for the linear programming calculations.
Management ScienceApplication of Combinatorial Programming to a Class of All-Zero-One Integer Programming Problems
97 Citations1968J.F. Pierce
Transportation ScienceInteger Programming Methods for a Vessel Scheduling Problem
97 Citations1971Leif Appelgren
Operations ResearchDynamic Programming Algorithms for the Integer Programming Problem—I: The Integer Programming Problem Viewed as a Knapsack Type Problem
75 Citations1968Jeremy F. Shapiro
Gomory has transformed the integer programming problem into a related group optimization problem which can be more easily solved and extended by amending it to find alternative optima.
Operations ResearchTechnical Note—An Improved Branch-and-Bound Method for Integer Programming
74 Citations1971John A. Tomlin
Two extensions of the successful Beale and Small branch-and-bound mixed-integer algorithm are proposed, utilizing the integer requirements on nonbasic variables to calculate stronger "penalties" when searching down the solution tree and to give a stronger criterion for abandoning unprofitable branches of the tree when backtracking.
Operations ResearchGeneralized Lagrange Multipliers in Integer Programming
71 Citations1971Jeremy F. Shapiro
This paper combines the theory of generalized Lagrange multipliers with a reformulation of the integer-programming problem due to group theory for generalized linear programming as suggested by Brooks and Geoffrion and is shown to be closely related to the cutting-plane method of Gomory.
Management ScienceAn Adaptive Group Theoretic Algorithm for Integer Programming Problems
50 Citations1971G. Anthony Gorry, Jeremy F. Shapiro
Group theory is used to integrate a wide variety of integer programming methods into a common computational process, Included are group optimization algorithms, Lagrangian methods, the cutting plane method, and the method of surrogate constraints.
Operations ResearchA Branch-and-Bound Algorithm for Zero-One Mixed Integer Programming Problems
42 Citations1971R.E. Davis, David A. Kendrick +1 more
This paper presents the results of experimentation on the development of an efficient branch-and-bound algorithm for the solution of zero-one linear mixed integer programming problems and a comparison with the computational experience obtained with several other algorithms on a number of problems.
Operations ResearchLetter to the Editor—Computational Experience with the Algorithm of Balas
39 Citations1967Bernhard Fleischmann
This note reports on the application of the Balas algorithm for linear programs with zero-one variables on larger problems involving up to 159 variables.
Journal of the Operational Research SocietySurvey of Integer Programming
38 Citations1965E. M. L. Beale
There are now four distinct approaches capable of solving real problems of linear programming problems when some or all variables are required to take integer values: cutting plane methods, primal methods, branch and bound methods, and partial enumeration methods.
Management ScienceRelaxation Methods for Pure and Mixed Integer Programming Problems
37 Citations1972G. Anthony Gorry, Jeremy F. Shapiro +1 more
The main procedure given shows how an optimal linear programming basis can be altered to reduce the magnitude of its determinant thereby reducing the size of the group induced by the basis.
DSpace@MIT (Massachusetts Institute of Technology)Airline crew scheduling : a group theoretic approach
22 Citations1969Herv Thiriez
International Journal of Parallel ProgrammingAn implicit enumeration program for zero-one integer programming
19 Citations1972Toshihide Ibaraki, T. K. Liu +2 more
This paper describes some techniques to improve the speed of the implicit enumeration method for solving zero-one integer programming problems, the most powerful is the one of using a column vector which works as a tag for each inequality.
New Methodologies in Agricultural Production Economics: a Review
15 Citations1973David Throsby