Relaksasi dan Dualitas Surrogate Program Multiobjektif Integer dengan Metode Skalarisasi

Muhammad Haris Sulthoni, Dr. Indarsih, S.Si., M.Si.

2026 | Tesis | S2 Matematika

Masalah Program Multiobjektif Integer (PMOI) merupakan masalah optimasi yang melibatkan sejumlah fungsi tujuan linear, kendala linear, dan variabel keputusan bilangan bulat. Solusi optimal dalam permasalahan ini, yang dikenal sebagai himpunan solusi nondominan, dapat diperoleh melalui metode pembobotan dengan normalisasi bobot pada skala [0,1]. Dalam proses penyelesaian eksak menggunakan algoritma pencarian seperti Metode Branch and Bound, penentuan batas nilai (bounding) memiliki peranan penting, yaitu sebagai estimasi ideal terhadap nilai solusi optimal. Batas ini dapat ditentukan melalui formulasi masalah dual yang dibentuk dari masalah primal. Penelitian ini membandingkan tiga pendekatan dualitas: dual surrogate, dual Lagrange, dan dual klasik, dengan fokus utama pada pendekatan dualitas surrogate. Pendekatan ini bekerja dengan menggabungkan seluruh kendala masalah menjadi satu kendala tunggal melalui pengali surrogate. Analisis teoritis menunjukkan bahwa masalah dual surrogate pada PMOI terboboti memberikan batas yang lebih baik dibandingkan dual Lagrange. Contoh numerik memperkuat temuan teoretis tersebut dengan membandingkan nilai optimal dari dual surrogate terhadap dua model dual lainnya.

Multiobjective Integer Programming (MOIP) is an optimization problem involving multiple linear objective functions, linear constraints, and integer decision variables. The optimal solutions for this problem, known as the set of non-dominated solutions, can be obtained through the weighting method by normalizing weights within the [0,1] interval. In exact solution processes using search algorithms such as the Branch and Bound method, bounding plays a critical role, which is as an ideal estimate of the optimal solution value. This bound can be determined through the dual formulation of the primal problem. This study compares three duality approaches: surrogate dual, Lagrangian dual, and classical dual, with a primary focus on the surrogate duality approach. This approach works by aggregating all problem constraints into a single constraint using surrogate multipliers. Theoretical analysis demonstrates that the weighted MOIP surrogate dual problem yields a better bound compared to the Lagrangian dual. Numerical examples reinforce these theoretical findings by comparing the optimal values of the surrogate dual against the other two dual models.

Kata Kunci : Dualitas, dual surrogate, integer, metode pembobotan, program multiobjektif,