Additional Integer Programming Applications

MGMT 306

Alex L. Wang

Purdue University

Fixed-Cost Transportation

Transportation Problems

• A very common problem
• Goods are produced in plants or stored in warehouses across the US
• How to route to consumers efficiently?
• Many interesting management/analytics questions:
  • If we can open only a few warehouses, which to open?
  • If we want to minimize carbon emissions, what mix of shipment options should we offer?
  • If different courriers “own” different routes, which couriers should we contract?
  • Etc.

GlassWorks

Transportation problem

Problem Description

• GlassWorks produces glass vases in Memphis and Dallas workshops
• Each workshop has a weekly production capacity of 250 vases
• This week, GlassWorks must ship 120 vases to Los Angeles, 140 vases to Newark, and 150 vases to Chicago
• Intermediate warehouses in Atlanta and Kansas City may be used for trans-shipment
• Unit shipping costs are indicated

ILP Model

• Variables \[\begin{aligned} x_{MA} \qquad&\text{number of vases to ship Memphis to Atlanta}\\ x_{MK} \qquad&\text{number of vases to ship Memphis to Kansas City}\\ x_{MC} \qquad&\text{number of vases to ship Memphis to Chicago}\\ \dots\qquad& (\text{12 total variables}) \end{aligned}\]

• Objective \[\min\qquad 3.5 x_{MA} + 5 x_{MK} + 14 x_{MC} + \dots 3 x_{CN}\qquad\text{(total shipping costs)}\]

ILP Model Constraints

• Flow at workshops \[\begin{aligned} &x_{MA} + x_{MK}+ x_{MC} \leq 250&&\text{(production capacity Memphis)}\\ &x_{DK} + x_{DA}+ x_{DL} \leq 250&&\text{(production capacity Dallas)} \end{aligned}\]

• Flow at warehouses \[\begin{aligned} &x_{MA} + x_{DA} - x_{AC} - x_{AN} =0&&\text{(net flow Atlanta)}\\ &x_{MK} + x_{DK} - x_{KC} - x_{KL} - x_{KN} = 0&&\text{(net flow KC)} \end{aligned}\]

• Flow at customers \[\begin{aligned} &x_{KL} + x_{DL} = 120 &&\text{(demand LA)}\\ &x_{KN} + x_{AN} + x_{CN} = 140&&\text{(demand Newark)}\\ &x_{MC} + x_{KC} + x_{AC} - x_{CN} = 150&&\text{(demand Chicago)} \end{aligned}\]

ILP Model Constraints Continued

• Nonnegativity and integrality \[x_{MA}, x_{MK},\dots,x_{CN}\geq 0 \text{ and integer}\]

Spreadsheet Model

Spreadsheet Model Alternate

Optimal Solution

Transportation with Fixed Costs or Minimums

Problem Description

• GlassWorks decides that this LP model is not realistic enough
• They want to incorporate the following additional stipulations:
  • Each route can transport at most 200 vases
  • The cost of shipping vases along any route consists of a fixed cost ($200) plus the variable costs (as before). This fixed cost must be paid if GlassWorks ships any number of vases along that route
  • Think: Linking constraints

ILP Model

• Variables \[\begin{aligned} x_{MA} \qquad&\text{number of vases to ship Memphis to Atlanta}\\ x_{MK} \qquad&\text{number of vases to ship Memphis to Kansas City}\\ x_{MC} \qquad&\text{number of vases to ship Memphis to Chicago}\\ \dots\qquad& (\text{12 total $x_{i,j}$ variables})\\ y_{MA} \qquad&\text{whether to ship from Memphis to Atlanta}\\ y_{MK} \qquad&\text{whether to ship from Memphis to Kansas City}\\ y_{MC} \qquad&\text{whether to ship from Memphis to Chicago}\\ \dots\qquad& (\text{12 total $y_{i,j}$ variables})\\ \end{aligned}\]

• Objective \[\begin{aligned} \min\qquad &3.5 x_{MA} + 5 x_{MK} + 14 x_{MC} + \dots + 3 x_{CN}\\ & + 200 y_{MA} + 200 y_{MK} + 200 y_{MC} + \dots + 200 y_{CN}\qquad\text{(total costs)} \end{aligned}\]

ILP Constraints

• Constraints from before
• Capacity and linking constraints \[x_{i,j} \leq 200 y_{i,j} \qquad\text{for every arc $(i,j)$}\]
• Binary decisions \[y_{i,j}\text{ binary for every arc $(i,j)$}\]

Spreadsheet Model

Spreadsheet Model Continued

Optimal solution

Fixed costs incentivize using fewer edges. The previous shipments from (Dallas-Kansas City-Chicago) are now rerouted (Dallas-Atlanta-Chicago) to reuse the Atlanta-Chicago route.

Other practical variants of this problem

• Multiple(non-interchangeable) goods - USPS must route mail to their recipients, but different pieces of mail still contribute to the same capacity constraints
• Fixed costs on warehouses - Logistics company needs to decide where to open a new warehouse
  • Add binary variables on warehouses and linking constraints
• Fixed costs on sets of routes - A major airline wants to expand its network and may sign contracts with competing regional airlines
  • Add binary variables per regional airline and group linking constraints
• …