We study single- and multiple-ratio robust fractional 0-1 programming problems (RFPs). In particular, this work considers RFPs under a wide-range of disjoint and joint uncertainty sets, where the former implies separate uncertainty sets for each numerator and denominator, and the latter accounts for different forms of inter-relatedness between them. First, we demonstrate that, unlike the deterministic case, single-ratio RFP is $NP$-hard under general polyhedral uncertainty sets. However, if the uncertainty sets are imbued with a certain structure – variants of the well-known budgeted uncertainty – the disjoint and joint single-ratio RFPs are polynomially-solvable when the deterministic counterpart is. We also propose mixed-integer linear programming (MILP) formulations for multiple-ratio RFPs. We conduct extensive computational experiments to evaluate the performance of our MILP reformulations, as well as to compare the disjoint and joint uncertainty sets. Finally, we demonstrate the value of the robust approach by examining the robust solution in a deterministic setting and vice versa.
Citation
Research report AG 18.04, IE, University of Pittsburgh, August 2018