Pre Test

Setuju/tidak setujukah anda bahwa sofware

efektif menyelesaikan problema-problema optimasi?

Mengapa kita harus belajar iterasi manual

(tanpa sofware)?

Integer (linear) Programming

minimize: subject to: cTx Ax b x0 x Zn

Related Problems
Mixed Integer Programming (MIP) Zero-one programming Integer quadratic programming Integer nonlinear programming

History
Introduced in 1951 (Dantzig) TSP as special case in 1954 (Dantzig) First convergent algorithm in 1958

(Gomory)
General branch-and-bound technique 1960

(Land and Doig)

Frequently used to prove bounds on

approximation algorithms (late 90s)

Current Status
Has become dominant over linear programming

in past decade
Saves industry billions of dollars/year Can solve 10,000+ city TSP problems 1 million variable LP approximations Branch-and-bound, cutting plane, and separation all used in practice General purpose packages do not tend to work as

well as with linear programming -- knowledge of the domain is critical.

Subproblems/Applications
Facility location

Locating warehouses or franchises (e.g., a Burger King)

Set covering and partitioning

Scheduling airline crews

Multicommodity distribution

Distributing auto parts

Traveling salesman and extensions

Routing deliveries
Capital budgeting Other applications

VLSI layout, clustering

Knapsack Problem
Integer (zero-one) Program:

maximize subject to:

where:
b = maximum weight ci = utility of item i ai = weight of item i

cTx ax b x binary

xi = 1 if item i is selected, or 0 otherwise

The problem is NP-hard.

Traveling Salesman Problem

Find shortest tours that visit all of n cities.

courtesy: Applegate, Bixby, Chvtal, and Cook

Traveling Salesman Problem n n minimize: cij xij

i =1 j =1
n

subject to:

xij = 2 1 i n
x ji = xij , binary
j =0

(path enters and leaves)

cij = cji = distance from city i to city j (assuming symmetric version) xij if tour goes from i to j or j to i, and 0 otherwise Anything missing?

Traveling Salesman Problem n n minimize: cij xij

i =1 j =1 n
j =0 n

subject to:

xij = 1
i =0

1 i n 1 j n

(out degrees = 1)

xij = 1

(in degrees = 1) (??)

ti t j + nxij n 1 2 i, j n
cij = distance from city i to city j

xij = 1 if tour visits i then j, and 0 otherwise (binary) ti = arbitrary real numbers we need to solve for

Important Properties
LP solution is an upper bound on IP solution

(assuming maximization)
If LP is infeasible then IP is infeasible If LP solution is integral (all variables have

integer values), then it is the IP solution.

Linear Programming Solution

1. Some LP problems will always have integer solutions

transportation problem assignment problem min-cost network flow (w/ integer capacities)

These are problems with a unimodular matrix A. (unimodular matrices have det(A) = 1).
2. Solve as linear program and round.

Can violate constraints, and be non-optimal. Works OK if

integer variables take on large values accuracy of constraints is questionable

maximize: z = cTx subject to: Ax b, x 0, x Zn function IPr(Ae, be, c, z*)

Integer Branch and Bound

// Ae, be are A and b with additional constraints // z* is the cost of current best solution

z, x, f = LP(Ae,be,c)

// f indicates whether feasible

if not(f) or (z < z*) return z* if (integer(x)) return z pick a non-integer variable xi from x zl* = IP(extend Ae,be with xi xi , c, z*) zg* = IP(extend Ae,be with xi -xi , c, zl*) return zg*

function IP(A, b, c) = IPr(A, b, c, -)

Example
l z
feasible

Find optimal solution. Cut along y axis, and make two recursive calls

Example
l z u

Find optimal solution. Solution is integral, so return it as current best z*

Example

u = z*

Find optimal solution. It is better than z*. Cut along x axis, and make two recursive calls

Example

Infeasible, Return.

Example

Infeasible, Return.

Example

l u u l = z*

Find optimal solution. It is better than z*. Cut along y axis, and make two recursive calls

Example

l u = z*

Find optimal solution. Solution is integral and better than z*. Return as new z*.

Example

l u = z*

Find optimal solution. Not as good as z*, return.

Langkah-langkah metode Branch dan Bound untuk masalah maksimasi dapat dilakukan seperti berikut :
1. Selesaikan LP dengan metode simpleks biasa 2. Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat

adalah bulat, solusi optimum bulat telah tercapai.

3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah.

Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu.

4. Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan

ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

METODE BRANCH DAN BOUND

Untuk memperoleh gambaran yang lebih jelas tentang

metode Branch dan Bound, perhatikan contoh masalah berikut :

Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 X1 ;

5 X2 4 X2 25 8 2 X2 10 X2 non negatif integer

Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 = 2,26 dan Z = 35,25.

Solusi ini menunjukkan batas atas awal.

22

METODE BRANCH DAN BOUND

Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2 = 2

dan Z = 34. Dalam metode Branch dan Bound, masalah itu dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang mungkin bagi X1 dan X2. ini hanya X2 yang memiliki bagian pecah, ia dipilih. Untuk menghilangkan bagian pecah dari nilai X2 = 2,25, dua kendala baru dibuat.

Variabel dengan nilai solusi pecah terbesar dipilih. Karena pada solusi

Kendala-kendala ini mewakili dua bagian baru dari masalah itu. Dua

nilai bulat terdekat terhadap 2,25 adalah 2 dan 3. Sehingga diperoleh dua masalah baru melalui dua kendala mutually exclusive, X2 2 dan X2 3, yang akan diuraikan berikut ini se-bagai bagian A dan B. Kendala-kendala ini secara efektif menghi-langkan semua nilai pecah yang mungkin bagi X2, antara 2 dan 3. Pengaruhnya mereka mengurangi ruang solusi layak sehingga angka solusi bulat yang dievaluasi pada masalah ini makin sedikit

METODE BRANCH DAN BOUND

Bagian A :
Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 X1 ; 5 X2 4 X2 2 X2 X2 X2 25 8 10 (berlebih) 2 0

Bagian B :
Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 X1 ; 5 X2 4 X2 2 X2 X2 X2 25 8 10 3 0

METODE BRANCH DAN BOUND

Bagian A dan B diselesaikan tanpa pembatasan bilangan bulat

dengan metode simpleks. Solusi simpleksnya adalah :

Bagian A : X1 = 8, X2 = 2 dan Z = 34 Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5

Bagian A menghasilkan suatu solusi yang semuanya bulat. Untuk

bagian A batas atas dan bawah adalah Z = 34. Solusi pecah bagian B membenarkan pencarian lebih lanjut karena menghasilkan nilai fungsi tujuan yang lebih besar dari batas atas bagian A. Sangat mungkin bahwa pencarian lebih lanjut dapat menghasilkan suatu solusi yang semuanya bulat dengan nilai fungsi tujuan melebihi batas atas bagian A = 34. pertama dengan kendala X1 6 dan yang lain dengan X2 7.

Bagian B dicabangkan ke dalam dua sub bagian, B1 dan B2,

METODE BRANCH DAN BOUND

Sub Bagian B1 :
Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 X1 X1 ; 5 X2 4 X2 2 X2 X2 X2 25 8 (berlebih) 10 3 6 0

Sub Bagian B2 :
Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 X1 X1 ; 5 X2 4 X2 2 X2 X2 X2 25 8 10 3 7 0

METODE BRANCH DAN BOUND

Solusi simpleksnya adalah :

Sub-bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25 Sub-bagian B2 : tidak layak.

Karena sub-bagian B1 menghasilkan nilai fungsi tujuan yang

lebih besar dari 34 (batas atas bagian A), maka harus dicabangkan lagi ke dalam dua sub masalah, dengan kendala X2 3 dan X2 4. Kedua kendala sub masalah diberi nama bagian B1a dan B2b.

METODE BRANCH DAN BOUND

Bagian B1a :
Maksimumkan Dengan syarat Z = 3 X1 + 2 X1 + X1 5 X2 4 X2 2 X2 X2 X2 X2 25 8 10 (berlebih) 3 3 6 0

X1 X1 ;

Bagian B1b :
Maksimumkan Dengan syarat Z = 3 X1 2 X1 X1 + + 5 X2 4 X2 2 X2 X2 X2 ; X2 25 8 10 3 (berlebih) 4 6 0

X1 X1

METODE BRANCH DAN BOUND

Solusi optimum dengan metode simpleks adalah :

Sub-bagian B1a : X1 = 6, X2 = 3 dan Z = 33 Sub-bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5

Kedua solusi itu memiliki batas atas ( Z = 33 dan Z = 33,5)

yang lebih buruk dibanding dengan solusi yang dihasilkan oleh bagian A. Karena itu, solusi bulat optimum adalah X1 = 8, X2 = 2 dan Z = 34 yang dihasilkan oleh bagian A.
Jika pencarian telah diselesaikan, solusi bulat dengan

fungsi tujuan tertinggi (dalam masalah maksimasi) dipilih sebagai solusi optimum.

29

METODE BRANCH DAN BOUND

Kelemahan dasar dari metode ini adalah bahwa diperlukan

pemecahan masalah LP untuk setiap pencabangan. Dalam masalah yang besar dapat memakan banyak waktu. Karena itu dalam prosedur pencabangan dan pencarian, analisa selanjutnya dihentikan jika :
1. Hasil dari sub-problem lebih jelek dibanding dengan batas atas

yang sudah diidentifikasi

2. Pencabangan selanjutnya menghasilkan solusi tak layak.

METODE BRANCH DAN BOUND

Seluruh prosedur Branch dan Bound untuk contoh yang lalu dapat digambarkan seperti berikut :

X2

0
X2 X1 = 8 3 X2 = 2,25 Z = 35,25

Solusi bulat optimum 3 X1 = 8 X2 X2 = 2 Z = 34 2

6 X1
X2 X1 = 6 4 X2 = 3,25 Z = 34,25

inferior

inferior

X1 = 6,5 X2 = 3 Z = 34,5

X1

Tak layak

Cutting Plane
The idea is to start with a relaxation R of the problem and then add constraints on the fly to find an actual feasible solution in S.
=S =R S

new constraint

new constraint

relaxation Example 1 Example 2 A linear relaxation

Cutting Plane: general algorithm

minimize: z = cTx, function CP(R, c) // R a relaxed set of constraints Ax b s.t. S polytope(Ax b) repeat:
x = LP(R,c) if x S return x find an inequality r satisfied by S, but violated by x (r separates x from S) R = R U {r}

subject to x S

Can add multiple inequalities on each iteration

Cutting Plane

feasible New plane

Note that we are removing a corner, and no integer solutions are being excluded.

Picking the Plane

Method 1: Gomory cuts (1958)
Cuts are generated from the LP Tableau

Each row defines a potential cut

Guaranteed to converge on solution General purpose, but inefficient in practice

Method 2: problem specific cuts (templates)

Consider the problem at hand and generate cuts

based on its structure

A template is a problem specific set of cuts

(probably of exponential size) which S satisfies. Each round picks a cut from this set.