The Mkc Problem:Formulation Matters

• IBM consulting engagement in steel mill industry

• Match orders with surplus inventory, taking into account “color” contraints

  • 2 colors per slab due to cutting before finishing mill

• Natural formulation: binary variables

  • Xij order i assigned to slab j
  • Ycj orders of color c obtained from slab j
  • Zj an order is filled by slab j used

• Unsolvable. Miplib3

• MIP-equivalent but LP-better formulation

  • Redefinition of variables: “feasible patterns”
  • Column generation approach
  • Solved to optimality in FOUR seconds

• “Color Generation Approach to Multiple Knapsack Problem with Color Side Constraints”, Ladanyi et al., (2001)

  
  

Previous slide

Next slide

Back to first slide

View graphic version