Question

Devise a branch-and-bound algorithm for the SET COVER problem. This entails deciding:

(a) What is a subproblem?

(b) How do you choose a subproblem to expand?

(c) How do you expand a subproblem?

(d) What is an appropriate lowerbound

Do you think that your choices above will work well on typical instances of the problem? Why?

Short answer

(a) A subproblem of set problem is given below.

(b) A choosing of subproblem to expand given below.

(c) A subproblem to expand is given below.

(d) An appropriate lowerbound is proved below.

Step-by-step solution

Step 1: Branch-and-bound algorithm for the SET COVER problem.

The idea of the branch and bound algorithm is simple. It finds the bounds of the cost function $f$given certain subsets of$X$ .

How do we arrive at these subsets exactly? An example would be if certain members of our solution vector $X$are integers, and we know that these members are bounded between $0and2$for example.

By this we can get the solution ofBranch-and-bound algorithm for the SET COVER problem easily.

The branch and bound algorithm is similar to backtracking but is used for optimization problems.

It performs a graph transversal on the space-state tree, but general searches Breadth first search instead of Depth first search.

During the search bounds for the objective function on the partial solution are determined.

Define subproblem.

a).

SET COVER problem.

This county is in its early stages of planning and is deciding where to put schools. There are only two constraints: each school should be in a town, and no one should have to travel more than thirty miles to reach one of them. What is the minimum number of schools needed? This is a typical set cover problem. For each town x, let $Sx$be the set of towns within thirty miles of it. A school at x will essentially “cover” these other towns. The question is then, how many sets $Sx$must be picked in order to cover all the towns in the county.

Step 3: Choose a subproblem to expand.

b).

This sounds trivial enough, but it is a very useful and common way of establishing that a problem is NP-complete:

Simply notice that it is a generalization of a known NP-complete problem. For example, the SET COVER problem is NP-complete because it is a generalization of VERTEX COVER (and also, incidentally, of three-D MATCHING) for more examples. Often it takes a little work to establish that one problem is a special case of another. The reduction from ZOE to ILP is a case in point. In ILP we are looking for an integer vector x that satisfies$Ax\le b,$ for given matrix $A$and vector $b$.

To write an instance of ZOE in this precise form, we need to rewrite each equation of the ZOE instance as two inequalities, and to add for each variable $xi$the inequalities$xi\le 1and-xi\le 0.$

Step 4: Expand a subproblem.

c).

SET COVER

Input: $A$set of elements$B$;

Sets,

$\begin{array}{l}S1,...,Sm\subseteq B\\ \end{array}$

Output: $A$selection of the Si whose union is $B$.

Cost: Number of sets picked. (In our example, the elements of$B$are the towns.)

This problem lends itself immediately to a greedy solution:

Repeat until all elements of b, e, and i. are covered: Pick the set with the largest number of uncovered element.

This is extremely natural and intuitive.

Let’s see what it would do on our earlier example:

It would first place a school at town a, since this covers the largest number of other towns. Thereafter, it would choose three more school and either for a total of four. However, there exists a solution with just three schools, at$xi\le 1and-xi\le 0.$

The greedy scheme is not optimal! But luckily, it isn’t too far from optimal.

Define lowerbound.        

d) .

An upper bound is a value larger than or equal to the largest value in a set.A lower bound is a value smaller than or equal to the smallest value in a set. Bounds can be used to express some certainty about uncertain events... Branch and Bound

Start with some problem $P_0$

Let $S=\left\{P0\right\},$the set of active subproblems,

$\begin{array}{l}\begin{array}{l}bestsofar=\infty \\ \end{array}\\ RepeatwhileSisnonempty:\\ \begin{array}{l}\\ chooseasubproblem\left(partialsolution\right)P\in SandremoveitfromS\end{array}\\ \begin{array}{l}\\ expanditintosmallersubproblemsP1,P2,...,Pk\end{array}\end{array}$

$\begin{array}{l}ForeachPi:\\ \begin{array}{l}\\ IfPiisacompletesolution:updatebestsofar\end{array}\\ \begin{array}{l}\\ elseiflowerbound\left(Pi\right)<bestsofar:addPitoS\end{array}\\ \begin{array}{l}\\ returnbestsofar\end{array}\end{array}$

And the$lowerbound\left(Pi\right)<bestsofar$in set problem is always less than.$bestsofar$