A tree-search algorithm for mixed integer programming problems

1965/03/01 by R. J. Dakin · 641 citations
Engineering · Mathematics · #Algorithm #Computer science #Integer programming #Mathematical optimization #Mathematics #Optimization and Mathematical Programming #Tree (set theory)

paper · pdf · doi:10.1093/comjnl/8.3.250

published in The Computer Journal 8(3), 250-255 (Oxford University Press)

openalex publication_date 1965/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

This paper describes a new algorithm for finding solutions to optimization problems in which some of the variables must take integral values. The algorithm appears to offer some advantages over a similar algorithm proposed by Land and Doig, from which it was developed. The paper describes computational procedures which result in modest storage requirements. The method has been programmed and used to solve several problems.

Cited by

• Experiments in mixed-integer linear programming
• ExMAG: Learning of Maximally Ancestral Graphs
• State-of-the-art review of optimization methods for short-term scheduling of batch processes
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Estimating the Size of Branch-and-Bound Trees
• A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming
• Warm-starting outer approximation for parametrized convex MINLP
• The Lazy Flipper: MAP Inference in Higher-Order Graphical Models by Depth-limited Exhaustive Search
• Long-term path planning with optimal deployment of a charging station for monitoring photovoltaic solar farms. [europepmc]
• An optimal takeout supply system of intelligent self-pickup cabinets: Evidence from campus safety during COVID-19 in China [europepmc]

Related

• Shaping and Trimming Branch-and-bound Trees
• Algorithms for Generating Pareto Fronts of Multi-objective Integer and Mixed-Integer Programming Problems
• Mixed Integer Linear Programming Formulation Techniques
• DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems
• Tree-Based Optimization: A Meta-Algorithm for Metaheuristic Optimization