Operations Research

Industrial Engineering

Integer Programming

11/3/2016

Model Integer Programming

Permasalahan integer programming (IP) adalah suatu Program Linear (LP) yang
beberapa atau seluruh variabel yang digunakan merupakan bilangan integer positif

Jenis-jenis permasalahan IP:

Pure IP problem: jika semua variabel harus bernilai integer

Maximize
subject to

Mixed IP problem: jika hanya beberapa variabel yang bernilai integer

Maximize
subject to

z = 3x1 + 4x2
5x1 + 8x2 24
x1, x2 0, x1 integer

0-1 IP problem: jika semua variabel harus bernilai 0 atau 1 (Binary Integer Programming/BIP)

Maximize
subject to

z = 3x1 + 4x2
5x1 + 8x2 24
x1, x2 0, x1 dan x2 integer

z = 3x1 + 4x2
5x1 + 8x2 24
x1, x2 = 0 or 1

11/3/2016

Integer Programming dan LP relaxation

Permasalahan IP biasanya lebih sulit untuk diselesaikan dibandingkan dengan
permasalahan LP
Hal ini disebabkan banyaknya kombinasi nilai integer yang harus diuji, dan
setiap kombinasi membutuhan penyelesaian normal LP atau NLP
LP relaxation dari IP adalah LP yang diperoleh dengan menghilangkan
pembatas semua bilangan integer atau pembatas

Contoh Pure IP problem :

Maximize
subject to

Contoh Pure IP problem yang telah di-longgarkan (relax):

Maximize
subject to

z = 3x1 + 4x2
5x1 + 8x2 24
x1, x2 0, x1 dan x2 integer
z = 3x1 + 4x2
5x1 + 8x2 24
x1, x2 0
11/3/2016

Pendekatan sederhana solusi IP

Pendekatan 1:

Cari seluruh kemungkinan

solusi
Tentukan nilai fungsi
tujuannya
Pilih nilai maksimum
(minimum)

7x1 + 4x2= 13

x2

Pendekatan 2:

Selesaikan LP relaxation
Bulatkan pada solusi integer
yang feasibel terdekat

x1
11/3/2016

Solusi Integer Programming

Contoh Problem:
Max z = 1200 x1 + 2000 x2
ST:
2x1 + 6 x2 27
x2 2
3x1 + x2 19
x1 , x2 0 and Integer

x2
6

x2 2
1

Penyelesaian problem Integer

Programming, Apakah solusi LP
dibulatkan untuk mendapakan
solusi IP?

x1
1

LP Optimal
x1 = 5 7/16
x2 = 2 11/16

11/3/2016

Solusi Integer Programming (2)

Max z = 1200 x1 + 2000 x2
ST:
2x1 + 6 x2 27
x2 2
3x1 + x2 19
x1 , x2 0 and Integer

x2
6

Pembulatan?

x1 = 5
x2 = 3

Pembulatan ke atas?
x1 = 6
x2 = 3

Pembulatan
ke bawah?
x1 = 5
x2 = 2

x1
1

LP Optimal
x1 = 5 7/16
x2 = 2 11/16

11/3/2016

Solusi Integer Programming (3)

x2

IP Optimal
x1 = 4
x2 = 3

x1
1

Untuk MAX problem:

nilai optimal dari IP nilai optimal dari LP relaxation
8

11/3/2016

Permodelan
Integer Programming

11/3/2016

Contoh 1: Problem investasi

Perusahaan Stockco mempertimbangkan empat jenis investasi (tiap investasi hanya

bisa dilakukan sekali)
Modal yang tersedia untuk investasi sebesar $ 14,000
Formulasikan model integer programming ini untuk memaksimumkan NPV dari
investasi-investasi berikut:
Pilihan Investasi

Modal

$5000

$7000

$4000

$3000

NPV

$16000

$22000

$12000

$8000

SOLUSI:
xi = investasi ke-i
Maximize
z = 16 x1+ 22 x2 + 12 x3 + 8 x4 (dalam ribuan)
Subject to
5 x1 + 7 x2 + 4 x3 + 3 x4 14 (batasan modal dlm ribuan)
x1, x2, x3, x4 = 0, 1 (0 = jika tdk investasi, 1=jika memilih investasi)
10

11/3/2016

Pengembangan Problem investasi

Perusahaan Stockco mempertimbangkan batasan-batasan logis berikut ini:
Tepat 3 investasi yang terpilih
Jika investasi ke-2 terpilih, maka investasi ke- 1 juga terpilih
Jika investasi ke- 1 terpilih, maka investasi ke- 3 tidak terpilih
Salah satu dari investasi ke- 3 atau ke-4 harus terpilih, tetapi tidak dapat keduaduanya
Tambahan pembatas:
Tepat 3 investasi yang terpilih
x1+ x2+ x3+ x4 =3
Jika investasi ke-2 terpilih, maka investasi ke- 1 juga terpilih
x1 x2
Jika investasi ke- 1 terpilih, maka investasi ke- 3 tidak terpilih
x1 + x3 1
Salah satu dari investasi ke- 3 atau ke-4 harus terpilih, tetapi tidak dapat keduaduanya
x3 + x4 = 1
11

11/3/2016

Contoh 2: Pemilihan pemain bola basket

Perkumpulan bola basket Pasti Menang sedang

menghadapi kompetisi tingkat nasional. Sang pelatih
hendak memilih 5 dari 7 pemain yang akan diturunkan
dalam pertandingan malam nanti. Data-data pemain
seperti terlihat pada tabel dibawah ini:

Pemain Guard
1
Yes
2
No
3
Yes
4
No
5
Yes
6
No
7
Yes
12

Posisi
Kemampuan
Forward Center Ball-Handling Shooting Rebounding Total
No
No
3
1
2
6
No
Yes
1
2
1
4
Yes
No
1
3
1
5
Yes
Yes
1
2
1
4
Yes
No
2
1
3
6
Yes
Yes
1
3
1
5
Yes
No
1
2
2
5
11/3/2016

Pemilihan pemain bola basket

Pembatas yang dialami pelatih adalah sebagai berikut:
Harus ada tepat lima pemain, dengan syarat:

Sedikitnya empat pemain sebagai guard.

Sedikitnya dua pemain sebagai forward.
Sedikitnya satu pemain sebagai center.

Rata-Rata tingkat ketrampilan pemain paling sedikit 2.

Salah satu dari pemain ke-2 atau pemain ke-3 harus
bermain.
Jika pemain ke-3 bermain, maka pemain ke-6 tidak bisa
bermain.
Jika pemain ke-1 bermain, maka pemain ke-4 dan ke-5
harus bermain juga.
13

11/3/2016

Solusi : Pemilihan pemain bola basket (1)

Variabel Keputusan
Xi = 1, jika pemain ke-i diturunkan ke lapangan.
= 0, jika pemain ke-i tidak diturunkan
Fungsi tujuan:
Max z = 6 x1 + 4 x2 + 5 x3 + 4 x4 + 6 x5 + 5 x6 + 5 x7
Pembatas :
Harus ada tepat lima pemain turun ke lapangan
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 5
Paling sedikit terdapat empat pemain guard.
x1 + x3 + x5 + x7 4
Paling sedikit terdapat dua pemain forward.
x3 + x4 + x5 + x6 + x7 2
Paling sedikit terdapat satu pemain center
x2 + x4 + x6 1
14
11/3/2016

Solusi : Pemilihan pemain bola basket (2)

Rata-Rata tingkat ketrampilan pemain paling sedikit 2
(a) Rata-rata ketrampilan pemain ball handling (menggiring
bola) lebih dari dua.
(3 x1 + x2 + x3 + x4 + 2 x5 + x6 + x7)/5 2
3 x1 + x2 + x3 + x4 + 2 x5 + x6 + x7 10
(b) Rata-rata ketrampilan pemain shooting (menembak bola)
lebih dari dua.
x1 + 2 x2 +3 x3 + 2 x4 + x5 + 3 x6 + 2 x7 10
(c) Rata-rata ketrampilan pemain rebounding (menghadang
lebih dari dua)
2 x1 + x2 + x3 + x4 + 3 x5 + x6 + 2 x7 10
15

11/3/2016

Solusi : Pemilihan pemain bola basket (2)

Salah satu dari pemain ke-2 atau pemain ke-3 harus bermain
x2 + x3 1
Variabel kemungkinan yang terjadi:
x2 = 1 & x3 = 0
Feasible
x2 = 0 & x3 = 1
Feasible
x2 = 1 & x3 = 1
Feasible
x2 = 0 & x3 = 0
Infeasible

16

11/3/2016

Solusi : Pemilihan pemain bola basket (3)

Jika pemain ke-3 bermain, maka pemain ke-6 tidak bisa
bermain
x3 + x6 1
Variabel kemungkinan yang terjadi:
Pemain 3 bermain, tetapi pemain 6 tidak bermain.
x3 = 1, x6 = 0
Feasible
Pemain 6 bermain, tetapi pemain 3 tidak bermain.
x3 = 0, x6 = 1
Feasible
Kedua-duanya bermain
x3 = 1, x6 = 1
Infeasible
Kedua-duanya tidak dapat bermain.
x3 = 0, x6 = 0
Feasible
17

11/3/2016

Solusi : Pemilihan pemain bola basket (4)

Jika pemain ke-1 bermain, maka pemain ke-4 dan ke-5
harus bermain juga
x1 x4
x1 x5
Jika x1 = 1, maka x4 = 1 dan x5 =1.
Variabel kemungkinan yang terjadi:

18

x1

x4

x5

Interpretasi

1 ketiga pemain bermain (feasibel).

0 ketiga pemain tidak bermain (feasibel).

0 hanya pemain 4 yang bermain (feasibel).

1 hanya pemain 5 yang bermain (feasibel).

1 pemain 4 dan 5 bermain, sedangkan pemain 1 tidak

(feasibel)
11/3/2016

Contoh 3 : Pengeboran Minyak

Pemilihan paling sedikit 5 lokasi dari 10 lokasi pengeboran

minyak yang telah direncanakan, dengan variabel
keputusan X1, X2,, X10 dan biaya pengeboran C1,
C2,, dan C10.

Batasan:

19

Paling banyak dua dari lokasi X5, X6, X7 dan X8 yang dapat
dipilih
Memilih lokasi X3 atau lokasi X4 akan mencegah untuk
memilih lokasi X5.
Memilih kombinasi lokasi X1 dan X7 akan mencegah untuk
memilih lokasi X8.
11/3/2016

Solusi Pengeboran Minyak (1)

Variabel Keputusan
Xi = 1, jika lokasi ke-i dilakukan pengeboran.
= 0, jika lokasi ke-i tidak dilakukan pengeboran.
Fungsi tujuan:
Min z = C1 x1 + C2 x2 + C3 x3 + C4 x4 +C5 x5 + C6 x6 + C7 x7 + C8 x8 +
C9 x9 + C10 x10
Subject to
(1) Pemilihan paling sedikit 5 lokasi dari 10 lokasi pengeboran
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 > 5

(2) Paling banyak dua dari lokasi X5, X6, X7 dan X8 yang dapat dipilih
x5 + x6 + x7 + x8 2

20

11/3/2016

Solusi Pengeboran Minyak (2)

Memilih lokasi X3 atau lokasi X4 akan mencegah untuk
memilih lokasi X5
x3 + x5 1
x4 + x5 1

21

x3=1 atau x4=1, maka harus x5=0 (jika memilih lokasi X3 atau
lokasi X4, lokasi X5 tidak boleh dipilih)
x5=1, maka nilai x3=0 dan x4=0 (jika memilih lokasi X5, maka
lokasi X3 dan lokasi X4 tidak boleh dipilih)

11/3/2016

Solusi Pengeboran Minyak (3)

Memilih kombinasi lokasi X1 dan X7 akan mencegah
untuk memilih lokasi X8
x1 + x7 + x8 2

kasus 1: tidak memilih lokasi X8

x8 = 0, maka x1 + x7 2 (dapat memilih lokasi S1, S7, atau keduaduanya, atau tidak keduanya).
x8 x1 x7

22

Interpretasi

0 Tidak memilih ketiga lokasi tersebut

1 Hanya memilih lokasi S7

0 Hanya memilih lokasi S1

1 Memilih lokasi S1 dan S7, tetapi lokasi S8 tidak

11/3/2016

Solusi Pengeboran Minyak (4)

Memilih kombinasi lokasi X1 dan X7 akan mencegah
untuk memilih lokasi X8
x1 + x7 + x8 2

kasus 2: Menyelidiki lokasi S8

23

x8 = 1, maka x1 + x7 1 (dapat memilih lokasi x1atau x7, tetapi tidak

kedua-duanya)
x8

x1

x7

Interpretasi

Hanya memilih lokasi S8

Memilih lokasi S8 dan S1, tetapi S7 tidak

Memilih lokasi S8 dan S7, tetapi S1 tidak

Memilih ketiga lokasi (infeasible)

11/3/2016

Contoh 4: Problem GANDHI

Perusahaan pakaian Gandhi memproduksi 3 jenis pakaian : kemeja, celana pendek,

dan celana panjang.
Mesin harus di sewa tiap minggu untuk memproduksi ketiga jenis pakaian tersebut
dengan biaya sewa :

$ 200 per minggu untuk mesin pembuat kemeja

$ 150 per minggu untuk mesin pembuat celana pendek
$ 100 per minggu untuk mesin pembuat celana panjang

Terdapat 150 jam waktu pekerja dan 160 m bahan pakaian (kain) yang tersedia per
minggunya, dengan data produksi sebagai berikut:
Jam kerja yang
dibutuhkan

Kain yang
dibutuhkan

Harga
Jual

Biaya
Variabel

kemeja

$12

$6

celana pendek

$8

$4

celana panjang

$15

$8

Formulasikan permasalahan diatas untuk memaksimumkan keuntungan per

minggunya!

24

11/3/2016

Solusi Problem Gandhi

Variabel keputusan:
xi = jumlah pakaian jenis ke-i yang diproduksi per minggunya (i=1, 2, 3)
yi = 1 jika pakaian jenis ke-i diproduksi, dan 0 jika tidak
Formulasi:
Max z = 6x1 + 4x2 + 7x3 200 y1 - 150 y2 - 100y3

subject to
3x1 + 2x2 + 6x3 <= 150
4x1 + 3x2 + 4x3 <= 160
x1 <= M y1
x2 <= M y2,
x3 <= M y3
x1, x2, x3 >= 0, dan integer
y1, y2, y3 >= 0, dan biner
25

11/3/2016

Contoh 5 : Problem Western

Penerbangan western memutuskan untuk memiliki

beberapa kota transit di USA
Jalur penerbangan yang dimiliki mencakup kota-kota
berikut : Atlanta, Boston, Chicago, denver, Houston, Los
angeles, New Orleans, New York, Pittsburgh, Salt Lake city,
San Francisco, dan Seattle
Western menginginkan untuk mempunyai kota transit
dalam 1000 mil dari tiap kota-kota ini
Hitunglah jumlah minimum dari kota transit

26

11/3/2016

Contoh 5 : Problem Western

(AT)
(BO)
(CH)
(DE)
Houston (HO)
(LA)
(NO)
(NY)
(PI)
(SL)
(SF)
Seattle (SE)

27

Kota dalam 1000 miles

AT, CH, HO, NO, NY, PI
BO, NY, PI
AT, CH, NY, NO, PI
DE, SL
AT, HO, NO
LA, SL, SF
AT, CH, HO, NO
AT, BO, CH, NY, PI
AT, BO, CH, NY, PI
DE, LA, SL, SF, SE
LA, SL, SF, SE
SL, SF, SE

11/3/2016

Solusi : Problem Western

Variabel keputusan
Xi = 1 jika kota i dilokasikan sebagai kota transit
Xi = 0 jika kota i tidak dijadikan sebagai kota transit
Minimize Z = X1AT + X2B0 + X3CH + X4DE + X5HO +
X6LA + X7NO + X8NY + X9PI + X10SL + X11SF +
X12SE

Pembatas:

28

11/3/2016

Solusi : Problem Western

AT
BO
CH
DE
HO
LA
NO
NY
PI
SL
SF
SE

29

AT BO CH DE HO LA NO NY
1 0 1 0 1 0 1 1
0 1 0 0 0 0 0 1
1 0 1 0 0 0 1 1
0 0 0 1 0 0 0 0
1 0 0 0 1 0 1 0
0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0
1 1 1 0 0 0 0 1
1 1 1 0 0 0 0 1
0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0

PI SL SF SE
1 0 0 0 xAT
1 0 0 0 xBO
1 0 0 0 xCH
0 1 0 0 xDE
0 0 0 0 xHO
0 1 1 0 xLA
0 0 0 0 xNO
1 0 0 0 xNY
1 0 0 0 xPI
0 1 1 1 xSL
0 1 1 1 xSF
0 1 1 1 xSE

11/3/2016

Required
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1
>=
1

Contoh 6 : Problem Alada

Propinsi Alada mempunyai 6 kota

Propinsi ini memiliki permasalahan pada kota mana akan
dibangun stasiun pemadam kebakaran
Paling sedikit jarak stasiun pemadam kebakaran 15 menit
(waktu tempuh) untuk masing masing kota
Waktu yang dibutuhkan dari kota yang satu ke kota yang
lain dilampirkan pada tabel dibawah ini.
Tentukan jumlah minimum dari pemadam kebakaran

30

11/3/2016

Contoh 6 : Problem Alada

Tabel waktu yang dibutuhkan dari kota yang satu ke kota
yang lain dilampirkan pada tabel dibawah ini.
Kota ke-

10

20

30

30

20

10

25

35

20

10

20

25

15

30

20

30

35

15

15

25

30

20

30

15

14

20

10

20

25

14

31

11/3/2016

Solusi : Problem Alada

Sebuah kota dapat dicover oleh stasiun pemadam

kebakaran jika jarak tempuhnya sebesar 15 menit
Covering set untuk setiap kota

32

Kota

Covering sets (15

menit)

1,2

1,2,6

3,4

3,4,5

4,5,6

2,5,6
11/3/2016

Solusi : Problem Alada

Variabel keputusan:
xi = 1 jika dibangun stasiun pemadam kebakaran pada
kota-i
= 0 jika kota-i tidak dibangun stasiun pemadam
Fungsi tujuan :
Minimum Z = x1+x2+x3+x4+x5+x6

Fungsi pembatas:

33

11/3/2016

Solusi : Problem Alada

Kota

1
2
3
4
5
6

34

1
1

2
1

3
0

4
0

5
0

6
0

1
0
0

1
0
0

0
1
1

0
1
1

0
0
1

1
0
0

0
0

0
1

0
0

1
0

1
1

1
1

x1
x2
x3
x4
x5
x6

<=
<=
<=
<=
<=
<=

11/3/2016

1
1
1
1
1
1

Konsep : Either-Or Constraints

Ada 2 konstrain

f ( x1, x 2,..., xn) 0

g ( x1, x 2,..., xn) 0
diasumsikan bahwa hanya ada satu yang memenuhi

Kita dapat menyelesaikan permasalahan ini dengan menambahkan metode

either-or constrains

f ( x1, x 2,..., xn) My

g ( x1, x 2,..., xn) M (1 y )
y = 0,1

M adalah besarnya nilai yang dapat menjamin bahwa kedua konstrain dapat
memenuhi nilai dari x1,x2,,xn yang dapat memenuhi konstrain yang lain
pada problem yang ada.
35

11/3/2016

Konsep If-then constraints

Jika ada dua konstrain

f(x1 ,x2, ,xn) dan g(x1 ,x2 , ,xn)
Kemudian kita tambahkan if-then konstrain
jika kontsrain f(x) dipenuhi maka g(x) dipenuhi juga

f ( x1, x 2,..., xn) M (1 y )

g ( x1, x 2,..., xn) My

y = 0,1
Disini, M adalah nilai positif yang besar, pilih yang terbesar
sehingga f < M and g < M mencakup semua nilai sehingga
memenuhi konstrain lain yang ada pada permasalahan
36

11/3/2016

Contoh 7 : Either-Or Constraints

Memenuhi paling tidak satu dari pembatas berikut :

(1) x + y 4
(2) 3x + 4y 15
(salah satu dari pembatas ke-1, atau ke-2, atau keduaduanya)

Feasibel solusinya adalah ;

37

x = 1, y = 3 (memenuhi kedua pembatas)

x = 0, y = 4 (memenuhi ke-1, tetapi tidak memenuhi ke-2)
x = 5, y = 0 (memenuhi ke-2, tetapi tidak memenuhi ke-1)
x = 2, y = 3 (tidak memenuhi kedua-duanya)
11/3/2016

Solusi Either-Or Constraints

Definisikan variabel baru z sebagai variabel binary (biner)

Nilai M merupakan bilangan besar, konstan positif

Sehingga pembatas ke-1 atau ke-2, dimodifikasi menjadi

(3) x + y 4 + M z
(4) 3 x + 4 y 15 + M (1 - z)
(5) z bilangan biner
Pembuktian:
Untuk mendapat solusi x = 5 dan y = 0, maka z dibuat = 1 :
5 + 0 = 5 4 + M, pembatas ke-3 memenuhi
15 + 0 = 15 15 + M (1 1), pembatas ke-4 memenuhi

Untuk mendapat solusi x = 0 dan y = 4, maka z dibuat = 0:

0 + 4 = 4 4 + M (0) = 4, pembatas ke-3 memenuhi
0 + (4) (4) = 16 15 + M (1 z) = 15 + M, pembatas ke-4 memenuhi

38

11/3/2016

Solusi Either-Or Constraints

Solusi dengan nilai z dibuat = 1000 :

Solusi x y x + y 3x + 4y
OK?
z 4+Mz 15 + M(1-z) Feasible
1a 1 3
4
15
Ya
0
4
1015
Ya
1b 1 3
4
15
Ya
1 1004
15
Ya
2a 0 4
4
16
Ya
0
4
1015
Ya
2b 0 4
4
16
Ya
1 1004
15
Tidak
3a 5 0
5
15
Ya
0
4
1015
Tidak
3c 5 0
5
15
Ya
1 1004
15
Ya
4a 2 3
5
18
Tidak 0
4
1015
Tidak
4b 2 3
5
18
Tidak 1 1004
15
Tidak
Kesimpulan:
Jika solusi yang memenuhi pembatas (1), (2), atau keduanya, dapat ditemukan nilai
yang tepat untuk z sehingga pembatas (3) dan (4) juga memenuhi
Solusi yang tidak memenuhi pembatas (1) dan (2), maka pembatas (3), (4), atau
keduanya juga tidak akan terpenuhi, berapapun nilai z

39

11/3/2016

Contoh 8: Aplikasi Dorian

Perusahaan Dorian automotif memproduksi 3 tipe model

mobil yaitu ; compact (kecil), midsize (menengah), dan large
(besar).
Ada 6,000 ton baja dan 60,000 jam kerja tersedia
Jika suatu tipe mobil diproduksi, maka mobil itu harus
diproduksi paling sedikit 1,000 unit mobil
Data produksi seperti terlihat di tabel bawah ini:
Kebutuhan baja
Kebutuhan jam tenaga kerja
Profit

Compact
1.5 ton
30 jam
$2000

Midsize
3 ton
25 jam
$3000

Large
5 ton
40 jam
$4000

Formulasikan permasalahan perencanaan produksi tersebut

untuk memaksimumkan profit.
40

11/3/2016

Solusi aplikasi Dorian

Variabel keputusan
xi = jumlah mobil tipe ke-i yang diproduksi

yi = 1 jika mobil tipe ke-i diproduksi, dan yi=0 jika tidak

Formulasi :
Maks z = 2 x1 + 3 x2 + 4 x3 (dalam ribuan)
Subject to:
x1 M y1
x2 M y2
x3 M y3
1000 x1

M (1 y1)

1000 x2

M (1 y2)

1000 x3

M (1 y3)

1.5 x1 + 3 x2 + 5 x3

6000

30 x1 + 25 x2 + 40 x3

60000

41

x1, x2, x3 0 dan integer

y1, y2, y3 = 0 atau 1
11/3/2016

Metode Percabangan dan

Pembatasan (Branch and Bound)

42

11/3/2016

Metode Branch and Bound

Metode Branch and Bound adalah metode paling

populer untuk menyelesaikan problem IP

Metode ini mencari solusi optimal IP dengan perhitungan

titik-titik di daerah feasibel sub-problem.

Jika solusi optimal dari LP relaxation adalah integer, maka

solusi LP relaxation tersebut juga merupakan solusi IP

43

11/3/2016

Branch-and-Bound Algorithm

Branch and bound algorithms are the most popular

methods for solving integer programming problems
Branching: among the remaining sub-problems, select the
one that was created most recently.
Bounding: for each new sub-problem, obtain its bound by
solving its LP relaxation problem.

44

11/3/2016

Branch-and-Bound Algorithm

Sub-problems are generated by branching on an

appropriately chosen fractional-valued variable .
Suppose that in a given sub-problem (call it all subproblem), assumes a fractional value between the
integers i and i+1. Then the two newly generated
subproblems are:
New Subproblem 1
Old subproblem + Constraint Xi <= i
New Subproblem 2
Old subproblem + Constraint xi >= i + 1
45

11/3/2016

Bounds

The optimal solution to an LP relaxation of an ILP

problem gives us a bound on the optimal objective
function value.
For maximization problems, the optimal relaxed objective
function values is an upper bound on the optimal integer
value.
For minimization problems, the optimal relaxed objective
function values is a lower bound on the optimal integer
value.

46

11/3/2016

Contoh 1
Contoh suatu permasalahan IP:
Maximize z = 8x1 + 5x2
subject to
x1 + x2 <= 6;
9x1 + 5x2 <= 45;
x1, x2 >= 0; x1, x2 integer

Permasalahan diatas dimulai dengan

membagi menjadi beberapa subproblem. Sub-problem 1 adalah
penyelesaian LP relaxation dari model
awal.
Optimal LP Solution:
x1 = 3.75 dan x2 = 2.25
dengan z = 41.25
47

11/3/2016

Feasible Region for the Problem

Subproblem 1: The LP relaxation of
original

Optimal LP Solution:
x1 = 3.75 and x2 = 2.25 and z = 41.25
Subproblem 2:
Subproblem 1 + Constraint x1 >= 4
Subproblem 3:
Subproblem 1 + Constraint x1 <= 3
Subproblem 4:
Subproblem 2 + Constraint x2 >= 2
Subproblem 5:
Subproblem 2 + Constraint x2 <= 1

48

11/3/2016

Daerah Feasible untuk Sub-problem

Percabangan (Branching):
Proses membagi suatu sub-problem menjadi dua atau lebih
sub-problem dibawahnya
Sub-problem 1 dibagi 2:
Subproblem 2: Subproblem 1 + Constraint x1 >= 4
(nilai x1 dibulatkan ke atas)
Solusi Optimal Sub-problem 2:
z = 41, x1 = 4, x2 = 9/5 = 1.8

Solusi optimal sub-problem 2 belum menghasilkan

bilangan integer, dan perlu dicabangkan lagi (konsep
LIFO sub-problem 3 tidak diproses dahulu)

Subproblem 3: Subproblem 1 + Constraint x1 <= 3

(nilai x1 dibulatkan ke bawah)
49

11/3/2016

Feasible Region for Subproblems 4 & 5

Sub-problem 2 dibagi 2:
Subproblem 4:
Subproblem 2 + Constraint x2 >= 2
(nilai x2 dibulatkan ke atas) => infeasible

Subproblem 5:
Subproblem 2 + Constraint x2 <= 1
(nilai x2 dibulatkan ke bawah)
Solusi Optimal Sub-problem 5:
z = 40.05, x1 = 4.44, x2 = 1

Solusi optimal sub-problem 5 belum

menghasilkan bilangan integer, dan perlu
dicabangkan lagi (konsep LIFO sub-problem
4 tidak diproses dahulu)
50

11/3/2016

The Branch and Bound Tree

1

Subproblem 1
z = 41.25
x1 = 3.75
x2 = 2.25
x1 3

x1 4

Subproblem 2
z = 41
x1 = 4
x2 = 1.8

x2 2

Subproblem 4
Infeasible

Subproblem 3

x2 1
Subproblem 5

Optimal solution of Subproblem 5:

z = 40.05, x1 = 4.44, x2 = 1

Subproblem 6: Subproblem 5 + Constraint x1 >= 5

Subproblem 7: Subproblem 5 + Constraint x1 <= 4

51

11/3/2016

Feasible Region for Subproblems 6 & 7

Subproblem 7:
Subproblem 5 + Constraint x1
>= 5
Optimal solution:
z = 37, x1 = 4, x2 = 1

Subproblem 6:
Subproblem 5 + Constraint
x1 <= 4

Optimal solution:
z = 40,
52

x1 = 5,

x2 = 0
11/3/2016

The Branch and Bound Tree

53

Optimal solution:

11/3/2016

Contoh 2
MAX: 2X1 + 3X2
S.T.
X1 + 3X2 <= 8.25
2.5X1 + X2 <= 8.75
X1, X2 >= 0 and integer

54

11/3/2016

Solution to LP Relaxation
X2

Feasible Integer Solutions

Optimal Relaxed Solution

X1 = 2.769
X2 = 1.826

Obj = 11.019

0
55

411/3/2016

X1

The Branch-And-Bound Algorithm

Problem I

Problem II

MAX: 2X1 + 3X2

S.T.
X1 + 3X2 <= 8.25
2.5X1 + X2 <= 8.75

MAX: 2X1 + 3X2

S.T.
X1 + 3X2 <= 8.25
2.5X1 + X2 <= 8.75

X1 <= 2

X1, X2 >= 0 and integer

56

X1 >= 3

x i 1
i

X1, X2 >= 0 and integer

11/3/2016

X
Solution
to LP Relaxation
2

Problem I
X1=2, X2=2.083, Obj = 10.25

Problem II
1

0
0
57

4
11/3/2016

X1

Branching
Original Problem
X1<=2

X1=2
X2=2.083
Obj = 10.25

58

X1=2.769
X2=1.826
Obj = 11.019

Problem I

X1>=3

X1=3
X2=1.25
Obj = 9.75

Problem II

11/3/2016

Branching
Original Problem
X1<=2

X1=2.769
X2=1.826
Obj = 11.019

X1>=3

Problem II
X1=2
X2=2.083
Obj = 10.25

Problem I

X1=3
X2=1.25
Obj = 9.75

Branch Problem I into Problem III and Problem IV

59

11/3/2016

The Branch-And-Bound Algorithm

Problem III

Problem IV

MAX: 2X1 + 3X2

S.T.
X1 + 3X2 <= 8.25
2.5X1 + X2 <= 8.75
X1 <= 2
X2 <= 2
X1, X2 >= 0 and integer

MAX: 2X1 + 3X2

S.T.
X1 + 3X2 <= 8.25
2.5X1 + X2 <= 8.75
X1 <= 3
X2 >= 3
X1, X2 >= 0 and integer

60

11/3/2016

Solution to LP Relaxation
X2

Problem III

X1=2, X2=2, Obj = 10

Problem II

X1=3, X2=1.25, Obj = 9.75

0
61

11/3/2016
4

X1

Branching
Original Problem

X1<=2

X1=2.769
X2=1.826
Obj = 11.019

X1>=3
Problem II

X1=2
X2=2.083
Obj = 10.25

X2<=2

Problem I

X2>=3
Problem III

X1=2
X2=2
Obj = 10

62

X1=3
X2=1.25
Obj = 9.75

Problem IV
infeasible

11/3/2016

Tugas
Fungsi Tujuan :
Maks Z = 100 X1 + 150X2
Fungsi konstrains :
8.000 X1 + 4.000 X2 < 40.000
15 X1 + 30 X2 < 200
X1, X2 > 0 dan integer
Selesaikan ILP di atas dengan metode branch and bound