Mixed-Integer Second-Order Cone Programming Reformulations of a Fractional 0-1 Program for Task Assignment
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
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