2.2.2 Anti-Assignment Problem (balAssign0)

Run LPL Code  ,  PDF Document


Assign people into groups in a way that the groups are as heterogeneous as possible. Each person is identified by four characteristics (department, location, rating, and title). Build 7 groups such that these characteristics are distributed between the groups as much as possible. Let typi,k be the characteristic (as string) of person i in category k, and let wk be the weight in the objective function for category k. Finally, the relation TY PESk,t is true if characteristic t is in category k. This problem is from AMPL/Logic

Modeling Steps

We define a set of people as i I and a set of groups as j J. All the characteristics t T are grouped into four categories k K.

A binary variable Xi,j (assign) is introduced and is 1 if person i is in group j. MinInGrp and MaxInGrp are two variables defining a minimal/maximal number of persons in all groups. Finally, let minTk,t and maxTk,t the minimal/maximal number of persons that have characteristic t in all groups. The model is then :

min        M axInGrp   - M inInGrp  +            wk (maxTk,t - minTk,t )
           ∑                           (k,t)∈TYP ES
subjectto     X    = 1   forall i ∈ I
            j            ∑
           M inInGrp  ≤     Xi,j ≤ M  axInGrp     forall j ∈ J
                       ∑  i
           minTk,t ≤         Xi,j ≤ maxTk,t    forall j ∈ J, (k, t) ∈ T Y PES

The objective function minimizes the deviations: Basically, we want the same number of persons in the 7 groups (MaxInGrp - MinInGrp), but also the same number of all characteristics in each category in the same group. The first constraint then states that each person must be in one single group. The other two constraints limit the deviations. To make this problem harder, decrease sample and/or increase the number of groups.

Further Comments

This model shows the difference in set/indices syntax in AMPL and LPL. Index and sets can have the same name in LPL. This may lead to some confusion initially, but it make the model much shorter and in my opinion more readable. It shows also, that AMPL is more powerful in set definitions (set of sets are possible, for instance and others), but this is outweighted in LPL by its algorithmic (programming) part. In LPL, all “compound sets” are defined as multi-dimensinal “relations”.

LPL code (run balAssign0)

model balAssign0 "Anti-Assignment Problem"; 
  set PEOPLE,i; 
  set GROUPS,j; 
  set CATEG,k "categories"; 
  set t  "all characteristics"; 
  string parameter typ{i,k}; 
  parameter typeWt{k}; 
  set TYPES{k,t}; 
  binary variable Assign{i,j}; 
  variable MinInGrp [0..Floor(#i/#j)]; 
  variable MaxInGrp [Ceil(#i/#j-1)..9999]; 
  variable MinType{TYPES[k,t]} [0..Floor((sum{i|typ=t}1)/#j)]; 
  variable MaxType{TYPES[k,t]} [Ceil(sum{i|typ=t}1/#j)..9999]; 
  minimize Variation: (MaxInGrp-MinInGrp) + 
    sum{TYPES[k,t]} typeWt*(MaxType-MinType); 
    AssignAll{i}: sum{j} Assign[i,j] = 1; 
    InGrpDefn{j}: MinInGrp <= sum{i} Assign[i,j] <= MaxInGrp; 
      MinType <= sum{i|typ=t} Assign[i,j] <= MaxType; 
  Write{j}('group %s' n%s' n', j, Format{i|Assign}('%s %11s' n',i, {k} typ)); 

AMPL code (download balAssign0.mod)

set ALL_PEOPLE ordered; 
param sample integer > 0; 
param selection integer >= 0, < sample; 
set PEOPLE := {i in ALL_PEOPLE: ord(i) mod sample = selection}; 
set CATEG; 
param type {ALL_PEOPLE,CATEG} symbolic; 
param typeWt {CATEG} >= 0; 
param numberGrps integer > 0; 
set TYPES{k in CATEG}:=setof{i in PEOPLE} type[i,k]; 
var Assign {i in PEOPLE, j in 1..numberGrps} binary; 
var MinInGrp <= floor (card(PEOPLE)/numberGrps); 
var MaxInGrp >= ceil (card(PEOPLE)/numberGrps); 
var MinType {k in CATEG, t in TYPES[k]} 
   <= floor (card {i in PEOPLE: type[i,k] = t} / numberGrps); 
var MaxType {k in CATEG, t in TYPES[k]} 
   >= ceil (card {i in PEOPLE: type[i,k] = t} / numberGrps); 
minimize Variation:  (MaxInGrp - MinInGrp) + 
   sum {k in CATEG, t in TYPES[k]} 
      typeWt[k] * (MaxType[k,t] - MinType[k,t]); 
subj to AssignAll {i in PEOPLE}: 
   sum {j in 1..numberGrps} Assign[i,j] = 1; 
subj to MinInGrpDefn {j in 1..numberGrps}: 
   MinInGrp <= sum {i in PEOPLE} Assign[i,j]; 
subj to MaxInGrpDefn {j in 1..numberGrps}: 
   MaxInGrp >= sum {i in PEOPLE} Assign[i,j]; 
subj to MinTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: 
   MinType[k,t] <= sum {i in PEOPLE: type[i,k] = t} Assign[i,j]; 
subj to MaxTypeDefn {j in 1..numberGrps, k in CATEG, t in TYPES[k]}: 
   MaxType[k,t] >= sum {i in PEOPLE: type[i,k] = t} Assign[i,j];

LPL data (download balAssign0.txt)

model data "TEST DATA for balassign0.lpl"; 
  integer parameter sample [0..9999] := 6; 
  integer parameter selection [0..sample-1] := 0; 
  integer parameter numberGrps := 7;; 
  set ALL_PEOPLE := [ 
   ... cut lines ... 
  typeWt{k} :=  / dept 1  loc 1  rate 1  title 1 /; 
  string parameter type{ALL_PEOPLE,CATEG} := / 
     : dept       loc     rate    title : 
BIW   NNE   Peoria        A   Assistant 
KRS   WSW   Springfield   B   Assistant 
TLR   NNW   Peoria        B   Adjunct 
... cut lines ... 
XYF   NNE   Peoria        A   Assistant 
JEN   NNE   Peoria        A   Deputy 
BLW   NNE   Peoria        A   Deputy /; 
  {a in ALL_PEOPLE} if(a%sample = selection,Addm(PEOPLE,a&'')); 
  {CATEG,ALL_PEOPLE} (Addm(t,type)); 
  {i in ALL_PEOPLE,k} (typ[i within PEOPLE,k]:=type[i,k]); 
  {i,k,t} if(typ[i,k]=t,TYPES[k,t]:=1); 
  parameter MinType1{TYPES[k,t]} := Floor(sum{i|typ=t}1/ numberGrps); 

AMPL data (download balAssign0.dat)

param sample := 6; 
param selection := 0; 
param numberGrps := 7; 
set ALL_PEOPLE := 
   ... cut lines ... 
param: CATEG: typeWt := dept 1  loc 1  rate 1  title 1; 
param type: 
     dept       loc     rate    title   := 
BIW   NNE   Peoria        A   Assistant 
KRS   WSW   Springfield   B   Assistant 
TLR   NNW   Peoria        B   Adjunct 
... cut lines ... 
XYF   NNE   Peoria        A   Assistant 
JEN   NNE   Peoria        A   Deputy 
BLW   NNE   Peoria        A   Deputy ;