Branch and cut - Revision history

Wc593 at 11:38, 21 December 2020

2020-12-21T11:38:14Z

← Older revision		Revision as of 07:38, 21 December 2020
Line 1:		Line 1:
	Author: Lindsay Siegmundt, Peter Haddad, Chris Babbington, Jon Boisvert, Haris Shaikh (SysEn ~~6800~~ Fall 2020)		Author: Lindsay Siegmundt, Peter Haddad, Chris Babbington, Jon Boisvert, Haris Shaikh (SysEn 5800 Fall 2020)

	~~Steward: Wei-Han Chen, Fengqi You~~

	== Introduction ==		== Introduction ==

Wc593: /* Strong Branching: */

2020-12-21T10:53:15Z

Strong Branching:

← Older revision		Revision as of 06:53, 21 December 2020
Line 25:		Line 25:

	==== '''Strong Branching:''' ====		==== '''Strong Branching:''' ====
	For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable ~~for the current~~ for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.<ref>A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation<nowiki/>https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf</ref>		For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.<ref>A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation<nowiki/>https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf</ref>

	==== '''Pseudo Cost:''' ====		==== '''Pseudo Cost:''' ====

Hs2222 at 04:10, 14 December 2020

2020-12-14T04:10:11Z

← Older revision		Revision as of 00:10, 14 December 2020
Line 4:		Line 4:

	== Introduction ==		== Introduction ==
	The Branch and Cut methodology was discovered in the 90s as a way to solve/optimize Mixed-Integer Linear Programs (Karamanov, Miroslav). This concept is comprised of two known optimization methodologies - Branch and Bound and Cutting Planes. Utilizing these two tools allows for the Branch and Cut to find an optimal solution through relaxing the problem to produce the upper bound. Relaxing the problem allows for the complex problem to be simplified in order for it to be solve more easily. Furthermore, the upper bound represents the highest value the objective can take in order to be feasible. The optimal solution is found when the objective is equal to the upper bound (Luedtke, Jim). This methodology is critical to the future of optimization since it combines two common tools in order to utilize each component in order to find the optimal solution. Moving forward, the critical components of different methodologies could be combined in order to find optimality in a more simple and direct manner.		The Branch and Cut methodology was discovered in the 90s as a way to solve/optimize Mixed-Integer Linear Programs (Karamanov, Miroslav)<ref>Karamanov, Miroslav. “Branch and Cut: An Empirical Study.” ''Carnegie Mellon University'' , Sept. 2006, https://www.cmu.edu/tepper/programs/phd/program/assets/dissertations/2006-operations-research-karamanov-dissertation.pdf.</ref>. This concept is comprised of two known optimization methodologies - Branch and Bound and Cutting Planes. Utilizing these two tools allows for the Branch and Cut to find an optimal solution through relaxing the problem to produce the upper bound. Relaxing the problem allows for the complex problem to be simplified in order for it to be solve more easily. Furthermore, the upper bound represents the highest value the objective can take in order to be feasible. The optimal solution is found when the objective is equal to the upper bound (Luedtke, Jim)<ref>Luedtke, Jim. “The Branch-and-Cut Algorithm for Solving Mixed-Integer Optimization Problems.” ''Institute for Mathematicians and Its Applications'', 10 Aug. 2016, https://www.ima.umn.edu/materials/2015-2016/ND8.1-12.16/25397/Luedtke-mip-bnc-forms.pdf.</ref>. This methodology is critical to the future of optimization since it combines two common tools in order to utilize each component in order to find the optimal solution. Moving forward, the critical components of different methodologies could be combined in order to find optimality in a more simple and direct manner.

	== Methodology & Algorithm ==		== Methodology & Algorithm ==
Line 22:		Line 22:

	==== Most Infeasible Branching: ====		==== Most Infeasible Branching: ====
	Most infeasible branching is a very popular method that picks the variable with fractional part closest to <math>0:5</math>, i.e.,<math> si = 0:5-\|xA_i- xA_i-0:5\|</math><ref>Branching rules revisited Tobias Achterberga;∗, Thorsten Kocha, Alexander Martinb</ref>. Most infeasible branching picks a variable where the least tendency can be recognized to which side the variable should be rounded. However, the performance of this method is not any superior to the rule of selecting a variable randomly.		Most infeasible branching is a very popular method that picks the variable with fractional part closest to <math>0:5</math>, i.e.,<math> si = 0:5-\|xA_i- xA_i-0:5\|</math><ref>Branching rules revisited Tobias Achterberga;∗, Thorsten Kocha, Alexander Martinb https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf</ref>. Most infeasible branching picks a variable where the least tendency can be recognized to which side the variable should be rounded. However, the performance of this method is not any superior to the rule of selecting a variable randomly.

	==== '''Strong Branching:''' ====		==== '''Strong Branching:''' ====
	For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.<ref>https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf</ref>		For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.<ref>A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation<nowiki/>https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf</ref>

	==== '''Pseudo Cost:''' ====		==== '''Pseudo Cost:''' ====
	[[File:Image.png\|thumb\|Pure psuedo cost branching]]		[[File:Image.png\|thumb\|Pure psuedo cost branching]]

			Another way to approximate a relaxation value is by utilizing a pseudo cost method. The pseudo-cost of a variable is an estimate of the per unit change in the objective function from making the value of the variable to be rounded up or down. For each variable we choose variable with the largest estimated LP objective gain<ref>Advances in Mixed Integer Programming http://scip.zib.de/download/slides/SCIP-branching.ppt</ref>.
	Another way to approximate a relaxation value is by utilizing a pseudo cost method. The pseudo-cost of a variable is an estimate of the per unit change in the objective function from making the value of the variable to be rounded up or down. For each variable we choose variable with the largest estimated LP objective gain<ref>http://scip.zib.de/download/slides/SCIP-branching.ppt</ref>.
	==='''Algorithm'''===		==='''Algorithm'''===
	Branch and Cut for is a variation of the Branch and Bound algorithm. Branch and Cut incorporates Gomery cuts allowing the search space of the given problem. The standard Simplex Algorithm will be used to solve each Integer Linear Programming Problem (LP).		Branch and Cut for is a variation of the Branch and Bound algorithm. Branch and Cut incorporates Gomery cuts allowing the search space of the given problem. The standard Simplex Algorithm will be used to solve each Integer Linear Programming Problem (LP).
Line 88:		Line 87:
	'''Step 6. Partition'''		'''Step 6. Partition'''

	Let <math>D^{lj=k}_{j=1}</math> be a partition of the constraint set <math>D</math> of problem <math>LP_l</math>. Add problems <math>D^{lj=k}_{j=1}</math> to L, where <math>LP^l_j</math> is <math>LP_l</math> with feasible region restricted to <math>D^l_j</math> and <math>Z_{lj}</math> for j=1,...k is set to the value of <math>Z^l</math> for the parent problem l. Go to step 3.		Let <math>D^{lj=k}_{j=1}</math> be a partition of the constraint set <math>D</math> of problem <math>LP_l</math>. Add problems <math>D^{lj=k}_{j=1}</math> to L, where <math>LP^l_j</math> is <math>LP_l</math> with feasible region restricted to <math>D^l_j</math> and <math>Z_{lj}</math> for j=1,...k is set to the value of <math>Z^l</math> for the parent problem l. Go to step 3.<ref name=":0">Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.</ref>

	==Numerical Example==		==Numerical Example==
Line 158:		Line 157:

	=== '''Combinatorial Optimization''' ===		=== '''Combinatorial Optimization''' ===
	Combinatorial Optimization is a great application for Branch and Cut. This style of optimization is the methodology of utilizing the finite known sets and information of the sets to optimize the solution. The original intent for this application was for maximizing flow as well as in the transportation industry (Maltby and Ross). This combinatorial optimization has also taken on some new areas where it is used often. Combinatorial Optimization is now an imperative component in studying artificial intelligence and machine learning algorithms to optimize solutions. The finite sets that Combinatorial Optimization tends to utilize and focus on includes graphs, partially ordered sets, and structures that define linear independence call matroids.		Combinatorial Optimization is a great application for Branch and Cut. This style of optimization is the methodology of utilizing the finite known sets and information of the sets to optimize the solution. The original intent for this application was for maximizing flow as well as in the transportation industry (Maltby and Ross). This combinatorial optimization has also taken on some new areas where it is used often. Combinatorial Optimization is now an imperative component in studying artificial intelligence and machine learning algorithms to optimize solutions. The finite sets that Combinatorial Optimization tends to utilize and focus on includes graphs, partially ordered sets, and structures that define linear independence call matroids.<ref>[https://brilliant.org/wiki/combinatorial-optimization/ Maltby, Henry, and Eli Ross. “Combinatorial Optimization.” ''Brilliant Math & Science Wiki'', https://brilliant.org/wiki/combinatorial-optimization/.]</ref>

	=== '''Bender’s Decomposition''' ===		=== '''Bender’s Decomposition''' ===
	Bender’s Decomposition is another Branch and Cut application that is utilized widely in Stochastic Programming. Bender’s Decomposition is where you take the initial problem and divide into two distinct subsets. By dividing the problem into two separate problems you are able to solve each set easier than the original instance (Benders). Therefore the first problem within the subset created can be solved for the first variable set. The second sub problem is then solved for, given that first problem solution. Doing this allows for the sub problem to be solved to determine whether the first problem is infeasible (Benders). Bender’s cuts can be added to constrain the problem until a feasible solution can be found.		Bender’s Decomposition is another Branch and Cut application that is utilized widely in Stochastic Programming. Bender’s Decomposition is where you take the initial problem and divide into two distinct subsets. By dividing the problem into two separate problems you are able to solve each set easier than the original instance (Benders). Therefore the first problem within the subset created can be solved for the first variable set. The second sub problem is then solved for, given that first problem solution. Doing this allows for the sub problem to be solved to determine whether the first problem is infeasible (Benders). Bender’s cuts can be added to constrain the problem until a feasible solution can be found.<ref name=":0" />

	=== '''Large-Scale Symmetric Traveling Salesmen Problem''' ===		=== '''Large-Scale Symmetric Traveling Salesmen Problem''' ===
	The Large-Scale Symmetric Traveling Salesmen Problem is a common problem that was always looked into optimizing for the shortest route while visiting each city once and returning to the original city at the end. On a larger scale this style of problem must be broken down into subsets or nodes (SIAM). By constraining this style of problem such as the methods of Combinatorial Optimization, the Traveling Salesmen Problem can be viewed as partially ordered sets. By doing this on a large scale with finite cities you are able to optimize the shortest path taken and ensure each city is only visited once.		The Large-Scale Symmetric Traveling Salesmen Problem is a common problem that was always looked into optimizing for the shortest route while visiting each city once and returning to the original city at the end. On a larger scale this style of problem must be broken down into subsets or nodes (SIAM). By constraining this style of problem such as the methods of Combinatorial Optimization, the Traveling Salesmen Problem can be viewed as partially ordered sets. By doing this on a large scale with finite cities you are able to optimize the shortest path taken and ensure each city is only visited once.<ref>Society for Industrial and Applied Mathematics. “SIAM Rev.” ''SIAM Review'', 18 July 2006, https://epubs.siam.org/doi/10.1137/1033004</ref>

	=== '''Submodular Function''' ===		=== '''Submodular Function''' ===
	Submodular Function is another function in which is used throughout artificial intelligence as well as machine learning. The reason for this is because as inputs are increased into the function the value or outputs decrease. This allows for a great optimization features in the cases stated above because inputs are continually growing. This allows for machine learning and artificial intelligence to continue to grow based on these algorithms (Tschiatschek, Iyer, and Bilmes). By enforcing new inputs to the system the system will learn more and more to ensure it optimizes the solution that is to be made.		Submodular Function is another function in which is used throughout artificial intelligence as well as machine learning. The reason for this is because as inputs are increased into the function the value or outputs decrease. This allows for a great optimization features in the cases stated above because inputs are continually growing. This allows for machine learning and artificial intelligence to continue to grow based on these algorithms (Tschiatschek, Iyer, and Bilmes)<ref>S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.</ref>. By enforcing new inputs to the system the system will learn more and more to ensure it optimizes the solution that is to be made.<ref>A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008</ref>

	==Conclusion==		==Conclusion==
	The Branch and Cut is an optimization algorithm used to optimize integer linear programming. It combines two other optimization algorithms - branch and bound and cutting planes in order to utilize the results from each method in order to create the most optimal solution. There are three different methodologies used within the specific method - most infeasible branching, strong branching, and pseudo code. Furthermore, Branch and Cut can be utilized it multiple scenarios - Submodular function, large-scale symmetric traveling salesmen problem, bender's decomposition, and combination optimization which increases the impact of the methodology.		The Branch and Cut is an optimization algorithm used to optimize integer linear programming. It combines two other optimization algorithms - branch and bound and cutting planes in order to utilize the results from each method in order to create the most optimal solution. There are three different methodologies used within the specific method - most infeasible branching, strong branching, and pseudo code. Furthermore, Branch and Cut can be utilized it multiple scenarios - Submodular function, large-scale symmetric traveling salesmen problem, bender's decomposition, and combination optimization which increases the impact of the methodology.

	==~~References~~==		==Reference==
			<references />
	~~# A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf~~
	~~# A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008~~
	~~# Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.~~
	~~# Karamanov, Miroslav. “Branch and Cut: An Empirical Study.” ''Carnegie Mellon University'' , Sept. 2006, https:~~/~~/www.cmu.edu/tepper/programs/phd/program/assets/dissertations/2006-operations-research-karamanov-dissertation.pdf.~~
	# Luedtke, Jim. “The Branch-and-Cut Algorithm for Solving Mixed-Integer Optimization Problems.” ''Institute for Mathematicians and Its Applications'', 10 Aug. 2016, https://www.ima.umn.edu/materials/2015-2016/ND8.1-12.16/25397/Luedtke-mip-bnc-forms.pdf.
	~~# Maltby, Henry, and Eli Ross. “Combinatorial Optimization.” ''Brilliant Math & Science Wiki'', https://brilliant.org/wiki/combinatorial-optimization/.~~
	~~# Society for Industrial and Applied Mathematics. “SIAM Rev.” ''SIAM Review'', 18 July 2006, https://epubs.siam.org/doi/10.1137/1033004.~~
	~~# S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.~~
	~~# Branching rules revisited Tobias Achterberga;∗, Thorsten Kocha, Alexander Martinb https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf~~
	~~# Advances in Mixed Integer Programming http://scip.zib.de/download/slides/SCIP-branching.ppt~~
	#

Hs2222 at 01:06, 14 December 2020

2020-12-14T01:06:54Z

← Older revision		Revision as of 21:06, 13 December 2020
Line 22:		Line 22:

	==== Most Infeasible Branching: ====		==== Most Infeasible Branching: ====
	Most infeasible branching is a very popular method that picks the variable with fractional part closest to <math>0:5</math>, i.e.,<math> si = 0:5-\|xA_i- xA_i-0:5\|</math>. Most infeasible branching picks a variable where the least tendency can be recognized to which side the variable should be rounded. However, the performance of this method is not any superior to the rule of selecting a variable randomly.		Most infeasible branching is a very popular method that picks the variable with fractional part closest to <math>0:5</math>, i.e.,<math> si = 0:5-\|xA_i- xA_i-0:5\|</math><ref>Branching rules revisited Tobias Achterberga;∗, Thorsten Kocha, Alexander Martinb</ref>. Most infeasible branching picks a variable where the least tendency can be recognized to which side the variable should be rounded. However, the performance of this method is not any superior to the rule of selecting a variable randomly.

	==== '''Strong Branching:''' ====		==== '''Strong Branching:''' ====
	For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.		For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.<ref>https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf</ref>

	==== '''Pseudo Cost:''' ====		==== '''Pseudo Cost:''' ====
	[[File:Image.png\|thumb\|Pure psuedo cost branching]]		[[File:Image.png\|thumb\|Pure psuedo cost branching]]
	Another way to approximate a relaxation value is by utilizing a pseudo cost method. The pseudo-cost of a variable is an estimate of the per unit change in the objective function from making the value of the variable to be rounded up or down. For each variable we choose variable with the largest estimated LP objective gain.

			Another way to approximate a relaxation value is by utilizing a pseudo cost method. The pseudo-cost of a variable is an estimate of the per unit change in the objective function from making the value of the variable to be rounded up or down. For each variable we choose variable with the largest estimated LP objective gain<ref>http://scip.zib.de/download/slides/SCIP-branching.ppt</ref>.
	==='''Algorithm'''===		==='''Algorithm'''===
	Branch and Cut for is a variation of the Branch and Bound algorithm. Branch and Cut incorporates Gomery cuts allowing the search space of the given problem. The standard Simplex Algorithm will be used to solve each Integer Linear Programming Problem (LP).		Branch and Cut for is a variation of the Branch and Bound algorithm. Branch and Cut incorporates Gomery cuts allowing the search space of the given problem. The standard Simplex Algorithm will be used to solve each Integer Linear Programming Problem (LP).
Line 172:		Line 174:
	==References==		==References==

			# A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf
	# A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008		# A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
	# Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.		# Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
Line 179:		Line 182:
	# Society for Industrial and Applied Mathematics. “SIAM Rev.” ''SIAM Review'', 18 July 2006, https://epubs.siam.org/doi/10.1137/1033004.		# Society for Industrial and Applied Mathematics. “SIAM Rev.” ''SIAM Review'', 18 July 2006, https://epubs.siam.org/doi/10.1137/1033004.
	# S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.		# S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.
			# Branching rules revisited Tobias Achterberga;∗, Thorsten Kocha, Alexander Martinb https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf
			# Advances in Mixed Integer Programming http://scip.zib.de/download/slides/SCIP-branching.ppt
	#		#

Texasbabb: /* Numerical Example */

2020-12-14T00:36:30Z

Numerical Example

← Older revision		Revision as of 20:36, 13 December 2020
Line 104:		Line 104:


	Branch on ~~x_1~~ to generate sub-problems		Branch on x<sub>1</sub> to generate sub-problems

	<math>min \ z=-4x_1-7x_2</math>		<math>min \ z=-4x_1-7x_2</math>

JonBoisvert: /* Step 2. Terminate: */

2020-12-14T00:33:12Z

Step 2. Terminate:

← Older revision		Revision as of 20:33, 13 December 2020
Line 75:		Line 75:
	'''Step 4. Cutting Planes:'''		'''Step 4. Cutting Planes:'''
	If a cutting plane is found:		If a cutting plane is found:
	then add to the ~~linear~~ Relaxation problem (as a constraint) and return to step 3.2		then add to the Linear Relaxation problem (as a constraint) and return to step 3.2
	Else:		Else:
	Continue.		Continue.

Texasbabb: /* Numerical Example */

2020-12-12T06:49:47Z

Numerical Example

← Older revision		Revision as of 02:49, 12 December 2020
Line 151:		Line 151:

	<math>z=-13.222,x_1=.778,x_2=1.444</math>		<math>z=-13.222,x_1=.778,x_2=1.444</math>





	~~min z = 4x1 + 7x2~~

	~~s.t. x<sub>1</sub> - x<sub>2</sub> ≥ 2~~
	~~-x<sub>1</sub> + 3x<sub>2</sub> ≥ 3~~
	~~x<sub>1</sub>, x<sub>2</sub> ≥ 0~~

	~~First Solution of LP = Min = 35.5 (x<sub>1</sub> = 4.5, x<sub>2</sub> = 2.5)~~

	~~Branch:~~

	~~min z = 4x<sub>1</sub> + 7x<sub>2</sub>~~

	~~s.t. x<sub>1</sub> - x<sub>2</sub> ≥ 2~~

	~~-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4~~

	~~x<sub>1</sub> ≥ 0~~

	~~x<sub>2</sub> ≥ 3~~

	~~Second Solution of LP = Min = 41 (x1 = 5, x2 = 3)~~

	~~Branch:~~

	~~min z = 4x<sub>1</sub> + 7x<sub>2</sub>~~

	~~s.t. x<sub>1</sub> - x<sub>2</sub> ≤ 2~~

	~~-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4~~

	~~x<sub>1</sub> ≥ 0~~

	~~x<sub>2</sub> ≤ 2~~

	~~Second Branch Solution of LP = Min = infeasible~~

	~~Add Cut:~~

	~~min z = 4x<sub>1</sub> + 7x<sub>2</sub>~~

	~~s.t. x<sub>1</sub> - x<sub>2</sub> ≤ 2~~

	~~-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4~~

	~~2x<sub>1</sub> ≤ 6 (Cut Dividing equation 1 by 2)~~

	~~x<sub>1</sub> ≤ 2~~

	~~x<sub>2</sub> ≥ 0~~

	~~Solution with cut = Min = -24.4 (x<sub>1</sub> = 2, x<sub>2</sub> = 1.2)~~

	==Application==		==Application==

Texasbabb: /* Numerical Example */

2020-12-12T06:44:46Z

Numerical Example

@@ Line 98: / Line 98: @@
 <math>x_1,x_2\geq0</math>
 <math>z =-19.56, x_1=1.88, x_2=1.72 </math>
-<math>z =-19.56, x_1=1.88, x_2=1.72</math>
 min z = 4x1 + 7x2
 s.t. x<sub>1</sub> - x<sub>2</sub> ≥ 2

Texasbabb: /* Numerical Example */

2020-12-12T05:43:25Z

Numerical Example

← Older revision		Revision as of 01:43, 12 December 2020
Line 89:		Line 89:

	==Numerical Example==		==Numerical Example==
	First, list out the ~~problem~~:		First, list out the MILP:

	<math>min \ z=-4x_1-7x_2</math>		<math>min \ z=-4x_1-7x_2</math>

			<math>6x_1 + x_2 \leq13</math>

			<math>-x_1+4x_2\leq5</math>

			<math>x_1,x_2\geq0</math>

			<math>z =-19.56, x_1=1.88, x_2=1.72 </math>

			<math>z =-19.56, x_1=1.88, x_2=1.72</math>



	min z = 4x1 + 7x2		min z = 4x1 + 7x2

Texasbabb: /* Numerical Example */

2020-12-11T07:11:04Z

Numerical Example

← Older revision		Revision as of 03:11, 11 December 2020
Line 91:		Line 91:
	First, list out the problem:		First, list out the problem:

	min z = -~~8x1~~ - ~~7x2~~		<math>min \ z=-4x_1-7x_2</math>

	s.t. 5x<sub>1</sub> - x<sub>2</sub> ~~≤ 13~~		min z = 4x1 + 7x2
	-x<sub>1</sub> + 5x<sub>2</sub> ~~≤ 4~~
			s.t. x<sub>1</sub> - x<sub>2</sub> ≥ 2
			-x<sub>1</sub> + 3x<sub>2</sub> ≥ 3
	x<sub>1</sub>, x<sub>2</sub> ≥ 0		x<sub>1</sub>, x<sub>2</sub> ≥ 0

	First Solution of ~~MILP~~ = Min = ~~-32~~.~~625~~ (x<sub>1</sub> = 2.~~875~~, x<sub>2</sub> = 1.~~3750~~)		First Solution of LP = Min = 35.5 (x<sub>1</sub> = 4.5, x<sub>2</sub> = 2.5)

	Branch:		Branch:

	min z = ~~-8x~~<sub>1</sub> - 7x<sub>2</sub>		min z = 4x<sub>1</sub> + 7x<sub>2</sub>

	s.t. 5x<sub>1</sub> - x<sub>2</sub> ~~≤ 13~~		s.t. x<sub>1</sub> - x<sub>2</sub> ≥ 2

	-x<sub>1</sub> + 5x<sub>2</sub> ≤ 4		-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4

	x<sub>1</sub> ~~≤ 2~~		x<sub>1</sub> ≥ 0

	x<sub>2</sub> ≥ 0		x<sub>2</sub> ≥ 3

	Second Solution of ~~MILP~~ = Min = ~~-24.4~~ (x1 = 2, x2 = ~~1.2~~)		Second Solution of LP = Min = 41 (x1 = 5, x2 = 3)

	Branch:		Branch:

	min z = ~~-8x~~<sub>1</sub> - 7x<sub>2</sub>		min z = 4x<sub>1</sub> + 7x<sub>2</sub>

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

	~~s.t.~~ 5x<sub>1</sub> ~~- x~~<sub>2</sub> ~~≤ 13~~		-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4

	-x<sub>1</sub> ~~+ 5x<sub>2</sub> ≤ 4~~		x<sub>1</sub> ≥ 0

	x<sub>1</sub> ≤ 2		x<sub>2</sub> ≤ 2

	~~x<sub>2</sub> ≥ 0~~		Second Branch Solution of LP = Min = infeasible

	Add Cut:		Add Cut:

	min z = ~~-8x~~<sub>1</sub> - 7x<sub>2</sub>		min z = 4x<sub>1</sub> + 7x<sub>2</sub>

	s.t. 5x<sub>1</sub> - x<sub>2</sub> ≤ 13		s.t. x<sub>1</sub> - x<sub>2</sub> ≤ 2

	-x<sub>1</sub> + 5x<sub>2</sub> ≤ 4		-x<sub>1</sub> + 3x<sub>2</sub> ≥ 4

	2x<sub>1</sub> ≤ 6 (Cut Dividing equation 1 by 2)		2x<sub>1</sub> ≤ 6 (Cut Dividing equation 1 by 2)