Mixed-Integer Second-Order Cone Programming Reformulations of a Fractional 0-1 Program for Task Assignment

Basit Öğe Kaydı
dc.contributor.authorGüngör, Murat
dc.date.accessioned2025-01-21T14:28:10Z
dc.date.available2025-01-21T14:28:10Z
dc.date.issued2024
dc.description.abstractFractional 0-1 programming is a subfield of nonlinear integer optimization in which the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. It is well-known that fractional 0-1 programs can be formulated as mixed-integer linear programs. Recently, several alternative mixed-integer second-order cone programming reformulations have been proposed for fractional 0-1 programs. These reformulations, which can be solved directly by standard commercial solvers, have been reported to be efficient for certain types of problems. In this paper, we consider a task assignment problem with respect to preferences, where the objective is to maximize total weighted satisfaction while maintaining a fair distribution. The problem’s mathematical model turns out to be a fractional 0-1 program. We investigate three mixed-integer second-order cone programming reformulations thereof, and we compare, by means of a computational study, the performance of these reformulations with a benchmark mixed-integer linear programming formulation that was proposed and analyzed in the literature before. The latter, namely the mixed-integer linear programming formulation, turns out to be significantly better for the problem in question.
dc.description.abstractKesirli 0-1 programlama, doğrusal olmayan tam sayılı en iyilemenin bir alt alanıdır. Amaç, afin fonksiyonlardan oluşan bir kesirler toplamının doğrusal kısıtlar altında en iyilenmesidir. Kesirli 0-1 programların kısmi tam sayılı doğrusal programlar olarak biçimlendirilebildiği iyi bilinmektedir. Yakın zamanda, kesirli 0-1 programlar için çeşitli alternatif kısmi tam sayılı ikinci mertebeden koni programlama biçimlendirmeleri önerilmiştir. Bu biçimlendirmeler, standart ticari çözücülerle doğrudan çözülebilmektedir ve bunların bazı problem tipleri için verimlilikleri bildirilmiştir. Bu makalede, amacın adil bir yük dağıtımı altında toplam ağırlıklı memnuniyeti en büyütmek olduğu, tercihleri dikkate alan bir iş atama problemi ele alınmaktadır. Problemin matematik modeli doğal olarak kesirli bir 0-1 programdır. Bu programın üç kısmi tam sayılı ikinci mertebeden koni programlama biçimlendirmesi incelenmiş ve bunlar, bilgisayar deneyleri yardımıyla, daha önce literatürde önerilen ve incelenen denek taşı bir kısmi tam sayılı doğrusal programlama biçimlendirmesi ile kıyaslanmıştır. Kısmi tam sayılı doğrusal programlama biçimlendirmesinin söz konusu iş atama problemi için kayda değer derecede daha iyi sonuçlar verdiği görülmüştür.
dc.identifier.dergipark1323701
dc.identifier.doi10.29137/umagd.1323701
dc.identifier.issn1308-5514
dc.identifier.issue1-20
dc.identifier.startpage29
dc.identifier.urihttps://dergipark.org.tr/tr/download/article-file/3248199
dc.identifier.urihttps://dergipark.org.tr/tr/pub/umagd/issue/82949/1323701
dc.identifier.urihttps://doi.org/10.29137/umagd.1323701
dc.identifier.urihttps://hdl.handle.net/20.500.12587/20242
dc.identifier.volume1
dc.language.isoen
dc.publisherKırıkkale Üniversitesi
dc.relation.ispartofUluslararası Mühendislik Araştırma ve Geliştirme Dergisi
dc.relation.publicationcategoryMakale - Ulusal Hakemli Dergi
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_20241229
dc.subjectfractional 0-1 programming
dc.subjecthyperbolic 0-1 programming
dc.subjectmixed-integer conic quadratic programming
dc.subjectmixed-integer second-order cone programming
dc.subjecttask assignment
dc.subjectpreferences
dc.subjectkesirli 0-1 programlama
dc.subjecthiperbolik 0-1 programlama
dc.subjectkısmi tam sayılı konik karesel programlama
dc.subjectkısmi tam sayılı ikinci mertebeden koni programlama
dc.subjectiş atama
dc.subjecttercihler
dc.subjectIndustrial Engineering
dc.titleMixed-Integer Second-Order Cone Programming Reformulations of a Fractional 0-1 Program for Task Assignment
dc.title.alternativeİş Atama İçin Kesirli Bir 0-1 Programın Kısmi Tam Sayılı İkinci Mertebeden Koni Programlama Biçimlendirmeleri
dc.typeArticle

Dosyalar

Koleksiyon

Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi
TR-Dizin İndeksli Yayınlar Koleksiyonu