-

 

 

 




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

 

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