Set covering problem - Revision history

Wc593 at 11:36, 21 December 2020

2020-12-21T11:36:18Z

← Older revision		Revision as of 07:36, 21 December 2020
Line 1:		Line 1:
	Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud		Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud (ChemE 6800 Fall 2020)
	~~<br>~~
	~~Steward: Allen Yang, Fengqi You~~

	== Introduction ==		== Introduction ==

Wc593: /* Approximation via LP relaxation and rounding */

2020-12-21T10:38:51Z

Approximation via LP relaxation and rounding

← Older revision		Revision as of 06:38, 21 December 2020
Line 40:		Line 40:

	== Approximation via LP relaxation and rounding ==		== Approximation via LP relaxation and rounding ==
	Set covering is a classical integer programming problem and solving integer program in general is NP-hard. Therefore, one approach to achieve an <math> O</math>(log<math>n</math>) approximation to set covering problem in polynomial time is solving via linear programming (LP) relaxation algorithms <ref name="one"> T. Grossman and A. Wool, [https://www.sciencedirect.com/science/article/abs/pii/S0377221796001610 "Computational experience with approximation algorithms for the set covering problem]," ''European Journal of Operational Research'', vol. 101, pp. 81-92, 1997. </ref> <ref name="twelve"> Williamson, David P., and David B. Shmoys. “The Design of Approximation Algorithms” [https://www.designofapproxalgs.com/book.pdf]. “Cambridge University Press”, 2011. </ref>. In LP relaxation, we relax the integrality requirement into a linear constraints. For instance, if we replace the constraints <math> y_i \in \{0, 1\}</math> with the constraints <math> 0 =< y_i <= 1 </math>, we obtain the following LP problem that can be solved in polynomial time:		Set covering is a classical integer programming problem and solving integer program in general is NP-hard. Therefore, one approach to achieve an <math> O</math>(log<math>n</math>) approximation to set covering problem in polynomial time is solving via linear programming (LP) relaxation algorithms <ref name="one"> T. Grossman and A. Wool, [https://www.sciencedirect.com/science/article/abs/pii/S0377221796001610 "Computational experience with approximation algorithms for the set covering problem]," ''European Journal of Operational Research'', vol. 101, pp. 81-92, 1997. </ref> <ref name="twelve"> Williamson, David P., and David B. Shmoys. “The Design of Approximation Algorithms” [https://www.designofapproxalgs.com/book.pdf]. “Cambridge University Press”, 2011. </ref>. In LP relaxation, we relax the integrality requirement into a linear constraints. For instance, if we replace the constraints <math> y_i \in \{0, 1\}</math> with the constraints <math> 0 \leq y_i \leq 1 </math>, we obtain the following LP problem that can be solved in polynomial time:

	minimize <math>\sum_{i=1}^n c_i y_i</math>		minimize <math>\sum_{i=1}^n c_i y_i</math>

	subject to <math> \sum_{i=1}^n y_i >= 1, \forall i= 1,....,m</math>		subject to <math> \sum_{i=1}^n y_i \geq 1, \forall i= 1,....,m</math>

	<math> 0 =< y_i<= 1, \forall i = 1,....,n</math>		<math> 0 \leq y_i\leq 1, \forall i = 1,....,n</math>

	The above LP formulation is a relaxation of the original ILP set cover problem. This means that every feasible solution of the integer program is also feasible for this LP program. Additionally, the value of any feasible solution for the integer program is the same value in LP since the objective functions of both integer and linear programs are the same. Solving the LP program will result in an optimal solution that is a lower bound for the original integer program since the minimization of LP finds a feasible solution of lowest possible values. Moreover, we use LP rounding algorithms to directly round the fractional LP solution to an integral combinatorial solution as follows:		The above LP formulation is a relaxation of the original ILP set cover problem. This means that every feasible solution of the integer program is also feasible for this LP program. Additionally, the value of any feasible solution for the integer program is the same value in LP since the objective functions of both integer and linear programs are the same. Solving the LP program will result in an optimal solution that is a lower bound for the original integer program since the minimization of LP finds a feasible solution of lowest possible values. Moreover, we use LP rounding algorithms to directly round the fractional LP solution to an integral combinatorial solution as follows:
Line 55:		Line 55:
	<br>		<br>

	Suppose we have an optimal solution <math> z^* </math> for the linear programming relaxation of the set cover problem. We round the fractional solution <math> z^* </math> to an integer solution <math> z </math> using LP rounding algorithm. In general, there are two approaches for rounding algorithms, deterministic and randomized rounding algorithm. In this section, we will explain the deterministic algorithms.In this approach, we include subset <math> s_i </math> in our solution if <math> z^* >= 1/d </math>, where <math> d </math> is the maximum number of sets in which any element appears. In practice, we set <math> z </math> to be as follows:<ref name="twelve"> Williamson, David P., and David B. Shmoys. “The Design of Approximation Algorithms” [https://www.designofapproxalgs.com/book.pdf]. “Cambridge University Press”, 2011. </ref>		Suppose we have an optimal solution <math> z^* </math> for the linear programming relaxation of the set cover problem. We round the fractional solution <math> z^* </math> to an integer solution <math> z </math> using LP rounding algorithm. In general, there are two approaches for rounding algorithms, deterministic and randomized rounding algorithm. In this section, we will explain the deterministic algorithms. In this approach, we include subset <math> s_i </math> in our solution if <math> z^* \geq 1/d </math>, where <math> d </math> is the maximum number of sets in which any element appears. In practice, we set <math> z </math> to be as follows:<ref name="twelve"> Williamson, David P., and David B. Shmoys. “The Design of Approximation Algorithms” [https://www.designofapproxalgs.com/book.pdf]. “Cambridge University Press”, 2011. </ref>

	<math> z = \begin{cases} 1, & \text{if } z^*>= 1/d \\ 0, & \text{otherwise } \end{cases}</math>		<math> z = \begin{cases} 1, & \text{if } z^*\geq 1/d \\ 0, & \text{otherwise } \end{cases}</math>

	The rounding algorithm is an approximation algorithm for the set cover problem. It is clear that the algorithm converge in polynomial time and <math> z </math> is a feasible solution to the integer program.		The rounding algorithm is an approximation algorithm for the set cover problem. It is clear that the algorithm converge in polynomial time and <math> z </math> is a feasible solution to the integer program.

Wc593: /* Integer linear program formulation */

2020-12-21T10:37:02Z

Integer linear program formulation

← Older revision		Revision as of 06:37, 21 December 2020
Line 31:		Line 31:
	'''Constraints '''		'''Constraints '''

	<math> \sum_{i=1}^n y_i >= 1, \forall i= 1,....,m</math>		<math> \sum_{i=1}^n y_i \geq 1, \forall i= 1,....,m</math>

	<math> y_i \in \{0, 1\}, \forall i = 1,....,n</math>		<math> y_i \in \{0, 1\}, \forall i = 1,....,n</math>

Sherry Liang: /* Numerical Example */

2020-12-15T04:48:43Z

Numerical Example

← Older revision		Revision as of 00:48, 15 December 2020
Line 398:		Line 398:

	We have a set <math>U</math> (stadium areas) that needs to be covered with <math>C</math> (camera locations).		We have a set <math>U</math> (stadium areas) that needs to be covered with <math>C</math> (camera locations).


	<math>U = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}</math>		<math>U = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}</math>
Line 418:		Line 419:

	<math>C_8 = \{1,2,4,6,8,12\} </math>		<math>C_8 = \{1,2,4,6,8,12\} </math>


	The cost of each Camera Location is the same in this case, we just hope to minimize the total number of cameras used, so we can assume the cost of each <math>C</math> to be 1.		The cost of each Camera Location is the same in this case, we just hope to minimize the total number of cameras used, so we can assume the cost of each <math>C</math> to be 1.

Sherry Liang: /* Numerical Example */

2020-12-15T04:46:31Z

Numerical Example

← Older revision		Revision as of 00:46, 15 December 2020
Line 452:		Line 452:

	Since <math>C_1</math>, <math>C_2</math>, <math>C_6</math> all have meaningful and the same values, we can choose either both <math>C_1</math> and <math>C_6</math> or both <math>C_2</math> and <math>C_6</math>, as <math>C_1</math> or <math>C_2 </math> add <math>7</math> to <math>I</math>, and <math>C_6</math> add <math>15</math> to <math>I</math>.		Since <math>C_1</math>, <math>C_2</math>, <math>C_6</math> all have meaningful and the same values, we can choose either both <math>C_1</math> and <math>C_6</math> or both <math>C_2</math> and <math>C_6</math>, as <math>C_1</math> or <math>C_2 </math> add <math>7</math> to <math>I</math>, and <math>C_6</math> add <math>15</math> to <math>I</math>.

			<math>I</math> becomes <math>\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}</math>.

	The solution we obtained is:		The solution we obtained is:

Sherry Liang: /* Numerical Example */

2020-12-15T04:45:00Z

Numerical Example

← Older revision		Revision as of 00:45, 15 December 2020
Line 393:		Line 393:


	~~<math>\{0,1\}</math>~~

	Let's now consider solving the problem using the greedy algorithm.
			'''Let's now consider solving the problem using the greedy algorithm.'''

	We have a set <math>U</math> (stadium areas) that needs to be covered with <math>C</math> (camera locations).		We have a set <math>U</math> (stadium areas) that needs to be covered with <math>C</math> (camera locations).

Sherry Liang: /* Numerical Example */

2020-12-15T04:43:49Z

Numerical Example

← Older revision		Revision as of 00:43, 15 December 2020
Line 110:		Line 110:
	We can then represent the above information using binary values. If the stadium area <math>i</math> can be covered with camera location <math>j</math>, then we have <math>y_{ij} = 1</math>. If not,<math>y_{ij} = 0</math>. For instance, stadium area 1 is covered by camera location 1, so <math>y_{11} = 1</math>, while stadium area 1 is not covered by camera location 2, so <math>y_{12} = 0</math>. The binary variables <math>y_{ij}</math> values are given in the table below:		We can then represent the above information using binary values. If the stadium area <math>i</math> can be covered with camera location <math>j</math>, then we have <math>y_{ij} = 1</math>. If not,<math>y_{ij} = 0</math>. For instance, stadium area 1 is covered by camera location 1, so <math>y_{11} = 1</math>, while stadium area 1 is not covered by camera location 2, so <math>y_{12} = 0</math>. The binary variables <math>y_{ij}</math> values are given in the table below:
	{\| class="wikitable"		{\| class="wikitable"
	\|+Table 3 Binary Table (All Camera Locations and Stadium Areas)		\|+Table 2 Binary Table (All Camera Locations and Stadium Areas)
	!		!
	!Camera1		!Camera1

Sherry Liang: /* Numerical Example */

2020-12-15T04:43:20Z

Numerical Example

← Older revision		Revision as of 00:43, 15 December 2020
Line 433:		Line 433:
	<math>I</math> = <math>\{1,2,4,6,8,12\}</math>		<math>I</math> = <math>\{1,2,4,6,8,12\}</math>

	The per new element cost for <math>C_1 = 1/2</math>		The per new element cost for <math>C_1 = 1/2</math>, for <math>C_2 = 1/1</math>, for <math>C_3 = 1/4</math>, for <math>C_4 = 1/2</math>, for <math>C_5 = 1/3</math>, for <math>C_6 = 1/2</math>, for <math>C_7 = 1/1</math>

	~~The per new element cost for~~ <math>~~C_2 = 1~~/1</math>		Since <math>C_3</math> has minimum value, <math>C_3</math> is added, and <math>I</math> becomes <math>\{1,2,4,5,6,8,9,11,12,13\}</math>.

	The per new element cost for <math>~~C_3~~ = 1/4</math>		Third Iteration:

			<math>I</math> = <math>\{1,2,4,5,6,8,9,11,12,13\}</math>

			The per new element cost for <math>C_1 = 1/2</math>, for <math>C_2 = 1/1</math>, for <math>C_4 = 1/2</math>, for <math>C_5 = 1/3</math>, for <math>C_6 = 1/2</math>, for <math>C_7 = 1/1</math>

			Since <math>C_5</math> has minimum value, <math>C_5</math> is added, and <math>I</math> becomes <math>\{1,2,3,4,5,6,8,9,10,11,12,13,14\}</math>.

			Fourth Iteration:

			<math>I</math> = <math>\{1,2,3,4,5,6,8,9,10,11,12,13,14\}</math>

			The per new element cost for <math>C_1 = 1/1</math>, for <math>C_2 = 1/1</math>, for <math>C_4 = 1/0</math>, for <math>C_6 = 1/1</math>, for <math>C_7 = 1/0</math>

	~~The per new element cost for~~ <math>~~C_4 = 1~~/2</math>		Since <math>C_1</math>, <math>C_2</math>, <math>C_6</math> all have meaningful and the same values, we can choose either both <math>C_1</math> and <math>C_6</math> or both <math>C_2</math> and <math>C_6</math>, as <math>C_1</math> or <math>C_2 </math> add <math>7</math> to <math>I</math>, and <math>C_6</math> add <math>15</math> to <math>I</math>.

	The ~~per new element cost for <math>C_5 = 1/3</math>~~		The solution we obtained is:

	~~The per new element cost for~~ <math>C_6 ~~= 1~~/2</math>		Option 1: <math>C_8</math> + <math>C_3</math> + <math>C_5</math> + <math>C_6</math> + <math>C_1</math>

	~~The per new element cost for~~ <math>~~C_7 = 1~~/1</math>		Option 2: <math>C_8</math> + <math>C_3</math> + <math>C_5</math> + <math>C_6</math> + <math>C_2</math>

	~~Since <math>C_3</math> has minimum value, <math>C_3</math> is added, and I becomes <math>\{1,2,4,5,6,8,9,11,12,13\}</math>~~.		The greedy algorithm does not provide the optimal solution in this case.

	~~Third Iteration:~~		The usual elimination algorithm would give us the minimum number of cameras that we need to install to be4, but the greedy algorithm gives us the minimum number of cameras that we need to install is 5.

	== Applications==		== Applications==

Sherry Liang: /* Numerical Example */

2020-12-15T04:32:56Z

Numerical Example

@@ Line 425: / Line 425: @@
 First Iteration:
-The per new element cost for <math>C_1 = 1/5</math>
+The per new element cost for <math>C_1 = 1/5</math>, for <math>C_2 = 1/4</math>, for <math>C_3 = 1/5</math>, for <math>C_4 = 1/4</math>, for <math>C_5 = 1/5</math>, for <math>C_6 = 1/3</math>, for <math>C_7 = 1/4</math>, for <math>C_8 = 1/6</math>
 Since <math>C_8</math> has minimum value, <math>C_8</math> is added, and <math>I</math> becomes <math>\{1,2,4,6,8,12\}</math>.

Sherry Liang: /* Numerical Example */

2020-12-15T04:31:13Z

Numerical Example

← Older revision		Revision as of 00:31, 15 December 2020
Line 401:		Line 401:
	<math>U = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}</math>		<math>U = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}</math>

	<math>C = \}C_1,C_2,C_3,C_4,C_5,C_6,C_7,C_8\}</math>		<math>C = \{C_1,C_2,C_3,C_4,C_5,C_6,C_7,C_8\}</math>

	<math>C_1 = \}1,3,4,6,7} </math>		<math>C_1 = \{1,3,4,6,7\} </math>

	<math>C_2 = \}4,7,8,12}</math>		<math>C_2 = \{4,7,8,12\}</math>

	<math>C_3 = {2,5,9,11,13}</math>		<math>C_3 = \{2,5,9,11,13\}</math>

	<math>C_4 = {1,2,14,15}</math>		<math>C_4 = \{1,2,14,15\}</math>

	<math>C_5 = {3,6,10,12,14}</math>		<math>C_5 = \{3,6,10,12,14\}</math>

	<math>C_6 = {8,14,15}</math>		<math>C_6 = \{8,14,15\}</math>

	<math>C_7 = {1,2,6,11}</math>		<math>C_7 = \{1,2,6,11\}</math>

	<math>C_8 = {1,2,4,6,8,12} </math>		<math>C_8 = \{1,2,4,6,8,12\} </math>

	The cost of each Camera Location is the same in this case, we just hope to minimize the total number of cameras used, so we can assume the cost of each <math>C</math> to be 1.		The cost of each Camera Location is the same in this case, we just hope to minimize the total number of cameras used, so we can assume the cost of each <math>C</math> to be 1.
Line 441:		Line 441:
	The per new element cost for <math>C_8 = 1/6</math>		The per new element cost for <math>C_8 = 1/6</math>

	Since <math>C_8</math> has minimum value, <math>C_8</math> is added, and <math>I</math> becomes <math>{1,2,4,6,8,12}</math>.		Since <math>C_8</math> has minimum value, <math>C_8</math> is added, and <math>I</math> becomes <math>\{1,2,4,6,8,12\}</math>.

	Second Iteration:		Second Iteration:

	<math>I</math> = <math>{1,2,4,6,8,12}</math>		<math>I</math> = <math>\{1,2,4,6,8,12\}</math>

	The per new element cost for <math>C_1 = 1/2</math>		The per new element cost for <math>C_1 = 1/2</math>
Line 461:		Line 461:
	The per new element cost for <math>C_7 = 1/1</math>		The per new element cost for <math>C_7 = 1/1</math>

	Since <math>C_3</math> has minimum value, <math>C_3</math> is added, and I becomes <math>{1,2,4,5,6,8,9,11,12,13}</math>.		Since <math>C_3</math> has minimum value, <math>C_3</math> is added, and I becomes <math>\{1,2,4,5,6,8,9,11,12,13\}</math>.

	Third Iteration:		Third Iteration: