A unified approach to mixed-integer optimization with logical constraints

Bertsimas, J, Cory-Wright, R and Pauphilet, J (2021) A unified approach to mixed-integer optimization with logical constraints. SIAM Journal on Optimization, 31 (3). pp. 2340-2367. ISSN 1052-6234 OPEN ACCESS

Abstract

We propose a united framework to address a family of classical mixed-component analysis, and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly using a big-M formulation. In this work, we challenge this longstanding modeling practice and express the logical constraints in a non-linear way. By imposing a regularization condition, we reformulate these problems as convex binary optimization problems, which are solvable using an outer-approximation procedure. In numerical experiments, we establish that a general-purpose numerical strategy, which combines cutting-plane, first-order, and local search methods, solves these problems faster and at a larger scale than state-of-the-art mixed-integer linear or second-order cone methods. Our approach successfully solves network design problems with 100s of nodes and provides solutions up to 40% better than the state-of-the-art; sparse portfolio selection problems with up to 3,200 securities compared with 400 securities for previous attempts; and sparse regression problems with up to 100,000 covariates.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Additional Information:

Accepted for publication in the SIAM Journal on Optimization

© 2021 Society for Industrial and Applied Mathematics

Date Deposited: 03 Jun 2021 08:38
Date of first compliant deposit: 02 Jun 2021
Subjects: Mathematical models
Last Modified: 04 Nov 2022 01:33
URI: https://lbsresearch.london.edu/id/eprint/1811
More

Export and Share


Download

Accepted Version - Text
  • Available under License

Statistics

Altmetrics
View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item