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

Fractional 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.

Kesirli 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.