Branch and bound for MINLP

Authors: Phuc Vo (pnv4), Sadie Rynestad (sr2269), Najiyyah Clark (nac228) (SYSEN5800, FALL 2021)

Introduction

           Branch and bound is a method used to solve Mixed Integer Non-Linear Programming (MINLP) models. There is a difference in the exact steps of the algorithm; however, the initial method created in 2000 by Ioannis Akrotirianakis, Istvan Maros, and Berc Rustem uses a general arrangement of the branch and bound that has iterative nature of the outer estimation (Altherr et al., 2019). The general efficiency of the branch and bound algorithm is improved by adding Gomory mixed-integer cuts as an alternative to branching to reduce the number of nodes and Non-Liner Programming (NLP) problems needed to solve the MINLP.

Algorithmic Discussion

           Relax and search are the basic performances common to algorithms when finding a solution to MINLP.  The difference in algorithms occurs depending on how these performances are executed. In convex MINLPs, the most unaffected relaxation is to ignore the totality constraints y ∈ ℤ ^p. This results in a nonlinear program (NLP) that is solved to global optimality to produce a lower bound on the optimal solution value ^z_MINLP. When the solution (x^o, y^o) is relaxed to have y ∈ Z^p, then (x^o, y⁰) is supposed to be the optimal answer of MINLP; otherwise, there is a j ∈ {1 . . . p} with y_j⁰  ℤ (Cacchiani & D’Ambrosio, 2017). The search is continuous when it comes to branch-and-bound whereby it creates two sub-problems; one with the additional constraint y_j ≥ [y^o_j] and the other one with additional constraints y_j ≤ [y⁰_j]. The same procedure is used to solve these two sub-problems, and it results in search-tree sub-problems that are investigated.

           On the other hand, when f(x, y) or g(x, y) is not convex functions, then quality algorithms for handling NLP will assure that convergence will occur to a local minimum only. Therefore, the simple solution will not be capable of providing a lower bound on ^z_MINLP. In this scenario of nonconvex MINLP, an additional relaxation procedure is needed. Generally, relaxation depends on the decomposition of a nonlinear function into elements and for every element, a "convex envelope" relaxation is developed (Cacchiani & D’Ambrosio, 2017). Branch and bound is again used in relaxation where there is the additional complexity that continuous variables x can need branching to better the convex relaxation of the initial nonconvex function. During solving this class, a difference occurs in the method in which relaxation is developed.

           Let have f(x), h(x) and g(x) that are convex as well as continuous differentiable. To form a general MINLP problem that will be solved using branch and bound method it will be done as shown below:

_minℤ(x, y) =C^Ty+f(x)

h(x) =0

s.t.g(x) +By≤0

y∈0, 1 and x ∈X

           The branch and bound usually follow the outer approximation for MINLP when incorporating Gomory cuts to reduce the search space for the problem (Jaber et al., 2021). The initial developer presented the algorithm as shown in the various methods below.

Initialization: Search Tree Root Value

0.     Upper bound=inf, Lower bound= -inf

1.     Initialize y⁰

Initialization of binary variables (y) is the first step of the branch and bound method, and the step defines each with a finite beginning value 0 or 1. Another way of achieving initialization is by solving a simple NLP setting 0≤y≤1.

Using y⁰ to solve NLP

If NLP is feasible

→ solve ℤ(x^0, y⁰). The product of this will be a new upper bound to the initial problem. Then move to step 3

Else NLP is not feasible

→ when the original set of values for y⁰ is selected; select a new (y⁰).

Steps 1 and 2 are supposed to be repeated until a feasible solution is found. Move to step 3.

The result from NLP should be the initial feasible solution x⁰ and y⁰ whereby ℤ(x⁰, y⁰). But when relaxed NLP is infeasible, the MINLP problem becomes infeasible.

Solving MINLP

Using y⁰ and x⁰ gotten from NLP, constraints and linearized objective is solved using the following equations:

min a

s.t.a ≤U B⁰

g(x⁰,y⁰)+g(x⁰,y⁰)≤0

f(x⁰,y⁰)+g(x⁰,y⁰)≤a

           When MINLP is solved, the product is a new set of (x) and (y). These new (y⁰) and (x⁰) are the branch's root and bound search tree.

Solving Nodes

           This starts by selecting an unsolved node, and in cases where no nodes are left, the problem is solved. The optimal solution found is ℤ (x^j, y^j). If all y^k = {0, 1}, it becomes a new incumbent and Z that will be obtained from the set of x^k and y^k will be the current optimal solution (Jaber et al., 2021). When x^k and y^k are used to solve each unsolved node, the equation below is used:

Using the previous feasible solution to solve MINLP in this form

Start with excluding root (x^j,yⁱ) will become (x⁰,y⁰)

Min a

s.t.a ≤U B^j

g(x^j,y^j)+g(x^j ,y^j)^T≤0jT

f(x^j,y^j)+f(x^j ,y^j)^T≤a

T is set with all indices of the solution tree in which NLP for y^j is feasible.

g(xⁱ,yⁱ)+g(xⁱ ,yⁱ)^T≤0iS

Such that S is the set that has all indices of solution whereby NLP yⁱ is infeasible

T_y+T_x≤

This constraint is a representation of the Gomory cut produced as algorithm runs. This line reduces the feasible region of the initial problem, which is y {0, 1}. The final product of solving MINLP is a new set of x^k and y^k.

Numerical Solution

Consider the optimization problem with the following objective function and constraints

Min 4x₁⁴-4x₂x₁²+x₂²+x₁²-x₁+1

s.t. -1≤x₁≤1

-1≤x₂≤1

To verify if [0.05, 0.5] is optimal relaxed solution (with continuous variables). This is the root node lower bound for the integer solution objective and beginning point for the brand and bound.

Obj=4(0.5)⁴-4(0.5) (0.5)⁴+ (0.5)²+ (0.5)²-0.5+1=

0.25-0.5+0.25+0.25+0.25-0.5+1=0.75

_xObj=0   =0= 4(4)x₁³-8x₂x₁+2x₁-1=2-2+1-1=0

              =0= -4x₁²+2x₂=-1+1=0

_xObj is positive definite for minimum

_x²Obj====

Or det(_x²Obj)=20-11=9

Principle minors =0

Application

           The branch and bound can be used in many programming problems because it converts them to mixed-integer nonlinear programming and solves them using the branch and bound method (Zhang et al., 2020). Besides the mathematical application, it can be used in various engineering and design issues.

Mathematical Problem

Mathematically, the Branch and bound method for MINLP is commonly used to solve the travelling salesman problem. In 1991, Padberg and Rinaldi created a solution to large-scale symmetric travelling salesman issues utilizing the branch and cut method (Jaber et al., 2021). MINLP problems that can be solved using branch and bound algorithms are; biological models, scheduling and network design (involving finding location).  

Industrial Application

           Designing a thermal insulation layer for the huge hadron collider requires branch and method for MINLP. Series of heat intercepts as well as surrounding insulators are used thermal insulation to reduce the power needed to keep the heat intercepts at specific temperatures (Cacchiani & D’Ambrosio, 2017). These issues come up in the plan of superconducting magnetic energy storage systems as well as have been utilized in large huge collider projects.

           Designers select the maximum number of intercepts; the discrete set of materials is selected depending on the thickness and area of every intercept and the intercepted material. The thermal conductivity as well as total mass of the insulation system depend on the selected material selected (Cacchiani & D’Ambrosio, 2017). Nonlinear functions on the model are needed for accuracy purposes like stress constraints, heat flow between the intercept and thermal expansion. Integer variables are utilized to model the discrete choice of the type of material to utilize in every layer.

           When branch and bound for MINLP is used, it identifies better materials compared to using other methods. Branch and bound have better improvement because of their capability to handle a more significant amount of intercepts than other methods (Altherr et al., 2019). Therefore, most designers tend to apply this method to ensure that they have an optimal solution.

Conclusion

           In general, Branch and bound method follow a scheme that grows exponentially because variables are added to the initial design problem. When Gomory cuts are added, they allow bounds to tighten by decreasing the number of feasible nodes tested and permitting the solver to converge on the optimal solutions with minimum iterations. However, it takes time to form inequalities to production cuts, which can slow down the real resolution of the MINLP problem. Due to this, it should be noted that the larger the problem, the more significant the cuts become.

References

Altherr, L., Leise, P., Pfetsch, M., & Schmitt, A. (2019). Resilient layout, design and operation of energy-efficient water distribution networks for high-rise buildings using MINLP. Optimization And Engineering, 20(2), 605-645. https://doi.org/10.1007/s11081-019-09423-8

Cacchiani, V., & D’Ambrosio, C. (2017). A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs. European Journal Of Operational Research, 260(3), 920-933. https://doi.org/10.1016/j.ejor.2016.10.015

Jaber, A., Lafon, P., & Younes, R. (2021). A branch-and-bound algorithm based on NSGAII for multi-objective mixed integer nonlinear optimization problems. Engineering Optimization, 1-19. https://doi.org/10.1080/0305215x.2021.1904918

Zhang, Y., Sahinidis, N., Nohra, C., & Rong, G. (2020). Optimality-based domain reduction for inequality-constrained NLP and MINLP problems. Journal Of Global Optimization, 77(3), 425-454. https://doi.org/10.1007/s10898-020-00886-z