The set partitioning problem (SPP) is the problem of exactly covering, at a minimal cost, the rows of an m×n binary matrix by subsetting its columns. Applications include airline crew scheduling, switching theory, and line balancing. For example, consider a crew scheduling problem in which a given airline must assign one and only one flight crew to each flight. A column is created for each feasible schedule for a single crew, and there is an associated cost with having the crew fly that schedule. An optimal schedule is chosen, minimizing cost.

The set partitioning problem can be formulated as:

Minimize the cost, Σ_j c_j x_j , such that Σ_j A_ij x_j = 1 ,   for i=1, 2, ... , m and j=1, 2, ... , n

where c_j are non-negative cost values, x_j = {0,1}, and A is an m×n matrix with elements a_ij = {0,1}.

The following DATA step uses data taken from Chu and Beasley (1998). A complete listing of the data lines can be found here. The input data contains the cost for each column of the problem.

   data sppaa01t;
     input cost rowIndex columnIndex;
     datalines;
   971 1 1
   971 2 1
   971 3 1
   971 4 1
   971 5 1
   971 6 1
   203 7 2
   203 8 2
       ... more datalines ...
   ;

The following statements solve the set partitioning problem. The indexed set, cost, is defined for each binary decision variable, x. The objective function, z, minimizes the cost. The constraint, partition, declares the constraint that Ax = 1. The mixed integer linear programming solver (MILP) in PROC OPTMODEL is able to solve this large problem with 8,904 binary variables and 823 linear constraints.

   proc optmodel;    
      set <num,num> pair;
      num cost {pair};
      set RSET = setof {<i,j> in pair} i;
      set CSET = setof {<i,j> in pair} j;
      read data sppaa01t into pair=[rowIndex columnIndex] cost;
      var x {CSET} binary;
      min z = sum{<i,j> in pair} cost[i,j] * x[j];
      constraint partition{i in RSET}: sum{<(i),j> in pair} x[j] = 1;    
      solve with milp;
   quit;

The above statements produce the following "Problem Summary" and "Solution Summary" tables. In the "Solution Summary" table, the Objective Value, 445341, is the minimum cost of covering the rows by subsetting the columns.

__________

P.C. Chu and J.E. Beasley (1998), "Constraint handling in genetic algorithms: the set partitioning problem," Journal of Heuristics, 4, 323-357.

Operating System and Release Information