Integer programming

MGMT 306

Alex L. Wang

Purdue University

Pareto Efficiency

Multiple criteria

  • In the previous chapters we focused on making decisions by optimizing a single objective
  • In reality, there may be many relevant but conflicting objectives
  • Two approaches:
    • Combine all the objectives into a single objective
    • Deal with multiple objectives. We need to redefine what it means for a solution to be “optimal”
  • In multi-objective problems, we will discuss “efficient” solutions

Example: Comparing Job Offers

  • Suppose we are looking for a new job and have received three offers: A, B, and C. We would like to pick the job with the shortest commute possible, highest salary, and highest expected job satisfaction
Job Commute time (in minutes) Salary ($K) Expected job satisfaction
Job A 15 75 8.5
Job B 75 80 7.0
Job C 20 85 7.5
  • We prefer a shorter commute, higher salary, and higher job satisfaction
  • What can we say?

Efficient solutions

  • Alternative A dominates alternative B if
    • A is at least as good as B with respect to every objective and
    • A is strictly better than B with respect to at least one objective
  • Alternative A is not efficient if it is dominated by some other alternative
  • An alternative is efficient if it is not dominated by any other alternative
  • Also called Pareto efficient or Pareto optimal

Example: Comparing Job Offers Efficient Solutions

  • Suppose we are looking for a new job and have received three offers: A, B, and C. We would like to pick the job with the shortest commute possible, highest salary, and highest expected job satisfaction
Job Commute time (in minutes) Salary ($K) Expected job satisfaction
Job A 15 75 8.5
Job B 75 80 7.0
Job C 20 85 7.5
  • We prefer a shorter commute, higher salary, and higher job satisfaction
  • What can we say?
    • Job C dominates Job B so Job B is not efficient
    • Job A and Job C are both efficient

Determining Efficient Solutions Graphically

  • If there are only two metrics (objectives) then we can plot the alternatives
Ad campaign Cost ($K) Estimated reach (K persons)
A 15 20
B 20 30
C 20 40
D 18 15

"Axis showing the coordinates of each ad campaign"

  • We prefer lower cost and higher estimated reach
  • One alternative dominates another if it is northwest of the other point
  • Which alternatives are efficient?

Determining Efficient Solutions Graphically (continued)

  • Alternative A: is efficient
  • Alternative B: is not efficient. It is dominated by Alternative C
  • Alternative C: is efficient
  • Alternative D: is not efficient. It is dominated by alternative A

Efficient Investment Example

Setup

  • A client has $ 80,000 to invest into some combination of three stocks
  • The client wants to maximize their annual return and also to avoid high risk
Stock Price/share Est. annual return/share Risk index/share
A $25 $3 0.5
B $50 $5 0.25
C $40 $4 0.3

Setup (cont.)

  • Portfolio alternatives:
    • Invest all $80,000 into stock A
    • Invest all $80,000 into stock B
    • Invest $20,000 into stock A and $60,000 into stock B
    • Invest $80,000 into stock C
  • Compute the estimated annual return and risk index for each portfolio
  • Which of these solutions are Pareto efficient?

Solution

Portfolio Est. annual return Risk index
1 $9,600 1,600
2 $8,000 400
3 $8,400 700
4 $8,000 600
  • Portfolios 1, 2, 3 are Pareto Efficient
  • Portfolio 4 is not pareto efficient: dominated by portfolio 2

Goal Programming

Overview

  • In some scenarios, there may be multiple “goals” that we would like to hit
  • You can think of these as somewhere in between a constraint and an objective function
  • “Ensure a profit of at least $3,000 if possible. Otherwise, maximize profit.”

Example with one goal

  • Organic Greenhouses:
    • 12 acres land to plant peppers or tomatoes
    • Peppers require 1.5 hours of labor/acre and tomatoes require 3 hours of labor/acre
    • 30 hours of labor available
    • At most 6 of the acres of land can be used for peppers
    • Profit per acre is $30,000 for peppers and $40,000 for tomatoes
  • Goal 1:
    • Profit at least $350,000

LP Setup

  • Set up LP as usual but no objective for now

  • Variables: \[\begin{aligned} &P\quad\text{acres of peppers to plant}\\ &T\quad\text{acres of tomatoes to plant}\\ \end{aligned}\]

  • Constraints \[\begin{aligned} & P + T \leq 12 &&\text{(total acreage)}\\ & 1.5 P + 3T \leq 30 && \text{(labor)}\\ & P \leq 6 && \text{(pepper acreage)}\\ & P, T \geq 0 && \text{(nonnegativity)} \end{aligned}\]

Excel setup

Excel setup showing a data table, variables, and constraints but no objective cell.

LP Setup for Goal 1

  • Introduce two new variables for Goal 1: \[\begin{aligned} & d_1^- &&\text{amount by which Goal 1 is underachieved}\\ & d_1^+ &&\text{amount by which Goal 1 is overachieved} \end{aligned}\]

  • Add constraints: \[\begin{aligned} & 30,000 P + 40,000 T +d_1^- - d_1^+ = 350,000 &&\text{(balance)}\\ &d_1^- , d_1^+ \geq 0&&\text{(nonnegativity)} \end{aligned}\]

  • Objective: \[\min \qquad d_1^-\qquad\text{(underachievement)}\]

Excel setup with Goal 1

Same Excel setup as before but now with variables and overages/underages shown.

Excel setup with Goal 1 (formulas)

This figure shows the formulas used to implement the previous Excel spreadsheet.

Excel setup with Goal 1 Solved

A solved spreadsheet for Goal 1

We learn that it is possible to achieve Goal 1 (the underachievement is 0)

Dealing with multiple goals

  • If we have multiple goals, we will prioritize them and try to hit the goals one at a time – preemptive priorities
  • We will do as well as we can on Goal 1
  • Then, we will do as well as we can on Goal 2 without sacrificing how well we did on Goal 1
  • Etc.

LP Modifications for multiple goals

  • For each Goal \(i\), introduce two new variables \[\begin{aligned} & d_i^- &&\text{amount by which Goal $i$ is underachieved}\\ & d_i^+ &&\text{amount by which Goal $i$ is overachieved} \end{aligned}\]
  • There are three types of goals we can model
    • At least some value \(\quad\min d_i^-\)
    • At most some value \(\quad\min d_i^+\)
    • Exactly some value \(\quad\min (d_i^- + d_i^+)\)

Organic Greenhouses with additional goals

  • Goal 2: Use at most 10 acre-inches of water per week
    • Peppers require 2 acre-inch of water per acre per week whereas tomatoes require 1 acre-inches of water per acre per week
  • Goal 3: Plant at least 4 acres of tomatoes
    • Organic Farms wants to uphold their reputation as tier-1 tomato producers.

Steps:

  • Minimize underachievement of Goal 1 and set that as a constraint
  • Minimize overachievement of Goal 2 and set as a constraint
  • Minimize underachievement of Goal 3

Excel with completed 2nd goal

completed Excel spreadsheet for second goal

Excel with completed 3rd goal

completed Excel spreadsheet for third goal

Goal Programming Practice

Setup

  • New England Cycle Company is planning production
  • They produce Tandem bikes and Single-Rider bikes
  • Tandem bikes require 2 seats, 2 tires, 2 hours of labour
  • Single-Rider bikes require 1 seat, 2 tires, 3 hours of labour, and 1 gear assembly
  • New England Cycle Company has 2000 seats, 2400 tires, 1000 gear assemblies
  • Each tandem bike and single-rider bike yields $40 in profit and $100 in profit respectively

Goals

Managment has the following goals:

  • Goal 1: Fulfill a contract of 400 tandem bikes it has already promised to deliver
  • Goal 2: Produce at least 1000 bicycles total
  • Goal 3: Achieve at least $100,000 profit
  • Goal 4: Use no more than 1600 labor hours