Computer Codes for Problems of Integer Programming
Annals of discrete mathematicsPublished 1 January 1979
A. H. Land, Susan Powell
Citations75
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
This chapter presents a “consumer research” report on the different products and also the methods for solving pure integer problems—frequently with special combinatorial structures.
Abstract
This chapter presents computer codes for the problems of integer programming. The term "integer programming" covers a wide spectrum of models, which can be characterized by mixed integer programming (MIP) at one end and combinatorial programming at the other end. The interest of those working in commercial organizations is currently focused at the MIP end of the spectrum—indeed on problems, which are basically large linear programming (LP) systems with relatively few integer variables. The chapter presents a "consumer research" report on the different products and also the methods for solving pure integer problems—frequently with special combinatorial structures. Thus, in a consumer report, one has to bear in mind, which consumers are intended for each code. The code should be capable of obtaining a guaranteed optimum solution. A large and complex problem may not be capable of yielding an optimum integer solution within feasible cost and time limits on any code so that the user has in fact to be content with a significant solution obtained by heuristic methods.
Keywords
Engineering
An Automatic Method for Solving Discrete Programming Problems
1,997 Citations2009A. H. Land, Alison Doig
EconometricaAn Automatic Method of Solving Discrete Programming Problems
1,835 Citations1960A. H. Land, A. G. Doig
A simple numerical algorithm is presented for the solution of programming problems in which some or all of the variables can take only discrete values, and lends itself to automatic computing.
Bulletin of the American Mathematical SocietyOutline of an algorithm for integer solutions to linear programs
1,352 Citations1958Ralph E. Gomory
Operations ResearchAn Additive Algorithm for Solving Linear Programs with Zero-One Variables
705 Citations1965Egon Balas
Management ScienceInteger Programming Algorithms: A Framework and State-of-the-Art Survey
353 Citations1972Arthur M. Geoffrion, Roy E. Marsten
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.
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.
Journal of the Operational Research SocietyRecent Advances in Mathematical Programming
292 Citations1964S. Vajda
Mathematical ProgrammingGlobal optimization using special ordered sets
277 Citations1976E. M. L. Beale, J. J. H. Forrest
Two methods for finding a global minimum of a function of a scalar variable in a finite interval, assuming that one can calculate function values and first derivatives, and also bounds on the second derivatives within any subinterval are described.
Management ScienceA Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
246 Citations1975Yoshiaki Toyoda
The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice problems.
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.
Mathematical ProgrammingThe efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
151 Citations1977M. Benichou, J. M. Gauthier +2 more
An attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method is described.
Management SciencePractical Solution of Large Mixed Integer Programming Problems with Umpire
145 Citations1974J. J. H. Forrest, Jack Hirst +1 more
This paper discusses some branch and bound methods implemented in the UMPIRE mathematical programming system for solving practical integer programming problems and gives details of computational experience with these methods.
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.
Mathematical ProgrammingA hybrid approach to discrete mathematical programming
118 Citations1978Roy E. Marsten, Thomas L. Morin
The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs that uses linear programming in a novel way to compute bounds.
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.
Journal of the London Mathematical SocietyBOOLEAN METHODS IN OPERATIONS RESEARCH AND RELATED AREAS
109 Citations1969S. Vajda
Management ScienceAn Algorithm for Large Set Partitioning Problems
93 Citations1974Roy E. Marsten
An algorithm is presented for the special integer linear program known as the set partitioning problem, which has a binary coefficient matrix, binary variables, and unit resources and all of its constraints are equations.
Mathematical ProgrammingInvestigation of some branch and bound strategies for the solution of mixed integer linear programs
90 Citations1973Gautam Mitra
The flexibility of this technique is examined through experiments with different branching and subproblem selection strategies, and the efficacy of these various heuristics is assessed.
Mathematical ProgrammingInteger programming approaches to the travelling salesman problem
86 Citations1976P. Miliotis
The generality of the method and the modest solution times achieved leads the author to believe that such an LP approach to other combinatorial problems deserves further consideration.
Mathematical ProgrammingExperiments in mixed-integer linear programming using pseudo-costs
78 Citations1977J. M. Gauthier, G. Ribière
This paper discusses heuristic “branch and bound” methods for solving mixed integer linear programming problems and introduces new heuristic rules for generating a tree which make use of pseudo-costs and estimations.
Operational Research Quarterly (1970-1977)Fortran Codes for Mathematical Programming; Linear, Quadratic and Discrete.
74 Citations1975David T. Birtwistle, A. H. Land +1 more
Management ScienceInteger Linear Programming: A Study in Computational Efficiency
73 Citations1969C.A. Trauth, Robert E. D. Woolsey
Twenty-nine integer linear programming problems, raging from very simple to apparently rather difficult, are introduced and the results of running these problems on four different computer codes, involving five distinct algorithms are presented.
Mathematical programming studiesA heuristic algorithm for mixed-integer programming problems
60 Citations1974Toshihide Ibaraki, Tateaki Ohashi +1 more
The heuristic algorithm was successful in obtaining exact optimal solutions for many problems with known optimal solutions and the quality of the obtained solutions seem to be quite high.
Operations ResearchA Convergent Duality Theory for Integer Programming
45 Citations1977David E. Bell, Jeremy F. Shapiro
The last dual problem in the sequence yields an optimal solution to the integer programming problem and it is shown that this dual problem approximates the convex hull of the feasible integer solutions in a neighborhood of the optimal solution it finds.
Mathematical ProgrammingComputational experience with a group theoretic integer programming algorithm
36 Citations1973G. Anthony Gorry, William D. Northup +1 more
The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.
Management ScienceExtensions of the Group Theoretic Approach in Integer Programming
35 Citations1971Laurence A. Wolsey
Operations ResearchA Computer Code for Integer Solutions to Linear Programs
23 Citations1965John Haldi, Leonard M. Isaacson
It is concluded that Gomory's original cutting-plane method merits further investigation and development as an efficient computational technique.
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.
Journal of the Operational Research SocietyAn Algorithm for Solving Mixed Integer Linear Programmes
11 Citations1964Paula M. J. Harris
A simplified form of an algorithm for solving mixed integer linear programmes is presented by considering the geometry of the problem and the ideas developed are translated into algebra.
Operations ResearchLetter to the Editor—Stronger Cuts in Gomory's All-Integer Integer Programming Algorithm
10 Citations1967Robert Wilson
Stronger cuts are available, and easily calculated, than those obtained by Gomory in the construction of his all-integer integer programming algorithm.
Computational experience with a modification of an algorithm by Hammer and Rudeanu for 0-1 linear programming
5 Citations1971František Fiala
The acceleration algorithm by Hammer and Rudeanu for linear zero-one programming problem was tested with several problems of small and medium size involving up to 300 variables on an IBM 360/67 and the results shown indicate that the algorithm is computationally competitive with the other known algorithms using implicit enumeration.
An Algorithm for Large Set Partitioning Problems
4 Citations1975Roy E. Marsten
SIAM Journal on Applied MathematicsA Sequential Approach to the $0 - 1$ Linear Programming Problem
3 Citations1976Nicos Christofides, Mary N. Trypia
The paper gives a method of minimizing a linear function of zero-one variables subject to linear constraints which is based on transforming an n-variable m-constraint problem into a sequence of n- variable 2- Constraint problems which are easier to solve.