15.053 Tuesday, April 24: Integer Programming Formulations 2
15.053 Tuesday, April 24: Integer Programming Formulations 2
15.053 Tuesday, April 24: Integer Programming Formulations 2
053
Tuesday, April 24
Overview of lecture
z
First half of lecture: more logical constraints non-linearities Second half of lecture classic combinatorial problems
set covering facility location graph coloring exam scheduling
Assume that x1 100 . We need an upper bound. Create a variable w1 with the following properties: If w1 = 1, then x1 10; If w1 = 0, then x2 25; w1 = 0 or 1. x1 9 + 91(1-w1) x2 25 - 25w1
w =1 w11= 1 x 9 x11 9 x 0 x22 0 w =0 w11= 0 x 100 x11 100 x 25 x22 25
4
Or-constraints in general.
ax b or cx d or both
Let M1 and M2 be integers so that ax M1 and cx M2 in any feasible solution. Typically M1 is very large, and M2 is very negative If w2 = 1, then ax b; If w2 = 0, then cx d; w2 = 0 or 1. ax b + (M1 b )(1-w2) cx d + (M2 d) w2
w2 = 1 ax b cx M2 w2 = 0 ax M1 cx d
5
Another example
| x1 x2 | 10 Assume x1 100 and x2 200. Note: x1 x2 -200 x2 x1 -100
x1 x2 10 + x2 x1
x1 - x2 x2 x1
if 0 x 3 if 4 x 7 if 8 x 9
f(x) = -5 + x
An NLP formulation How do we model the function f(x)? Later we will assume that f(x) is part of the objective function, and we will maximize it.
7
Warning, this transformation will be challenging to follow the first time around.
8
Last step
z = 2x if 0 x 3 if 4 x 7 if 8 x 9
z= 9x z = -5 + x
10
w1 + w2 + w3 = 1
If w1 = 1, then 0 x1 3
If w1 = 0, then x1 = 0
If w2 = 1, then 4 x2 7
If w2 = 0, then x2 = 0
If w3 = 1, then 8 x3 9
If w3 = 0, then x3 = 0
x = x1 + x2 + x3
1 f ( x3 ) = 4 x3
if 0 x 3 2 if 3 x 3 6 if 7 x 3 10
w1 + w 2 + w3 = 1 x3 = x31 + x32 + x32 If w1 = 1, then 0 x31 2 If w1 = 0, then x31 = 0 If w2 = 1, then If w2 = 0, then x32 = 0 If w3 = 1, then If w3 = 0, then x33 = 0
Integer programs can represent piecewise linear functions of one variable. They cannot represent non-linear functions with curves. But they can nearly model non-linear functions with curves. One can create a piecewise linear function that is close to the original function.
12
Mental Break
z
MIT Jeopardy
13
053 Chocolates
Cleaver, Nooz, Ollie, and Tim have started a firm
called 053 chocolates.
Slogan: 053 chocolates are optimum. Cleaver wants to ensure that everyone has easy
access to the chocolates, and so requests that
every district has an 053s or is next to a district
with an 053s.
Nooz wants to minimize the number of 053 stores
to satisfy the covering constraints. How can
we satisfy the both Nooz and Cleaver?
14
053 Chocolates
5 4 11 8X
6 9 12 15 X
Locate 053 Chocolate stores so that each district has a store in it or next to it. Minimize the number of stores needed.
13 16
10 14
15
1 5 4 11 10 14
2 6 8
j J
Sj = S
19
6 customers.
3 possible locations for chocolate stores
1 2 3
B 4
A 5
C
6
What is the best location for two chocolate stores so as to minimize total distance to customers?
20
1 A B C 4 2 6
2 1 2 2
3 4 6 2
4 4 2 6
5 1 2 2
6 4 6 2
21
Formulation as an IP
Variables
1 2 3 3
B 4
A 5
C 6
x iA + x iB + x iC = 1 for i = 1 to 6
x ij y j for i = 1 to 6, and j = A, B, C y A + y B + yC = 2
22
Location problems
z z z
Locations: (Warehouses, or stores, or sites, or internet routers or ) need to be opened Customers need to be served A customer cannot be served by a location unless the location is opened Variants: there may be a cost for opening a location customers in some problems may be served
by more than one location
There may be a capacity on how much is
stored at the warehouse.
24
Graph Coloring
Sedgwick Logan Weld Moffat Jackson Routt Morgan Larimer Phillips
Boulder
Yuma
Adams
Washington
Arapahoe
Garfield
Elbert Douglas Pitkin Mesa Lake Park Lincoln Teller Delta Gunnison Chaffee El Paso
Kit Carson
Cheyenne
Fremont Montrose Ouray Saguache San Miguel Hinsdale Otero Dolores San Juan Mineral Rio Grande Montezuma Las Animas La Plata Archuleta Conejos Costilla Alamosa Huerfano Bent Custer Crowley Pueblo
Kiowa
Prowers
Baca
This is a map of the counties in Colorado. Is it possible to color the counties with 4 colors so that no counties with a common border have the same color?
25
Graph Coloring
Sedgwick Logan Moff at Jackson Routt Mor gan Larimer Weld Phillips
Boulder
Yuma
Adams
Washingt on
Ar apahoe
Elbert Douglas Pitkin Mesa Lake Park Lincoln Teller Delt a Gunnison Chaff ee El Paso
Kit Carson
Cheyenne
Fr emont Montr ose Our ay Saguache Hinsdale Ot er o Dolor es San Juan Miner al Rio Gr ande Montezuma Las Animas La Plat a Archulet a Conej os Costilla Alamosa Huerf ano Bent Cust er Cr owley Pueblo
Kiowa
San Miguel
Pr owers
Baca
Graph Coloring
Sedgwick Moff at Routt Mor gan Boulder Gilpin Clear Cr eek Summit Denver Jeff erson Ar apahoe Adams Washingt on Yuma Larimer Weld Logan Phillips
G = (N, A) N = {1, 2, 3, n} set of counties A = set of arcs. (i, j) A if counties i and j are adjacent.
Jackson
Rio Blanco
Gr and
Garfield
Eagle
Douglas Pitkin Mesa Delt a Gunnison Chaff ee Fr emont Montr ose Our ay San Miguel Dolor es San Juan Hinsdale Saguache Cust er Pueblo Lake Park Teller El Paso
Elbert
Kit Carson
Lincoln Cheyenne
Kiowa Cr owley
Alamosa
Las Animas
Baca
Exercise: write an integer program whose solution gives the minimum number of colors to color a map. Key choice: what are the decision variables?
27
28
29
Suppose that there are exactly m exam periods. Formulate the problem of minimizing the number of people in total who are taking two exams at the same time.
30
The IP formulation
1 if exam i is scheduled in period k Let x ik =
0 otherwise 1 if exams i and j are scheduled in period k
k Let y ij =
0 otherwise Minimize subject to ______________________
k x ik + x jk y ij + 1
for all i, j
_________________________________ _________________________________
31
Integer Programs can model an amazing number of different things. linear constraints logical constraints non-linearities It can be challenging to model It can be challenging to solve Next lectures: how to solve IPs
32