Reformulation Techniques and Solution Approaches for Fractional 0-1 Programs and ApplicationsMehmanchi, Erfan (2020) Reformulation Techniques and Solution Approaches for Fractional 0-1 Programs and Applications. Doctoral Dissertation, University of Pittsburgh. (Unpublished)
AbstractFractional 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 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 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
Details
MetricsMonthly Views for the past 3 yearsPlum AnalyticsActions (login required)
|