Over. Int. Con. App. of Int. Lin. Pro.
Integer Linear Programming
Master of Business Administration
MBA 8419 – Decision Making Technology
Copyright By PowCoder代写 加微信 powcoder
1 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Overview of the presentation
Integrality constraints Definitions and importance
Applications of integer linear programming Revenue management
Airline Company Schedule planning
Call center 0-1 Formulations
Location problem Product design problem
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Def. and Imp. Integrality constraints
Definitions and importance
Integrality constraint categories
General integer variables
Description : Decision that are represented using general discrete variables.
Examples : Production decisions expressed in number of lots (skus); Assignment decisions (employees → schedules) ; etc.
Binary variables
Description : Decision that are represented using discrete variables that can take one of two values, either 0 or 1.
Examples : Decisions that represent choices ; Design decisions ; etc.
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Def. and Imp. Integrality constraints
Definitions and importance
Why are these decisions important ?
Example 1 : consider a plan that would call for 1 054.75 chairs to be produced. 2 rounding options :
1 054 chairs
1 055 chairs
Impact : the production of 1 extra chair has a relatively small marginal impact for the company.
Example 2 : consider a plan that would call for 14.33 houses to be built. 2 rounding options :
Impact : the construction of 1 extra house will have a much higher marginal impact for the developer.
4 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Def. and Imp. Integrality constraints
Definitions and importance
Consider the following optimization problem max z = 100×1 + 150×2
Subject to
80×1 + 40×2 ≤ 400 (1) 15×1 + 30×2 ≤ 200 (2) x1,x2 ≥0 (3) x1, x2 integers (4)
If the problem is solved by excluding the integrality requirements :
x1 = 2,222, x2 = 5,555 et z = 1055,556
Simple solution method
Find all the rounded solutions Identify the best integer solutions
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Def. and Imp. Integrality constraints
Definitions and importance
Rounded solutions :
(x1 =2,×2 =5)⇒Feasibleandz =950
(x1 =2,×2 =6)⇒Infeasible15(2)+30(6)=210̸≤200 (x1 =3,×2 =5)⇒Infeasible80(3)+40(5)=440̸≤400 (x1 = 3, x2 = 6) ⇒ Infeasible, constraints (3) and (4)
Only one solution is feasible : x1 =2,×2 =5etz =950
The optimal solution :
x1 =1,×2 =6etz =1000
Simple methods do not necessarily produce optimal solutions. Also, the number of rounded solutions can grow rapidly.
6 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Revenue management
Description : A discipline that aims to understand customers’ perception of product value and accurately aligning product prices, placement and availability with each customer segment with the objective of maximizing revenues.
Examples :
Airline industry
Railway industry Hotels
Question : How should the rates of products be set such as to maximize the revenues generated ?
Specificities : pricing strategies vs. overbooking policies vs. ma- naging supplies
7 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Revenue management
FIGURE – General context – flight planning
8 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Revenue management
Leisure Air : Fare type optimization
Context : Ressources :
Boeing 737-400 (132 seats E) Currently in Pittsburgh
Boeing 737-400 (132 seats E) Current in Newark
Operations :
Leg no.1 : P → C,
Leg no.2 : N → C, Leg no.3 : C → M, Leg no.4 : C → O.
Illustration of the legs
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Revenue management
Leisure Air
Context (cont’d) :
The companies proposes 2 types of fares for its economy class :
discount-fare Q full-fare Y
Reservations using the discount-fare Q class must be made 14 days in advance and must include a Saturday night stay in the destination city.
Reservations using the full-fare Y class may be made anytime, with no penalty for changing the reservation at a later date.
The company is interested in planning the itineraries and tarifs that it should propose to its clientele. To determine the itineraries and fares, the company would like to know :
How many seats should be assigned to each O-D itinerary and fare type ? ODIF ⇒ Origin-Destination-Itinerary Fare
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Revenue management
Tickets, Prices and Predicted Demand
No. ODIF Price Demand
PCQ 178$ 33 PMQ 268$ 44 POQ 228$ 45 PCY 380$ 16 PMY 456$ 6 POY 560$ 11 NCQ 199$ 26 NMQ 249$ 56 NOQ 349$ 39 NCY 385$ 15 NMY 444$ 7 NOY 580$ 9 CMQ 179$ 64 CMY 380$ 8 COQ 224$ 46 COY 582$ 10
11 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Revenue management
Optimization Model
Definitions P=Pittsburgh,
N=Newark, C=Charlotte, O=Orlando, M=Myrtle Beach
Decision Variables
PCQ = nb. of seats assigned to flight P-C for fare Q PMQ = nb. of seats assigned to flight P-M for fare Q POQ = nb. of seats assigned to flight P-O for fare Q PCY = nb. of seats assigned to flight P-C for fare Y
NCQ = nb. of seats assigned to flight N-C for fare Q .
COY = nb. of seats assigned to flight C-O for fare Y
12 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Revenue management
Optimization Model (cont’d) Objective Function
max 178PCQ + 268PMQ + 228POQ + 380PCY + . . . + 224COQ + 582COY
Subject to
Aircraft capacity 4 Legs
P-C : N-C : C-M : C-O :
PCQ+PMQ+POQ+PCY +PMY +POY ≤132 NCQ+NMQ+NOQ+NCY +NMY +NOY ≤132 PMQ+PMY +NMQ+NMY +CMQ+CMY ≤132 POQ+POY +NOQ+NOY +COQ+COY ≤132
Demands PCQ≤33 NCQ≤26 CMQ≤64
PMQ≤44 NMQ≤56 CMY ≤8
POQ≤45 NOQ≤39 COQ≤46
PCY ≤16 PMY ≤6 NCY ≤15 NMY ≤7 COY ≤10
POY ≤11 NOY ≤9
Non-negativity and integrality for all decision variables
13 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Schedule planning
Call Center
Operators daily work shifts that last 9 hours
Shifts can start at the beginning of every 3 hour period Minimum number of operators for each period :
Period 0-3 3-6 6-9 9-12 12-15 15-18 18-21 21-24 Need 6 4 12 20 20 24 14 14
Salaries :
Base : 75$ per shift of 9h
11 $ for shifts starting at 0h, 3h ou 6h 5 $ for shifts starting at 18h ou 21h
Q : How many operators to hire to start at each of the periods ? 14 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Schedule planning
Decision variables
xj = nb. of operators that will begin their shifts at hour j, where j = 0,3,6,9,12,15,18,21.
FIGURE – Graphical Representation
15 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Schedule planning
Optimization Model
minz =86×0 +86×3 +86×6 +75×9 +75×12 +75×15 +80×18 +80×21
subject to
x0 +x18 +x21 ≥6 x0 + x3 + x21 ≥ 4
x0 + x3 + x6 ≥ 12
x3 + x6 + x9 ≥ 20
x6 +x9 +x12 ≥20 x9 +x12 +x15 ≥24 x12 +x15 +x18 ≥14 x15 +x18 +x21 ≥14
xj ≥ 0 and integer for j = 0,3,6,9,12,15,18,21.
16 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
Schedule planning
Call Center (cont’d)
Description : A company that provides an after sales service for its clients needs to plan the number of operators to adequately cover the demand over the period of a normal day of operations.
Minimum requirements for switchboard operators
Period 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 Need 6 5 2 2 3 3 4 12
Period 8-9 9-10 10-11 11-12 12-13 13-14 14-15 15-16 Need 20 23 24 24 20 22 24 25 Period 16-17 17-18 18-19 19-20 20-21 21-22 22-23 23-24 Need 22 20 18 16 15 14 9 7
Daily work shift ⇒ 8h. = 7h. of work and 1h. break (meal)
Beginning hour for shifts : 7 h., 8 h., 9 h., 15 h., 16 h., 23 h. and midnight Salaries
Base ⇒ 80$
Premiums ⇒ 5$ (shifts beginning at 23 h.) et 10$ (shifts beginning at midnight) Meals : the meal break can be taken either 3 or 4 hours after the beginning of the shift.
However, breaks can only be taken when the company’s cafeteria is open.
Cafeteria’s opening hours : from 11 h. to 14 h., from 17 h. to 20 h. and from 2 h. to 4 h.
17 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Schedule planning
Optimization Model Decision Variables
Beginning 7h.
Break + 3h.
Break scheduled at 10h. ⇒ Caf. closed Impossible
Break scheduled at 11h. ⇒ Caf. opened x8
Break scheduled at 12h. ⇒ Caf. opened x9
Break + 4h.
Break scheduled at 11h. ⇒ Caf. opened y7
Break scheduled at 12h. ⇒ Caf. opened y8
Break scheduled at 13h. ⇒ Caf. opened y9
Therefore,
x8 = nb. of operators that will begin their shifts at 8 h. and that will take a meal break between 11 h. and 12 h.
y8 = nb. of operators that will begin their shifts at 8 h. and that will take a meal break between 12 h. and 13 h.
18 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Schedule planning
General Representation
19 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Schedule planning
Optimization Model (cont’d) Objective function
minz = 90×0 +80(y7 +x8 +y8 +x9 +y9 +x15 +y15 +x16)+85(x23 +y23)
Subject to
x0 +x23 +y23 ≥6 x0 + y23 ≥ 2
x0 + y7 ≥ 12
y7 + x8 + y8 ≥ 20 .
x16 +x23 +y23 ≥7
Non-negativity and integrality for all decision variables
20 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
Location Problems
Description : The long-range planning department for the Ohio Trust Company bank is
considering expanding its operation into a 20-county region in the northeastern Ohio.
FIGURE – Region considered for expansion
21 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
Description (cont’d) :
Ohio Trust does not have a principal place of business (PPB) in
any of the 20 counties.
According to the banking laws in Ohio, if a bank establishes a PPB in any county, branch banks can be established in that county and in any adjacent county.
However, to establish a new PPB, Ohio Trust must either obtained approval for a new bank from the state’s superintendent of banks or purchase an existing bank.
Question : Ohio Trust would like to determine the minimum num- ber of PPBs necessary to do business throughout the 20-county region.
22 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
Description (cont’d)
FIGURE – Counties and adjacent ones
23 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
Optimization Model
Decision Variables
xi = 1 if a PPB is established in county i ; 0 otherwise. For i = 1,…,20
Fonction objectif :
Minimize the number of PPBs that are necessary to achieve the
necessary to cover the considered region minx1 +x2 +…+x20
24 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
Optimization Model (cont’d)
Subject to :
Ohio Trust must cover each county to be able to do business :
x1 +x2 +x12 +x16 ≥1
x1 +x2 +x3 +x12 ≥1
x2 +x3 +x4 +x9 +x10 +x12 +x13 ≥1 .
Ashtabula Lake Cuyahoga .
Integrality constraints : xi = 0 or 1, i = 1,…,20
x11 +x14 +x19 +x20 ≥ 1
25 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming Location coverage planning
FIGURE – Optimal solution – 3 PPBs
26 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro. Rev. Man. Sch. Pla. 0-1 For. Applications of integer linear programming
0-1 Formulations
Product Design and Market Share Optimization
General Context : Technique that can be used to learn how pros-
pective buyers of a product valued the product’s attributes.
Salem Foods
Company that is planning to enter the frozen pizza market. There are currently two existing brands, Antonio’s and King’s, that have the major share of the market.
Four important attributes to define the porduct : crust (thin and thick)
cheese (mozzarella and blend)
sauce (smooth and chunky)
sausage (mild, medium and hot)
Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Salem Foods (cont’d)
The two competitors, which are currently in the market, propose the following products :
Description of the proposed pizzas :
Types of pizza crust
cheese mozzarella blend
sauce chunky smooth
sausage medium mild
Antonio’s King’s
thick thin
28 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Salem Foods (cont’d)
Part-worths for the Salem Foods Problem
crust cheese sauce sausage flavor
Consumer 1
thin thick mozzarella blend smooth 11 2 6 7 3 11 7 15 17 16
7 5 8 14 16 13 20 20 17 17 2 8 6 11 30 12 17 1192 9 19 12 16 16 5 9 4 14 23
chunky mild medium hot 17 26 27 8 26 14 1 10
7 29 16 19 14 25 29 10 20 15 5 12 30221220 25 30 23 19 16 16 30 3
8 potential consumers expressed their preference (utility) for specially prepared pizzas with chosen levels for the attributes. A regression analysis → part-worth for each of the attribute levels.
Interpretation consummer 1 ⇒
consummer 1 ⇒ consumer 1 ⇒
ideal pizza
+ cheese blend + sauce chunky
thin crust 11
crust thick
2 +6 +17 +27 =52
pizza King’s
crust thin + cheese blend + sauce smooth + sausage mild total utility
+ 17 pizza Antonio’s
+ sausage medium + 27
total utilitity = 62
+ cheese mozzarella + sauce chunky
+ sausage medium
total utility
11 +7 +3 +26 =47
29 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Salem Foods (cont’d)
General Objective :
1. Salem is interested in designing a pizza which will please po- tential consumers such that the company will obtain a majority of the market.
2. In order to be profitable for Salem, the proposed pizza will have to generate a maximum utility for the largest number of potential consumers.
Hypothesis : the considered sample of potential consumers is representative of the market that is pursued.
30 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Optimization Model Decision Variables
Product design :
xij = 1 if Salem chooses level i for attribute j ; 0 otherwise
Market share :
yk = 1 if consumer k chooses the Salem brand, 0 otherwise
Objective Function
The objective for the company is to carve out the highest possible market share.
maxy1 +y2 +…+y8
31 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Optimization Model (cont’d) Subject to
Product design
Attributes crust cheese sauce sausage flavor
choice restrictions x11 + x21 = 1 x12 + x22 = 1 x13 + x23 = 1 x14 + x24 + x34 = 1
32 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Optimization Model (cont’d) Subject to (cont’d)
Defining the market share
Example for consumer 1 :
Total utility function for Salem’s pizza :
11×11 +2×21 +6×12 +7×22 +3×13 +17×23 +26×14 +27×24 +8×34 Joint analysis :
Types of pizza Ideal Antonio’s King’s
Total utility 62 52⋆
To modify the present choice of consumer 1 :
11×11 +2×21 +6×12 +7×22 +3×13 +17×23 +26×14 +27×24 +8×34 >52
Therefore,
11×11 +2×21 +6×12 +7×22 +3×13 +17×23 +26×14 +27×24 +8×34 ≥1+52y1
33 Integer Linear Programming
Over. Int. Con. App. of Int. Lin. Pro.
Rev. Man. Sch. Pla. 0-1 For.
Applications of integer linear programming 0-1 Formulations
Optimization Model (cont’d) Subject to (cont’d)
Consumer 1
Constraint
11×11 +2×21 +6×12 +7×22 +3×13 +17×23 +26×14 +27×24 +8×34 ≥1+52y1 11×11 +7×21 +15×12 +17×22 +16×13 +26×23 +14×14 +1×24 +10×34 ≥1+58y2 7×11 +5×21 +8×12 +14×22 +16×13 +7×23 +29×14 +16×24 +19×34 ≥1+66y3 13×11 +20×21 +20×12 +17×22 +17×13 +14×23 +25×14 +29×24 +10×34 ≥1+83y4 2×11 +8×21 +6×12 +11×22 +30×13 +20×23 +15×14 +5×24 +12×34 ≥1+58y5 12×11 +17×21 +11×12 +9×22 +2×13 +30×23 +22×14 +12×24 +20×34 ≥1+70y6 9×11 +19×21 +12×12 +16×22 +16×13 +25×23 +30×14 +23×24 +19×34 ≥1+79y7 5×11 +9×21 +4×12 +14×22 +23×13 +16×23 +16×14 +30×24 +3×34 ≥1+59y8
Antonio’s King’s King’s Antonio’s King’s Antonio’s Antonio’s Antonio’s
Integrality constraints
xij =0or1,foralli andj
yk =0or1,fork =1,…,8
34 Integer Linear Programming
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com