1

Decision Models and Analytics

7. Integer Programming

Professor Jiawei Zhang

 Agenda 2

How to deal with integer constraints?

How to model yes/no decisions

How to model logical conditions

– Capital budgeting problem
– Assignment problems

Modeling fixed cost

– Supply chain network design

Reading from Optimization Modeling

– Chapter 6
– Chapter 7
 Agenda 3

Templates:

CapitalBudgeting_template.xlsx

CarMatching_template.xlsx

AssigningSchoolBus_template.xlsx

OnlineRetailing_template.xlsx
 Integer Constraints 4

Sometimes decision variables can only take integer values.

When are non-integer solutions acceptable?

- Solution is naturally divisible (e.g., $, pounds, hours)
- Solution represents a rate (e.g., units per week)
 Simple Rounding 5

Simple rounding: round the LP solution to the nearest integers, while

keeping feasibility

The rounded solution is usually NOT an optimal integer solution.

 6

MIP Example
Consider the following MIP:

Maximize 50,000x1 + 34,000x2

Subject to
10x1 + 7x2 ≤ 49
x1 + x2 ≥ 5
x1, x2 ≥ 0 and integer

Refer to IntegerModel_template.xlsx
 7

Excel Model: LP Relaxation

LP Relaxation: LP associated with an MIP when dropping the
integrality constraints
 8

Excel Model: MIP

MIP solution: The MIP solution is indeed quite different, leading to
a lower objective value
 9

10 x1 + 7 x2≤49
x
Solution: Graphical Method
2 Maximize 50,000x1 + 34,000x2

7 Subject to
10x1 + 7x2 ≤ 49
x1+x2≥5 x1 + x2 ≥ 5
x1, x2 ≥ 0 and integer
5

Z=50,000

5 x1

9
 10

10 x1 + 7 x2≤49
x
Solution: Graphical Method
2 Maximize 50,000x1 + 34,000x2

7 Subject to
10x1 + 7x2 ≤ 49
x1+x2≥5 x1 + x2 ≥ 5
x1, x2 ≥ 0 and integer
5

Z=50,000 Optimal LP solution:

x*LP=(4.67, 0.33),
with Z*=244,667
x*LP=(4.67, 0.33),
Z=244,667
5 x1

10
 11

10 x1 + 7 x2≤49
x
Solution: Graphical Method
2 Maximize 50,000x1 + 34,000x2
x*MIP=(0, 7),
7 Z*MIP=238,000 Subject to
10x1 + 7x2 ≤ 49
x1+x2≥5 x1 + x2 ≥ 5
x1, x2 ≥ 0 and integer
5

Z=50,000 Optimal LP solution:

x*LP=(4.67, 0.33),
with Z*LP=244,667
x*LP=(4.67, 0.33),
Z=244,667 Optimal MIP solution:
x*MIP=(0, 7),
5 x1 with Z*MIP=238,000

Gap (Z*LP− Z*MIP)/Z*LP= −2.72%

11
 Integer Constraints 12

It is easy to add an integer constraint to a linear program.

If B22:D22 are decision cells and are constrained to integer values, then

But the model then becomes “harder” to solve, and may take “very”
long time.
Solver Message 13
 Important Note 14

Uncheck “Ignore Integer

Constraints”.

Under Solver options make

sure you set the Integer
Optimality (%) to zero.
Always select this option.

You may also increase the

“Max Time”.
 15

Integer Constraints
A Mixed Integer Program (MIP) is an extension of a Linear Program
where some variables are restricted to be integer or binary (0-1).

Objective and constraints are still restricted to be linear.

Easy to add an integer constraint to a linear program.

But the model then becomes computationally harder to solve, and

may take (VERY) long time!
 Rounding LP Solution
When is rounding acceptable?

Probably okay if variables take on large values and rounding does not
have big impact on feasibility or optimality.
– This holds true for numerous resource allocation problems,
especially when a large quantity of the resource is available.

Rounding is a BIG problem if optimal LP solution values are small.

Especially when the decisions are Yes/No, 1/0.

Why not always use the int constraint in Solver?

– Tradeoff between solvability and realism
– The int constraint makes the problem much harder to solve

16
 Capital Budgeting
The company is evaluating seven projects, each with its cash
requirement and net present value (NPV) contribution.
Investment Cash Required NPV
1 $5,000 $16,000
2 $2,500 $8,000
3 $3,500 $10,000
4 $6,000 $19,500
5 $7,000 $22,000
6 $4,500 $12,000
7 $3,000 $7,500

The available cash for investment is $15,000.

The objective is to determine the investment policy that maximizes the

NPV.

It should be noted that if the company decides to participate in any of

these projects, it must fully commit to that project.
17
 Managerial Definition 18

Decision:

Objective:

Constraints:

Refer to CapitalBudgeting_template.xlsx
 Greedy Solution 19

Calculate for each project the ratio NPV/Cash Required

Investment Cash Required NPV Ratio
1 $5,000 $16,000 3.2
2 $2,500 $8,000 3.2
3 $3,500 $10,000 2.857143
4 $6,000 $19,500 3.25
5 $7,000 $22,000 3.142857
6 $4,500 $12,000 2.666667
7 $3,000 $7,500 2.5
Choose projects with the highest ratios:
• Project 4
• Projects 1
• Projects 2
• Project 5 (not enough fund for project 5)

Total NPV: $43,500

Can we do better?
 Mathematical Model 20

Decision Variables:

Objective:

Constraints:
 Adding Binary Constraint 21

Making the changing cells binary, not integer

 Optimal Solution 22

A B C D E
2 Investment Cash Required NPV Invest?
3 1 $5,000 $16,000 1
4 2 $2,500 $8,000 1
5 3 $3,500 $10,000 0
6 4 $6,000 $19,500 0
7 5 $7,000 $22,000 1
8 6 $4,500 $12,000 0
9 7 $3,000 $7,500 0
10
11 Cash Available $15,000
12
13 Constraint Objective
14 Cash Required 14500 Total NPV 46000
15 <=
16 Cash Available $15,000

Changing cells: E3:E9

Objective cell: E14  maximize
Constraint: B14 <= B16
E3:E9 Binary
 LP Relaxation 23

A B C D E
2 Investment Cash Required NPV Invest?
3 1 $5,000 $16,000 0
4 2 $2,500 $8,000 0
5 3 $3,500 $10,000 0
6 4 $6,000 $19,500 2.5
7 5 $7,000 $22,000 0
8 6 $4,500 $12,000 0
9 7 $3,000 $7,500 0
10
11 Cash Available $15,000
12
13 Constraint Objective
14 Cash Required 15000 Total NPV 48750
15 <=
16 Cash Available $15,000
 Change to Integer Constraint 24

A B C D E
2 Investment Cash Required NPV Invest?
3 1 $5,000 $16,000 0
4 2 $2,500 $8,000 6
5 3 $3,500 $10,000 0
6 4 $6,000 $19,500 0
7 5 $7,000 $22,000 0
8 6 $4,500 $12,000 0
9 7 $3,000 $7,500 0
10
11 Cash Available $15,000
12
13 Constraint Objective
14 Cash Required 15000 Total NPV 48000
15 <=
16 Cash Available $15,000
 25

Binary Variables & Logical Conditions

Example 1:
Assume that if project 4 is undertaken, then project 5 must be
undertaken. This is represented by:

Example 2:
Assume that either both projects 4 and 5 are undertaken or are not
undertaken. This is represented by:

Example 3:
Either project 4 or project 5 must be undertaken, but not both.
 26

Binary Variables & Logical Conditions

Example 4:
If project 4 is selected, then project 5 must be rejected.

Example 5:
At most three of the projects 1 through 5 can be selected.

Example 6:
Exactly one of the first three projects must be selected.
 27

Binary Variables & Logical Conditions

Example 7:
Projects 1 and 3 have synergies worth an additional $9,000 in NPV.
How can we capture this? Add to the model and resolve.
Matching in Ride Sharing 28

3
5
6

1
2
4 2

4 3
1
 Matching in Ride Hailing 29

At a specific moment, there are four ride requests that need to be allocated
or assigned.

Currently, there are only six cars in close proximity that can accommodate
these ride requests.

The system has provided estimated waiting times (in minutes) for each
potential assignment of the ride requests.
Waiting Time Estimate
Car 1 Car 2 Car 3 Car 4 Car 5 Car 6
User 1 2 3 4 10 5 10
User 2 4 10 8 9 4 12
User 3 3 8 9 12 10 10
User 4 5 4 6 10 1 5
What is the optimal assignment of the ride requests to minimize the total
waiting time?

Refer to CarMatching_template.xlsx
29
 Structuring the Car Matching Problem 30

Decisions to be made

Performance measure

Things that restrict your choices

Data needed
 Mathematical Formulation 31

Input parameters:

Decision variables:

Objective function:

Constraints:
Input Cells 32
 Decision/Changing Cells 33

• Changing cells: B10:G13

– Binary Variables : 1  successful pairing, 0  unsuccessful pairing
 Objective Cell 34

• Total Waiting Time = SUMPRODUCT(B2:G5, B10:G13)

 Constraint Cells 35

• Each user should be picked up by one of the drivers.

– Only one “1” entry in each row
– E.g., User 1: SUM(B10:G10) = 1
– Constraint: H10:H13 = J10:J13

• Each car can only be assigned to at most one user.

– At most one “1” entry in each column
– E.g., Car 1: SUM(B10:B13) <= 1
– Constraint: B14:G14 <= B16:G16
Constraint Cells 36
Solver Setup 37

• Set Obj: C18

• To: Min

• Change cell: B10:G13

• Subject to Constraints
B14:G14 <= B16:G16
H10:H13 = J10:J13
An Optimal Solution 38
 Matching in Ride Hailing 39

What if the platform also considers the driver’s income?

Each driver has to make a minimum amount for the rest of the day:

Car 1 Car 2 Car 3 Car 4 Car 5 Car 6

$90 $95 $85 $110 105 $120

The fare for each of the rides are $45, $35, $37, and $50.

After the driver gets to the destination, the estimate income for the rest of
the day
Car 1 Car 2 Car 3 Car 4 Car 5 Car 6
User 1 $60 $55 $66 $80 $75 $90
User 2 $45 $45 $50 $65 $60 $85
User 3 $70 $65 $75 $90 $85 $100
User 4 $40 $35 $42 $60 $55 $65
None $90 $85 $90 $105 $105 $115
 Assigning School Buses 40

A city is soliciting bids from six bus companies for eight routes in the
surrounding school district.

Each company provides a bid indicating the cost they will charge for
driving selected routes, with some companies not bidding on certain
routes.

The bid data is presented below, with values represented in dollars. (If a
company does not bid on a route, the corresponding entry is left blank.)

Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8

Company 1 8200 7800 5400 3900
Company 2 7800 8200 6300 3300 4900
Company 3 4800 4400 5600 3600
Company 4 8000 5000 6800 6700 4200
Company 5 7200 6400 3900 6400 2800 3000
Company 6 7000 5800 7500 4500 5600 6000 4200
 Assigning School Buses 41

The city needs to determine the assignment of companies to routes with

the following specifications:

1. If a company does not submit a bid for a route, it cannot be

assigned to that route.
2. Each route must be assigned to exactly one company.
3. A company can be assigned to at most two routes.

The objective is to minimize the total cost of covering all the routes.

Refer to AssigningSchoolBus_Data.xlsx
 Structuring the School Bus Problem 42

Decisions to be made

Performance measure

Things that restrict your choices

Data needed
 Mathematical Formulation 43

Input parameters:

Decision variables:

Objective function:

Constraints:
 Input Cells 44

A B C D E F G H I
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 123000 117000 81000 58500
4 Company 2 117000 123000 94500 49500 73500
5 Company 3 72000 66000 84000 54000
6 Company 4 120000 75000 102000 100500 63000
7 Company 5 108000 96000 58500 96000 42000 45000
8 Company 6 105000 87000 112500 67500 84000 90000 63000
 Decision/Changing Cells 45

• Changing cells: B12:I17

– Binary Variables : 1  successful bid, 0  unsuccessful bid

A B C D E F G H I
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 123000 117000 81000 58500
4 Company 2 117000 123000 94500 49500 73500
5 Company 3 72000 66000 84000 54000
6 Company 4 120000 75000 102000 100500 63000
7 Company 5 108000 96000 58500 96000 42000 45000
8 Company 6 105000 87000 112500 67500 84000 90000 63000
9
10 Decision
11 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
12 Company 1
13 Company 2
14 Company 3
15 Company 4
16 Company 5
17 Company 6
 Constraint Cells 46

• A company can be assigned to at most two routes.

– At most two “1” entries in each row
– E.g., Company 1: Let cell J12 = SUM(B12:I12) <= 2
– Constraint: J12:J17 <= L12:L17

• Exactly one company must be assigned to each route.

– Only one “1” entry in each column
– E.g., Route 1: Let cell B18 = SUM(B12:B17) , B18 = 1
– Constraint: B18:I18 = B20:I20
 Constraint Cells 47

A B C D E F G H I J K L
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 123000 117000 81000 58500
4 Company 2 117000 123000 94500 49500 73500
5 Company 3 72000 66000 84000 54000
6 Company 4 120000 75000 102000 100500 63000
7 Company 5 108000 96000 58500 96000 42000 45000
8 Company 6 105000 87000 112500 67500 84000 90000 63000
9
=SUM(B12:I12)
10 Decision
11 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
12 Company 1 0 <= 2
13 Company 2 0 <= 2
14 Company 3 0 <= 2
15 Company 4 0 <= 2
16 Company 5 0 <= 2
17 Company 6 0 <= 2
18 0 0 0 0 0 0 0 0
=SUM(I12:I17)
19 = = = = = = = =
20 1 1 1 1 1 1 1 1
 Constraint Cells 48

• If a company does not bid on a route, it cannot be assigned to that route.

– There are multiple ways to formulate this constraint
– One of them is to set an upper bound to the decision variables such
that
Decision variable = 0 when the company doesn’t bid on the route
– Constraint: B12:I17 <= B3:I8
A B C D E F G H I J K L
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 0 123000 117000 81000 0 58500 0 0
4 Company 2 117000 123000 0 94500 0 49500 73500 0
5 Company 3 0 72000 0 0 0 66000 84000 54000
6 Company 4 0 0 120000 75000 102000 0 100500 63000
7 Company 5 108000 96000 0 58500 96000 42000 0 45000
8 Company 6 105000 87000 112500 67500 84000 0 90000 63000
9
=SUM(B12:I12)
10 Decision
11 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
12 Company 1 0 <= 2
13 Company 2 0 <= 2
14 Company 3 0 <= 2
15 Company 4 0 <= 2
16 Company 5 0 <= 2
17 Company 6 0 <= 2
18 0 0 0 0 0 0 0 0
=SUM(I12:I17)
19 = = = = = = = =
 Objective Cell 49

• Total Cost = SUMPRODUCT(B3:I8,B12:I17)

A B C D E F G H I J K L
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 0 123000 117000 81000 0 58500 0 0
4 Company 2 117000 123000 0 94500 0 49500 73500 0
5 Company 3 0 72000 0 0 0 66000 84000 54000
6 Company 4 0 0 120000 75000 102000 0 100500 63000
7 Company 5 108000 96000 0 58500 96000 42000 0 45000
8 Company 6 105000 87000 112500 67500 84000 0 90000 63000
9
=SUM(B12:I12)
10 Decision
11 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
12 Company 1 0 <= 2
13 Company 2 0 <= 2
14 Company 3 0 <= 2
15 Company 4 0 <= 2
16 Company 5 0 <= 2
17 Company 6 0 <= 2
18 0 0 0 0 0 0 0 0
=SUM(I12:I17)
19 = = = = = = = =
20 1 1 1 1 1 1 1 1
21
22 Total Cost $ - =SUMPRODUCT(B3:I8,B12:I17)
Solver Setup 50

• Set Obj: B22

• To: Min

• Change cell: B12:I17

• Subject to Constraints
B12:I17 <= B3:I8
B18:I18 = B20:I20
J12:J17 <= L12:L17
 An Optimal Solution 51

A B C D E F G H I J K L
1 Bids on Bus Routes
2 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
3 Company 1 0 123000 117000 81000 0 58500 0 0
4 Company 2 117000 123000 0 94500 0 49500 73500 0
5 Company 3 0 72000 0 0 0 66000 84000 54000
6 Company 4 0 0 120000 75000 102000 0 100500 63000
7 Company 5 108000 96000 0 58500 96000 42000 0 45000
8 Company 6 105000 87000 112500 67500 84000 0 90000 63000
9
=SUM(B12:I12)
10 Decision
11 Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
12 Company 1 0 0 1 0 0 0 0 0 1 <= 2
13 Company 2 0 0 0 0 0 1 1 0 2 <= 2
14 Company 3 0 1 0 0 0 0 0 0 1 <= 2
15 Company 4 0 0 0 0 0 0 0 0 0 <= 2
16 Company 5 0 0 0 1 0 0 0 1 2 <= 2
17 Company 6 1 0 0 0 1 0 0 0 2 <= 2
18 1 1 1 1 1 1 1 1
=SUM(I12:I17)
19 = = = = = = = =
20 1 1 1 1 1 1 1 1
21
22 Total Cost $ 604,500 =SUMPRODUCT(B3:I8,B12:I17)
 Supply Chain Design 52

Online retailing companies like Amazon require a vast network of

inventories located in different areas to ensure prompt delivery of products
to their customers.

With the rise of services like Amazon Prime and the introduction of new
offerings like Amazon Prime Now, the significance of strategically
selecting warehouse locations and partnering with the appropriate local
warehouses has significantly grown.

52
 Supply Chain Design 53

In response to the increasing demand, Amazon has made the strategic

decision to establish new warehouses in the Gulf Coast region.

Through extensive research and analysis, four potential warehouse

locations have been identified.

Each location has a designated capacity and an average cost-per-unit for

shipping to any of the five Gulf Coast states.

TX LA MS AL FL Fixed Cost Capacity

WH 1 $2.00 $4.00 $3.00 $2.50 $1.50 $10,000 14000
WH 2 $3.00 $2.50 $3.75 $2.00 $1.75 $8,000 18000
WH 3 $2.75 $2.00 $3.25 $3.00 $4.00 $7,000 16500
WH 4 $1.25 $1.75 $4.00 $3.50 $3.00 $12,000 16000

Demand 8000 3500 4000 2000 7000

53
 Supply Chain Design 54

By carefully evaluating the capacity of each warehouse, their operating

costs, and the average shipping costs to the respective states, Amazon can
make informed decisions on which warehouses to operate.

The goal is to minimize costs while efficiently meeting the demand for its
products in the Gulf Coast region.

Template file: OnlineRetailing_template.xlsx

54
 Structuring the Warehouse Problem 55

Decisions to be made

Performance measure

Things that restrict your choices

Data needed
 Mathematical Formulation 56

Input parameters:

Decision variables:

Objective function:

Constraints:
 Input Cells 57

A B C D E F G H I
2 TX LA MS AL FL Fixed Cost Capacity
3 WH 1 $2.00 $4.00 $3.00 $2.50 $1.50 $10,000 14000
4 WH 2 $3.00 $2.50 $3.75 $2.00 $1.75 $8,000 18000
5 WH 3 $2.75 $2.00 $3.25 $3.00 $4.00 $7,000 16500
6 WH 4 $1.25 $1.75 $4.00 $3.50 $3.00 $12,000 16000
7
8 Demand 8000 3500 4000 2000 7000
 Decision/Changing Cells 58

• Changing cells:
– B12:F15: number of units shipped from WH (1/2/3/4) to each state
– J12:J15: binary variables indicating whether WH (1/2/3/4) is in operation
=1 when the WH is in operation
=0 when the WH is closed

A B C D E F G H I J
10 Decisions & Constraints
Operate
TX LA MS AL FL
11 or not?
12 WH 1
13 WH 2
14 WH 3
15 WH 4
 Constraint Cells 59

• The warehouse operation should meet the demand of each of the five states.
– Sum of each column equals to the quantity shipped (inflow) to each
state
– E.g., for TX, inflow = SUM(B12:B15)
– Demand Constraint
Inflow = Demand  B16:F16 = B18:F18
 Constraint Cells 60

• Units stored in each warehouse shouldn’t exceed its “effective capacity.”

– The capacity of a warehouse is only available when it is in operation
– Therefore, we define effective capacity = capacity * operate or not as
shown in I12:I15
– Sum of each row equals to the quantity stored in/shipped from each
warehouse (outflow)
– Capacity Constraint:
Outflow <= Effective Capacity  G12:G15 <= I12:I15
 Objective Cell 61

• Total Cost = SUMPRODUCT(H3:H6,J12:J15) + SUMPRODUCT(B3:F6,B12:F15)

Solver Setup 62

• Set Obj: B21

• To: Min

• Change cell:
B12:F15, J12:J15

• Subject to Constraints
B16:F16 = B18:F18
G12:G15 <= I12:I15
J12:J15 = binary
An Optimal Solution 63
 64

General Fixed-Cost Models

• Fixed-cost (minimization) models are used when a fixed cost is incurred if an
activity is undertaken at any positive level.

• Examples:
– Construction of a warehouse incurs a fixed cost that is the same whether
the warehouse is then used at partial or full capacity;
– Setup cost required to prepare a machine or production line to produce a
different type of product than the current one;
– For instance, the cost of producing x shirts during a week is 0 if x=0, but it
is 1500+20x if x>0.
 65

Fixed-Cost: Modeling Approach

Define two decision variables per fixed cost situation:
x=production quantity
y=binary variable for setup

Constraint: x ≤ M y, where M is an upper bound on the optimal value of. For

instance, if x≤14,000, then we could set M=14,000.

Solver will try to minimize y and hence set y=0 whenever possible.

The alternative of using the IF(…) function is not that efficient for Solver.