Branch and bound algorithm for the Set Cover problem? [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

Can someone pleas share with me a java program that uses the Branch and bound method to solve the Set Cover problem? Following is what I have so far. So at each stage, the algorithm is supposed to take a set and get two instances of the problem: 1.select the first set from the array list 2. don't take the first set from the arraylist. At this point I'm stuck on how to start the branch and bound.

import java.util.*;

public class BranchAndBound {
    static int bestSoFar=100;
    static int count=0;
    public static void main(String args[]){

    //create the universe
    int numU = 10;
    MySets universe = ne开发者_JAVA百科w MySets();
    for(int i=1;i<=numU;i++){
           universe.add(i);
    }

    //create each set
    MySets s1 = new MySets();
    MySets s2 = new MySets();
    MySets s3 = new MySets();
    MySets s4 = new MySets();
    MySets s5 = new MySets();

    ArrayList<MySets> s=new ArrayList<MySets>();
    //elements
    s1.add(1);s1.add(2);s1.add(3);s1.add(8);s1.add(9);s1.add(10);
    s2.add(1);s2.add(2);s2.add(3);s2.add(4);s2.add(5);
    s3.add(4);s3.add(5);s3.add(7);
    s4.add(5);s4.add(6);s4.add(7);
    s5.add(6);s5.add(7);s5.add(8);s5.add(9);s5.add(10);

    s.add(s1);s.add(s2);s.add(s3);s.add(s4);s.add(s5);
    branchAndBound(universe,s,0);

    }

    public static void branchAndBound(MySets U,ArrayList<MySets> listSets,int countSelected){
        MySets universe = new MySets();
        universe.addAll(U);

        ArrayList<MySets> s=new ArrayList<MySets>();
        s.addAll(listSets);

        MySets selectedSet= new MySets();

        selectedSet.addAll(listSets.get(0));
        count++;

        universe.removeAll(selectedSet);//the universe now contains the elements still need to be covered
        listSets.remove(0);//remove the first elemeent from the list

        displaySet(selectedSet, "selected set");
        displaySet(universe, "universe");

        while(!universe.isEmpty() && !listSets.isEmpty()){
            branchAndBound(universe,listSets,count);
        }
    }




public static void displaySet(MySets s, String name){
    System.out.print(name+"==>");
    Iterator it=s.iterator();
    while(it.hasNext()){
      Integer value=(Integer)it.next();
      System.out.print(+value+" ");
    }//while
    System.out.println();
}//displaySet
}

---

I believe you asked a similar question earlier and a related one here. As pointed out there, Set Covering is NP-Hard. So, no polynomial algorithm is known to exist for it. When you abstract away from the specifics of the problem, it is an integer program (IP). So, you can use any general purpose IP solver such as the one provided in MS-Excel. All general integer programming problems are solved using branch-and-bound method. So, you do not need one specifically for Set Covering alone. All you need to do is to formulate the set covering problem as an integer program and provide it to the solver which should take care of the rest. Folks on SO are unlikely to have a ready-made code available to share with you. Integer Programming/Linear Programming (which forms the basis for integer programming) codes are quite detailed and specialized.