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

Year 2024, Volume: 16 Issue: 1, 20 - 29, 31.01.2024

Murat Güngör

https://doi.org/10.29137/umagd.1323701

Abstract

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.

Keywords

fractional 0-1 programming, hyperbolic 0-1 programming, mixed-integer conic quadratic programming, mixed-integer second-order cone programming, task assignment, preferences

İş Atama İçin Kesirli Bir 0-1 Programın Kısmi Tam Sayılı İkinci Mertebeden Koni Programlama Biçimlendirmeleri

Abstract

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.

Keywords

kesirli 0-1 programlama, hiperbolik 0-1 programlama, kısmi tam sayılı konik karesel programlama, kısmi tam sayılı ikinci mertebeden koni programlama, iş atama, tercihler

References

• 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
• Alizadeh, F., & Goldfarb, D. (2003). Second-order cone programming. Mathematical Programming, Series B, 95, 3–51. doi:10.1007/s10107-002-0339-5
• 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
• 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
• 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
• 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
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization.
• Chi, C.-Y., Li, W.-C., & Lin, C.-H. (2017). Convex Optimization Problems. doi:10.1201/9781315366920-5
• Glover, F. (1975). Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science, 22, 455–460. doi:10.1287/mnsc.22.4.455
• 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
• 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
• 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
• 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
• Ş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
• 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
• 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