A Unified Approach to Mixed-Integer Optimization: Nonlinear Formulations and Scalable Algorithms

Abstract: We propose a unified framework to address a family of classical mixed-integer optimization problems with semicontinuous decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal 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. Numerically, we establish that a general-purpose strategy, combining cutting-plane, first-order, and local search methods, solves these problems faster and at a larger scale than MICO solvers. For instance, our approach successfully solves network design problems with 100s of nodes and provides solutions up to 40% better.

optimization and control

Audience: researchers in the topic

Discrete Optimization Talks

Series comments: DOTs are virtual discrete optimization talks, organized by Aleksandr M. Kazachkov and Elias B. Khalil. To receive updates about upcoming DOTs, please join our mailing list. Topics of interest include theoretical, computational, and applied aspects of integer and combinatorial optimization.

The format is two thirty-minute talks and time for questions. Currently (January-April 2021), the seminars are scheduled on end-of-the-month Fridays at 1:00 p.m. ET. A special feature of DOTs is a social component. After a usual talk, you might grab a tea/coffee and chat with other attendees. Why not here too? Join us for some informal discussion after each DOT and throughout the week on our Discord channel.