Optimization Online


On robust fractional 0-1 programming

Erfan Mehmanchi (erfan.mehmanchi***at***pitt.edu)
Colin Gillen (cpg12***at***pitt.edu)
Andres Gomez (agomez***at***pitt.edu)
Oleg Prokopyev (droleg***at***pitt.edu)

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

Keywords: fractional 0-1 programming, robust optimization, linear mixed-integer programming

Category 1: Robust Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Research report AG 18.04, IE, University of Pittsburgh, August 2018

Download: [PDF]

Entry Submitted: 08/31/2018
Entry Accepted: 08/31/2018
Entry Last Modified: 07/23/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society