Corrected exercise Branch and Bound

This page presents a detailed corrected exercise of the problem of linear programming solved by the algorithm of branch and bound.

branch and bound

A machine shop owner plans to expand by purchasing new machines, presses and lathes. The owner estimated that each purchased press will increase profits by 100 $ per day and each spin will increase profits by 150 $ per day. The number of machines the owner can purchase is limited by the cost of the machines and the floor space available in the workshop. Machine purchase prices and space requirements are as follows.

branch and bound separation and evaluation

The owner has a budget of 40,000 $ for the purchase of machinery and 200 square feet of floor space available. The owner wants to know how many of each type of machine to buy to maximize the daily increase in profits. Solve this problem.

Solution

The first step is modeling the problem, this is a linear problem as an integer (so the simplex cannot apply).

branch and bound separation and evaluation

With x_1 the number of presses and x_2 the number of turns.

We start the branch and bound method by first solving the problem as a regular linear programming model with no restrictions on integers (that is, restrictions on integers are relaxed or relaxed). The linear programming model for the problem and the optimal relaxed solution is

branch and bound separation and evaluation

The relaxed optimal solution is x_1=2.22 and x_2=5.56 with Z=1055.56.

The branch and bound method uses a diagram consisting of nodes and branches as a framework for the solution process. The first node in the branch and link diagram, shown in Figure C-1, contains the relaxed linear programming solution shown earlier and the rounded solution.

branch and bound separation and evaluation

We denote upper bound the result of the relaxed optimal solution, and lower bound the result of the optimal solution as an integer (rounded down).

First connection

Create two constraints (or subsets) to eliminate the fractional part of the value from the solution and see which is farthest from the rounded integer value (i.e. which variable has the largest fractional part in value absolute). The 0.56 part of 5.56 is the largest fractional part; thus, x_2 will be the variable we are going to "plug" into.

In other words, we will create two alternative linear programs taking into account respectively that x_2 must be less than or equal to 5 on the one hand; and x_2 must be greater than or equal to 6 on the other hand.

So we have the following connection:

branch and bound separation and evaluation

Let's solve the problem on the left:

branch and bound separation and evaluation

This gives the solution x_1=2.5, x_2=5 and Z=1000.

Let's solve the system on the right:

branch and bound separation and evaluation

This system has for solution x_1=1.33 and x_2=6, Z=1033.33

From a practical point of view, we cut the definition field with the constraint x_2=6 and have resolved on either side of the constraint the linear system released.

branch and bound separation and evaluation

Let's update our graph with the new UB and LB of each system obtained.

branch and bound separation and evaluation

Since we don't have an optimal and feasible integer solution yet, we need to continue branching (i.e., partitioning) the model, either from node 2 or from node 3. A look at Figure reveals that if we branch from node 2, the maximum value that can possibly be reached is 1000 $ (the upper bound).

However, if we start from node 3, a higher maximum value of 1033 $ is possible. Thus, we will branch off from node 3. In general, always branch off from the node with the maximum upper bound.

Second connection

Now the branching steps previously followed at node 1 are repeated at node 3. First, the variable that has the value with the largest fractional part is selected. Since x_2 has an integer value, x_1, with a fractional part of 0.33, is the only variable we can select. Thus, two new constraints are developed from x_1.

branch and bound separation and evaluation

Taking node 4, we have the following linear program:

branch and bound separation and evaluation

The solution to the problem is x_1=1 and x_2=6.17 with Z=1025.

The second problem is:

branch and bound separation and evaluation

This problem does not admit a solution (first constraint is violated). So we have the following solution graph:

branch and bound separation and evaluation

We still don't have an integer solution, so we have to continue the branch and bound algorithm

Third connection

Node 4 has the best UB. Since x_2 is the only variable that is not an integer, we will branch to this variable.

branch and bound separation and evaluation

After solving the two linear programs at nodes 6 and 7, we get the results following:

branch and bound separation and evaluation

The solution to node 6 corresponds to the criteria of the original problem (ie in whole number). Only the branch at 3 and 4 have a UB higher than node 6, however, the branch that gives node 5 and 7 does not have a feasible solution. We conclude that the optimal solution is found at node 6.

Summary of the method

Here is a summary in English of the method we have just used.

branch and bound separation and evaluation

To share
en_GBEN
%d bloggers like this: