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
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
|
Date Deposited: | 03 Jun 2021 08:38 |
Date of first compliant deposit: | 02 Jun 2021 |
Subjects: | Mathematical models |
Last Modified: | 13 Oct 2024 01:45 |
URI: | https://lbsresearch.london.edu/id/eprint/1811 |