## TRANSFORMASI LINIER UNTUK PERSOALAN PROGRAM KUADRATIK NOL-SATU

## M Khahfi Zuhanda
Universitas Medan Area, Medan Surel : Khahfi@staff.uma.ac.id Diterima : 25 Oktober 2017; Disetujui : 01 November 2017

## ABSTRAK
Program non linier merupakan persoalan yang cukup menarik untuk di bahas oleh  matematikawan. Salah  satunya  program  kuadratik  nol-satu  yang  fungsi  tujuan  dan  kendala  berbentuk  persamaan kuadratik.  Program  kuadratik  nol-satu  merupakan  kelas  khusus  dalam  pemrograman  non-linier karena persyaratan peubah keputusan bernilai nol-satu. Tulisan ini akan mengajukan sebuah teknik untuk  menyelesaikan  persoalan  program  kuadratik  nol-satu  yang  dikembangkan  oleh  Sherali  dan Smith.  Teknik  ini  mengubah  Quadratic  Problems  (QP)  menjadi  kebentuk  Bilinier  Problems(BP) terlebih  dahulu.  Akhir  dari  proses  ini  mengakibatkan  transformasi    program  kuadratik  nol-satu menjadi persoalan linier nol-satu.
Kata Kunci :  integer, linierisasi, nol-satu, program kuadratik

## ABSTRACT
Non-linear programming is an interesting issue to be discussed by mathematician. One of them is a zero-one quadratic  programming,  where  the  objective  function  and  constraints  are  quadratic  equations.  The  zero-one quadratic programming is a special case in non-linear programming because of the requirement of value variable is  zero-one.  This  paper  propose  a  technique  for  solving  the  zero-one  quadratic  programming  problem  was developed by Sherali and Smith. This technique converts the Quadratic Problems (QP) into Bilinier Problems (BP)  first.  The  end  of  this  process  will  transfrom  zero-one  quadratic  programming  to  zero-one  linear programming problem
Keywords: Integer, Linearization, Quadratic Programming, Zero-One,
1.   Pendahuluan Seiring perkembangan
zaman, perkembangan ilmu pengetahuan kini meningkat  tajam.  Ilmu  pengetahuan  telah banyak membantu manusia dalam memberikan solusi  kompleksnya  permasalahan  dalam kehidupan  sehari-hari.  Mulai  dari  bidang kedokteran,  ekonomi,  sosial,  politik,  sumber daya, dan lain-lain. Permasalahan optimasi non linier  tak  luput  dalam  memberi  kontribusi dalam  segala  aspek.  Dalam  beberapa  tahun terakhir, telah banyak matematikawan mengembangkan  permasalahan  non  linier, salah satunya program kuadratik nol-satu.
Program kuadratik nol-satu merupakan  kelas  khusus  dari  pemrograman non  linier.  Program  kuadratik  nol-satu ditujukan  untuk  meminimalkan  subjek  fungsi
objektif  kuadratik  dengan  beberapa  kendala kuadratik,  dengan  kondisi  bahwa  masing- masing  variabel  dibatasi  nilai  nol  atau  satu. Permasalahan  program  kuadratik  nol-satu sering muncul pada beberapa persoalan seperti telekomunikasi, manufaktur, penjadwalan, dan lain-lain.
Beberapa  literatur  strategi  linierisasi juga  telah  dilakukan  untuk  menyelesaikan permasalahan  program  kuadratik  nol-satu menjadi  bentuk  pemrograman  linier  integer, mulai  dari  Gharibi  dan  Xia  [1],  dan berkembang  menjadi  formulasi  yang  lebih ringkas  dan  membutuhkan  variabel  biner seperti yang dilakukan Furini dan Traversi [2], Gharibi [3] mengembangkan Teknik Linierisasi Balas  dan  Mazzolla  program  kuadratik  nol- satu. De Santis dan
Rinaldi [4]
mengembangkan reformulasi
persoalan
kuadratik  nol-satu  kontinu.  Koncherberger,
Alidaee,  dan  Rego  [5]  mengembangkan algoritma  Taboo  Search  untuk  menyelesaikan program kuadratik biner.
Permasalahan  pemrograman  kuadratik nol-satu  merupakan  salah  satu  permasalahan optimisasi  tak  linear  yang  sangat  penting, karena muncul dalam berbagai aspek, termasuk dalam  aspek  perekonomian,  sains  terapan, analisis  portofolio,  dan  pengendalian  optimal. Salah satu metode yang dapat digunakan untuk menyelesaikan  permasalahan  pemrograman kuadratik  nol-satu  adalah  dengan  teknik linierisasi bilinier yaitu dengan mentransformasikan  persamaan  kuadratik menjadi bentuk linier. Pada penelitian ini akan dianalisis bagaimana teknik linierisasi program kuadratik  nol-satu  yang  telah  diperkenalkan oleh Sherali dan Smith [6] untuk menyelesaikan persoalan program kuadratik nol-satu.
Teknik  linierisasi  program  kuadratik nol-satu  lebih  efektif  dalam  menyelesaikan program  kuadratik  yang  memiliki  batasan masalah variabel nol-satu. Teknik ini merupakan  teknik  linieirisasi  terbaru  untuk persoalan  kuadratik  nol-satu yang sebelumnya telah diperkenalkan oleh Sherali dan Smith [6]. Lalu  dikembangkan  kembali  oleh  Gharibi  dan Xia [1] dengan tightness strategy .
Penelitian ini akan menunjukkan secara literatur penerapan
linierisasi
program kuadratik nol-satu dan menyelesaikan beberapa  contoh  persoalan  numerik  program kuadratik nol-satu.
Permasalahan  pemrograman  kuadratik merupakan salah satu permasalahan optimisasi tak linear  yang  sangat penting,  karena muncul dalam  berbagai  aspek,  termasuk  dalam  aspek perekonomian, sains terapan, analisis portofolio,  dan  pengendalian  optimal.Banyak ilmuan  meneliti  program  kuadratik,tetapi untuk kasus persoalan program kuadratik  nol- satu,  teknik  linierisasi  Sherali  dan  Smith  lebih efektif  untuk  menyelesaikan  proram  kuadratik nol-satu.  Karena  solusi  yang  dibatasi  oleh  nol- satu  membuat  fungsi  kuadratik  menjadi permasalahan  yang  baru.  Karena  variable berorde  dua  akan  sama  besar  pengaruhnya dengan variabel berorde  satu.  Andai  di  berikan  persoalan program  kuadratik  yang  fungsi  tujuan  dan kendalanya  berbentuk  persamaan  kuadratik dengan  variabelnya dibatasi oleh nol dan satu. Dimana  persamaan  yang  berbentuk  kuadratik akandi transformasi menjadi linier. Transformasi  program  kuadratik  berakibat penambahan  variable  dan  persamaan  kedalam fungsi kendala.
Tujuan  dalam  penelitian  ini  adalah menjabarkan dan menganalisa teknik linierisasi untuk  menyelesaikanpersoalankuadratik  nol- satu..

## 2.    Pembahasan

## 2.1  Teknik Liniersasi Sherali dan Smith
Permasalahan  program  kuadratik  merupakan salah  satu  permasalahan  optimisasi  tak  linear yang  sangat  penting,  karena  muncul  dalam berbagai  aspek,  termasuk  dalam  aspek perekonomian,  sains  terapan,  komputasi,  dan komunikasi.  Banyak  ilmuan  meneliti  program kuadratik,  akan  tetapi,  untuk  kasus  persoalan program  kuadratik  nol-satu,  teknik  linierisasi Sherali  dan  Smith  lebih  efektif  untuk menyelesaikan  proram  kuadratik  nol-satu. Karena  solusi  yang  dibatasi  oleh  nol-satu membuat fungsi kuadratik menjadi permasalahan yang baru.
Berikut  ini  merupakan  bentuk  program kuadratik nol-satu Minimumkan (2.1) Kendala: (2.2) (2.3) Dimana dan adalah matriks dimensi .
Dalam  linierisasi  program  kuadratik  nol-satu dapat melalui beberapa langkah yaitu:
Langkah  1. Mengubah  persamaan  kuadratik menjadi kebentuk persamaan bilinier.
Misalkan  program  kuadratik  di  transformasi menjadi  perkalian  antara  fungsi  linier. Sehingga  dapat  dinyatakan  dalam  proses sebagai berikut
(2.4)
Dan merupakan baris  ke ,  dan adalah sebuah  relaksasi  dari
seperti  yang
ditunjukkan  pada  persamaan  (2.4).  Andaikan didefinisikan
sebagai  vektor  yang mempunyai anggota-anggota dan misalkan . Dan didefinisikan pula bahwa
dan }
Maka  di  reformulasikan  persoalan  program kuadratik  adalah QP yang  juga  merupakan bentuk  fungsi Bilinear  Problem (BP).  Maka persoalan QP dapat  dinyatakan  kedalam persoalan BP , maka diperoleh persamaan yang dapat dituliskan sebagai berikut
BP: Minimumkan (2.5) Kendala (2.6) (2.7) (2.8) (2.9) Dan diketahui juga bahwa (2.10)
Langkah  2. Mentransformasi  persamaan  bilinier dengan mensubtitusi dengan variabel yang baru. Selanjutnya,  proses  dilinierisasi  kondisi dan
dengan  perkalian  persamaan  (2.10)
dengan dan dimana  persamaan (2.10) i adalah  baris  ke i dari  salah  satu  bagian vektor  pertidaksamaan  di  persamaan  (2.10),
. Sehingga diperoleh untuk dan (2.11)
Misalkan e mempresentasikan  sebuah  vektor. Maka, BP dapat  di  transformasikan  mengikuti persamaan
BP: Minimumkan
Kendala
(2.12) dan
dan
),
Langkah  3. Menambah  persamaan  pada  fungsi kendala  akibat  penambahan  variabel  baru  pada transformasi sebelumnya .
Perhatikan  bahwa  persamaan  (2.11)  menjamin bahwa  persamaan  (2.12)  berlaku  untuk x bilangan  biner. Dengan  memperhatikan struktur  pertidaksamaan  pada  persamaan (2.12) yang dapat dinyatakan sebagai berikut
(2.13)
Sehingga  transformasi  persamaan  yang  baru berdasarkan persamaan (4.13) dapat dinyatakan sebagai berikut BP: Minimumkan (2.14) Kendala (2.15) (2.16) (2.17) (2.18) (2.19)
(2.20)
Langkah  4. Merelaksasi  bentuk  BP  dari  langkah sebelumnya  dengan  menghapus  batas  atas  dan bawah dari pertidaksamaan persamaan yang baru. Kemudian,  persoalan  BP  ditunjukkan  oleh persamaan  (2.14)  disederhanakan  dengan menghapus batas atas pertidaksamaan untuk di  persamaan  (2.18)  dan  untuk di persamaan  (2.19). adalah  batas  bawah pertidaksamaan dimana di persamaan (2.17). Sehingga dapat ditulis
Sehingga  bentuk  relaksasi  BP  ini  dapat dinyatakan sebagai berikut:
BP: Minimumkan Kendala
(2.21)
Maka  tranformasi  persamaan  linierisasi program kuadratik nol-satu selesai [6].

## I. R EPRESENTASI PENDEKATAN PROGRAM
KUADRATIK NOL - SATU
Berdasarkan  definisi  pada  subbab  (2.1),  maka dapat  mempresentasikan  hubungan  antara persoalan  program  kuadratik  umumnya dengan persoalan program kuadratik nol-satu.
Lemma. 3.1 Andaikan
untuk
(3.1) (3.2)
memiliki  hubungan  yang  sama  antara  program kuadratik  nol  satu  dengan  program  kuadratik umumnya.
Bukti
Andaikan maka
pada persamaan  (3.1)  jelas  bernilai  0  dan  sisi  kanan menjadi
.  Dan  dalam  kasus lainnya,  andaikan dengan  kata  lain maka  sisi  kanan  persamaan  (3.1)  dapat dituliskan menjadi dimana sama deng an  sisi  kirinya  yaitu
.  Dan  begitu  juga  dapat  dilakukan  pada persaamaan (3.2)
Akibat. Andaikan
(3.4)
jika dan hanya jika
(3.5)
Bukti disubtitusikan  persamaan  (3.1)  dan  (3.2), maka  dapat  diperoleh  dan  dinyatakan  sebagai berikut
(3.6)
Hasil diatas berlaku untuk G i dan yang telah
dinyatakan
sebelumnya.
Linierisasi
berdasarkan Akibat  3.2 merupakan  persoalan BP  persamaan  (2.21),  dimana  pertidaksamaan liner  persamaan  (2.21)  tidak  lain  adalah persamaan  (3.3).    Sebenarnya,  tidak  semua pertidaksamaan persamaan (3.4) yang diperlukan  dalam  model  akhir  linierisasi. Untuk menunjukkan ini, pertama diperkenalkan  berikut  prinsip  merumuskan program  kuadratik  nol-satu  kedalam  program linear piece-wise.
Proposisi 3.1 Setiap program convex yang linier atau fungsi tujuan linier piece-wice dan kendala sama dengan program linier dalam arti bahwa ada  proyeksi one-to-one antara  kedua  solusi layak.
Bukti Ditunjukkan bahwa Minimumkan Adalah sama untuk Minimumkan Kendala
Diasumsikan  bahwa  fungsi  tujuan  merupakan linear.  Himpunan  kendala  merupakan convex dan  dikarakteristik  dengan  pertidaksamaan linier piece-wise .  Sehingga  persamaan  tersebut berbentuk polyhedral  convex ,  yang  harus memiliki  ekspresi  linear.  Itu  menunjukkan bahwa  persamaan Proposisi  3.1 berlaku  jika variabel dibatasi oleh nol atau satu. Selanjutnya ditunjukkan adanya persamaan  program linier piece-wise  convex untuk  masalah  minimisasi kuadratik nol-satu.
Proposisi  3.2 Untuk  masalah  minimisasi kuadratik  nol-satu,  ada  persamaan  program linier piece-wise dengan  fungsi  tujuan  dan kendala convex .
Bukti . Maksimum beberapa fungsi linear adalah convex dan  minimum concave .  Kemudian persamaan  (3.1)  dan  persamaan  (3.3)  pada Lemma
3.1
menyajikan masing-masing formulasi convex dan concave .  Oleh  karena  itu, untuk  setiap  diberikan  persoalan  minimisasi kuadratik  nol-satu,  maka  dapat  diperoleh persamaan  program  linier piece-wise  convex dengan  menggunakan  persamaan  (3.1)  dan (3.2).  Perhatikan  bahwa  persamaan  (3.1)  dan persamaan  (3.2)  digunakan  secara  bersamaan ketika memenuhi persamaan kendala.
Maka  sekarang  dapat  ditunjukkan  bahwa persamaan  (2.1)  -  (2.3)  mengikuti  formulasi persamaan
Minimumkan
− } (3.7)
Kendala ≥ g (3.8) (3.9)
Linierisasi  persamaan  (3.6)  -  (3.8)  dapat  di tunjukkan dibawah ini. Persamaan (3.7) adalah setara dengan
Kendala (3.10) (3.11) (3.12)
Karena persamaan (3.9) - (3.11) adalah relaksasi persamaan  (3.6)  dan  persamaan  (3.9)  -  (3.11) juga  terkandung  dalam  persamaan  (3.6). Sekarang  dapat  diperoleh  linierisasi  untuk persamaan (3.5) – (3.8), yang setara dengan .
Selanjutnya,  ditunjukkan  bahwa non-necessity
pertidaksamaan  seperti dan yang juga telah di teliti oleh Adam dan Forrester [7], [8]. Sehingga linierisasi yang diperoleh dengan pendekatan piece-wise convex adalah tepat.
3     Simpulan dan Saran 3.1  Simpulan Untuk  menyelesaikan  persoalan  program kuadratik  nol-satu  dalam  tulisan  ini  adalah dengan  teknik  linierisasi,  yaitu  dengan mentranformasikan persoalan program kuadratik  kebentuk  persoalan  program  linier. Dalam teknik linierisasi Quadratic Problems (QP) diubah  menjadi Bilinear  Problems (BP) terlebih dahulu.  Dimana,  fungsi  kuadratik  dipecah menjadi  perkalian  fungsi  linier.  Akibat  dari proses BP persamaan  dari  fungsi  kendala menjadi bertambah.
Selanjutnya BP yang  merupakan  relaksasi  dari perkalian  fungsi  linier  kendala  disubtitusikan dengan  variabel  yang  baru.  Sehingga  fungsi tujuan dan kendala yang merupakan persamaan BP bertransformasi menjadi persamaan  linier.  Aki-bat  dari  transformasi BP maka  bertambahlah  persamaan  pada  fungsi kendala  yang  mengacu  pada  struktur perubahan BP .  Kemudian  proses  selanjutnya menyederhanakan pertidaksamaan fungsi kendala  dengan  merelaksasi BP dengan menghapus  batas  atas  dan  bawah  dengan mensubtitusi persamaan yang baru.
Program  kuadratik  nol-satu  juga  dapat direpresentasikan  dengan General  Quadratic Programming ,  sebab BP memiliki  hubungan yang sama dengan
General
Quadratic Programming . Untuk
menunjukkan ini, persoalan program kuadratik nol-satu dirumuskan  kedalam  persoalan  program  linier piece-wise .  Pada  persoalan  minimasi  kuadratik nol-satu,  terdapat  persamaan  program  linier
piece-wise  convex .  Sehingga  teknik  linierisasi yang diperoleh dengan piece-wise convex benar. .

## 3.2  Saran
Setelah  penelitian  literature  dilakukan  teknik transformasi  linier  program  kuadratik  nol-satu disarakan  untuk  melakukan  linierisasi  apabila jumlah  variabel  kecil  tapi  apabila  jumlah variabel banyak perlu dilakukan lebih lanjut.

## Daftar Pustaka
W.  Gharibi    dan  Y.  Xia.  A  tight  linearization strategy  for  zero-one  quadratic  programming problems.  International  Journal  of  Computer Science Issues: 294-299, 2012.
1.
F,  Furini  dan  E,  Traversi.  Extended Linear Formulation for
BinaryQuadratic    Problems.  Paris:
Universite de Paris Dauphine. 2013.
2. W.  Gharibi.  Improved  Balas  and Mazzola Linearization for Quadratic 0- 1 Programs with Application in  a New Cutting  Plane  Algorithm.  Dept.  of Computer, Science, College of
Computer  Science  and  Information Systems, Jazan University, Jazan 82822- 6694, KSA. 2012.
M.  DeSantis,    dan  F  Rinaldi.  Continuous Reformulations  for  ZeroOne  Programming Problems.  Springer  Science  and  Business Media, LLC, 2011.
G,  Kochenberger,  B  Alidaee  ,  dan  C,  Rego.  An unconstrained  quadratic  binary  programming approach  to  the  vertex  coloring  problem. Annals  of  Operations  Research,  139(1):229241, 2005.
H.D  Sherali,  dan  J.C.  Smith.  An  Improved Linierization  Strategy  for  Zero-One  Quadratic Problems.  Optimization  Letters,  vol.1,pp.33-47. 2007
W.  Adams,  and  R.  Forrester.  ASimple Approach  for  Generating    Concise  Linear Representations  of  Mixed  0-1  Polynomial Programs. Operations Research Letters, vol. 33, no. 1, pp. 55-61, 2005.
W.  Adams  ,  and  R.  Forrester.  Linear  Forms  of Nonlinear  Expressions:  New  Insights  on  Old Ideas. Operations Research Letters, vol. 35, no. 4, pp. 510, 2007