<div>

</div>

<center><h1>Mathematical Optimization for Engineers</h1></center>
<center><h2>Lab 9 - Branch and Bound Method</h2></center>

In this exercise, we want to consider the following optimization problem
<br>
<br>
$$\begin{aligned}
        \min_{x_1,x_2} \quad - x_1 - 2 x_2 + 10 \\
        \mbox{s.t. } \quad 5 x_1 + 3 x_2 & \; \leq \; 15 \\
                                 x_2 & \; \leq \; 2 \\
                                 x_1,x_2 & \; \in \; \mathbb{N}_0,
\end{aligned}$$
where $\mathbb{N}_0 = \{0,1,2,3,\dots \}$.
<br>
<br>
<br>
1.  Sketch the feasible set of the optimization problem and the contour
    lines of the objective function.
<br>
<br>
2.  Use the Branch & Bound algorithm to solve the
    optimization problem.  You can solve the relaxed problems either
    geometrically or you can use the built-in function "linprog" from scipy.optimize)
<br>
<br>
3.  Assign the terms "lower bound" and "upper bound" to each solution of
    the relaxed problems and construct the branching tree.

The feasible set and the contour lines of the objective function are sketched in the Figure below. Note that the feasible set consists only of the red points.
<br>
<br>
<div>

</div>
<br>
<br>
In previous labs, we looked at continuous optimization problems where the feasible set was continuous. The methods we have learned so far cannot be applied to discrete feasible sets. This is the reason, why we appply the Branch & Bound method.

### Branching & bounding of nodes

&emsp; <u>Node 1:</u>

First of all, the integer constraints are <u>relaxed</u> by replacing them with
<br>
$$\begin{aligned}
        x_1 & \geq 0 \\
        x_2 & \geq 0
\end{aligned}$$

so that the feasible set looks like
<br>
<br>
<div>

</div>
<br>
<br>
Note that the feasible set of the relaxed problem consists of <u>all</u> the points inside and on the boundary of the yellow region, i.e. the relaxed problem is a continunous problem.

The resulting optimization problem is a linear program. 

We see, that the optimal solution of this problem (blue point) is $x^* = \left( \begin{array}{{c}}
                            1.8 \\ 2 \\
                            \end{array} \right)$ with objective function
value $f^* = 4.2$. 
<br>
<br>
<div>

</div>
<br>
<br>

Unfortunately, the optimal solution $x^*$ is not integer, thus this is not the optimal solution of the original problem (not even a feasible point, red in colour). On the other hand, the value of the objective function of node 1 is called a "<u>**global** lower bound</u>" on the value of the objective function of the original problem.

&emsp; &emsp; <u>Branching node 1:</u>

Since $x^*$ is not integer, we perform a so-called "branching" step.
This means, that we take one non-integer variable (in this case $x_1$)
and branch it. This implies, that we create two subproblems: node 2 and
node 3. Node 2 additionally contains the constraint $$\label{connode2}
        x_1 \leq 1$$ and node 3 includes the constraint
$$\label{connode3}
        x_1 \geq 2$$ 
        
Note, that $x_1 ^* = 1.8$ lies between the integer
values 1 and 2.
<br>
<br>
<div>

</div>
<br>
<br>

&emsp; <u>Node 2:</u>

The optimal solution of node 2 is $x^* = \left( \begin{array}{{c}}
                            1 \\ 2 \\
                            \end{array} \right)$ with objective function
value $f^* = 5$. 
<br>
<br>
<div>

</div>
<br>
<br>
Now, the optimal solution $x^*$ is integer, thus the
value of the objective function of node 2 is called an "upper bound".
Note that we do not know whether this is also the optimal solution of
the original optimization problem, since node 3 may contain a better
integer value than this one. Since we found an integer solution in node
2, we do not have to branch any more. Further branching will not lead to
better objective functions.

&emsp; <u>Node 3:</u>

The optimal solution of node 3 is $x^* = \left( \begin{array}{{c}}
                            2 \\ 1.\bar{6} \\
                            \end{array} \right)$ with objective function
value $f^* = 4.\bar{6}$. 
<br>
<br>
<div>

</div>
<br>
<br>

Unfortunately, the optimal solution $x^*$ is
not integer, thus this is not the optimal solution of the original
problem. Thus, the value of the objective function of node 3 is only a
"<u>**local** lower bound</u>".

&emsp; &emsp; <u>Branching node 3</u>

Since $x^*$ is not integer, we have to branch. This means, that we take one non-integer component from $x^*$ and create two subproblems: node 4 and node 5. Node 4 contains all constraints from node 3 and additionally the constraint
\begin{equation} \label{connode4}
		x_2 \leq 1
\end{equation}
and node 5 contains also all constraints from node 3 and additionally the constraint
\begin{equation} \label{connode5}
		x_2 \geq 2
\end{equation}

Note, that $x_2 ^* = 1.\bar{6}$ lies between the integer values 1 and 2.
<br>
<br>
<div>

</div>

&emsp; <u>Node 4:</u>

The optimal solution of node 4 is
$x^* = \left( \begin{array}{{c}}
							2.4 \\ 1 \\
							\end{array} \right)$ with objective function value $f^* = 5.6$. 
<br>
<br>
<div>

</div>
<br>
<br>                   

The optimal solution $x^*$ is not integer, thus this is not the optimal solution of the original problem. Once again, the value of the objective function of node 4 is only a "**local** lower bound".

Normally, we would have to branch now again. However, we are lucky in this case. The value of the objective function of node 4 ($f^* = 5.6$) is greater than the value of the upper bound (node 2: 	$f^* = 5$). When branching node 4, the feasible set gets smaller, thus the values of the objective function will be at least $5.6$. This means we do not have to branch node 4 again and can skip it. The optimal solution of the original problem is not in the feasible set of node 4.

&emsp; <u>Node 5:</u>

The feasible set of node 5 is empty. Thus, node 5 can be skipped as well.

Here's a summary of what we have done so far:
<br>
<br>
<div>

</div>
<br>
<br>
<div>

</div>
<br>
<br>

It is very important to note, that the value of the lower bound on the objective value has to increase or stay constant (the upper bound can decrease or stay constant) while descending in the tree. Obviously, this is here the case: node 1 has a smaller objective value, than node 3. Node 3 has a smaller objective value than node 4.

The optimal value of the objective function of the original problem has to be at least as high as the value of the objective function of node 1. That's why we call the value of the objective function of node 1 a **global** lower bound. Node 3 has only a **local** lower bound, since it may be possible to find a smaller objective value in node 2 or its subtree.

If the optimal solution of some node is integer, we call the respective objective value an **upper** bound. In case of upper bounds, we do not distinguish between global or local upper bounds. In some sense, all upper bounds can be seen as global, since the objective value of the original problem is equal to the value of the best (smallest) upper bound.

Note, that these terms only refer to **minimization** problems.

# Windsurfing problem
You are an eager windsurfer and want to advance to racing competitivity. Currently, you do not own a racing board and you have a limited budget to spend. Therefore, you want to optimize on choosing the right board(s) and the right time on surfing lessons. The trainer offers you up to 10 hours of surfing lessons. The boards differ depending on the wind conditions. There can be strong wind or light wind.

All parameters are given in the template.



Your task is: 

Formulate the optimization problem. 
Hint: You can only use a board if you have bought it.  ;)



Solve the optimization problem using scipy. 





```python
from scipy.optimize import minimize, Bounds, NonlinearConstraint
import numpy as np
```


```python
# use of nonlinear function as it is simpler to implement

def constraints(x): 
    # return constraints
    c = np.empty(9)
    
    # parameters 
    
    # variable names (renaming makes the following equations simpler)
    # continuous degree of freedom
    # your code here
    
    
    # discrete degree of freedom
    # buy descions
    # your code here

    
    # next uses of board
    # your code here

    
    # board and surf lesson costs 
    p = [112, 50, 218, 25]

    # constraint on budget
    cost_board1 = p[0] 
    cost_board2 = p[1] 
    cost_board3 = p[2] 
    cost_surf_lesson = p[3] 
    
    # budget constraint
    # your code here
    
    # choose only one board for wind_high

    # choose only boards that you have bought
    # your code here

    
    # choose only one board for wind_high
    # your code here
    
    # choose only boards that you have bought
    # your code here

    return c

def average_speed_objective(x): 
    
    # variable names (renaming makes the following equations simpler)
    # continuous degree of freedom

    # discrete degree of freedom
    # buy descions
    # your code here

    
    # next uses of board
    # your code here
    
    
    # next uses of board
    # your code here

    
    # parameters
    speed_board1_wind_high = 18.1
    speed_board2_wind_high = 25.8
    speed_board3_wind_high = 25.8
    speed_lesson_wind_high = 1.5
    
    speed_board1_wind_low = 24.3
    speed_board2_wind_low = 21.0
    speed_board3_wind_low = 24.3
    speed_lesson_wind_low = 0.1
    
    # wind high
    speed1 = use_board1_wind_high * speed_board1_wind_high \
            + use_board2_wind_high * speed_board2_wind_high\
            + use_board3_wind_high * speed_board3_wind_high\
            + speed_lesson_wind_high * surf_lesson_hours
    
    # wind low
    speed2 = use_board1_wind_low * speed_board1_wind_low \
            + use_board2_wind_low * speed_board2_wind_low\
            + use_board3_wind_low * speed_board3_wind_low\
            + speed_lesson_wind_low * surf_lesson_hours
            
    return -(speed1+speed2)/2  # for maximization
  
    
    
```


```python
def print_sol(x):     
    # variable names (renaming makes the following equations simpler)
    # continuous degree of freedom

    # discrete degree of freedom
    # buy descions
    # your code here

    
    # next uses of board
    # your code here
    
    
    # next uses of board
    # your code here
    
    
    print('surf_lesson_hours ', "{:.1f}".format(x[0]))
    print('buy_board_1 ', "{:.1f}".format(x[1]))
    print('buy_board_2 ', "{:.1f}".format(x[2]))
    print('buy_board_3 ', "{:.1f}".format(x[3]))
    print('use_board1_wind_high ', "{:.1f}".format(x[4]))
    print('use_board2_wind_high ', "{:.1f}".format(x[5]))
    print('use_board3_wind_high ', "{:.1f}".format(x[6]))
    print('use_board1_wind_low ', "{:.1f}".format(x[7]))
    print('use_board2_wind_low ', "{:.1f}".format(x[8]))
    print('use_board3_wind_low ', "{:.1f}".format(x[9]))
    
```


```python
# solve problem
budget = 400
# either one board and lessons, or two boards or two boards and lessons
constraint_lower_bounds = # your code here
constraint_upper_bounds = # your code here

# 'Nonlinear constraints'
# your code here

# Bounds on decision variables
# your code here

# call optimization routine (SLSQP)
# your code here

print_sol(sol.x)
```


```python
# Branching steps
```

98cd7cc4ba0b294d0dd48e374349090495c2f735
ipynb
Jupyter Notebook
EngineeringOptimization/GitLab/Lab09.ipynb
dalexa10/EngineeringDesignOptimization
eb5b5e4edd773aef629f59aea8a9771af41bd224
MIT
EngineeringOptimization/GitLab/Lab09.ipynb
dalexa10/EngineeringDesignOptimization
eb5b5e4edd773aef629f59aea8a9771af41bd224
MIT
EngineeringOptimization/GitLab/Lab09.ipynb
dalexa10/EngineeringDesignOptimization
eb5b5e4edd773aef629f59aea8a9771af41bd224
MIT
Qwen/Qwen-72B
1. YES
2. YES