Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Reformulation Techniques and Solution Approaches for Fractional 0-1 Programs and Applications

Mehmanchi, Erfan (2020) Reformulation Techniques and Solution Approaches for Fractional 0-1 Programs and Applications. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img]
Preview
PDF
Updated Version

Download (1MB) | Preview

Abstract

Fractional binary programs (FPs) form a broad class of nonlinear integer optimization problems, where the objective is to optimize the sum of ratios of (linear) binary functions. FPs arise naturally in a number of important real-life applications such as scheduling, retail
assortment, facility location, stochastic service systems, and machine learning, among others.

This dissertation studies methods that improve the performance of solution approaches for fractional binary programs in their general structure. In particular, we first explore the links between equivalent mixed-integer linear programming (MILP) and conic quadratic programming reformulations of FPs. Thereby, we show that integrating the ideas behind these two types of reformulations of FPs allows us to push further the limits of the current state-of-the-art results and tackle larger-size problems.

In practice, the parameters of an optimization problem are often subject to uncertainty. To deal with uncertainties in FPs, we extend the robust methodology to fractional binary
programming. In particular, we study robust fractional binary programs (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. 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 MILP formulations for multiple-ratio RFPs and evaluate their performances by using real and synthetic data sets.

One interesting application of FPs arises in feature selection which is an essential preprocessing step for many machine learning and pattern recognition systems and involves identification of the most characterizing features from the data. Notably, correlation-based and mutual-information-based feature selection problems can be reformulated as single-ratio FPs. We study approaches that ensure globally optimal solutions for medium- and reasonably large-sized instances of the aforementioned problems, where the existing MILPs in the literature fail. We perform computational experiments with diverse classes of real data sets and report encouraging results.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: University of Pittsburgh ETD
Status: Unpublished
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Mehmanchi, Erfanerm83@pitt.eduerm83
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairProkopyev, Olegdroleg@pitt.edu
Committee MemberGomez, Andresgomezand@usc.edu
Committee MemberPardalos, Panospardalos@ise.ufl.edu
Committee MemberRajgopal, Jayantgunner1@pitt.edu
Committee MemberZeng, Bobzeng@pitt.edu
Date: 29 January 2020
Date Type: Publication
Defense Date: 13 September 2019
Approval Date: 29 January 2020
Submission Date: 8 September 2019
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 141
Institution: University of Pittsburgh
Schools and Programs: Swanson School of Engineering > Industrial Engineering
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Fractional 0-1 programming
Date Deposited: 29 Jan 2020 16:44
Last Modified: 29 Jan 2020 16:44
URI: http://d-scholarship.pitt.edu/id/eprint/37617

Metrics

Monthly Views for the past 3 years

Plum Analytics


Actions (login required)

View Item View Item