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. ISSN 1052-6234 (Accepted)

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: M > Mathematical models
Last Modified: 18 Oct 2021 06:23
URI: https://lbsresearch.london.edu/id/eprint/1811
More

Export and Share


Download

Accepted Version - Text
  • Restricted to Repository staff only

Statistics

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item