Optimization Online


A mixed-integer fractional optimization approach to best subset selection

Andres Gomez (agomez***at***pitt.edu)
Oleg Prokopyev (droleg***at***pitt.edu)

Abstract: We consider the best subset selection problem in linear regression, i.e., finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We show that, for a broad range of criteria used in the statistics literature, the best subset selection problem can be modeled as a mixed-integer fractional optimization problem. Then we show how to exploit underlying submodularity in the problem to strengthen the formulations, and propose to tackle the problem by solving a sequence of mixed-integer quadratic optimization problems. The proposed approach can be implemented with off-the-shelf solvers and, in our computations, it outperforms existing alternatives by orders of magnitude.

Keywords: fractional optimization, mixed-integer optimization, submodularity, linear regression

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

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Applications -- Science and Engineering (Statistics )

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

Download: [PDF]

Entry Submitted: 08/31/2018
Entry Accepted: 09/01/2018
Entry Last Modified: 03/30/2020

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