Set covering

Describes the problem and presents the model and data files.

Consider selecting workers to build a house. The construction of a house can be divided into a number of tasks, each requiring a number of skills (e.g., plumbing or masonry). A worker may or may not perform a task, depending on skills. In addition, each worker can be hired for a cost that also depends on his qualifications. The problem consists of selecting a set of workers to perform all the tasks, while minimizing the cost. This is known as a set-covering problem. The key idea in modeling a set-covering problem as an integer program is to associate a 0/1 variable with each worker to represent whether the worker is hired. To make sure that all the tasks are performed, it is sufficient to choose at least one worker by task. This constraint can be expressed by a simple linear inequality.

The example covering.mod describes a set-covering model for this problem and Instance data for the set-covering model (covering.dat) below shows some instance data.

int NbWorkers = ...;
range Workers = 1..NbWorkers;
{string} Tasks = ...;
{int} Qualified[Tasks] = ...;
assert 
  forall( t in Tasks , i in Qualified[t] ) i in asSet(Workers);
//alternate formulation:
assert 
  forall( t in Tasks ) 
    card(Qualified[t] inter asSet(Workers))==card(Qualified[t]);
int Cost[Workers] = ...;
dvar boolean Hire[Workers];

minimize 
  sum(c in Workers) Cost[c] * Hire[c];
subject to {
  forall(j in Tasks)
    ct:
      sum( c in Qualified[j] ) 
        Hire[c] >= 1;
}
{int} Crew = { c | c in Workers : Hire[c] == 1 };
execute DISPLAY {
  writeln("Crew=",Crew);
}

The first instruction in the model declares a number of workers as an integer, a range for the workers, and a string type for the tasks. The instruction

{int} Qualified[Tasks] = ...;

declares the workers qualified to perform a given task, Therefore, Qualified[Tasks] is the set of workers able to perform task t.

The problem variables

dvar boolean Hire[Workers];

indicate whether a worker is hired for the project.

The constraints

  forall(j in Tasks)
    ct:
      sum( c in Qualified[j] ) 
        Hire[c] >= 1;

make sure that each task is covered by at least one worker.

Note also the declaration

{int} Crew = { c | c in Workers : Hire[c] == 1 };

which collects all the hired workers in the set Crew to produce a more pleasing representation of the results.

The example covering.dat shows data for an instance of this model.

NbWorkers = 32;
Tasks = { masonry, carpentry, plumbing, ceiling,
     electricity, heating, insulation, roofing, 
     painting, windows, facade, garden, 
     garage, driveway, moving };
Qualified = [
   { 1  9 19  22  25  28  31 }
   { 2 12 15 19 21 23 27 29 30 31 32 }
   { 3 10 19 24 26 30 32 }
   { 4 21 25 28 32 }
   { 5 11 16 22 23 27 31 }
   { 6 20 24 26 30 32 }
   { 7 12 17 25 30 31 } 
   {  8 17 20 22 23  }
   {  9 13 14  26 29 30 31 }
   {  10 21 25 31 32 }
   {  14 15 18 23 24 27 30 32 }
   {  18 19 22 24 26 29 31 }
   {  11 20 25 28 30 32 }
   {  16 19 23 31 }
   {  9 18 26 28 31 32 }
];
Cost = [ 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 6 6 6 7 8 9 ];

// solution (optimal) with objective 14
Crew= {23 25 26}