Single Point based Search: Fair share problem: Given a set of N positive integers S={x1, x2, x3,…, xk,… xN}, decide whether S can be partitioned into two sets S0 and S1 such that the sum of numbers in S0 equals to the sum of numbers in S1. This problem can be formulated as a minimisation problem using the objective function which takes the absolute value of the difference between the sum of elements in S0 and the sum of elements in S1. Assuming that such a partition is possible, then the minimum for a given problem instance would have an objective value of 0. A candidate solution can be represented using a binary array r=[b1, b2, b3,…, bk,… bN], where bk is a binary variable indicating which set the k-th number in S is partitioned into, that is, if bk =0, then the k-th number is partitioned in to S0, otherwise (which means bk =1) the k-th number is partitioned in to S1. For example, given the set with five integers S={4, 1, 2, 2, 1}, the solution [0,1,0,1,1] indicates that S is partitioned into S0={4, 2} (first and third numbers in S) and S1={1, 2, 1} (second, fourth and fifth numbers in S), and this solution has an objective value of 2 which is computed by |(4+2)−(1+2+1)│, while the optimal solution for this instance is [0,0,1,1,1] indicating that the first and second numbers are in partition S0 while the remaining numbers are in S1 yielding the objective value of |(4+1)−(2+2+1)| = 0 How many different candidate solutions can be encoded with the proposed candidate solution representation scheme? Provide your answer in terms of N.
Single Point based Search:
Fair share problem: Given a set of N positive integers S={x1, x2, x3,…, xk,… xN}, decide whether S can be partitioned into two sets S0 and S1 such that the sum of numbers in S0 equals to the sum of numbers in S1. This problem can be formulated as a minimisation problem using the objective function which takes the absolute value of the difference between the sum of elements in S0 and the sum of elements in S1. Assuming that such a partition is possible, then the minimum for a given problem instance would have an objective value of 0. A candidate solution can be represented using a binary array r=[b1, b2, b3,…, bk,… bN], where bk is a binary variable indicating which set the k-th number in S is partitioned into, that is, if bk =0, then the k-th number is partitioned in to S0, otherwise (which means bk =1) the k-th number is partitioned in to S1. For example, given the set with five integers S={4, 1, 2, 2, 1}, the solution [0,1,0,1,1] indicates that S is partitioned into S0={4, 2} (first and third numbers in S) and S1={1, 2, 1} (second, fourth and fifth numbers in S), and this solution has an objective value of 2 which is computed by |(4+2)−(1+2+1)│, while the optimal solution for this instance is [0,0,1,1,1] indicating that the first and second numbers are in partition S0 while the remaining numbers are in S1 yielding the objective value of |(4+1)−(2+2+1)| = 0
- How many different candidate solutions can be encoded with the proposed candidate solution representation scheme? Provide your answer in terms of N.
Step by step
Solved in 2 steps
