15.053 Tuesday, April 24: Integer Programming Formulations 2

Download as pdf or txt
Download as pdf or txt
You are on page 1of 32

15.

053

Tuesday, April 24

Integer Programming Formulations 2

Quote of the Day


What chiefly characterizes creative thinking from more mundane forms are (i) willingness to accept vaguely defined problem statements and gradually structure them, (ii) continuing preoccupation with problems over a considerable period of time, and (iii) extensive background knowledge in relevant and potentially relevant areas. -- Herbert Simon

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

Logical Constraints with non-binary variables


Variables: x1, x2, x3, are non-negative integers x1 10 or x2 25 or both

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

Translation: x1 x2 10 or x2 x1 10 If w3 = 1, then If w3 = 0, then

Fill in the table


w3 = 1 w3 = 0 x1 - x2 x2 x1
6

x1 x2 10 + x2 x1

x1 - x2 x2 x1

IP and piecewise linear functions.


f(x) = 2 x f(x) = 9 x
cost

if 0 x 3 if 4 x 7 if 8 x 9

f(x) = -5 + x

Assume that x is integer valued. 0 3 7 9 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

Version 1: Create Binary Variables


Step 1. Create three binary variables, w1, w2, and w3

w1 + w2 + w3 = 1 If 0 x 3 then w1 = 1 If 4 x 7 then w2 = 1 If 8 x 9 then w3 = 1 wj {0, 1} for j = 1, 2, 3.

Almost works, but we need something else.

Warning, this transformation will be challenging to follow the first time around.
8

Version 2: Split x into three variables


Step 2. Split x into three variables x1, x2, x3.

If 0 x 3 then x1 = x; otherwise, x1 = 0. If 4 x 7 then x2 = x; otherwise, x2 = 0. If 8 x 9 then x3 = x; otherwise, x3 = 0. x = x1 + x2 + x3.


9

Version 2 continued. Combine Steps 1 and 2.


Transformation
w1 + w 2 + w3 = 1 0 x1 3 w 1

Last step
z = 2x if 0 x 3 if 4 x 7 if 8 x 9

4w2 x2 7 w2 8w3 x3 9 w3 x = x1 + x2 + x3 f(x) = 2x1 + (9w2 x2) + (-5w3 + x3)

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

Another non-linear function


z = 2 x1 + 5x2 + f(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

w1 + w 2 + w3 = 1 x3 = x31 + x32 + x32 0 x31 2 w1 x32 x33 z = 2 x1 + 5x2 +


11

On representing non-linear functions


z

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

How do we represent this as an IP?


xj = 1 if set j is selected xj = 0 otherwise Minimize x + x + + x16 Minimize x11+ x22+ + x16 s.t. x + x + x + x 1 s.t. x11+ x22+ x44 + x55 1 x +x +x +x +x 1 x11+ x22+ x33+ x55+ x66 1 Constraints Variables Objective

x13 + x15 + x16 1 xj {0, 1} for each j.


16

Representation as Set Covering Problem


# 1 2 7 9 12 15 13 16 16 {13, 15, 16}
17

1 5 4 11 10 14

2 6 8

Subset {1, 2, 4, 5} {1, 2, 3, 5, 6} {2, 3, 6, 7}

Set covering Problem


Let S = {1, 2, , n}, and suppose Sj S for each j. We say that index set J is a cover of S if

j J

Sj = S

Set covering problem: find a minimum


cardinality set cover of S.

Application to locating fire stations.


Locating hospitals.
Locating Starbucks
and many non-obvious applications.
18

More Integer Programming Formulations


z

Facility Location Problems Graph Coloring Exam Scheduling

19

053 Chocolates Location


z z

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

Distances from possible chocolate stores to customers

21

Formulation as an IP
Variables
1 2 3 3

1 if store j is opened yj = 0 otherwise

B 4

A 5

C 6

1 if costomer is is served by store j x ij = 0 otherwise


Objective Constraints

d ij x ij = 4 x1A + 2 x1B + 6 x1C + x2A +

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

x ij {0,1} for all i , j ; y j {0,1} for all j

22

Warehouse Location Problem

Figure by MIT OCW.

Open warehouses so as to minimize the total cost of doing business


23

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

Grand Rio Blanco

Boulder

Yuma

Gilpin Clear Eagle Summit Creek Jefferson Denver

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

Gr and Rio Blanco

Boulder

Yuma

Gilpin Clear Garfield Eagle Summit Cr eek Jeff erson Denver

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

Here is a four coloring of the map.


26

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

Pr owers Ot er o Huerf ano Bent

Miner al Rio Gr ande

Alamosa

Montezuma La Plat a Archulet a Conej os Costilla

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

The Integer Programming Formulation

28

An Exam Scheduling Problem


The University of Waterford has to schedule 500
exams over two weeks. The objective is to schedule
the exams in the fewest number of periods so that no
person has to take two exams at the same time.
G = (N, A) N = {1, 2, 3, n} set of exams

A = set of arcs. (i, j) A if a person needs to take exam i and exam j.

How would one model this as an integer program?

29

Another Exam Scheduling Problem


G = (N, A) N = {1, 2, 3, n} There are m exam periods. A = set of arcs. (i, j) A if a person needs to take exam i and exam j. let cij = the number of persons who need to take
exam i and exam j.
set of exams

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

Summary of Integer Programming


z

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

You might also like