Originally posted by: wsherman

I'm currently trying to get practice with column generation technique. I have an existing LP that I would like to adapt into a column generation problem similar to the common 'cutstock' example built into cplex. My LP is similar to a staffing problem. I want to draft a team of football players, where my goal is to draft a team of the highest ranking players constrained by team composition and player salary. Adding column generation to an already simple LP is over-engineering the problem, but I wanted more experience with staffing applications of column generation

Original Problem Description:

My formulation is setup such that I have 100 players to choose from, can only spend up to $100k, and must have 3 players of role 1, 5 players of role 2, 2 players of role 3, and and additional 2 players to be allocated between either roles 2 or 3. The decision variable is a vector of 100 boolean values corresponding to each player. A '1' means that player was selected for the team and a '0' indicates they were not selected. Roles are built into the index order of the roster list. The first 33 players are all role 1, indices 34 through 66 are role 2, and the last 34 players are role 3. Most of the code for the above description is listed below.

Original LP:

range roster = 1..100;

dvar boolean team[roster]

minimize sum(i in roster) 
    ranks[i]*team[i];
subject to {

    forall (i in roster) salary_Constraint:
        sum(i in roster) salary[i]*team[i] <= 100000;
    forall (i in roster) role1_Constraint:
        sum(j in 1.33) team[j] = 3;
    forall (i in roster) role2_Constraint:
        5 <= sum(k in 34.66) team[j] <= 7;
    forall (i in roster) role3_Constraint:
        2 <= sum(l in 67.100) team[j] <= 4;

}

Column Generation Description:

I've spent a good amount of time trying to formulate my original LP as a column generation example. I've run into three different issues on how to approach the formulation so let me describe what I've done so far and what I'm unsure of. My formulation is based off the 'Cutstock' example in cplex where:

tuple pattern {
   key int id;
   int cost;
   int fill[Items];
}

minimize
  sum( p in Patterns ) 
    p.cost * Cut[p];

subject to {
  forall( i in Items ) 
    ctFill:
      sum( p in Patterns ) 
        p.fill[i] * Cut[p] >= Amount[i];
}

Issue 1: Objective and Decision Variable Selection

Cutstock has two components to it's final solution: the columns of patterns to be cut AND the amount to cut each pattern. In my case, I believe I only have one solution to my component: The pattern. Because my original decision variable is a boolean list describing player selection, I'm only interested in a binary column pattern. With that in mind, I'm not entirely sure how to incorporate the new dvar for my column generation formulation. Should I have some placeholder decision variable in 0..1 such that:

dvar float+ team[Patterns] in 0..1;

minimize sum(p in Patterns, j in 0..100)
        p.ranks[j]*p.fill[j]*team[p] ;

Where team is just the placeholder decision variable that doesn't change the outcome of the original objective. Is this the right approach to my new objective or should I try something different.

Issue 2: Pattern Formulation

I previously mentioned that I've combined all 3 roles into single 100-length array. I've incorporated this into a tuple Pattern as follows:

tuple pattern {
   key int id;
   int ranks[roster];
   int costs[roster];
   int fill[roster];
}

where each player has a unique rank and cost associated with them. Ranks are unique to each role so there will be ranks 1 through 33 (or 34) for roles 1, 2 and 3. Ranks are not 1 to 100. Costs are the salaries tied to each player. Fill is the pattern just like in cutstock. I want my new formulation to run through new combinations of players to be drafted and seek out the specific combination that minimizes my objective while satisfying my constraints.

With all that in mind, does it make sense to keep the pattern as a list of 100 players or should I give each player role a dedicated pattern to be generated?

tuple pattern {
   key int id;
   int ranks1[1..33];
   int costs1[1..33];
   int fill1[1..33];
   
   int ranks2[1..33];
   int costs2[1..33];
   int fill2[1..33];
   
   int ranks3[1..34];
   int costs3[1..34];
   int fill3[1..34];
}

Issue 3: Filling Duals

Cutstock runs the following code to fill an array with duals and pass it to the subproblem:

execute FillDuals {
  for(var i in Items) {
     Duals[i] = ctFill[i].dual;
  }
}

In the case of cutstock, there is only 1 constraint in the master to fill duals with. In my case, there are 4 constraints. In order to account for this, should my code look something like this:

execute FillDuals {
  for(j in 1..4 var i in roster) {
     Duals[1][i] = salary_Constraint[i].dual;
     Duals[2][i] = role1_Constraint[i].dual;
     Duals[3][i] = role2_Constraint[i].dual;
     Duals[4][i] = role3_Constraint[i].dual;
    }
}

Thanks for taking the time to ready my comment and questions. Any tips or suggestions would be appreciated.

Originally posted by: Mathsg

Hi,

I am using column generation same as your case. could you share you code with me so let i get an idea that how to implement column generation in engineering problem. I am optimizing network planning problem but i dont know how to get start of it. can you help me as you are my senior in this field. I am looking forward to hearing from you. thank you