The reduced cost branch and bound algorithm for mixed integer programming

DOI10.1016/0305-0548(85)90039-5MaRDI QIDQ1085067zbMATH OpenOpenAlexFDO

Authors Kipp Martin, Dennis J. Sweeney, Michael E. Doherty

Publication date 1985

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(85)90039-5

zbMATH Keywords

branch and boundmixed integer programming

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11)

Review text

A different branch and bound algorithm for mixed integer programming is presented. Unlike standard linear programming based branch and bound algorithms, where a single fractional variable (or Special Ordered Set) is selected for problem separation, the proposed method selects groups of variables for separation on the basis of their reduced cost in an LP relaxation. The proposed method restricts a large portion of the integer variables to zero on one branch. The net effect is that the original integer program is solved by optimizing a series of smaller, more tightly restricted, integer programs. The authors have programmed the algorithm using the Extended Control Language of the IBM MPSX/370-MIP/370 mixed integer programming package. Computational results are presented that demonstrate the efficiency of the method on problems where the 0/1 variables are partitioned into multiple choice constraints containing special ordered sets of variables. While the computational results are limited to this class of problems the algorithm can, in theory, be applied to any mixed integer programming problem.

Recommendations

• Fixed Order Branch-and-Bound Methods for Mixed-Integer Programming: The <scp>zoom</scp> System
• Technical Note—An Improved Branch-and-Bound Method for Integer Programming
• A branch and bound algorithm for solving separable convex integer programming problems
• An implicit branch-and-bound algorithm for mixed-integer linear programming
• Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program

Cites work

• An Algorithm for Large Zero-One Knapsack Problems
• An ideal column algorithm for integer programs with special ordered sets of variables
• An integer programming approach to a class of combinatorial problems
• Branch and Bound Methods for Multi-Item Scheduling
• Experiments in mixed-integer linear programming using pseudo-costs
• scientific article; zbMATH DE number 3526452 (Why is no real title available?)
• scientific article; zbMATH DE number 3410784 (Why is no real title available?)
• Integer Programming Algorithms: A Framework and State-of-the-Art Survey
• Practical Solution of Large Mixed Integer Programming Problems with Umpire
• Zero-one programming with many variables and few constraints

Cited in

(8)

• A possible way to reduce degeneracy in integer programming computations
• An intelligent algorithm for mixed-integer programming models
• Computational comparison on the partitioning strategies in multiple choice integer programming
• Algorithms for solving the mixed integer two-level linear programming problem
• Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program
• Fixed Order Branch-and-Bound Methods for Mixed-Integer Programming: The <scp>zoom</scp> System
• Technical Note—An Improved Branch-and-Bound Method for Integer Programming
• Branch and bound with estimation based on pseudo-shadow-prices

Describes a project that uses

Uses Software

• LINDO

This page was built for publication: The reduced cost branch and bound algorithm for mixed integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085067)