TY  - JOUR
T1  - Mixed-Integer Second-Order Cone Programming Reformulations of a Fractional 0-1 Program for Task Assignment
TT  - İş Atama İçin Kesirli Bir 0-1 Programın Kısmi Tam Sayılı İkinci Mertebeden Koni Programlama Biçimlendirmeleri
AU  - Güngör, Murat
PY  - 2024
DA  - January
DO  - 10.29137/umagd.1323701
JF  - International Journal of Engineering Research and Development
JO  - IJERAD
PB  - Kirikkale University
WT  - DergiPark
SN  - 1308-5506
SP  - 20
EP  - 29
VL  - 16
IS  - 1
LA  - en
AB  - 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.
KW  - fractional 0-1 programming
KW  - hyperbolic 0-1 programming
KW  - mixed-integer conic quadratic programming
KW  - mixed-integer second-order cone programming
KW  - task assignment
KW  - preferences
N2  - 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.
CR  - Adams, W. P., & Forrester, R. J. (2005). A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters, 33, 55–61. doi:10.1016/j.orl.2004.05.001
CR  - Alizadeh, F., & Goldfarb, D. (2003). Second-order cone programming. Mathematical Programming, Series B, 95, 3–51. doi:10.1007/s10107-002-0339-5
CR  - Atamtürk, A., & Gómez, A. (2020). Submodularity in conic quadratic mixed 0-1 optimization. Operations Research, 68, 609–630. doi:10.1287/opre.2019.1888
CR  - Benson, H. Y., & Sağlam, Ü. (2014). Mixed-Integer Second-Order Cone Programming: A Survey. INFORMS Tutorials in Operations Research, 13–36. doi:10.1287/educ.2013.0115
CR  - Borrero, J. S., Gillen, C., & Prokopyev, O. A. (2016). A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems. Operations Research Letters, 44, 479–486. doi:10.1016/j.orl.2016.03.015
CR  - Borrero, J. S., Gillen, C., & Prokopyev, O. A. (2017). Fractional 0-1 programming: applications and algorithms. Journal of Global Optimization, 69, 255–282. doi:10.1007/s10898-016-0487-4
CR  - Boyd, S., & Vandenberghe, L. (2004). Convex Optimization.
CR  - Chi, C.-Y., Li, W.-C., & Lin, C.-H. (2017). Convex Optimization Problems. doi:10.1201/9781315366920-5
CR  - Glover, F. (1975). Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science, 22, 455–460. doi:10.1287/mnsc.22.4.455
CR  - Güngör, M. (2019). A fractional 0-1 program for task assignment with respect to preferences. Computers and Industrial Engineering, 131, 263–268. doi:10.1016/j.cie.2019.03.048
CR  - Li, H. (1994). A global approach for general 0-1 fractional programming. European Journal of Operational Research, 73, 590–596. doi:10.1016/0377-2217(94)90257-7
CR  - Lobo, M. S., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). Applications of second-order cone programming. Linear Algebra and Its Applications, 284, 193–228. doi:10.1016/S0024-3795(98)10032-0
CR  - Mehmanchi, E., Gómez, A., & Prokopyev, O. A. (2019). Fractional 0–1 programs: links between mixed-integer linear and conic quadratic formulations. Journal of Global Optimization, 75, 273–339. doi:10.1007/s10898-019-00817-7
CR  - Şen, A., Atamtürk, A., & Kaminsky, P. (2018). A conic integer optimization approach to the constrained assortment problem under the mixed multinomial logit model. Operations Research, 66, 994–1003. doi:10.1287/opre.2017.1703
CR  - Tawarmalani, M., Ahmed, S., & Nikolaos, V. (2002). Global Optimization of 0-1 Hyperbolic Programs. Journal of Global Optimization, 24, 385–416. doi:10.1023/A:1021279918708
CR  - Wu, T. (1997). A note on a global approach for general 0–1 fractional programming. European Journal of Operational Research, 101, 220–223. doi:10.1016/S0377-2217(96)00258-5
UR  - https://doi.org/10.29137/umagd.1323701
L1  - https://dergipark.org.tr/en/download/article-file/3248199
ER  -