Disjunctive inequalities - Revision history

Drm323: /* Big-M Method */

2021-12-16T03:06:23Z

Big-M Method

← Older revision		Revision as of 23:06, 15 December 2021
Line 139:		Line 139:
	===Big-M Method===		===Big-M Method===

	We begin by setting 2 ~~binaries~~ variables <math>y_1</math> and <math>y_2</math>.		We now present the same constraint set reformulated by the Big-M method. We can begin by setting 2 binary variables <math>y_1</math> and <math>y_2</math> summing to 1.

	<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}		<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Drm323: /* Big-M Method */

2021-12-16T03:05:23Z

Big-M Method

← Older revision		Revision as of 23:05, 15 December 2021
Line 143:		Line 143:
	<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}		<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

	Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting <math> M*(1-y_i) </math> depending on if the inequality is greater than or less than.		Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting <math> M*(1-y_i) </math> depending on if the inequality is greater than or equal to, or less than or equal to.

	<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>		<math>-M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>

	<math> M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>		<math>-M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>

	<math> M*(1-y_1)+1 \leq x_2+x_3 \leq 7+M(1-y_1)</math>		<math>-M*(1-y_1)+1 \leq x_2+x_3 \leq 7+M(1-y_1)</math>

	<math>-M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>		<math>-M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>

Drm323: /* Big-M Method */

2021-12-16T03:04:33Z

Big-M Method

← Older revision		Revision as of 23:04, 15 December 2021
Line 143:		Line 143:
	<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}		<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

	Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting <math> M*(1-y_i) <math> depending on if the inequality is greater than or less than.		Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting <math> M*(1-y_i) </math> depending on if the inequality is greater than or less than.

	<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>		<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>

Drm323: /* Big-M Method */

2021-12-16T03:04:08Z

Big-M Method

← Older revision		Revision as of 23:04, 15 December 2021
Line 143:		Line 143:
	<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}		<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

	Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality.		Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting <math> M*(1-y_i) <math> depending on if the inequality is greater than or less than.

	<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>		<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>
Line 149:		Line 149:
	<math> M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>		<math> M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>

	<math> M*(1-y_1)+1 \leq x_3 \leq 7+M(1-y_1)</math>		<math> M*(1-y_1)+1 \leq x_2+x_3 \leq 7+M(1-y_1)</math>

	<math>~~\neg~~ M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>		<math>-M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>

	<math>~~\neg~~ M*(1-y_2)+4 \leq x_2 \leq 6+M(1-y_2)</math>		<math>-M*(1-y_2)+4 \leq x_2 \leq 6+M(1-y_2)</math>

	<math>~~\neg~~ M*(1-y_2)+2 \leq x_3 \leq 8+M(1-y_2)</math>		<math>-M*(1-y_2)+2 \leq x_2+x_3 \leq 8+M(1-y_2)</math>

	In this way, if <math>y_1 = 1</math> and <math>y_2 = 0</math> the first set of inequalities is enforced and the second set of inequalities are dramatically ~~expanding rendering~~ them ~~effectively~~.		In this way, if <math>y_1 = 1</math> and <math>y_2 = 0</math> the first set of inequalities is enforced and the second set of inequalities are dramatically expanded, effectively keeping them from constraining the problem, given that <math>M</math> is large enough.

	==Applications==		==Applications==

Md992: /* Big-M Method */

2021-12-16T02:54:25Z

Big-M Method

← Older revision		Revision as of 22:54, 15 December 2021
Line 139:		Line 139:
	===Big-M Method===		===Big-M Method===

	We begin by setting 2 binaries variables <math>y_1</math> and <math>~~y_1~~</math>.		We begin by setting 2 binaries variables <math>y_1</math> and <math>y_2</math>.

	<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}		<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Md992: /* Numerical Example */

2021-12-16T02:48:43Z

Numerical Example

← Older revision		Revision as of 22:48, 15 December 2021
Line 85:		Line 85:
	==Numerical Example==		==Numerical Example==

	Given the following Disjunctive Inequality form below, reformulate the following problem using ~~C0onvex~~ Hull method and Big-M:		Given the following Disjunctive Inequality form below, reformulate the following problem using Convex Hull method and Big-M:

	<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor		<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor

Md992: /* Numerical Example */

2021-12-16T02:48:29Z

Numerical Example

← Older revision		Revision as of 22:48, 15 December 2021
Line 85:		Line 85:
	==Numerical Example==		==Numerical Example==

	Given the following Disjunctive Inequality form below, reformulate the following problem using ~~convex hull~~ method and Big-M:		Given the following Disjunctive Inequality form below, reformulate the following problem using C0onvex Hull method and Big-M:

	<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor		<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor

Md992: /* Big-M Method */

2021-12-16T02:47:55Z

Big-M Method

← Older revision		Revision as of 22:47, 15 December 2021
Line 145:		Line 145:
	Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality.		Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality.

	<math>~~\neg~~ M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>		<math> M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>

	<math>~~\neg~~ M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>		<math> M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>

	<math>~~\neg~~ M*(1-y_1)+1 \leq x_3 \leq 7+M(1-y_1)</math>		<math> M*(1-y_1)+1 \leq x_3 \leq 7+M(1-y_1)</math>

	<math>\neg -M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>		<math>\neg M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>

	<math>\neg -M*(1-y_2)+4 \leq x_2 \leq 6+M(1-y_2)</math>		<math>\neg M*(1-y_2)+4 \leq x_2 \leq 6+M(1-y_2)</math>

	<math>\neg -M*(1-y_2)+2 \leq x_3 \leq 8+M(1-y_2)</math>		<math>\neg M*(1-y_2)+2 \leq x_3 \leq 8+M(1-y_2)</math>

	In this way, if <math>y_1 = 1</math> and <math>y_2 = 0</math> the first set of inequalities is enforced and the second set of inequalities are dramatically expanding rendering them effectively.		In this way, if <math>y_1 = 1</math> and <math>y_2 = 0</math> the first set of inequalities is enforced and the second set of inequalities are dramatically expanding rendering them effectively.

Md992: /* Numerical Example */

2021-12-16T02:47:14Z

Numerical Example

← Older revision		Revision as of 22:47, 15 December 2021
Line 84:		Line 84:

	==Numerical Example==		==Numerical Example==
	~~===Convex Hull Method===~~
	Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:		Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method and Big-M:

	<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor		<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor
Line 92:		Line 92:

	</math>		</math>
			===Convex Hull Method===
	We begin by setting introducing a binary variable y as a summation to 1:		We begin by setting introducing a binary variable y as a summation to 1:

Line 136:		Line 136:

	The reformulated constraint set is thus all of these constraints, making the problem a MIP.		The reformulated constraint set is thus all of these constraints, making the problem a MIP.

			===Big-M Method===

			We begin by setting 2 binaries variables <math>y_1</math> and <math>y_1</math>.

			<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

			Next, we add the binary variable <math>M</math> as it is a arbitrarily large constant which is used to reformulate the inequality.

			<math>\neg M*(1-y_1)+0 \leq x_1 \leq 13+M(1-y_1)</math>

			<math>\neg M*(1-y_1)+0 \leq x_2 \leq 4+M(1-y_1)</math>

			<math>\neg M*(1-y_1)+1 \leq x_3 \leq 7+M(1-y_1)</math>

			<math>\neg -M*(1-y_2)+2 \leq x_1 \leq 10+M(1-y_2)</math>

			<math>\neg -M*(1-y_2)+4 \leq x_2 \leq 6+M(1-y_2)</math>

			<math>\neg -M*(1-y_2)+2 \leq x_3 \leq 8+M(1-y_2)</math>

			In this way, if <math>y_1 = 1</math> and <math>y_2 = 0</math> the first set of inequalities is enforced and the second set of inequalities are dramatically expanding rendering them effectively.

	==Applications==		==Applications==

Drm323: /* Convex Hull Method */

2021-12-16T02:36:09Z

Convex Hull Method

← Older revision		Revision as of 22:36, 15 December 2021
Line 87:		Line 87:
	Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:		Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

	<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_3 \le 7 \end{bmatrix} \lor		<math>\begin{bmatrix} y \\ 0\le x_1 \le13 \\ 0\le x_2 \le4 \\ 1\le x_2 + x_3 \le 7 \end{bmatrix} \lor

	\begin{bmatrix} \neg y \\ 2\le x_1 \le10 \\ 4\le x_2 \le6\ \\ 2\le x_3 \le 8 \end{bmatrix}		\begin{bmatrix} \neg y \\ 2\le x_1 \le10 \\ 4\le x_2 \le6\ \\ 2\le x_2 + x_3 \le 8 \end{bmatrix}

	</math>		</math>
Line 127:		Line 127:
	<math> 0\leq x_{21}\leq y_{1}*4 </math>		<math> 0\leq x_{21}\leq y_{1}*4 </math>

	<math> 1y_{1}\leq x_{31}\leq y_{1}7 </math>		<math> 1y_{1}\leq x_{21} + x_{31}\leq y_{1}7 </math>

	<math> 2y_{2}\leq x_{12}\leq y_{2}10 </math>		<math> 2y_{2}\leq x_{12}\leq y_{2}10 </math>
Line 133:		Line 133:
	<math> 4y_{2}\leq x_{22}\leq y_{2}6 </math>		<math> 4y_{2}\leq x_{22}\leq y_{2}6 </math>

	<math> 2y_{2}\leq x_{22}\leq y_{2}8 </math>		<math> 2y_{2}\leq x_{22} + x_{32}\leq y_{2}8 </math>

	The reformulated constraint set is thus all of these constraints, making the problem a MIP.		The reformulated constraint set is thus all of these constraints, making the problem a MIP.