Branch and bound for MINLP - Revision history

Pnv4: Pnv4 moved page Branch and bound (BB) for MINLP to Branch and bound for MINLP

2021-12-15T01:56:08Z

Pnv4 moved page Branch and bound (BB) for MINLP to Branch and bound for MINLP

← Older revision	Revision as of 21:56, 14 December 2021
(No difference)

Pnv4 at 01:46, 15 December 2021

2021-12-15T01:46:31Z

← Older revision		Revision as of 21:46, 14 December 2021
Line 23:		Line 23:
	=== Initialization: Search Tree Root Value ===		=== Initialization: Search Tree Root Value ===

	# Upper bound = <math>inf</math>Lower bound = <math>-inf</math>		Step 1
			Upper bound = <math>inf</math>
			Lower bound = <math>-inf</math>

	# Initialize <math>y^0</math>		Step 2: Initialize <math>y^0</math>

	Initialization of binary variables (<math>y</math>) 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 <math>0\leq y\leq1</math>.		Initialization of binary variables (<math>y</math>) 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 <math>0\leq y\leq1</math>.

Pnv4 at 01:29, 15 December 2021

2021-12-15T01:29:39Z

← Older revision		Revision as of 21:29, 14 December 2021
Line 108:		Line 108:
	<math>\triangledown_x^2Obj= \begin{bmatrix} \frac{2^2Obj}{2x_1^2}\quad \frac{2^2Obj}{2x_12x_2} \\ \frac{2^2Obj}{2x_12x_2}\quad \frac{2^2Obj}{2x_2^2}\end{bmatrix} = \begin{bmatrix} 16(3)x_1^2-8x_2+2\quad -8x_1\\ -8x_1\qquad 2\end{bmatrix} = \begin{bmatrix} 10\quad -4\\ -4\qquad 2\end{bmatrix} = \binom{0.343}{11.66} </math>		<math>\triangledown_x^2Obj= \begin{bmatrix} \frac{2^2Obj}{2x_1^2}\quad \frac{2^2Obj}{2x_12x_2} \\ \frac{2^2Obj}{2x_12x_2}\quad \frac{2^2Obj}{2x_2^2}\end{bmatrix} = \begin{bmatrix} 16(3)x_1^2-8x_2+2\quad -8x_1\\ -8x_1\qquad 2\end{bmatrix} = \begin{bmatrix} 10\quad -4\\ -4\qquad 2\end{bmatrix} = \binom{0.343}{11.66} </math>

	Or det(~~<sub>x</sub><sup>2</sup>Obj~~)=20-11=9		Or <math>det(\triangledown_x^2Obj)=20-11=9</math>

	Principle minors =0		Principle minors <math>=0</math>

	== Application ==		== Application ==

Pnv4 at 01:28, 15 December 2021

2021-12-15T01:28:01Z

← Older revision		Revision as of 21:28, 14 December 2021
Line 106:		Line 106:
	<math>\triangledown_xObj </math> is positive definite for minimum		<math>\triangledown_xObj </math> is positive definite for minimum

	<math>\triangledown_x^2Obj= \begin{bmatrix} \frac{2^2Obj}{2x_1^2}\quad k \\ y\quad r\end{bmatrix} </math>		<math>\triangledown_x^2Obj= \begin{bmatrix} \frac{2^2Obj}{2x_1^2}\quad \frac{2^2Obj}{2x_12x_2} \\ \frac{2^2Obj}{2x_12x_2}\quad \frac{2^2Obj}{2x_2^2}\end{bmatrix} = \begin{bmatrix} 16(3)x_1^2-8x_2+2\quad -8x_1\\ -8x_1\qquad 2\end{bmatrix} = \begin{bmatrix} 10\quad -4\\ -4\qquad 2\end{bmatrix} = \binom{0.343}{11.66} </math>

	Or det(<sub>x</sub><sup>2</sup>Obj)=20-11=9		Or det(<sub>x</sub><sup>2</sup>Obj)=20-11=9

Pnv4 at 01:17, 15 December 2021

2021-12-15T01:17:56Z

← Older revision		Revision as of 21:17, 14 December 2021
Line 106:		Line 106:
	<math>\triangledown_xObj </math> is positive definite for minimum		<math>\triangledown_xObj </math> is positive definite for minimum

	<math>\triangledown_x^2Obj= </math>		<math>\triangledown_x^2Obj= \begin{bmatrix} \frac{2^2Obj}{2x_1^2}\quad k \\ y\quad r\end{bmatrix} </math>

	~~<sub>x</sub><sup>2</sup>Obj====~~

	Or det(<sub>x</sub><sup>2</sup>Obj)=20-11=9		Or det(<sub>x</sub><sup>2</sup>Obj)=20-11=9

Pnv4 at 00:01, 15 December 2021

2021-12-15T00:01:27Z

← Older revision		Revision as of 20:01, 14 December 2021
Line 129:		Line 129:

	== References ==		== 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		1. 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		2. 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		3. 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		4. 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

Pnv4: /* Numerical Solution */

2021-12-14T23:56:12Z

Numerical Solution

← Older revision		Revision as of 19:56, 14 December 2021
Line 105:		Line 105:

	<math>\triangledown_xObj </math> is positive definite for minimum		<math>\triangledown_xObj </math> is positive definite for minimum

			<math>\triangledown_x^2Obj= </math>

	<sub>x</sub><sup>2</sup>Obj====		<sub>x</sub><sup>2</sup>Obj====

Pnv4 at 23:46, 14 December 2021

2021-12-14T23:46:58Z

← Older revision		Revision as of 19:46, 14 December 2021
Line 116:		Line 116:

	== Mathematical Problem ==		== 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).		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 ==		== 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.		''' ''' 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.
	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.

	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 ==		== Conclusion ==
Line 129:		Line 127:

	== References ==		== 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. ~~<nowiki>~~https://doi.org/10.1007/s11081-019-09423-8~~</nowiki>~~		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. ~~<nowiki>~~https://doi.org/10.1016/j.ejor.2016.10.015~~</nowiki>~~		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. ~~<nowiki>~~https://doi.org/10.1080/0305215x.2021.1904918~~</nowiki>~~		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. ~~<nowiki>~~https://doi.org/10.1007/s10898-020-00886-z~~</nowiki>~~		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

Pnv4 at 23:08, 14 December 2021

2021-12-14T23:08:05Z

← Older revision		Revision as of 19:08, 14 December 2021
Line 90:		Line 90:
	<math>s.t \quad -1\leq x_1 \leq 1 </math>		<math>s.t \quad -1\leq x_1 \leq 1 </math>

	~~''s.t.'' -1≤''x''~~<~~sub~~>1</~~sub~~>≤1		<math> \quad -1\leq x_2 \leq 1 </math>

	~~-1≤''x''<sub>2</sub>≤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.

	~~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~~.		<math>Obj=4(0.5)^4-4(0.5) (0.5)^4+ (0.5)^2+ (0.5)^2-0.5+1=

	~~Obj=4(~~0.~~5)<sup>4</sup>~~-4(0.5~~) (~~0.~~5)<sup>4</sup>~~+ (0.~~5)<sup>2</sup>~~+ (0.~~5)<sup>2</sup>~~-0.5+1=		0.25-0.5+0.25+0.25+0.25-0.5+1=0.75</math>

	~~0.25-0.5+0.25+0.25+0.25-0.5+1~~=0~~.75~~		<math>\triangledown_xObj=0 </math>

	<~~sub~~>x</~~sub~~>~~Obj=0~~ =0= 4(4)~~''x''<sub>1</sub><sup>~~3~~</sup>~~-~~8''x''<sub>2</sub>''x''<sub>1</sub>~~+~~2''x''<sub>1</sub>~~-1=2-2+1-1=0		<math>\frac{2Obj}{2x_1}</math><math>= 0 = 4(4)x_1^3-8x_2x_1+2x_1-1=2-2+1-1=0</math>

	~~=0= -4''x''~~<~~sub~~>1</~~sub~~><~~sup~~>2~~</sup>~~+~~2''x''<sub>2</sub>~~=-1+1=0		<math>\frac{2Obj}{2x_2}</math><math>= 0 = -4x_1^2+2x_2=-1+1=0</math>

	<~~sub~~>x</~~sub~~>~~Obj~~ is positive definite for minimum		<math>\triangledown_xObj </math> is positive definite for minimum

	<sub>x</sub><sup>2</sup>Obj====		<sub>x</sub><sup>2</sup>Obj====

Pnv4 at 22:57, 14 December 2021

2021-12-14T22:57:10Z

← Older revision		Revision as of 18:57, 14 December 2021
Line 86:		Line 86:
	Consider the optimization problem with the following objective function and constraints		Consider the optimization problem with the following objective function and constraints

	~~Min 4''x''~~<~~sub>1</sub><sup~~>4~~</sup>~~-~~4''x''<sub>~~2~~</sub>''x''<sub>1</sub><sup>~~2~~</sup>~~+~~''x''<sub>~~2~~</sub><sup>2</sup>~~+~~''x''<sub>~~1</~~sub><sup~~>2<~~/sup~~>-~~''x''<sub>~~1</~~sub~~>+1		<math>\min\ 4x_1^4-4x_2x_1^2+x_2^2+x_1^2-x_1+1</math>

			<math>s.t \quad -1\leq x_1 \leq 1 </math>

	''s.t.'' -1≤''x''<sub>1</sub>≤1		''s.t.'' -1≤''x''<sub>1</sub>≤1