blognya komarudin bin sayuti

blognya komarudin bin sayuti header image 2

Degeneracy dan cycling pada algoritma simplex

April 17th, 2012 · 1 Comment

Walaupun solusi global optimum dapat tercapai (seperti disebutkan di post ini), ada keadaan ketika algoritma simpleks mengalami kemacetan. Ada dua istilah yang berkaitan dengan keadaan ini, yakni degeneracy dan cycling. Pada postingan ini, saya akan menjelaskan kedua istilah tersebut dan memaparkan varian dari simpleks yang dapat mengatasinya.

Degeneracy terjadi ketika dua iterasi yang berurutan memiliki nilai objective yang sama. Dengan kata lain, iterasi tidak berhasil menemukan nilai objective yang lebih baik walaupun memiliki basic variable yang berbeda. Salah satu penyebab keadaan ini adalah adanya suatu kendala (constraint) yang bisa dinyatakan dalam kombinasi linear kendala-kendala lainnya. Dalam istilah aljabar linier, sifat linearly independent tidak terpenuhi.

Untuk lebih lengkapnya, keadaan degeneracy dapat dinyatakan sebagai beberapa keadaan (yg belum tentu ekuivalen) berikut:

  1. Dua iterasi yang berurutan memiliki nilai objective yang sama
  2. Jumlah kendala yang aktif pada suatu solusi lebih besar dari jumlah peubah (variable)
  3. Ada basic variable yang bernilai nol
  4. Basic solution memiliki jumlah peubah yang bernilai nol lebih dari \(n – m\) (selisih jumlah peubah/variable/kolom dan jumlah kendala/constraint/baris)

Keadaan degeneracy tidak mempengaruhi kemampuan algoritma simpleks dalam mencapai solusi optimum (jika ada). Ketika algoritma simplex menemukan titik yang degenerate, maka satu atau beberapa iterasi berikutnya biasanya degenerate juga. Biasanya, algoritma simplex akan keluar dari titik yang degenerate ini dan meneruskan kembali menuju solusi optimum. Pada beberapa kuliah yang saya ikuti [1], pembicara memaparkan bahwa mereka dapat menghemat lebih dari 20% waktu komputasi apabila keadaan degeneracy dihindari secara eksplisit. Perlu dicatat juga, biasanya keadaan degeneracy cukup sering terjadi terutama untuk network problem.

Programa linier berikut dapat mengalami keadaan degeneracy:

Problem tersebut kita reformulasi ulang dengan menambahkan variable slack:

 

\(\)

Kalau kita gunakan aturan pemilihan pivot terdahulu, maka urutan solusinya adalah sebagai berikut:

Iterasi Objective value Variable basic Variable nonbasic
1 5 \((x,S_1,S_3)=(5,10,0)\) \((y,S_2) = (0,0)\)
2 5 \((x,y,S_1)=(5,0,10)\) \((S_2,S_3) = (0,0)\)
3 15 \((x,y,S_3)=(5,10,10)\) \((S_1,S_2) = (0,0)\)
4 20 \((y,S_2,S_3)=(20,25,5)\) \((x,S_1) = (0,0)\)

 

Terlihat bahwasanya terjadi degeneracy pada iterasi pertama dan kedua dengan solusi \((x,y) = (5, 0)\). Agar lebih jelasnya, kami tampilkan plot dari programa linear tersebut. Dari plot tersebut, bisa dipahami bahwa \(x -y \leq 5\) adalah constraint yg redundant dan mengakibatkan degeneracy. Constraint tersebut redundat karena constraint tersebut dapat dihilangkan tanpa mengubah daerah solusi feasible dan tanpa mengubah titik optimum LP.

 

Perlu dicatat, degeneracy bisa menimbulkan permasalahan ketika algoritma simplex tidak keluar dari titik yang degenerate. Dengan kata lain, algoritma simplex dapat kembali ke titik degenerate yang pernah ia temui sebelumnya. Keadaan ini disebut cycling. Jika keadaan cycling terjadi, maka algoritma simplex tidak akan berhenti meraih solusi optimal,  unboundedness atau infesible. Keadaan cycling ini sangat jarang terjadi.

Berikut adalah contoh dari sebuah programa linear yang dapat menemui keadaan cycling [2]:

Jika kita menggunakan aturan pivot yang biasa, maka iterasi algoritma simplex tidak akan pernah selesai karena algoritma simplex berputar-putar pada basis yang sama. Untuk menghindari keadaan cycling, ada beberapa pilihan yang bisa ditempuh:

  1. Pre-Solve
  2. Lexicography rule
  3. Bland’s rule

Pre-solve ditujukan untuk menghilangkan kendala-kendala yang redundant sehingga mengurangi probabilitas terjadinya degeneracy dan cycling. Akan tetapi, pre-solve tidak menjamin bahwa ia akan mampu menghindarkan dari cycling secara pasti. Untuk benar-benar menghindari cycling, kita bisa mengubah aturan pemilihan pivot menjadi aturan pivot lexicography atau aturan Bland.

Aturan Lexicography akan memungkinkan kita memilih variable keluar yang memiliki nilai ratio yang paling ketat. Jika terjadi tie, maka variabel keluar yang dipilih adalah variabel yang secara lexicography paling kecil. Lexicography lebih kecil berarti nilai variable pertama yg tidak sama dari grup pertama memiliki nilai lebih kecil dari pada grup yang kedua. Sebagai contoh \(A =(3,8,2,-3,5)\) adalah lexicography lebih kecil dari \(B=(3,9,6,2,3)\). Komponen pertama yg berbeda adalah komponen kedua, yakni \(A_2 = 8\) dan \(B_2 = 9\). karena \(A_2 < B_2\) maka \(A \overset{L}{<}B\) (dibaca \(A\) secara lexicography lebih kecil dari \(B\)). Dengan menggunakan aturan ini, baris objective function akan naik secara lexicography secara terus-menerus. Sehingga, tidak akan suatu basis tidak akan ditemui dua kali dan ini menghambat adanya cycling.

Aturan Bland juga dapat digunakan untuk menghindari keadaan cycling. Pemilihan pivot pada aturan Bland adalah memilih variabel masuk yang memiliki reduced cost negatif yang ditemui pertama kali (dengan indeks terkecil). Variable keluar yang dipilih adalah variabel dengan ratio yg paling ketat. Jika terjadi tie, maka yang dipilih adalah variabel dengan nilai indeks terkecil. Dengan aturan Bland, pad nilai fungsi objective yang sama, variabel yang penah menjadi variabel basic tidak akan pernah menjadi variable basic lagi. Sehingga, cycling dapat dihindari.

OLK berikut sudah mengimplementasikan kedua aturan pemilihan pivot tersebut:

olkGUI.version.0.4.4

olkGUI.Linux.version.0.4.4 (tested with Fedora 16)

Panduan pengguna OLK GUI ver.0.4.4

 

[1] Saya lupa kuliahnya apa aja 😀

[2] Vanderbei, R.J., Linear Programming Foundations and Extensions, Third edition, Springer, 2008.

Print Friendly, PDF & Email

Tags: Linear Programming · Mathematical programming

1 response so far ↓

  • 1 ARmi // Apr 18, 2012 at 1:49 pm

    update terus tentang algoritma nih 😀
    keep post yah brad 🙂