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

Authors : Murat Güngör

Pages : 20-29

Doi:10.29137/umagd.1323701

View : 55 | Download : 46

Publication Date : 2024-01-31

Article Type : Research Paper

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 : 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