Implementation of Branch and Bound Method for Integer Linear Programming Using MATLAB

Experiment Objective: This experiment aims to implement the branch and bound method using MATLAB to solve integer linear programming problems, facilitating better understanding and application of the algorithm. The implementation will demonstrate how to handle integer constraints through systematic tree traversal and bound comparisons. Experiment Content: In this experiment, we will solve the following linear integer programming problem using the branch and bound method, with detailed explanation of the algorithm implementation steps. The branch and bound method is an effective algorithm for solving integer linear programming problems that works by dividing the problem into smaller subproblems. We will study and implement this algorithm to understand its working principles and practical applications. Key implementation aspects include using MATLAB's linprog function for linear relaxation solutions, node management for branching, and bound comparison techniques. The problem formulation is: Maximize z = 4x1 + 3x2 Subject to: 2x1 + 1x2 <= 6 1x1 + 2x2 <= 5 x1, x2 are non-negative integers We will implement the branch and bound method to find the optimal solution, detailing the implementation process including: initial linear relaxation solution, branching criteria based on fractional variables, bound calculation using objective function values, and pruning strategies. The MATLAB code will involve functions for solving linear programming subproblems, maintaining a node list, and implementing the branching logic with integer feasibility checks.