Integer Programming by Implicit Enumeration and Balas’ Method

Previous article Next article Integer Programming by Implicit Enumeration and Balas’ MethodArthur M. GeoffrionArthur M. Geoffrionhttps: //doi. org/10. 1137/1009031PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout1 Egon Balas, An additive algorithm for solving linear programs with zero-one variables, Operations Res. , 13 (1965), 517–546 MR0183535 0194. 19903 CrossrefISIGoogle Scholar2 M. L. Balinski, Integer programming: Methods, uses, computation, Management Sci. , 12 (1965), 253–313 MR0192924 0129. 12004 CrossrefISIGoogle Scholar3 S. I. Firstman, An approximating algorithm for an optimum aim-points problem, Naval Res. Logist. Quart. , 7 (1960), 151–167 CrossrefGoogle Scholar4 R. J. Freeman, Computational experience with the Balas integer programming algorithm, P-3241, The RAND Corporation, Santa Monica, California, 1965 Google Scholar5 F. Glover, A multiphase-dual algorithm for the zero-one integer programming problem, Operations Res. , 13 (1965), 879–919 0163. 41301 CrossrefISIGoogle Scholar6 Frank Proschan and, T. A. Bray, Optimum redundancy under multiple constraints, Operations Res. , 13 (1965), 800–814 MR0187914 CrossrefISIGoogle Scholar7 R. J. Walker, R. Bellman and, M. Hall, Jr. , An enumerative technique for a class of combinatorial problemsProc. Sympos. Appl. Math. , Vol. 10, American Mathematical Society, Providence, R. I. , 1960, 91–94, Combinatorial Analysis MR0121306 0096. 00603 CrossrefGoogle Scholar Previous article Next article FiguresRelatedReferencesCited byDetails Machine learning-based optimal design of groundwater pollution monitoring networkEnvironmental Research, Vol. 211 Cross Ref Some new perspectives for solving 0–1 integer programming problems using Balas method11 March 2021 | Computational Management Science, Vol. 18, No. 2 Cross Ref An Optimal Sensor Deployment Technique for Spectrum Monitoring Applications Cross Ref Parallel branch and bound algorithm for solving integer linear programming models derived from behavioral synthesisParallel Computing, Vol. 101 Cross Ref Virtual Service Placement for Edge Computing Under Finite Memory and BandwidthIEEE Transactions on Communications, Vol. 68, No. 12 Cross Ref Optimum Selection of Mobile Edge Computing Hosts Based on Extended Balas-Geoffrion Additive Algorithm Cross Ref Integer based formulation for the simple assembly line balancing problem with multiple identical tasksComputers & Industrial Engineering, Vol. 104 Cross Ref Location and allocation based branch and bound algorithms for the capacitated multi-facility Weber problem18 September 2012 | Annals of Operations Research, Vol. 222, No. 1 Cross Ref References22 August 2014 Cross Ref General Bibliography8 August 2014 Cross Ref Branch-and-Bound Methods8 August 2014 Cross Ref Global optimization of capacity expansion and flow assignment in multicommodity networks16 July 2013 | Pesquisa Operacional, Vol. 33, No. 2 Cross Ref Branch-and-Bound Methods21 January 2013 Cross Ref Recommendation systems with complex constraintsACM Transactions on Information Systems, Vol. 29, No. 4 Cross Ref A binary integer linear programming-based approach for solving the allocation problem in multiprocessor partitioned scheduling Cross Ref Optimizing data collection path in sensor networks with mobile elements18 February 2011 | International Journal of Automation and Computing, Vol. 8, No. 1 Cross Ref Optimizing the Path-Points Identification for Data Mules in Mobile WSNs Cross Ref Path-Planning with Avoidance Using Nonlinear Branch-and-Bound OptimizationJournal of Guidance, Control, and Dynamics, Vol. 32, No. 2 Cross Ref Genetic Algorithm Based Length Reduction of a Mobile BS Path in WSNs Cross Ref Reducing the Path Length of a Mobile BS in WSNs Cross Ref Comparison of Branching Strategies for Path-Planning with Avoidance Using Nonlinear Branch-and-Bound15 June 2012 Cross Ref A revised Taha's algorithm for polynomial 0-1 programmingOptimization, Vol. 56, No. 5-6 Cross Ref Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method16 January 2007 | Journal of Global Optimization, Vol. 39, No. 1 Cross Ref An Optimization Model to Determine Master Designs and Runs for Advertisement Printing24 May 2006 | Journal of Mathematical Modelling and Algorithms, Vol. 6, No. 2 Cross Ref New Implicit Enumeration Method for Polynomial 0-1 ProgrammingSystems Engineering - Theory & Practice, Vol. 27, No. 3 Cross Ref Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower boundsEuropean Journal of Operational Research, Vol. 168, No. 3 Cross Ref An Airspace Planning Model for Selecting Flight-plans Under Workload, Safety, and Equity ConsiderationsTransportation Science, Vol. 36, No. 4 Cross Ref Global Optimization Procedures for the Capacitated Euclidean and l p Distance Multifacility Location-Allocation ProblemsOperations Research, Vol. 50, No. 3 Cross Ref A two-phase linear programming approach for redundancy allocation problemsYugoslav Journal of Operations Research, Vol. 12, No. 2 Cross Ref Calculating uncertainty intervals in approximate equation systemsApplied Numerical Mathematics, Vol. 27, No. 1 Cross Ref DISCRETE STRUCTURAL OPTIMIZATION WITH COMMERCIALLY AVAILABLE SECTIONSDoboku Gakkai Ronbunshu, Vol. 1996, No. 549 Cross Ref Three-dimensional pattern matching in protein structure analysis31 May 2005 Cross Ref Multi-item capacitated lot-sizing by a Cross decomposition based algorithmAnnals of Operations Research, Vol. 50, No. 1 Cross Ref A zero-one implicit enumeration method for optimizing investments in transmission expansion planningIEEE Transactions on Power Systems, Vol. 9, No. 3 Cross Ref A localization and reformulation discrete programming approach for the rectilinear distance location-allocation problemDiscrete Applied Mathematics, Vol. 49, No. 1-3 Cross Ref A squared-euclidean distance location-allocation problemNaval Research Logistics, Vol. 39, No. 4 Cross Ref Testability Design via Testability Measures Cross Ref Network Design Programming of U. S. Highway ImprovementsJournal of Transportation Engineering, Vol. 117, No. 4 Cross Ref A parallel implementation of the EQUIP expert system8 June 2005 Cross Ref Task allocation and scheduling models for multiprocessor digital signal processingIEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 38, No. 12 Cross Ref European assembly constituencies for wales - comparing of methods for solving a political districting problemMathematical Programming, Vol. 42, No. 1-3 Cross Ref Models and methods of solution of quadratic integer programming problemsCybernetics, Vol. 23, No. 3 Cross Ref References Cross Ref Heuristic ranking and selection procedures for network design problemsJournal of Advanced Transportation, Vol. 21, No. 1 Cross Ref Feature Selection for Automatic Classification of Non-Gaussian DataIEEE Transactions on Systems, Man, and Cybernetics, Vol. 17, No. 2 Cross Ref Zero-one integer programs with few constraints —Lower bounding theoryEuropean Journal of Operational Research, Vol. 21, No. 2 Cross Ref A branch and bound algorithm for extreme point mathematical programming problemsDiscrete Applied Mathematics, Vol. 11, No. 3 Cross Ref A heuristic for multiple choice programmingComputers & Operations Research, Vol. 12, No. 1 Cross Ref Automatic Design for Testability Via Testability MeasuresIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 4, No. 1 Cross Ref An efficient 0–1 integer programming algorithm for advertising media selectionJournal of the Academy of Marketing Science, Vol. 12, No. 1-2 Cross Ref Programming problems with pseudo-monotonic objectives27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 15, No. 2 Cross Ref Optimal Location of Telephone ExchangesIFAC Proceedings Volumes, Vol. 16, No. 12 Cross Ref An analytical decision model for resource allocation in highway maintenance managementTransportation Research Part A: General, Vol. 17, No. 2 Cross Ref A mathematical programming model for optimal service selection in the airline industryEuropean Journal of Operational Research, Vol. 8, No. 4 Cross Ref SOLVING A CAPITAL/TECHNOLOGY CONSTRAINT PROBLEM BY IMPLICIT ENUMERATION**Part of the work was done while the author was a scientific staff member at Bell Northern Research, Canada. Cross Ref Experiments in integer programmingDiscrete Applied Mathematics, Vol. 2, No. 1 Cross Ref A local algorithm for integer optimization problemsUSSR Computational Mathematics and Mathematical Physics, Vol. 20, No. 3 Cross Ref Regional Energy ModellingIFAC Proceedings Volumes, Vol. 13, No. 5 Cross Ref Ein algorithmic zur lösung einer klasse linearer 0–1-optimierungsaufgaben mit spezieller struktur27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 11, No. 3 Cross Ref Ein Modell zur Optimierung des langfristigen Ausbaus elektrischer ÜbertragungsnetzeOR Spektrum, Vol. 1, No. 2 Cross Ref Enumerative Methods in Integer Programming Cross Ref Computer Codes for Problems of Integer Programming Cross Ref Implementationstechniken für einen Branch-and-Bound-Algorithmus zur Lösung von (0–1) -Programmen Cross Ref An implicit enumeration algorithm for the all integer programming problemComputers & Mathematics with Applications, Vol. 4, No. 1 Cross Ref BRANCH AND BOUND METHODOLOGY Cross Ref An Optimization Model for Overall Urban Energy PlanningIFAC Proceedings Volumes, Vol. 11, No. 1 Cross Ref The Segregated Storage Problem: Some Properties and an Effective Heuristic9 July 2007 | A I I E Transactions, Vol. 9, No. 4 Cross Ref Optimum redundancy assignment of supervisory control systems in power systemsElectrical Engineering in Japan, Vol. 97, No. 4 Cross Ref Numerical methods for assembly-line balancing (survey) Cybernetics, Vol. 13, No. 1 Cross Ref Implicit Enumeration with Generalized Upper Bounds Cross Ref A Lifo Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem Using Held and Karp's 1-Tree Relaxation Cross Ref Regional electric power system planning using mixed integer linear programmingIFAC Proceedings Volumes, Vol. 10, No. 14 Cross Ref Theoretical comparisons of search strategies in branch-and-bound algorithmsInternational Journal of Computer & Information Sciences, Vol. 5, No. 4 Cross Ref Scheduling a Project Under Multiple Resource Constraints: A Zero-One Programming ApproachA I I E Transactions, Vol. 8, No. 4 Cross Ref A Comparison of Three Algorithms for Linear Zero-One ProgramsACM Transactions on Mathematical Software, Vol. 2, No. 4 Cross Ref Set Partitioning: A surveyEgon Balas and Manfred W. Padberg18 July 2006 | SIAM Review, Vol. 18, No. 4AbstractPDF (5511 KB) Ein lexikographischer Suchalgorithmus zur ganzzahligen Programmierung: L E X SZeitschrift für Operations Research, Vol. 20, No. 5 Cross Ref On Solving Fractional (0, 1) Programs By Implicit Enumeration25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 14, No. 3 Cross Ref A Sequential Approach to the 0 - 1 Linear Programming ProblemNicos Christofides and Mary Trypia12 July 2006 | SIAM Journal on Applied Mathematics, Vol. 31, No. 2AbstractPDF (1195 KB) On a Two Facility Scheduling Problem with Sequence Dependent Processing Time9 July 2007 | A I I E Transactions, Vol. 8, No. 2 Cross Ref The Fixed-Charge Transportation Problem: A Computational Study with a Branch-and-Bound Code9 July 2007 | A I I E Transactions, Vol. 8, No. 2 Cross Ref The Optimal Partitioning of GraphsNicos Christofides and P. Brooker12 July 2006 | SIAM Journal on Applied Mathematics, Vol. 30, No. 1AbstractPDF (1463 KB) Ein Algorithmus zur Lösung einer speziellen Klasse ganzzahliger Optimierungsmodelle Cross Ref Lösung gemischt-ganzzahliger Planungsprobleme Cross Ref Implicit enumeration based algorithms for postoptimizing zero-one programsNaval Research Logistics Quarterly, Vol. 22, No. 4 Cross Ref Resolution of the 0–1 knapsack problem: Comparison of methodsMathematical Programming, Vol. 8, No. 1 Cross Ref Numerische Erfahrungen mit der Filtermethode von Balas in der linearen binären OptimierungComputing, Vol. 14, No. 3 Cross Ref A recursive branch and bound algorithm for the multidimensional knapsack problemNaval Research Logistics Quarterly, Vol. 22, No. 2 Cross Ref Optimal and Heuristic Facility Phase-out StrategiesA I I E Transactions, Vol. 7, No. 2 Cross Ref Set Partitioning Cross Ref Les Procedures D’exploration et D’optimisation par Separation Et Evaluation Cross Ref Postoptimality analysis in integer programming by implicit enumeration: The mixed integer caseNaval Research Logistics Quarterly, Vol. 21, No. 4 Cross Ref Optimal expansion of an existing networkMathematical Programming, Vol. 6, No. 1 Cross Ref A Minimum-Cost Feature-Selection Algorithm for Binary-Valued FeaturesIEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-4, No. 6 Cross Ref The use of linear programming to select an optimal set of prime implicantsComputer-Aided Design, Vol. 6, No. 4 Cross Ref Optimal Temporary Deferral of Reinforcements in a Single Terminal Flow NetworkIEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-4, No. 3 Cross Ref Cost-minimal trees in directed acyclic graphsZeitschrift für Operations Research, Vol. 18, No. 1 Cross Ref Ein Algorithmus zur Lösung linearer gemischt-ganzzahliger Optimierungsprobleme: MILEX Cross Ref Research in progressComputer-Aided Design, Vol. 6, No. 1 Cross Ref A Survey of Integer Programming Emphasizing Computation and Relations among Models Cross Ref EDUCATION. Decision Sciences, Vol. 4, No. 1 Cross Ref Optimal location of public facilitiesNaval Research Logistics Quarterly, Vol. 19, No. 4 Cross Ref Postoptimality analysis in zero-one programming by implicit enumerationNaval Research Logistics Quarterly, Vol. 19, No. 3 Cross Ref Design of Optimal Switching Networks by Integer ProgrammingIEEE Transactions on Computers, Vol. C-21, No. 6 Cross Ref A Result on Set Extraction and Application to Covering-Closure TablesIEEE Transactions on Computers, Vol. C-21, No. 6 Cross Ref On the Maximization of a Pseudo-Boolean FunctionJournal of the ACM, Vol. 19, No. 2 Cross Ref Generalized implicit enumeration using bounds on variables for solving linear programs with zero-one variablesNaval Research Logistics Quarterly, Vol. 19, No. 1 Cross Ref An implicit enumeration program for zero-one integer programmingInternational Journal of Computer & Information Sciences, Vol. 1, No. 1 Cross Ref On Finding the Paths Through a Network29 July 2013 | Bell System Technical Journal, Vol. 51, No. 2 Cross Ref Enumerative inequalities in integer programmingMathematical Programming, Vol. 2, No. 1 Cross Ref AN ALGORITHM FOR A GENERAL CONSTRAINED SET COVERING PROBLEM Cross Ref Tree-search algorithms for quadratic assignment problemsNaval Research Logistics Quarterly, Vol. 18, No. 1 Cross Ref Assembly Line Balancing by Zero-One Integer Programming9 July 2007 | A I I E Transactions, Vol. 3, No. 1 Cross Ref Ganzzahlige Programmierung — Ein Überblick Cross Ref An Approach to Solving Linear Discrete Optimization ProblemsJournal of the ACM, Vol. 17, No. 2 Cross Ref Capital Budgeting and Mixed Zero-One Integer Programming9 July 2007 | A I I E Transactions, Vol. 2, No. 1 Cross Ref Logical Design of Optimal Digital Networks by Integer Programming Cross Ref Heuristic Techniques for Solving Large Combinatorial Problems on a Computer Cross Ref Simplification of the Covering Problem with Application to Boolean ExpressionsJournal of the ACM, Vol. 17, No. 1 Cross Ref Solving an integer programming problem Cross Ref Scheduling and task allocation for parallel digital signal processing architectures Cross Ref Computer-based man-job matching: Current practice and applicable researchSocio-Economic Planning Sciences, Vol. 3, No. 4 Cross Ref Volume 9, Issue 2| 1967SIAM Review History Submitted: 09 March 1966Published online: 18 July 2006 InformationCopyright © 1967 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI: 10. 1137/1009031Article page range: pp. 178-190ISSN (print): 0036-1445ISSN (online): 1095-7200Publisher: Society for Industrial and Applied Mathematics